Names and things (reference semantics) vs. boxes and things (value semantics)

The goal of this post is to explain the “names and things” semantics (reference semantics) that is shared by many dynamic languages (including Python and Lisp in particular that this post singles out for illustration) and its implications.

There are many great posts about this topic written by others. What this post is trying to achieve then is to contribute an article that:

  • (1) illustrates with many examples of Python code and Lisp code side by side (numbered for easy reference);
  • (2) tries to start with minimal common prior background and finish with explanations for many related side questions and gotchas;
  • (3) lots of ASCII art diagrams

Note: You don’t need to be familiar with Lisp to understand this post (part of (2)). You may skip Lisp examples (but I want to add that it’s not hard to read Lisp code.) You don’t need to be familiar with Python either.

Unless stated otherwise, Python examples are written in Python 3 and Lisp examples in Elisp (Emacs Lisp). (There will be a Common Lisp note at the end.)

Before we begin, I’d like to thank /r/learnpython (and /u/zahlman, /u/sqeekypotato, /u/wololongong) for their feedback on a smaller post that this post is based on. Feedback on this post is welcome too.

1. Motivation

Some questions on stackoverflow.com indicate that there are some beginners who find the way Python variables work mysterious, resulting in the question “Is Python pass by reference? Is it pass by value?” and other similar questions popping up in their mind. Questions that came to my mind as well long time ago. Similarly for elisp beginners.

Understanding the way reference semantics shows itself in the two languages is essential for understanding the following things:

  • immutable objects vs. mutable objects, and what is object identity, and shallow copy vs. deep copy.
  • why swapping operation (on integers) in general cannot be written as a function (in Python and in Lisp) (which contrasts with C++).
  • why Lisp macros setq, setf, incf and push cannot be written as functions.
  • how to manipulate lists in Lisp

Let’s start with a litmus test. The following is a Python snippet (and Lisp snippet) that first assigns the vector [10,11,12] to the variable aa, then defines a function, then calls the function on aa and then prints it. (The array-like data structure is called lists in Python, and vectors in Emacs Lisp. They will always be called vectors in this post to simplify this post.1) The function foo has parameter bb (then bb is a local variable within the function body), it assigns the sum of 90 and 9 to be the first element of bb, and then it assigns 9999 to the local variable bb.

Snippet 10: (first in Python)

aa = [10, 11, 12]

def foo(bb):
    bb[0] = 90 + 9
    bb = 9999

foo(aa)

print(aa)  # => [99, 11, 12]

(now in Lisp)

(setq aa (vector 10 11 12))

(defun foo (bb)
  (setf (elt bb 0) (+ 90 9))
  (setq bb 9999))

(foo aa)

(print aa)  ; => [99 11 12]

Notice that the output is neither 9999 nor [10, 11, 12]. This post is mainly for those who find this output mysterious. Before explaining it, I’d like to point out two things. First, this “mysterious” behavior isn’t unique to just function calls. In fact, if you inline the function call manually, you get the same result, and this means that the thing goes deeper than the issue of “call by value” or “call by reference”. The following is like Snippet 10, except the function called is inlined away.

Snippet 20:

aa = [10, 11, 12]

bb = aa

bb[0] = 90 + 9
bb = 9999

print(aa)  # => [99, 11, 12]

(setq aa (vector 10 11 12))

(setq bb aa)

(setf (elt bb 0) (+ 90 9))
(setq bb 9999)

(print aa)  ; => [99 11 12]

Second, this behavior isn’t unique to Python and Lisp, in fact, this behavior is shared by many other (but maybe not all) dynamic languages, which is a good news because once you get an understanding of this behavior, you can reuse that understanding in those other languages as well. Compile your understanding once, run anywhere. For example, in my case, when I was learning elisp, I remember reading an article about Python variables and it helped me with my confusion about Lisp variables at that time.

2. Alfie Bobbie thought experiment

Suppose you are an art teacher and you are to give a series of homework assignments to a student, say John, over a week. On Monday, you ask John to make a penguin doll and then name it Alfie. What does it mean to name a doll Alfie? It means that for example when you say “Where is Alfie?” to John, John will point his finger at that penguin doll.

Next day, you give John another task, which is “Name Alfie Bobby.” In other words, give Alfie yet another name: Bobby. So that doll now has two nicknames: Alfie and Bobby.

Next day, you give John the third task: make Bobby three-eyed. Then next day, John’s task is to make another doll, this time, a dolphin doll, and then name it Bobby, in other words, the nickname Bobby is now assigned to the dolphin doll and not to the now three-eyed penguin doll. The penguin doll no longer has Bobby as one of its nicknames. Next day, you ask John to describe Alfie. How will John describe Alfie, out of the following three options?

(1) “Alfie is a dolphin doll.”

(2) “Alfie is a three-eyed penguin doll.”

(3) “Alfie is a regular penguin doll with two eyes”

Of course, only (2) is correct. The point of this thought experiment is that you don’t find the outcome of this experiment mysterious at all, you knew almost instantly that (2) is the right answer, but did you realize that this thought experiment is actually analogous to Snippet 20?

3. The aa bb experiment (back to Snippet 20)

Here is a way of relating the thought experiment to Snippet 20. (I’ll also explain Snippet 20 with diagrams later)

In Python, there are names (i.e. nicknames like aa or bb) and there are things (i.e. objects2 such as integers, vectors3, strings, and so on.), and names refer to things.

Imagine you are to give orders (by coding) to a Python interpreter, which we’ll call John. Let’s say your code asks John to make a vector and then name it aa. This corresponds to the first line aa = [10, 11, 12] in Snippet 20. The right hand side in that line is asking “make a vector with these elements” and the line itself is asking “then name it aa“. Next, you give John another task, which is “name aa bb”, which corresponds to the line bb = aa. In other words, give aa yet another name: bb. In other words, give the object with nickname aa yet another nickname: bb. So that vector object now has two names: aa and bb.

Next, you give John the third task: make bb three-eyed. This is the line bb[0] = 90 + 9, if you define three-eyed vectors to be those vectors whose first element is 99. Next, you ask John to make some other thing (this time an object that happens to be an integer) and then name it bb. This is the line bb = 9999. The name bb is now assigned to the number 9999 and not to the now three-eyed vector. The vector no longer has bb as one of its nicknames. Next, you ask John to describe aa. This is the line print(aa). How will John describe aa?

(1) 9999

(2) [99, 11, 12]

(3) [10, 11, 12]

You can see that the answer has to be and is (2). This “names referring to things” semantics contrasts with the “boxes containing things” semantics of the C language where there are boxes (unmovable boxes) and things, and boxes contain things. In the former semantics, the assignment operator simply assigns a nickname (which could already be a nickname of some object) to a Python object (which could already have a nickname or even many nicknames) that is the result of the computation of the expression on the right hand side. (The result of the computation can be a newly created object or an already existing object, depending on what the expression on the right side is asking for.) In the latter semantics, the assignment operator simply copies the thing (that is the result of the computation of the expression on the right hand side) into the specified box (specified by the left hand side). We’ll get into more details of “boxes containing things” semantics later, but for now we focus on “names referring to things” semantics of Python and Lisp.

Now that the litmus snippet is explained, to complete the picture, I’d like to also add that the “names referring to things” paradigm extends to the behavior of container objects, local variables, function calls in a consistent and simple way: Container objects (such as vectors) refer to the objects they conceptually contain. In other words, they refer to other objects instead of physically containing them. (In some of the next sections, we’ll go through another litmus snippet testing this point.) With local variables and function arguments, you have locally effective names referring to things.

In the “Boxes containing things” semantics on the other hand, container objects (such as structs in C) physically contain boxes that physically contain other objects. With local variables and function arguments, you have temporary boxes containing things.

4. Boxes containing object references

There is another way of looking at the “names referring to things” semantics, which explains the term “reference semantics”. One can think of the “names and things” semantics as a special variation on the “boxes and things” semantics where the things that get stored in boxes are always pointers/references to other objects, rather than objects themselves.4 So in this point of view, one can say that the assignment operator in reference semantics just copies references to objects, rather than objects themselves, and to complete the picture, one can add that container objects contain references to other objects, rather than the objects themselves.

Make sure that you can convert between the following two (effectively equivalent) point of views on reference semantics:

  • “There are nicknames and there are objects. Nicknames refer to objects.”
  • “There are boxes and there are objects. Boxes contain object references, i.e., references to objects.”

In the rest of the article, we will only use the terms “reference semantics” and “value semantics”.

Let’s summarize our observations thus far into two sentences: In reference semantics, objects are shared by default. In value semantics, objects are copied by default.

While I am invoking a particular specific interpretation of the phrases “value semantics” and “reference semantics”, it is possible that there are other possible interpretations of these phrases you might have in mind. In that case, just replace occurrences of “value semantics” and “reference semantics” in this post with “the C-like semantics” and “the Python-or-Lisp-like semantics” while reading this post, but nevertheless feel free to share other possible interpretations in comments.

5. Two different meanings of change

The litmus example demonstrates how the phrase “change something” can have two very different meanings. In one of Disney movies, a teenage female protagonist goes to a wizard. The protagonist says “I wish my mother would change”. The wizard says “All right. I’ll make that happen.” and the next day the protagonist sees her mother transform into a bear. In another movie, the protagonist, who is again a teenage daughter to follow the “Alice in wonderland” trope, finds a portal to another world. In the other world, she finds a flat identical to her own, and two people who look like her parents, except they have black buttons where their eyes should be. The protagonist’s initial reaction to this other world is “I like this new place. I like these new parents. I am living here from now on.”

In both movies, one could say that the protagonist’s mother changes. In the former movie, change was in the sense of transformation. In the latter movie, change was in the sense of new designation.

When you see a car with a bumper sticker that says “change your mayor” and if it was near an election day, it means change in the sense of new designation. The bumper sticker is saying “let’s vote for someone else this time”. But if it wasn’t near any election day, and if the driver was an influential lobbyist or adviser and if the bumper sticker said “I change your mayor”, it means “I change the mayor’s policies. I make him change his mind..” That’s change of mayor in the sense of transformation.

When you change your mayor in the sense of transformation, a lot of people can say “My mayor changed.” and it affects a lot of people. But when you change your mayor in the sense of new designation, by moving to another city for example, that does not affect a lot of people. No side effect. Recall Snippet 10. We change bb first in the sense of transformation, and that affects aa, and then we change bb in the sense of new designation, and that does not affect aa.

If you want to unambiguously say that some code changes an object in the sense of transformation, you can say the code mutates the object, you can also say the code changes the state of the object.

If you want to unambiguously say that some code changes something in the sense of new designation, you can use the verb “set”. Example:

  • “this code sets the element at index 2 of this vector to …”
  • “this code sets aa[2] to …”
  • “CDR is SETFable.”

The two different meanings are sometimes also phrased in the following ways, depending on literature:

  • “There is a difference between changing the binding and changing the object”
  • “There is a difference between modifying the variable and modifying the object”
  • “changing the variable vs changing the object”
  • “modifying the place vs modifying the object”

6. Pass by value or pass by reference

Now that we have clear idea on what is going on in Snippet 10, let’s get back to the questions that mention phrases like:

  • pass by value
  • pass by reference
  • call by sharing
  • pass by object
  • or any of the above phrases where “pass” is replaced with “call” or vice versa

Answers to these questions depend on what the askers meant by these phrases5. I wish to point out just two things:

  1. What we see in Snippet 10’s outcome is nothing like “C++’s pass by reference”.
  2. When someone says “Python is pass-by-value except values are object references”, “values” in that sentence means contents of boxes (rather than states of Python objects), and with that interpretation, the sentence is correct. This is good to know because “Language X is pass-by-value except …” is a popular saying.
  3. Wikipedia article on evaluation strategy seems to suggest that “call by sharing” is the term for this that is used in the Python community. Now you know what is meant when someone says “Language X uses call by sharing.”

7. With vectors

Let’s start drawing diagrams, with simple examples first.

In the following code, the first line creates a vector that holds three integers. 10 is its first element, 11 is its second element and 12 is its third element. The last three lines in the code show how to access the three elements.

Snippet 30:

aa = [10, 11, 12]
bb = aa
a0 = aa[0]
a1 = aa[1]
a2 = aa[2]
(setq aa (vector 10 11 12))
(setq bb aa)
(setq a0 (elt aa 0))
(setq a1 (elt aa 1))
(setq a2 (elt aa 2))

Execution of the second line results in the names aa and bb referring to or pointing to the same vector, or in another point of view, aa and bb are references to the same object. Aftermath of execution of the snippet is shown in the following arrow diagram.

aa: ---+
       |  
       |  
       v

   +--------------------+
   |       0:   1:   2: |
   |                    |
   |       |    |    |  |
   +-------|----|----|--+
           |    |    | 
       ^   v    v    v 
       |               
       |   10   11   12
bb: ---+               
           ^    ^    ^ 
           |    |    | 
           |    |    | 

          a0:  a1:  a2:

The rectangle in the diagram represents the vector object. The diagram is showing one vector object, three integer objects, five names and their relations. The vector now has two names aa and bb. The vector says “10 is my first element, 11 is my second element, 12 is my third element” or rather “10 is my element at index 0, 11 is my element at index 1, 12 is my element at index 2.” In the diagram, I just wrote 0:, 1:, and 2: instead of writing “element at index 0” and so on. The last three lines in the code give names a0, a1, a2 to the three elements. See how the integer 10 has two arrows pointing to it because there are at least two different ways to refer to it, for example, you can refer to it by saying a0, and also by saying “first element of aa”.

The fact that the variables aa and bb refer to just one vector and not two vectors is usually phrased in many ways, such as:

  • “aa and bb are the same object
  • “… are the same vector
  • “… are same under object identity

Now you know what object identity is. You can test object identity with the function eq in Lisp, or with the is operator in Python. If you run (eq aa bb) in Lisp (after running of Snippet 30), it will return t (which means true), which confirms that aa and bb are the same object. If you run aa is bb in Python, it will return True, which confirms the same.

Now suppose we run the following code right after we ran Snippet 30.

Snippet 40:

bb[0] = 90 + 9
bb = 9999
print(aa)
(setf (elt bb 0) (+ 90 9))
(setq bb 9999)
(print aa)

The first two lines do something to bb, and the last line prints aa, not bb. What is the value of aa now? A vector of three elements: 99, 11, 12. Did two things to bb, but only one affected the value of aa. Let’s see the aftermath in diagram:

aa:---+
      |  
      |  
      v

  +--------------------+
  |       0:   1:   2: |
  |                    |
  |       |    |    |  |
  +-------|----|----|--+
          |    |    |
   99 <---+    |    |
               v    v   

          10   11   12  
bb:--+ 
     |    ^    ^    ^
     |    |    |    |
     v    |    |    |

   9999  a0:  a1:  a2:

The first line in the code mutated or modified the vector by reassigning something different to its first element field. When the vector is thinking “my element at index 0…”, that now refers to a different number, which is 99. The name a0 still refers to the original number, which is 10. So a vector can be mutated. We say that a vector is a mutable object because its state can change, as demonstrated here. Integers are immutable objects: their states cannot change.

The second line in the code reassigns the name bb to a different thing, which is 9999. The name aa still refers to the original thing, which is the vector.

We did two things to bb: the first line did mutation of bb, the second line did reassignment of the name bb. Result of mutating bb is visible through the variable aa as well and that’s because aa and bb at that time were the same object. On the other hand, reassignment of the name bb did not have any effect on what you see through the variable aa and that’s not surprising. These points may seem unremarkable but what if we try another example code:

Snippet 50:

aa = [10, 11, 12]

def dothings(bb):
    bb[0] = 90 + 9
    bb = 9999

dothings(aa)

print(aa)
(setq aa (vector 10 11 12))

(defun do-things (bb)
  (setf (elt bb 0) (+ 90 9))
  (setq bb 9999))

(do-things aa)

(print aa)

Now what is the value of aa? A vector of three numbers: 99, 11, 12. By now, this result shouldn’t be surprising. This is actually the same as Snippet 10.

8. With integers, simplest immutable objects

Before we move on to diagrams involving nested vectors, let’s talk about integers. Integers are immutable objects and so when you have the object that is 10, that is, when you have the integer object whose state is “I represent the integer 10”, the object just stays that way, you can’t cause the object to become 11 or 15 or anything else.

The following computes the sum of 1 and 1, assigns the result to aa, then assigns it to bb.

Snippet 60:

aa = 1 + 1
bb = aa
(setq aa (+ 1 1))
(setq bb aa)

Aftermath of execution of the code in diagram follows. (We’ll soon get to the minor issue of possibility of this diagram and next diagrams not always being correct)

aa: ---+
       |
       |
       v

       2

       ^
       |
       |
bb: ---+

First line in the code connects the name aa to 2, then the second line connects the name bb to the same object.

Now suppose we run the following code right after we ran the previous snippet:

Snippet 70:

bb = bb + 10
print(aa)
print(bb)
(setq bb (+ bb 10))
(print aa)
(print bb)

What get printed for values of aa and bb? 2 and 12. The name bb now refers to a new number that was the result of evaluating the expression bb + 10 or (+ bb 10). (Recall what the assignment operator in reference semantics does.) In diagram:

aa: ---+
       |
       |
       v

       2     12

             ^
             |
             |
bb: ---------+

The name aa is still pointing to the original number that aa and bb together used to point to.

Can one write a function that takes a number and then adds 10 to that number? To test, what would happen if we run the following?

Snippet 80:

aa = 1 + 1
def dosomething(bb):
    bb = bb + 10
dosomething(aa)
print(aa)
(setq aa (+ 1 1))
(defun do-something (bb)
  (setq bb (+ bb 10)))
(do-something aa)
(print aa)

What gets printed? The result is 2 and it’s not 12. This example just repeats the previous snippet but with a function call. When you call the function dosomething by passing aa, the interpreter first makes the local variable bb refer to whatever aa was referring to at the time, then the first line in the function body makes bb refer to a new number. Value of aa after that is still 2.

Now some might say “What about the += operator in Python or incf in Lisp? How can it do what it does?” I’ll demonstrate what it does, how it does what it does, and what it doesn’t do, with the following code.

Snippet 90:

aa = 1 + 1
bb = aa
bb += 10
print(aa)
print(bb)
(require 'cl-lib)

(setq aa (+ 1 1))
(setq bb aa)
(cl-incf bb 10)
(print aa)
(print bb)

Output is 2 and 12.

What happens is that whenever Python interpreter encounters this statement

bb += 10

it replaces the statement with the new statement bb = bb + 10 and runs that new statement instead.6 Likewise, whenever Emacs encounters the expression (cl-incf bb 10), it replaces the expression with the new expression (setq bb (+ bb 10)) and evaluates that new expression instead. This is possible because cl-incf is a Lisp macro, rather than a Lisp function.

Whatever you do to bb with your code, it does not affect aa or any other variables that refer to integers or other immutable objects. That’s the thing with immutable objects. So you can rely on “numbers next to names” diagrams instead for convenience, by which I mean diagrams that doesn’t have arrows pointing to numbers, you just draw numbers next to the variable names. For example, you can draw this diagram

aa: 2    



bb: 2

rather than the diagram where aa and bb points to the same 2, and you can also rely on this diagram

aa: 2


bb: 12

rather than on the diagram where aa points to 2 and bb points to 12. They don’t look that much convenient for now because these diagrams are very simple. We will meet complicated diagrams soon.

Notice that for immutable objects, there can be no external difference between reference semantics and value semantics. That is unless you decide to check object identity between immutable things, but you wouldn’t do that (see the post on identities of immutable objects). Because it is assumed that we wouldn’t do that, some interpreters might choose to use value semantics for some small immutable objects for performance reasons, much like how we can rely on “numbers next to names” diagrams.

9. Nested structures, shallow copy, deep copy

I’ll demonstrate what shallow copies are, using diagrams. The following code creates a vector of three elements, and the first element happens to be a vector. So we have a nested structure (a vector containing a vector). The second line in the code makes a shallow copy of aa.

Snippet 100:

aa = [[0, 0], 11, 12]
cc = aa[:]
(setq aa (vector (vector 0 0) 11 12))
(setq cc (copy-sequence aa))

Now aa and cc are different objects, not the same object. But aa and cc share their elements. Structure is copied, but elements are not copied, they are just shared.

          +------------+
aa: --->  | 0:  1:  2: |
          | |   |   |  |
          +-|---|---|--+
            |   v   v   
+------+    |           
|0: 1: | <--+  11   12  
||  |  | <---+        
+|--|--+     |  ^   ^ 
 v  v        |  |   | 
 0  0     +--|--|---|--+
          |  |  |   |  |
cc: --->  | 0:  1:  2: |
          +------------+

That’s what a shallow copy is, at least in Python. Let me quote a paragraph from S.Lott, from a stackoverflow.com thread: “Shallow copies duplicate as little as possible. A shallow copy of a collection is a copy of the collection structure, not the elements. With a shallow copy, two collections now share the individual elements.”

So the vectors aa and cc are different under object identity. The first element of aa and the first element of cc are same under object identity. The second element of aa and the… wait, let’s recall that we are not supposed to check object identity between integers.

This relation between aa and cc is usually expressed in many ways, such as:

  • “cc is a shallow copy of aa”
  • “cc is a copy of aa, except their elements are shared.”
  • “copy-sequence returns a copy of a vector, but their elements are not copied.”

Diagrams are getting complex, so let’s invoke the “draw numbers next to names” trick, and redraw the previous diagram like this:

          +------------+
aa: --->  | 0:  1:  2: |
          | |   11  12 |
          +-|----------+
+------+    |           
|0: 1: | <--+           
|0  0  | <---+        
+------+     |        
          +--|---------+
          |  |  11  12 |
cc: --->  | 0:  1:  2: |
          +------------+

Now what happens if we run the following code right after we run the previous code? In the following code, we do something to the first element of cc, and then we print the first element of aa, not of cc:

Snippet 110:

cc[0][1] = 90 + 9
cc[0] = 9999
print(aa[0])
(setf (elt (elt cc 0) 1) (+ 90 9))
(setf (elt cc 0) 9999)
(print (elt aa 0))

The first element of aa is now a vector of 0 and 99. The aftermath in diagram:

          +------------+
aa: --->  | 0:  1:  2: |
          | |   11  12 |
          +-|----------+
+------+    |           
|0: 1: | <--+           
|0  99 |     +--> 9999 
+------+     |        
          +--|---------+
          |  |  11  12 |
cc: --->  | 0:  1:  2: |
          +------------+

We did two things to the first element of cc. The first line of code did mutation of first element of cc. Mutating that element had an effect on first element of aa and that’s not surprising because first element of aa and that of cc were the same object at that time. On the other hand, the second line, the assignment to the first element of cc had no effect on the first element of aa, and that’s not surprising either. Yes, this is our first litmus example in disguise. To relate to it, notice that the expression cc[0] in the last snippet is playing the same role as the expression bb in Snippet 10 (the litmus example).

As for difference between shallow copy and deep copy, Here is a relevant quote from the Python documentation:

The difference between shallow and deep copying is only relevant for compound objects (objects that contain other objects, like lists or class instances):

  • A shallow copy constructs a new compound object and then (to the extent possible) inserts references into it to the objects found in the original.
  • A deep copy constructs a new compound object and then, recursively, inserts copies into it of the objects found in the original

The following shows another way of making a shallow copy.

Snippet 115:

aa = [[0, 0], 11, 12]
cc = [0, 0, 0]

cc[0] = aa[0]
cc[1] = aa[1]
cc[2] = aa[2]
(setq aa (vector (vector 0 0) 11 12))
(setq cc (vector 0 0 0))

(setf (elt cc 0) (elt aa 0))
(setf (elt cc 1) (elt aa 1))
(setf (elt cc 2) (elt aa 2))

And here is yet another way of making a shallow copy.

Snippet 116:

aa = [[0, 0], 11, 12]
cc = [aa[0], aa[1], aa[2]]
(setq aa (vector (vector 0 0) 11 12))
(setq cc (vector (elt aa 0)
                 (elt aa 1)
                 (elt aa 2)))

These two alternative ways of making a shallow copy are more verbose. I only included them here for illustration.

As for making a deep copy, you have to define a recursive function or borrow one from a relevant library.

10. assignment to an expression

This section is about something that is already demonstrated implicitly in some of previous sections. In this section, I want to make it explicit. Have I mentioned what is supposed to happen when we run something like the following code?

Snippet 117:

xx[i+j][0][k+1] = f(a, b, c) + g(e, f)
(setf (elt (elt (elt xx (+ i j)) 0)
           (1+ k))
      (+ (f a b c)
         (g e f)))

What is guaranteed to happen is that the expression on the right hand side (f(a, b, c) + g(e, f) in the Python snippet or (+ (f a b c) (g e f)) in the Lisp snippet) is evaluated. Let’s call the result of the evaluation the r-object, for lack of a better term.

What technically does NOT happen is the evaluation of the expression on the left hand side (xx[i+j][0][k+1] in the Python snippet or (elt (elt (elt xx (+ i j)) 0) (1+ k)) in the Lisp snippet). Nevertheless, let’s call the result of the evaluation of the left hand side the l-object.

As demonstrated many times in earlier sections, the change of the l-object is not in the sense of transformation, but in the sense of new designation. The l-object is never mutated.

In terms of arrow diagrams, what happens is that some arrow pointing to the l-object changes its direction to point to the r-object. There could have been many arrows pointing to the l-object if you drew the diagram in a more full context encompassing more code, but only one arrow changes its direction.

While the l-object is not mutated, the parent object (the object you get by evaluating the sub-expression xx[i+j][0]) IS mutated.

11. value semantics, C, elephants

Since we talked a lot about reference semantics, let’s talk a little bit about value semantics. The C language uses value semantics. This section does NOT assume familiarity with C, so this section might work as a tiny intro to C as well, and this is the only way I can explain value semantics in more detail. Recall that in value semantics, there are boxes and there are things and boxes contain things. C is a compiled language and is statistically typed, so when you declare an integer variable like this

int aa;

the variable aa can only hold integers. You can think of this as being there a box labeled aa, and that box can contain only values of int type.

Now consider this C code.

Snippet 120:

int i = 123;
float f = 3.14;
i = i + i;
i = f + f;

Above code declares an int variable i and a float variable f. Initially the value of i is 123 and the value of f is 3.14. The third line computes the expression i + i and the result int value 246 is copied into the box labeled i.

The last line is interesting. It is specifying an int variable on the left side, but the expression on the right hand side gives a float, and remember that an int variable can only hold an int value. So what happens? When you try to assign a value to a variable and the types are different, one of the following things happens:

  • the compiler gives an error or warning, or
  • the program comes up with a new value of right type (related to the original value) and assigns it instead.

Now consider this C code.

Snippet 130:

#include <stdio.h>

struct Point {
   int x;
   int y;
};


int main(void) {
  struct Point aa;
  aa.x = 10;
  aa.y = 11;
  struct Point bb = aa;

  bb.x = 90 + 9;

  printf("aa.x equals %d\n", aa.x);
  printf("bb.x equals %d\n", bb.x);

  return 0;
}

The line struct Point aa; declares a variable of type Point. This data type is composed of two int fields. So you can imagine a box labeled aa, which is composed of two smaller boxes, and the two small boxes can only hold int values, while the big box can only hold Point values. The next two lines initializes aa to have 10 and 11 as its elements, and the next line struct Point bb = aa;, which declares bb but also assigns aa to bb, copies contents of aa and writes into the box labeled bb, because that’s what the assignment operator does in value semantics. So you get:

      aa
+------+-------+
|      |       |
|  10  |  11   |
|      |       |
+------+-------+


      bb    
+------+-------+
|      |       |
|  10  |  11   |
|      |       |
|      |       |
+------+-------+

and then the line bb.x = 90 + 9; does something to bb and you get:

      aa
+------+-------+
|      |       |
|  10  |  11   |
|      |       |
+------+-------+


      bb    
+------+-------+
|      |       |
|  99  |  11   |
|      |       |
|      |       |
+------+-------+

Notice how that did not affect aa. This contrasts with results of Snippet 10 or Snippet 20 in reference semantics.

In languages with value semantics, the word “variable” usually means “box” in our metaphor, and “value” usually means contents of a box. So, while this post keeps saying “box”, you should say “variable” if you are posting a question in a C forum.

If you are new to C, you are going to have a question at this point. These boxes have fixed sizes according to their types, but then how does one work with something like vector objects which can contain arbitrary many other objects of arbitrary types? What is the size of a box for a vector object? What if the vector has so many elements that it cannot be contained within that box?

It all comes down to this: how do you store an elephant in a freezer when you are given a freezer that is smaller than that elephant? You don’t. You work around. You don’t store a big object into a box of small size. Instead, you store some kind of reference to that big object into a box that is designed to store references. This is where pointer variables in C come in. They store memory addresses. The question “how do I do vectors stuff in C” is a very good question because its full answer teaches you not only about pointers, but also about double pointers, but I will not go into that. I only wanted to assure you that value semantics is not less powerful.

That’s it for value semantics, but since you are now being introduced to C, I feel I need to say more about C. In C, a box is just some contiguous block of memory. The metaphor “box” (or rather the abstract notion of “variable”) is in the compiler’s mind. A box can be on the stack or on the heap. What are the stack and the heap? C snippets in this post so far involve only the stack. Construction and destruction of boxes on the stack are done automatically so that you don’t have to manually write C code saying something like “destroy this box” for this. The stack is the memory set aside for this automatic business. It’s called the stack because if you try to guess how this automatic business is done, something resembling the stack data structure would be the first thing that comes to your mind. For elephants stuff, you need to write C code saying something like “I order a box of size n bytes” or “I’m done using that box. Now destroy the box, i.e., release that block of memory”, and the heap is the memory set aside for elephants that you might create. This is good to know even if you don’t plan to learn C, because some useful articles on Python invoke the concept of the heap and stack frames: recall that reference semantics can be considered a special case of value semantics.

12. For those coming from C

Make sure you can convert between the following two (effectively equivalent) pictures:

  • “Everything is a pointer in Python”
  • “There is no pointer in Python.”

You know what each of the two statements means. The second statement at first can make you feel restrained (not being able to work with addresses directly), but many of the tasks that you usually do with double pointers in C can be done in a language with reference semantics.

Languages that use reference semantics usually use a garbage collector so that objects live as long as necessary. Remembering this and the fact that there are no boxes can be helpful when trying to understand closures later (if the language supports closures).

Many times you may have to recall that integers are immutable objects (in Python and Lisp). Any data type that is not a container type is highly likely to be an immutable type in these languages.

13. copying vs. sharing

Now you know that copying is possible in reference semantics and sharing is possible in value semantics, you might be wondering when to copy vs when to share.

The main benefit of copying is that copies are independent from each other. When cc is a deep copy of aa, whatever you do to cc does not affect aa. When reasoning about aa, you don’t have to worry about what other’s code might do to cc. (This is also the benefit of immutable objects.)

The main benefit of sharing, other than less memory usage, is the fact that when cc and aa refer to the same object, mutation of cc is automatically announced to user of aa instantly without you manually having to notify to the user of aa. Similarly, when cc[0] and aa[0] refer to the same object (which is the case if cc is a shallow copy of aa), mutation of cc[0] is automatically visible to aa without you having to do some update operation on aa. When a new mayor is elected, it takes newspapers and tv and internet to get everyone notified of that fact. But when an adviser changes the mayor, every resident instantly has an updated mayor. without having to be notified of anything. And that is the convenience of mutating a shared mutable object.

14. Next sections

Some of next sections are specific to Python, and some are specific to Lisp. If you are reading this post as part of learning Lisp, feel free to skip the sections specific to Python. And vice versa.

15. Python specific

15.1. The plus equal operator in Python

There is some gotchas related to the augmented assignment operator += in Python, which can be summarized as:

  • The plus equal operator does different things depending on whether it’s working on immutable objects or mutable objects.
  • Strings are immutable in Python (unlike in Emacs Lisp).

Result of the following code is not surprising now.

Snippet 140:

ii = 100
jj = ii

jj += 50

print(ii)  # => 100
print(jj)  # => 150

But the result of the following code may be surprising.

Snippet 150:

mm = [7, 8]
nn = mm

nn += [4, 1]

print(mm)  # => [7, 8, 4, 1]
print(nn)  # => [7, 8, 4, 1]

The twist is that while the statement jj += 50 expands to jj = jj + 50, the statement nn += [4, 1] does NOT expand to nn = nn + [4,1], but to some function call that takes nn and mutates it. So the += operator treats mutable targets and immutable targets differently. For more on this, look into iadd in Python documentation.

15.2. Python tuples, immutable or mutable?

In the following code, we assign a tuple object, which is a kind of container object, to the variable tt and then we try to assign something as its first element.

Snippet 160:

tt = (10, 11, 12)
tt[0] = 90 + 9

But running that code results in the following error:

TypeError: 'tuple' object does not support item assignment

Such operation is just not allowed with tuple objects. On the other hand, the following code runs fine.

Snippet 170:

tt = ([0, 0], 11, 12)
tt[0][1] = 90 + 9

print(tt)  # => ([0, 99], 11, 12)

So we are allowed to change elements of a tuple in the sense of transformation, but changing its elements in the sense of new designation is not allowed. This raises a question, what category do tuple objects belong to, among immutable vs mutable? Python documentation’s position is that tuple objects should be considered immutable objects. They are platypuses of immutable objects. The general statement “mammals don’t lay eggs” has exceptions, and some of my statements about immutable objects in this post may have exceptions.

15.3. Mutable default arguments gotcha in Python

Since two of the three main gotchas in Python are already mentioned, I’ll mention the third one too: Default arguments in Python and Lisp.

16. Lisp specific

16.1. setf vs. setq

If you are new to Lisp, reading some of Lisp snippets in this post, a question might have come to your mind: what is the difference between setq and setf? When to use which?

The main difference is that

(setf (elt bb 0) (+ 90 9))

works but

(setq (elt bb 0) (+ 90 9))

does not work.

On the other hand

(setq aa (+ 1 1))

works and

(setf aa (+ 1 1))

also works.

You can always use setf in place of setq. Why am I using setq in some places then? Habit and/or tradition.

16.2. Lisp symbols

It is important to know that the “names referring to objects” picture is an approximation, in case of Lisp. The real picture is “symbols referring to objects”. Also, symbols are objects too in Lisp. When you run the following code, the symbol aa gets associated with 99.

(setq aa (+ 90 9))

So, symbol objects can play the role of Lisp variables, but they can be used for other roles as well which I will not mention. They are multipurpose.

The following docstring for setq makes clear that symbol objects are really being used for the role of variables:

setq is a special form in `C source code'.

(setq [SYM VAL]...)

Set each SYM to the value of its VAL.
The symbols SYM are variables; they are literal (not evaluated).
The values VAL are expressions; they are evaluated.
Thus, (setq x (1+ y)) sets `x' to the value of `(1+ y)'.

One usually says that the print name of the symbol aa is “aa”, or simply that the name of the symbol is “aa”.

Usually, there is only one symbol object of the same print name. But that’s not always the case. There are exceptions. You don’t need to know about these exceptions until you learn to define Lisp macros, which is when you get to use functions like make-symbol or gensym to create these exceptional symbol objects (i.e. uninterned symbols) which are guaranteed to be distinct from whatever symbols you happen to use in your Lisp code.

Common Lisp note: In case of Common Lisp, there is only one symbol object of the same print name in the same package.

And one more thing to complete the picture. Emacs Lisp and Common Lisp are Lisp-2. Being a Lisp-2 just means, to quote Wikipedia, “The namespace for function names is separate from the namespace for data variables.”, or to quote from Peter McLain in a stackoverflow thread , “Lisp2 has (at least) two namespaces (symbols have a slot for their a function value and one for a regular value).”

16.3. Do not modify a constant

Speaking of immutable objects and mutable objects, I need to mention that in Lisp there are certain cases where you should not modify some objects even though those objects are mutable. In other words, you should treat them as if they are immutable. What are these cases? First, we need to know what literal objects are.

CLHS Glossary defines “literal” (as in “literal objects”) as follows:

adj. (of an object) referenced directly in a program rather than being computed by the program; that is, appearing as data in a quote form, or, if the object is a self-evaluating object, appearing as unquoted data.

Snippet 180:

;;; a literal vector
(setq vv [10 20 30])

;;; a computed vector
(setq vv2 (vector 10 20 30))

;;; a literal string
(setq ss "hello world")

;;; a literal list (also a quote form)
(setq ll '(10 20 30))

;;; a computed list
(setq ll2 (list 10 20 30))

The variables vv, ss, ll refer to literal objects, but vv2 and ll2 don’t.

So the rule is that you should not modify literal objects. In other words, you should not mutate any part of literal data. Instead, you should treat them as constant data for your program. Hence the phrase “do not modify a constant”. Since it is understood that we would treat them as constants, the compiler (or even the interpreter) may sometimes try to optimize code for example by collapsing constants (or parts of them) appearing in code if they are structurally equal (i.e. if they are same under the function equal). And that in turn is why you should not modify a literal object. It’s a back and forth relation.

You know you are not supposed to check object identity on immutable objects. And you need to treat literal objects as if they are immutable objects. As a result, you are not supposed to check object identity between parts of literal objects.

16.4. Common Lisp note

Everything in this post, unless stated otherwise, applies to Common Lisp as well, but you might need to change some function names in some elisp snippets in this post to make them Common Lisp code. For example cl-incf to incf, and copy-sequence to copy-seq.

Do NOT setf or setq to undeclared variables in Common Lisp. Lisp snippets in this post are violating that advice, if thought of as stand alone code.

If you are interested in more differences, see differences between Common Lisp and Emacs Lisp

16.5. Further reading for Emacs users and Lisp beginners

This post is part of the Living with Emacs Lisp series. The next post to read the post on how to manipulate lists in Lisp.

Footnotes:

1

The reason the simplification is done this way rather than the other way around is because of Lisp lists which are different creatures altogether

2

In Python, even integers are objects. This is due to how the Python documentation defines the term “object”. This post adopts that usage of that term, for simplicity.

3

Recall that we (incorrectly) call Python lists “vectors” for simplicity in this post.

4

plus enabling of some garbarge collector

5

except for phrases like “call by sharing” and “pass by object references” which seems to have only one possible interpretation

6

I am simplifying a bit here. This will be addressed later.

This entry was posted in Emacs, Lisp, Python and tagged , , . Bookmark the permalink.

One Response to Names and things (reference semantics) vs. boxes and things (value semantics)

  1. Pingback: Living with Emacs Lisp | Yoo Box

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s