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

The goal of this post is to explain the “names and things” semantics (or 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 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 (with integers) in general cannot be a function (in Python and in Lisp) (which contrasts with C++).
• why Lisp macros setq, setf, incf and push cannot be functions.
• how to work with Lisp lists

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 Lisp, I remember reading an article about Python variables and it helped me with my confusion over 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. 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, 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.

## 6. Pass by value or pass by reference

Now that you 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))


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

## 10. 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? 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 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.

## 11. 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.

## 12. 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.

## 13. 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.

## 14. Python specific

### 14.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.

### 14.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.

### 14.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.

## 15. Lisp specific

### 15.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.

### 15.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 variables role:

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.

Just one more twist you need to check out. Read about Lisp-2. Emacs Lisp and Common Lisp are Lisp-2. Now you have the complete picture.

### 15.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.

### 15.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.

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

### 15.5. Further reading for Emacs users and Lisp beginners

This post is part of the Living with Emacs Lisp series. The next post you want to read in this series is probably something about Lisp lists, which I will write soon.

## 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.

## It is not hard to edit Lisp code

• those who are a bit curious about Lisp
• beginners of Lisp
• Dan

The goal of this post is to convince you that you can edit or write Lisp code with ease. In particular, to convince you that in the end managing all those parentheses is no problem at all, that is, you don’t count parens. This post contains

• editor-agnostic tips on how to edit Lisp code
• and some tips for Emacs users in particular (which you should of course skip if you use other editors or IDEs)

Readers are assumed to have read the previous article: It is not hard to read Lisp code.

Many tips in this post were already expressed before in some places in some form or another, but I thought I would make a single post containing all tips organized in a particular way, and with examples and exercises. Reading this post, especially if you do all exercises, which you should, is going to take a long time, so at the end of this post, let’s watch some video of dancing chickens to reward ourselves.

## 1. Intro

Dan: “Eve, I heard you can write Lisp code. Is that true?”
Eve: “Yes. Why?”
Dan: “Do you want to apply to my department? The department needs someone who can do Lisp. Need to modify some small scripts written in Lisp, left by someone who left to become a wrestler. This town now has only two programmers, you and me, and I don’t Lisp.”
Eve: “You can learn Lisp.”
Dan: “I tried, but I find that editing Lisp code is too difficult compared to other languages. Maybe Lisp is not for everybody? And I’m just an amateur programmer.”
Eve: “Trust me, you can become one of those who can edit Lisp code seamlessly. I’ll tell you how.”
Dan: “Will it take months for me to become such? Please don’t tell me to just use Emacs”
Eve: “Whatever decent editor you choose, you and your text editor together start a journey. A journey that is much shorter than you expect. This journey passes through three distinct and recognizable phases1, and these are:”

1. the “no red tape” phase
2. the “red tape” phase
3. the “automation” phase

Dan: “Abbreviated to NRA?”
Eve: “Maybe. Anyway, good news is, you are already at the first phase. The first phase works as a good motivator for the second phase. And the second phase motivates you to get to the third phase. You may be able to go through these phases within just one day.”

Just like cooking rice on the stove, something that looks hard at first, but actually easy if you do it in a particular way.

## 2. Which editor or IDE to use

If you have not decided, I heard that PLT Scheme and LispWorks are good.

In the long term, any editor or IDE that comes with some plug-ins ecosystem is bound to evolve to acquire every possible feature for helping Lisp coding. (If you miss a feature, be excited, you will be the author of an awesome future plug-in implementing the missing feature. Find a work around for now, but still mark a date on your calendar, one year from now, the start date of your plug-in development.) Also, it would be helpful (especially in the third phase) if the editor of your choice allows you to define macros or commands of your own in programmable manner.

What about Vim users? Vim is not my area of expertise, but if you are a Vim user, read this thread. In short, some people made a plugin for you.

The rest of this post assumes that you are using some text editor that is somewhat programmable or a Lisp-specific IDE.

## 3. The three phases

In the first phase, the “no red tape” phase, you edit Lisp code in an unconstrained way and you have some ways of dealing with mismatched parentheses you sometimes accidentally introduce during this phase. This leads to the second phase, the “red tape” phase, where you edit code under a set of rules. The rules are designed to prevent mismatched parentheses and to promote structure-based editing. But you might find editing in this phase to be cumbersome or tedious. That is why you get to the third phase where you automate things as much as possible. After that, editing per se should be almost effortless, and then what you do is the same as in other languages: read others code, write some code, practice, ask what are good practices, etc, that is, there is more to writing code other than just effortless text editing, but you and Dan already know that.

Before we get to tips for the first phase, let’s go through some tips common to all phases first.

## 4. Always indent.

Recall (from the previous article) that readability mostly comes from indentation and that there is only one correct indentation style, namely, the indentation that your text editor suggests. Find a keyboard shortcut or a button that correctly indents the selected code.

Suppose you have the following code:

(print (+ 1
2
3))
(print "blah")

(defun my-hi ()
(dotimes (_ 2)))


Let’s say you want to move the two print forms into the dotimes form, so that the resulting code (if correctly indented) is:

(defun my-hi ()
(dotimes (_ 2)
(print (+ 1
2
3))
(print "blah")))


Without correct indentation, if you just cut the two print froms and paste them into the dotimes form, you just get:

(defun my-hi ()
(dotimes (_ 2)
(print (+ 1
2
3))
(print "blah")))


which is badly indented. You must always reindent after you paste any code, using the appropriate keyboard shortcut or button.

While editing Lisp code, always make sure to keep the code correctly indented after every edit (or just after every edit that can mess up indentation, such as pasting). Adopting this obsessive habit will help you in two ways:

• code is always kept readable (it is hard to edit less-readable code, more so for beginners)
• easier to spot missing open parens (a.k.a. opening parentheses) or close parens (a.k.a. closing parentheses) (as is demonstrated with the following exercise)

Exercise 10. Try deleting the third line from the following code (thereby making it an invalid code because missing open parens) and then reindent the whole code and see what happens. Alternatively, try deleting the 5th line and reindent and see.

(defun my-hi ()
(dotimes (_ 2)
(print (+ 1
2
3))
(print "blah")))


If this habit seems tedious, find a way to automate some of it in your editor. It is highly likely that automating this is already a feature or there is a relevant plug-in for your editor, otherwise, mark a date on your calendar.

### 4.1. Emacs note

Some notes for Emacs users.

On an Emacs Lisp buffer (a buffer you get by opening a file with extension .el), the key C-j runs the command newline-and-indent which inserts a newline and then indent according major mode (so, pressing C-j is the same as pressing RET TAB). On the scratch buffer, the same key does a different thing. Other Emacs notes in this post assumes that you are coding on an Emacs Lisp buffer, not on the scratch buffer. Speaking of which, you might want to see how to enable Unicode encoding, lexical scope, and CL functions in an Emacs Lisp file. I will also assume that you are using the latest stable version of GNU Emacs.

Also check out M-j which runs indent-new-comment-line which seems to do the same thing as C-j except some slight difference when you run this command within comments.

Recall the two keys for indenting in Emacs: TAB and C-M-\

TAB runs the command indent-for-tab-command which in Emacs Lisp buffers simply indent the current line or region according to the elisp indentation standard. C-M-\ runs the command indent-region which does exactly what you expect from its name: it indents the region according to the standard.

It is a good habit to always press C-M-\ right after you paste some expressions, and it will correctly indent the pasted expressions, even if you have not manually selected the region before pressing C-M-\ (unlike TAB).

For the purpose of this post, the following terms are interchangeable:

• “expression” or “symbolic expression”
• “balanced expression” in the Emacs manual and documentation of commands
• “sexp” in some Emacs command names

Some other indentation tips are scattered across other Emacs notes in this post.

## 5. Evaluate!

Lisp happens to be one of those dynamic languages. You may have heard of pros and cons of such languages. Do exploit the pros such as rapid prototyping or quicker “code, test, code again, test again” loop during Lisp coding. Remember that you can evaluate the whole code (the whole file), or just some part of the code, or even just one defun form that you just modified a bit. If this paragraph does not seem to make sense, watch this impressive demo video and you’ll get it.

In your text editor, find a way to evaluate some selected part of code, or find a plug-in for it.

### 5.1. Emacs note

Open an Emacs Lisp file, empty or not. Notice the “Emacs-Lisp” menu in the menu bar and see that there is a menu item for evaluating a region (selected region), and another for evaluating the last expression (the last expression before point). Did you know that you can use C-h k even for menu items and toolbar items? Use C-h k to read documentations for the two commands bound to the two menu items.

Visit any Emacs Lisp buffer and then press C-h m to see if there are any keys that hook your interest. Let’s see. On vanilla Emacs, I see:

C-M-i           completion-at-point
C-M-q           indent-pp-sexp
C-M-x           eval-defun
...


C-M-i is what you can press right after you type def and then Emacs will say to you “Possible completions are defadvice, defalias, default, …. Would you like to choose one?”.

C-M-q is for when you have some badly indented code like so:

(defun my-hi ()
(dotimes (_ 2)
(print (+ 1
2
3))
(print "blah")))


Assuming that point is at anywhere within the above snippet, you can press C-M-u multiple times until point is at the start of the defun form, and then you can press C-M-q to fix indentation of the defun form. It seems that pressing C-M-q is the same as pressing C-M-SPC C-M-\

C-M-x runs eval-defun which evaluates the top-level form containing point, or after point. The command is named eval-defun probably because a top-level form is often called a defun (at least within the Emacs documentation), regardless of whether it is actually a defun form or not.

Here is how you might edit some Emacs Lisp code. The workflow is like this. Let’s say you have some code in your init file that you copied from somewhere else, maybe from EmacsWiki. One day, you decide you want some slightly different behavior from the copied code. So you modify some defuns in the code, and then you evaluate them right there, and then you can test the change you just made. If the test indicates that something is wrong, you modify the code again. The cycle continues until you get it all right. In each cycle, you may or may not need to restart Emacs, and most of the times you don’t.

## 6. One liners

Beginners should stay away from writing one-liners like:

(defun my-hi () (dotimes (_ 2) (print (+ 1 2 3)) (print "blah")))


because:

• editing a long one-liner is hard, more so for beginners, and
• reading a one-liner is hard.

Let’s say you ended up writing some very long one liner (this can happen even if you didn’t mean to). What can you do after the fact? You can break the one line into multiple lines, and then, as always, you reindent the code.

You might say, “exactly how should I break this line into multiple lines? I mean, where in the original line should I insert newlines?” There isn’t one answer, but as you read more and more Lisp code, you will get a feel for where to put newlines.

## 7. Breaking lines

Whenever you are breaking a line, don’t forget to indent all the way. For example, consider the following code:

(let ((n (frobbotz))) (display (+ n 1)
port))


Let’s say you want to break the first line into two lines by breaking at the start of the display form. If you just insert a newline there, you get:

(let ((n (frobbotz)))
(display (+ n 1)
port))


which is badly indented, and then if you press some button to indent the current line (the second line), you get:

(let ((n (frobbotz)))
(display (+ n 1)
port))


which is still badly indented. You need to correctly indent the third line as well, to get:

(let ((n (frobbotz)))
(display (+ n 1)
port))


In your text editor, there should be a command for breaking a line while also automatically deleting trailing whitespaces (for example, you might want to delete the trailing whitespace that might be at the end of the first line in the new code).

As for indenting all the way, a good alternative to “Correctly indent the current line. Move to next line. Correctly indent the current line. Move to next line … Done.” is to simply press the button for selecting the expression (following the text cursor), and then press the button for correctly indenting the selected expression.

### 7.1. Emacs note

Suppose again you have this code:

(let ((n (frobbotz))) (display (+ n 1)
port))


On vanilla Emacs, move to the start of the display form, and then press: C-j C-M-SPC C-M-\ and see what happens. Alternatively, you could have pressed C-j C-M-q instead, which is shorter. Notice that C-j deletes the trailing whitespace automatically. (M-j deletes the trailing whitespace too.) Consequently, before you press C-j, you could have put point at anywhere between the end of ((n (frobbotz))) and the start of the display form2.

If you use paredit, C-j is bound to the command paredit-newline so that you don’t even have to press C-M-SPC C-M-\ or C-M-q afterward. Paredit is amazing like that.

## 8. Joining lines

Sometimes you might want to do the reverse of breaking a line, that is, you might want to join two lines into one. Your text editor is likely to have a command for exactly that. Such command should, automatically in addition, combine many whitespaces into one. In other words, when you have the following code:

(display (+ n 1)
port)


and then when you invoke the command for joining the two lines, you should get:

(display (+ n 1) port)


rather than this:

(display (+ n 1)         port)


Find that command in your text editor. (Emacs note: See C-h f join-line)

Exercise 20. Invoke the command three times to change from this:

(display (+ n
1)
(+ n
1))


to this:

(display (+ n 1) (+ n 1))


(Emacs note: you need to start from the last line, not the first line.)

Exercise 30. Now do the reverse. Split the line back into four lines.

Exercise 40. Break the following one line into many lines, however way you want. Then join to single line again. Then break again, but this time, break in a different way.

(setq exp (read-string (format "%s expansion for \"%s\": " type name) nil nil nil t))


## 9. Placement of close parens

Suppose you have this Common Lisp code:

(defvar *persons*
(list (make-person "fred")
(make-person "jane")
(make-person "susan")))


If you want to change that to the following code, you only have to invoke the command for breaking a line once.

(defvar *persons*
(list (make-person "fred")
(make-person "jane")
(make-person "susan")
))


The latter style makes it easier to append a new make-person form (as the new last item). (Nevertheless, it is not that hard to append a new item in the former style. We’ll get to that.)

Some beginners go too far with this and make lots of lone trailing parens on their own lines, like so:

(defun my-clone-indirect-buffer-other-window (newname display-flag &optional norecord)
"Like clone-indirect-buffer' but display in another window."
(interactive
(progn
(if (get major-mode 'no-clone-indirect)
(error "Cannot indirectly clone a buffer in %s mode" mode-name)
)
(list (if current-prefix-arg
(read-buffer "Name of indirect buffer: " (current-buffer))
)
t)
)
)
(let ((pop-up-windows t))
(clone-indirect-buffer newname display-flag norecord)
)
)


Exercise 50. Invoke the command for joining lines multiple times to change that to this code:

(defun my-clone-indirect-buffer-other-window (newname display-flag &optional norecord)
"Like clone-indirect-buffer' but display in another window."
(interactive
(progn
(if (get major-mode 'no-clone-indirect)
(error "Cannot indirectly clone a buffer in %s mode" mode-name))
(list (if current-prefix-arg
(read-buffer "Name of indirect buffer: " (current-buffer)))
t)))
(let ((pop-up-windows t))
(clone-indirect-buffer newname display-flag norecord)))


You might want to read this thread from which above code is also taken.

Some things I want to point out before we move on to the next section:

• Putting close parens together (rather than writing close parens on their own lines) is the convention.
• We’ll get to why following this convention is not hard.
• There are some cases where putting close parens separately can be OK. (See this thread and Rainer Joswig’s answer.)

Some people put some close parens separately to indicate unfinished code, like so:

(defun my-blah ()
(let ((b 2))
(why)
(did)
(the)
(chicken)
))


and then when they are done writing the let form, they join close parens together to indicate that writing the let form is done, like so:

(defun my-blah ()
(let ((b 2))
(why)
(did)
(the)
(chicken)
(cross)
(the)


Maybe that can be a useful habit for you to adopt as well, if you decide you like it.

I just realized that I have never seen a chicken cross a road. If I ever get into poultry farming, I should put a realistic miniature road in my farm, and make it a tourist attraction for those who want to see a chicken cross a road at least once in their lifetime.

## 10. The “No red tape” phase

There are many ways of dealing with occurrence of mismatched parentheses in this phase. One of them is to simply check for syntax errors more often. Maybe press the “compile” or “run” button often, if any, or the “is there a missing paren” button often. Recall that you can evaluate just one defun you just edited instead of evaluating the whole code.

In your editor, there should be a command for locating missing parens. If not, evaluating or compiling is a good enough substitute because it would at least report existence of missing parens if any. If something like real time syntax check is provided, that also helps.

What should you do when real time syntax check told you that you accidentally just introduced some mismatched parens? Simply undo (usually bound to Ctrl+Z) and start over. Example situation: Suppose you have the following code:

(defun my-hi ()
(dotimes (_ 2)
(print "hello")
(print "world"))
(print "the end"))


Suppose that you want to remove (print "world"), and that you (wrongly) decide to do that by deleting or commenting out the second-to-last line. So you have:

(defun my-hi ()
(dotimes (_ 2)
(print "hello")
(print "the end"))


But then the real time syntax check now tells you that there is a missing paren. Even if real time check isn’t supported in your editor, you would find that out anyway if you invoke the indenting command on the defun. Upon realizing that just deleting the line was a wrong way to remove (print "world"), you can simply undo the deletion of line and start again.

One might ask: is there a tool that automatically fixes missing parens? Probably impossible.

### 10.1. typing the correct number of closing parentheses

This is something you don’t have to deal with in later phases (second and third phases), but in the “no red tape” phase, you do need help for this from your text editor.

(sqrt (+ (expt (/ ΔL′ (* Sl kL)) 2.0)
(expt (/ ΔC′ (* Sc kC)) 2.0)
(expt (/ ΔH′ (* Sh kH)) 2.0)
(* Rt (/ ΔC′ (* Sc kC)) (/ ΔH′ (* Sh kH)))))


If you were to write above code, how would you figure out how many close parens to type at the end? If your editor has the feature of highlighting the open paren matching the close paren you are typing, that is how you know how many to type, you just type close paren repeatedly at the end until the matching open paren is the one you want to match.

One might ask: can there be a command that just inserts the correct number of close parens? A command like “Insert enough close parens to complete this top-level form” can be made, but in general for non-top-level forms, probably not.

### 10.2. Emacs note

On vanilla Emacs, every time you type a close paren, the text cursor moves to the matching open paren for a second. Handy in the first phase.

Exercise 55. See what happens if the matching open paren is not visible on screen (for example, when it is somewhere above the displayed lines). (Watch the echo area).

If you enable show-paren-mode (available within vanilla Emacs), whenever point is after a close paren (resp. before an open paren), Emacs shows you the matching open paren (resp. close paren). Have this mode enabled. Useful in all phases.

To check for missing parens in real time, use FlyParens.

You probably know how to undo in Emacs, and how to bind the undo command to C-z without enabling CUA mode, if you don’t want to use CUA mode for some reason.

## 11. The “red tape” phase

Spend some time trying editing Lisp code in the first phase. If editing Lisp code does not feel cumbersome then, or if it feels only as cumbersome as editing code in other languages, then there is probably no need for you to go to the second phase, and no need to use anything like paredit. But if you are not satisfied with the first phase, or if maintaining balanced parentheses still feels like a chore, then it’s time to move to the second phase, the “red tape” phase.

The first rule of the second phase is this: you will type parens only in pairs (except in comments and strings). In other words, every time you type an open paren, the next action should be to type a close paren, and every time you type a close paren, the previous action should have been typing of an open paren. Typing of () should be considered an atomic operation from now on, in other words, you never do something like typing just an open paren and then doing something other than typing the corresponding close paren.

By following this rule, you never introduce mismatched paren in the first place. But how does one type (foo) without violating the rule? You first type () and then type foo between the two parens.

Exercise 60. Configure your text editor so that there is a convenient keyboard shortcut for typing () (and then placing the text cursor between the two parens).

Emacs note: M-( runs the command insert-parentheses which types ().

How would you type

(let (a b c) (foo))


Let’s make that more interesting. How would you write the following?

(let (a
b
c)
(foo)
(bar))


One way of writing that is to first write the following (which you now know how to write without violating the rule):

(let)


and then write (a b c) to get:

(let (a b c))


and then

(let (a b c)
())


and then

(let (a b c)
(foo))


and so on. (Recall that you already know how to break (a b c) into multiple lines.)

Another way is to first write:

(foo)
(bar)


and then wrap that with a let form, but how do you do that? If you cannot find a command for that, you can simply cut the two expressions (foo) (bar) into clipboard and then write the following

(let (a b c))


and then break the line to get:

(let (a b c)
)


and then paste back (foo) (bar) so you get:

(let (a b c)
(foo)
(bar))


Exercise 70. Try both ways.

Second rule is that you don’t do anything that results in mismatched parens. For example, deleting or commenting out the second-to-last line in the following code is not allowed, but deleting just the expression (print "world") is OK.

(defun my-hi ()
(dotimes (_ 2)
(print "hello")
(print "world"))
(print "the end"))


What are some of allowed operations then? Here are some, which I will call “basic operations” from now on:

1. well formed cut – cutting one or more expressions to the clipboard (As mentioned in the previous article, by “expression”, I mean symbolic expression)
2. well formed copy
3. well formed paste – pasting expressions from clipboard (and then indenting correctly)
4. well formed commenting – commenting out one or more expressions
5. well formed delete
6. joining or splitting lines (and then indenting correctly)
7. typing ()
8. typing something that does not contain any parens or newlines (except within strings and comments)
9. opening a blank line or removing one

Notice that the wrapping operation (wrapping with a let form) was done by a well formed cut (of two expressions (foo) (bar)), and then some other basic operations, and then a well formed paste. In fact, notice that the previous exercise was done using only basic operations.

To do well formed cut (or well formed copy) easily, you need to know a convenient way to select expressions. For example, how do you select the bar form and the moo form together in the following code in your text editor?

(+ (foo)
(bar a
(b c d))
(moo a
(b (c))))


The answer of course is to select from the start of the bar form to the end of the moo form, but where exactly (within those close parens) is the end of the moo form? If your text editor has some features for helping you see which close paren matches which open paren, then you can use those features to pinpoint the ending close paren for the moo form. Your editor should also have separate features or plugins for easy selection of expressions. Find them.

Emacs note: In vanilla Emacs, this is how you would select the bar form and the moo form: move point to anywhere within the bar form, and press C-M-u as many times as necessary (to get to the starting position of the bar form), and then press C-M-SPC as many times as necessary (twice in this case). This is generally how you select one or more expressions.

Notice that the basic operations work on the level of expressions, not on the level of letters, words or lines. Think of each basic operation as an atomic operation. In particular, if you are in the middle of doing some well formed cut and the phone rings, you complete the operation before answering the phone.

You can edit Lisp code using only basic operations, as we’ll see in next sections. The idea of the red tape phase is like the lesson of Vim: “In Vim, the trick is you work mainly with text objects (words, lines, sentences, code blocks, etc), not with letters.” In Lisp editing, the trick is you work with expressions (sexps), not with lines or letters.

Note: in some cases, you might need some kind of clipboard manager (either as a feature within your text editor, or as an external program) if you need use more than one clipboard. These cases will happen.

You should get to know the text cursor movement commands based on expressions (rather than on lines or letters) in your text editor, such as “move the cursor forward passing one expression”, “move up one nesting level.” and so on, because they will come in handy later and because they might be used for selecting expressions.

Emacs note: In vanilla Emacs,

• the command forward-sexp, for moving past one expression, is bound to <C-M-right> and C-M-f
• backward-sexp is bound to <C-M-left> and C-M-b
• backward-up-list, for moving up one level, is bound to <C-M-up> and C-M-u
• down-list, for moving down one level, is bound to <C-M-down> and C-M-d

## 12. How would Eve write it

Suppose Eve wrote the following elisp code, which can look highly nested and complicated to beginners.

(defun my-preview-config ()
(when (<= 900 (x-display-pixel-height))
(setq preview-scale-function 1.5)
(when (eq system-type 'windows-nt)
(let ((winversion
(when (string-match (rx "nt"
(group (+ digit))
"."
(group (+ digit))
"."
(+ digit)
eos)
system-configuration)
(list
(string-to-number (match-string 1 system-configuration))
(string-to-number (match-string 2 system-configuration))))))
(when (version-list-<= '(6 2) winversion)
(setq preview-scale-function 'preview-scale-from-face))))))


How would have Eve wrote that code, using only basic operations? The answer lies in, how do you draw a face? You don’t normally draw a face from left to right like you would with writing a sentence. You draw from outside to inside, that is, from big picture to small detail. First, you draw an outline of a face, like so.

.
.
.
.          |   |    |    |     |   |
.          |   |    |    |     |   |
.       +--+---+----+----+-----+---+----+
.       |                               |
.       |                               |
.       |                               |
.       |                               |
.       |                               |
.       |                               |
.       |                               |
.       |                               |
.       |                               |
.       |                               |
.       |                               |
.       |                               |
.       +-------------------------------+
.


And then you draw outlines for eyes, nose, mouth:

.
.
.
.          |   |    |    |     |   |
.          |   |    |    |     |   |
.       +--+---+----+----+-----+---+----+
.       |                               |
.       |    ------        ------\      |
.       |   |      \      /       |     |
.       |   \      |      |       /     |
.       |    -----/        \------      |
.       |                               |
.       |           |      +            |
.       |           +------+            |
.       |                               |
.       |         +------------/        |
.       |         |           /         |
.       |         +-----------          |
.       +-------------------------------+
.


And then maybe you draw some teeth inside the mouth, and fill more details for eyes, and so on. So the big structure is drawn first, and then smaller structures nested inside it, and then even smaller structures inside them.

Eve did not write her code in textual order. In particular, the bunch of close parens at the end are not what Eve wrote last (if she did, she would be violating the rules of the red tape phase). Rather, she drew her code in big-to-small order (that is, outer-to-inner order). Before explaining how exactly she did it, let me explain what the code does: the code defines a function named my-preview-config that does the following (when called):

1. If the screen height is bigger than or equal to 900, set the variable preview-scale-function to the number 1.5.
2. But if the system is Windows 8+ in addition, set the variable preview-scale-function to the symbol preview-scale-from-face.

This is how she would write the code. She first write this (which you know is possible using only basic operations):

(defun my-preview-config ()
)


That is like drawing just the outline of a face. Next, she edit further to get:

(defun my-preview-config ()
(when --BIG-HEIGHT--
--BLAH--))


She’s using place-holders like --BLAH-IN-CAPITAL-LETTERS-- to indicate parts not yet written, i.e., parts to be written later. Next, she searches through the elisp reference to find what function to call to get screen height. She learns that it’s x-display-pixel-height, so she edit further to get:

(defun my-preview-config ()
(when (<= 900 (x-display-pixel-height))
--BLAH--))


Next, she replaces --BLAH-- to get:

(defun my-preview-config ()
(when (<= 900 (x-display-pixel-height))
(setq preview-scale-function 1.5)
(when (eq system-type 'windows-nt)
--)))


The expression (eq system-type 'windows-nt) checks whether the system is MS Windows. Next, she searches the internet for how to check for MS Windows version in elisp. It turns out that she has to extract some internal version number from the variable system-configuration (which is a string) using some regular expression, and then if the extracted internal version number is something like 6.2, then the system is Windows 8. She is like “writing that logic is going to take more time than I expected”. But she is not worrying. She writes the big picture of the logic, like so:

(defun my-preview-config ()
(when (<= 900 (x-display-pixel-height))
(setq preview-scale-function 1.5)
(when (eq system-type 'windows-nt)
(let ((winversion
--EXTRACT-WINVERSION--))
(when (--BIGGER-THAN-OR-EQUEL-TO-6.2-- winversion)
(setq preview-scale-function 'preview-scale-from-face))))))


The new part in above code should be read as: “Extract the internal version number and stores it to the local variable winversion. Then compare the value of winversion to 6.2, and if winversion is bigger than or equal to 6.2, then do (setq preview-scale-function 'preview-scale-from-face)“. Notice that the placeholder --EXTRACT-WINVERSION-- is there because she hasn’t yet figured out how to extract the version number. And the placeholder --BIGGER-THAN-OR-EQUEL-TO-6.2-- is there because she does not know how to compare version numbers yet. Notice that she just wrote above code before figuring out how to extract and compare version numbers.

Next, she look through the elisp reference to find what function to call to compare version numbers. She learns that version numbers are normally represented as lists of integers (and not as floats), and that version-list-<= is the function she should use. So she replaces --BIGGER-THAN-OR-EQUEL-TO-6.2-- to get:

(defun my-preview-config ()
(when (<= 900 (x-display-pixel-height))
(setq preview-scale-function 1.5)
(when (eq system-type 'windows-nt)
(let ((winversion
--EXTRACT-WINVERSION--))
(when (version-list-<= '(6 2) winversion)
(setq preview-scale-function 'preview-scale-from-face))))))


Notice that she finished code for version comparison before finishing code for version extraction. There is no reason for you to always write expressions in chronological order.

Next, she opens a new elisp file. She writes code for extracting the version number by trial and error and testing things out and she does all that within the new elisp file. Finally, she arrives at the following code for extracting the version number:

(when (string-match (rx "nt"
(group (+ digit))
"."
(group (+ digit))
"."
(+ digit)
eos)
system-configuration)
(list
(string-to-number (match-string 1 system-configuration))
(string-to-number (match-string 2 system-configuration))))


Next, she copies above code and paste it into where the placeholder --EXTRACT-WINVERSION-- is. The final result:

(defun my-preview-config ()
(when (<= 900 (x-display-pixel-height))
(setq preview-scale-function 1.5)
(when (eq system-type 'windows-nt)
(let ((winversion
(when (string-match (rx "nt"
(group (+ digit))
"."
(group (+ digit))
"."
(+ digit)
eos)
system-configuration)
(list
(string-to-number (match-string 1 system-configuration))
(string-to-number (match-string 2 system-configuration))))))
(when (version-list-<= '(6 2) winversion)
(setq preview-scale-function 'preview-scale-from-face))))))


The way she wrote this function definition is mainly in the order of “from top level to bottom level”, but when she was figuring out the part for version extraction, she was probably building the expression in the order of “from bottom level to top level”. That is how Eve writes Lisp code: sometimes, top-down, other times, bottom-up.

Exercise 80. Repeat Eve’s workflow. Recall that Eve’s workflow involves basic operations only.

## 13. Preemptively breaking a line

Let’s say you have written this expression:

(+ a b (and (moo) (oink)) c)


Now suppose that you want to replace the moo form with a much more complicated moo form. Maybe you want to pass (+ 100 200) and (+ 300 400) as arguments to the moo form. But before doing that, you might want to break the one line expression into multiple lines first, so that you get:

(+ a
b
(and (moo)
(oink))
c)


Then you pass the arguments to the moo form, so that you get:

(+ a
b
(and (moo (+ 100 200)
(+ 300 400))
(oink))
c)


The lesson here is that sometimes, breaking a one-line expression into multiple lines before you write more into the expression can be easier than breaking the line afterward,

## 14. Wrapping

Suppose you are writing a function that prints the sum of the three arguments and then prints a list containing the sum twice. So you write the following code and just after you write (print (list )), you suddenly realize, “wait, I should have stored the sum in a local variable”:

(defun my-func (foo bar baz)
(print (+ foo
bar
moo))
(print (list )))


So you cut the expression (+ foo bar moo) into clipboard, and write num in place, and you get

(defun my-func (foo bar baz)
(print num)
(print (list )))


and then you finish writing the second print form, and you get:

(defun my-func (foo bar baz)
(print num)
(print (list num num)))


and then you wrap the two print forms with a let form, and you get:

(defun my-func (foo bar baz)
(let ((num (+ foo
bar
moo)))
(print num)
(print (list num num))))


Notice that going from our first code to this final code requires only basic operations, and that you have to use at least two clipboards (one for storing (+ foo bar moo) and another for storing the two print forms).

This kind of wrapping can be done more easily (and without requiring use of two clipboards) if your text editor has a command for what I will call the simple wrap operation. The simple wrap operation is wrapping one or more expressions with two parens and then indenting correctly. For example, when you have this code:

(defun my-func (foo bar baz)
(print num)
(print (list num num)))


and then you edit further to get:

(defun my-func (foo bar baz)
let ((num --))
(print num)
(print (list num num)))


and then when you perform the simple wrap operation to the four expressions let ((num --)) ... (print (list ..)), you get:

(defun my-func (foo bar baz)
(let ((num --))
(print num)
(print (list num num))))


and then you can paste back (+ foo bar moo) to get:

(defun my-func (foo bar baz)
(let ((num (+ foo
bar
moo)))
(print num)
(print (list num num))))


Alternatively, you could have pasted it back before doing the simple wrap. A matter of preference.

Emacs Note: In vanilla Emacs, the simple wrap operation corresponds to selecting one or more expressions and then pressing M-( C-M-\ and that is because M-( runs the command insert-parentheses which is dwim.

If your text editor has a command for what I will call “forward slurp” then you can use that instead too. To demonstrate what it is, suppose again you have this code:

(defun my-func (foo bar baz)
(print num)
(print (list num num)))


and then you edit further to get:

(defun my-func (foo bar baz)
(let ((num --)))
(print num)
(print (list num num)))


and then you call “forward slurp” command to cause the let form to slurp the print forms in, like this:

(defun my-func (foo bar baz)
(let ((num --))
(print num)
(print (list num num))))


Emacs Note: Vanilla Emacs does not provide such a command. Paredit mode provides one. Paredit users should try M-x apropos-command RET paredit slurp to find it.

In your text editor, find a command or a plugin that provides “simple wrap” or “forward slurp”. We add these operations to our list of basic operations.

If you can’t find such commands, use the code templates feature to make them.

In case you are curious, the reverse of “forward slurp” is “forward barf” (according to paredit).

## 15. Unwrapping

To change this code:

(defun my-func (foo bar baz)
(let ((num --))
(print num)
(print (list num num))))


into this:

(defun my-func (foo bar baz)
(print num)
(print (list num num)))


you can follow these steps: select the two print forms, then cut, then select the let form, then paste, then reindent.

Emacs note: I don’t know if vanilla Emacs provides commands for unwrapping, but paredit mode again provides one: the paredit-splice-sexp-killing-backward command which is bound to <M-up>.

Emacs note: To make pasting over selection work as expected, enable delete-selection-mode, if you don’t want to enable cua-mode for some reason.

## 16. Inserting in the middle

Suppose we have this code.

(moo (oink 2
(cow x))
(oink 2
(cow x)))


Suppose you decide you want to insert another argument to the moo form, between the two oink forms. In particular, let’s say you want to change above code to this code:

(moo (oink 2
(cow x))
(let ((x 1) (y 1))
(+ x y))
(oink 2
(cow x)))


Here is a way of doing that. First, change the original code to the following code (by opening a blank line in the right place and then inserting () on that blank line):

(moo (oink 2
(cow x))
()
(oink 2
(cow x)))


and then, to this:

(moo (oink 2
(cow x))
(let ())
(oink 2
(cow x)))


and so on.

That is how you insert an argument as a middle argument (as opposed to the first or last argument) of a form.

Exercise 90. Insert the expression (+ 50000 60000) into the right place in the following code:

(setq blah (list (+ 10000
20000)
(+ 30000
40000)
(+ 70000
80000)))


## 17. Appending

Suppose we have this:

(defun my-blah (x)
(foo (la (la 1 x))
(bar (moo 123
(oink 2
(cow x)))))
(la 1))


Notice that the moo form is given two arguments: 123 and the oink form.

Now suppose you want to insert (let) as the last argument to the moo form. How would you do that?

One way of doing it is to first break the second-to-last line at the right place to get:

(defun my-blah (x)
(foo (la (la 1 x))
(bar (moo 123
(oink 2
(cow x))
)))
(la 1))


and to do that, you either

• use the “show me which open paren matches this close paren” feature of your text editor to place the text cursor at the right place before breaking the line, or
• place the text cursor at the start of the oink form, and then invoke the command for “move past one expression” to move past the oink form, then break the line.

After breaking the line, it should be easy to insert (let) to get:

(defun my-blah (x)
(foo (la (la 1 x))
(bar (moo 123
(oink 2
(cow x))
(let))))
(la 1))


Another way is to first get:

(defun my-blah (x)
(foo (la (la 1 x))
(bar (moo 123
(oink 2
(cow x)))))
(let)
(la 1))


and then repeat “forward slurp” at right places until (let) ends up at the right place.

Emacs note: If you use paredit, you just move point to any whitespace before (cow x) and then invoke paredit-forward-slurp-sexp repeatedly until (let) is at the right place.

Emacs note: Yet another way is to use M-) which is bound to move-past-close-and-reindent in vanilla Emacs. If the point is somewhere inside (cow x), which would be the case if the cow form was the last thing you wrote, then you can just press M-) multiple times until point is at the right level, and then you write (let).

After that, you can fill details of the let form if you want. So suppose you have done that and you now have this code:

(defun my-blah (x)
(foo (la (la 1 x))
(bar (moo 123
(oink 2
(cow x))
(let ((z 1))
(+ x z)))))
(la 1))


Now suppose you want to delete the let form now for some reason. If you delete it, then you get something like:

(defun my-blah (x)
(foo (la (la 1 x))
(bar (moo 123
(oink 2
(cow x))
)))
(la 1))


and then you can join lines to get back to the original code, if you want.

Now you know how to append something to a form, and how to do the reverse.

Exercise 100. Suppose you have this code:

(defun my-search-foo ()
(catch 'loop
(let ((i 0))
(while (< i 10)
(let ((j 0))
(while (< j 10)
(if (foo i j)
(throw 'loop (list i j)))))))))


Insert two cl-incf forms at right places to get this code:

(defun my-search-foo ()
(catch 'loop
(let ((i 0))
(while (< i 10)
(let ((j 0))
(while (< j 10)
(if (foo i j)
(throw 'loop (list i j)))
(cl-incf j)))
(cl-incf i)))))


(Above is taken from this gif)

## 18. Prepending

There is a useful operation that I call “move rectangle down”. I will show you what it is, using JavaScript example.

Suppose you have the following JavaScript code and that the text cursor is between var and height:

var height, // blah
width,  // blah lorem
size;   // blah lorem
console.log("hello");


When you perform the “move rectangle down” operation, you get the following code and it leaves the text cursor at the end of var:

var
height, // blah
width,  // blah lorem
size;   // blah lorem
console.log("hello");


Because the text cursor is at the end of var, you can then just start typing something so that you get, for example:

var speed,  // blah
height, // blah
width,  // blah lorem
size;   // blah lorem
console.log("hello");


Find the command for “move rectangle down” in your text editor. If you can’t find it, it is easy to make that command, because the operation is simply “type newline and then type spaces as many as the length of the previous line and then move to the end of the previous line.”

Emacs note: It’s the command split-line which is normally bound to C-M-o.

This operation is different from what we discussed in the “breaking lines” section, but nevertheless the reverse of this operation is the thing we discussed in the “joining lines” section.

Exercise 110. With help of the “move rectangle down” operation, change this JavaScript code3:

var myString =
["Monday.",
"Bus day.",
"Happy birthday."
].join('\n');


to this code4:

var myString =
["What day.",
"Monday.",
"Bus day.",
"Happy birthday."
].join('\n');


You can also use this operation to prepend something to a form, that is, insert something as the first argument to a form.

Exercise 120. Suppose you have this code:

(setq blah (list (+ 30000
40000)
(+ 50000
60000)))


Insert (+ 10000 20000) and (+ 70000 80000) at right places to get this code:

(setq blah (list (+ 10000
20000)
(+ 30000
40000)
(+ 50000
60000)
(+ 70000
80000)))


Exercise 130. Now do the reverse.

Actually, there is another way of prepending something to a form. When you have this:

(setq blah (list (+ 30000
40000)
(+ 50000
60000)))


You could type () at the start of the first argument, to get:

(setq blah (list ()(+ 30000
40000)
(+ 50000
60000)))


and then break the line to get:

(setq blah (list ()
(+ 30000
40000)
(+ 50000
60000)))


and then fill details of the new first argument.

Exercise 140. (Fizz buzz) Write a program (in Common Lisp or Emacs Lisp) that prints the numbers from 0 to 99. But for multiples of 3, print “Fizz” instead of the number and for the multiples of 5, print “Buzz”. For numbers which are multiples of both 3 and 5, print “FizzBuzz”. Write that program by inserting appropriate clauses to the cond form in the following unfinished code:

(dotimes (i 100)
(cond ((zerop (mod i 3))
(print "Fizz"))
((zerop (mod i 5))
(print "Buzz"))))


Exercise 150: Change this code

(setq blah (list (+ 10000
20000)
(+ 30000
40000)
(+ 50000
60000)
(+ 70000
80000)))


to this code:

(setq blah (list
(+ 10000
20000)
(+ 30000
40000)
(+ 50000
60000)
(+ 70000
80000)
))


Exercise 160: Now do the reverse.

(Hint: the previous two exercises just reduce to breaking or joining some lines and then reindenting. For reindenting, you might want to select the list form and then invoke the command for reindenting the selected expression, rather than fixing indent line by line.)

Emacs note: this is where C-M-u comes in handy. In vanilla Emacs, C-M-h runs the command mark-defun which selects the top level form. Also, if you use paredit, you can use the command paredit-reindent-defun which is bound to M-q to reindent the top level form.

## 19. Automate

Welcome to the final phase: the automation phase. In this phase, you just automate things as much as you feel necessary. Here are some ideas you can take if you like:

• Configure your editor so that correct indentation is done every time you paste something.
• Configure so that a close paren is automatically inserted every time you insert an open paren.
• Make each basic operation into a command.
• Make some often used sequence of basic operations into a command.
• Code templates

Emacs note: paredit takes care of some of above ideas.

Google Common Lisp Style Guide gives you some idea on how you would write and format Lisp code, some of which you might apply to other dialects of Lisp too. There is probably no need to follow everything in that guide.

### 20.1. Further reading for Emacs users

This post is part of the Living with Emacs Lisp series, and the next thing you should read in this series is probably something about “how to debug init code”, which I will write soon.

If you are interested in writing Common Lisp within Emacs, start with my SLIME starting guide.

## 21. Dancing chickens

Domino’s Techno Chicken:

Admit it, you want to watch that again even though you have already watched it years ago.

## Footnotes:

1

which is similar to what Terence Tao called the three phases of math education, which in turn is similar to Douglas Adams three phases of civilization

2

There are two places between them. You’ll see if you use the bar-shaped text cursor instead of the box-shaped one.

4

This list of strings is actually a conversation that can happen between an English person and a Korean person, each of them knowing only one language.

## It is not hard to read Lisp code

It is natural for someone who sees Lisp code for the first time to have the impression that Lisp might have poor readability. On the other hand, you know there are people who have been reading and writing Lisp code fine. With this post, I hope I can convince you that you can read Lisp code with ease. The context of this post is that this post is a module of Living with Emacs Lisp series, intended for beginning users of Emacs.

Most of this post is about how to read Lisp code in general, and then there is one section about how to read Emacs Lisp in particular.

## 1. Intro

Alice: “How can you read Lisp code written by others? How do you do that?”
Bob: “You can see the nesting structure from how the code is indented. “
Alice: “Yes, I heard that Lisp programmers don’t actually count parens (a.k.a parentheses) but still how do you read from indentation? “
Bob: “Look at it this way. To me, Lisp code looks like an expanded tree view. You look at the vertical alignment here and there to see the structure of the code. Give me some Lisp code and let’s see.”
Alice: “OK. Here is some Emacs Lisp code I got from someone long time ago. I’m going to indent this now.”1

(when (eq system-type 'windows-nt)
(defvar my-gs-exe-list
(list "C:/Program Files/gs/gs9.14/bin/gswin32c.exe"
"c:/Program Files/gs/gs9.10/bin/GSWIN64C.EXE"
"C:/Program Files/gs/gs9.06/bin/GSWIN32C.EXE"))
(dolist (exe my-gs-exe-list)
(if (file-exists-p exe)
(setq preview-gs-command exe)))
;; (setq preview-image-type 'pnm)
)


Bob: “I don’t use Emacs, but I’m curious, how do you indent in your text editor?”
Alice: “In Emacs? I select the text and then I press C-M-\ (indent-region). Done. Discoverable through the menu interface too.”

(when (eq system-type 'windows-nt)
(defvar my-gs-exe-list
(list "C:/Program Files/gs/gs9.14/bin/gswin32c.exe"
"c:/Program Files/gs/gs9.10/bin/GSWIN64C.EXE"
"C:/Program Files/gs/gs9.06/bin/GSWIN32C.EXE"))
(dolist (exe my-gs-exe-list)
(if (file-exists-p exe)
(setq preview-gs-command exe)))
;; (setq preview-image-type 'pnm)
)


Bob: “There you see. You can see the nested structure now. Do you see it?”

## 2. Tree view

Let’s take an example from the Wikipedia article on tree view:

• Smiles
• Happy
• Neither
• Vehicles
• Parts
• Wheel
• Whole
• Truck
• Car

You can see the nesting structure from how much each item is indented. Same is true with Lisp code:

(smiles
happy
neither)
(vehicles
(parts
wheel)
(whole
truck
car))


Notice how the lines (smiles and (vehicles have zero indent (hence the same level: the top level), and how the three lines happy, sad, neither) share the same one level deep indent.

## 3. Terminology

Before moving on to more examples, let’s establish some terminology.

I’ll assume you are familiar with the term “statement” and “expression” in other programming languages. Recall that expressions can contain other expressions in them. In some languages, statements always return some value, making the distinction between statements and expressions void. Lisp is one of such, and when you see something in Lisp code and you think “this looks like a block” or “this looks like a statement”, you can actually simply assume that what you are seeing is just an expression (albeit playing the role of “block” or “statement” in some sense). Put simple, you have expressions. The Lisp term is symbolic expressions, they are also called s-expressions, or just expressions. Sometimes they are called s-exps or sexps.

For example, take this code again:

(when (eq system-type 'windows-nt)
(defvar my-gs-exe-list
(list "C:/Program Files/gs/gs9.14/bin/gswin32c.exe"
"c:/Program Files/gs/gs9.10/bin/GSWIN64C.EXE"
"C:/Program Files/gs/gs9.06/bin/GSWIN32C.EXE"))
(dolist (exe my-gs-exe-list)
(if (file-exists-p exe)
(setq preview-gs-command exe)))
;; (setq preview-image-type 'pnm)
)


That code contains lots of expressions. That entire code can be considered one big expression (when ....), which we usually call a when form. The first line contains some short expression, namely, (eq system-type 'windows-nt). We say that this expression is an eq form.

The lines 2 to 5 contain an expression which is a defvar form. The lines 3 to 5 contains an expression which is a list form.

Also, when itself is an expression. You can actually verify that because when you enter when alone to the Lisp interpreter, it won’t say “Syntax error! That’s not a valid expression!” (but it will say something like “you did not define that variable!”.)

You can check that the following is an expression too:

'windows-nt


which contains the following smaller expression

windows-nt


The following is an expression too.

"C:/Program Files/gs/gs9.14/bin/gswin32c.exe"


This is not an expression:

"C:/Program


Neither this:

(+ 1 1


Nor this:

(+ 1 1))


But it does contain an expression, namely:

(+ 1 1)


which in turn contains smaller expressions like

+


and

1


So we learned:

• what (symbolic) expressions are
• usage of the phrase “blah form”
• how to check if something is an expression, when not sure

.

### 3.1. Emacs Lisp note

If you an Emacs user and want to know whether something in Emacs Lisp code is an expression, you enter that something into the buffer created by:

M-x ielm


Try entering each of the non-examples in this section and see what happens.

### 3.2. Common Lisp note

If you are an Emacs user and want to access the Common Lisp interpreter via Emacs, you might want to look into any of the SLIME starting guides or this guide in particular.

If you are using other editors, you probably can get help from that editor’s community.

Recall that the interpreter can be accessed from command line even before you set up integration with your editor.

## 4. Variations

Sometimes this code (two big expressions):

(smiles
happy
neither)
(vehicles
(parts
wheel)
(whole
truck
car))


is alternatively written as:

(smiles happy
neither)
(vehicles (parts wheel)
(whole truck
car))


That way is more vertically squeezed, and horizontally spread out. You’ll also encounter code that is differently squeezed like:

(smiles happy sad neither)
(vehicles
(parts wheel)
(whole truck car))


So I have shown three different styles. The issue of which style to use in which case is a matter I will not go into, For now, just notice that each style is readable to you. In each of the three cases, you can see the nesting structure easily from indentation alone.

## 5. How to find where the expression ends.

Some code taken from the dash.el library:

(defmacro --split-with (pred list)
"Anaphoric form of -split-with'."
(declare (debug (form form)))
(let ((l (make-symbol "list")) ;; <-- the outermost let form starts here
(r (make-symbol "result"))
(c (make-symbol "continue")))
(let ((,l ,list)
(,r nil)
(,c t))
(while (and ,l ,c)
(let ((it (car ,l))) ;; <-- the innermost let form starts here
(if (not ,pred)
(setq ,c nil)
(!cons it ,r)
(!cdr ,l))))
(list (nreverse ,r) ,l))))

(defun -split-with (pred list)
"Returns a list of ((-take-while PRED LIST) (-drop-while PRED LIST)), in no more than one pass through the list."
(--split-with (funcall pred it) list))


Quiz: That code has three let forms in it. The third let form (the innermost one) spans how many lines?

There is a way to figure that out. The four lines following the beginning line of the let form are indented deeper than the beginning line, so you conclude that these four lines belong to the let form. So we conclude that the let form occupies 5 lines (including the beginning line).

Now, how many lines does the first let form (the outermost one) occupy?

In general, the algorithm to figure that out is like this:

1. Set D to the indent depth of the beginning line (of the form you are interested)
3. Go to the next non-blank line. (If none, exit the algorithm)
4. If the indent depth of the current line is bigger than D, paint this line red and go to Step 3. If not, exit the algorithm.

Lines that are painted red by this algorithm are the lines that the form occupies.

Run this algorithm to conclude that the first let form occupies 13 lines (excluding blank lines).

Actually, this algorithm is buggy because of two corner cases. I’ll demonstrate both with another part of code from dash.el:

(defun dash--table-carry (lists restore-lists &optional re)
"Helper for -table' and -table-flat'.

If a list overflows, carry to the right and reset the list.

Return how many lists were re-seted."
(while (and (not (car lists))
(not (equal lists '(nil))))
(setcar lists (car restore-lists))
(!cdr lists)
(!cdr restore-lists)
(when re
(push (nreverse (car re)) (cadr re))
(setcar re nil)
(!cdr re))))


That is a defun form and defines the function dash--table-carry. The algorithm would give you the wrong conclusion that the defun form spans just two lines. Just below the first line, there’s the docstring consisting of 5 lines, including blank lines. This docstring is part of the defun form. I’m sure you can figure out how to modify the algorithm to take care of this corner case.

This defun form contains an and form. The and form occupies only two lines, but the algorithm would tell you otherwise (notice that the and form starts in the middle of the beginning line). You can figure out how to modify the algorithm to take care of this corner case as well.

## 6. Some difference from Python

There is some slight difference in the way Lisp code is indented and the way other languages code is indented. I will demonstrate with comparison to Python.

The following Python code is taken from Python documentation:

if x < 0:
x = 0
print('Negative changed to zero')
elif x == 0:
print('Zero')
elif x == 1:
print('Single')
else:
print('More')


The keyword elif is short for “else if” and now you see what that code is doing. Notice that the lines containing the keyword elif or else are indented to the same level as the line containing the if keyword, namely, zero level.

The equivalent Lisp code is this:

(cond ((< x 0)
(setq x 0)
(print "Negative changed to zero."))
((= x 0)
(print "Zero."))
((= x 1)
(print "Single"))
(t
(print "More")))


Notice that the lines ((= x 0) and ((= x 1) (these are lines that start the elif clauses) and the line (t are not indented to the same level as the beginning line of the cond form. This somewhat contrasts with Python. But then notice that those lines nevertheless are indented to the same level as the ((< x 0) part.

Anyway, run our (modified) algorithm to that Lisp code to verify the following questions and answers:

• How many lines does the cond form occupy? All the lines.
• How many lines is the first elif clause in our Lisp code? Two lines.
• How many lines is the if clause? Three lines.

That was a very simple cond form, so you don’t really feel the algorithm running in your head, because you can see structure almost instantly in this case. But when you encounter a much more complicated cond form, that is when you find yourself running the algorithm.

Back to Python. Suppose you are reading some Python code that contains some if..elif..else.. which in turn contains another if..elif..else.., in other words, you are reading nested conditional statements. Suppose then that you see an else clause. How do you figure out whether this else clause belongs to the outer conditional or the inner conditional? You can figure that out by looking at how much the else keyword is indented and see whether it is indented to the same level as the if keyword in the outer conditional or as that in the inner conditional.

On the other hand, when you have a cond form within a cond form and you see an else clause, how do you figure out whether it belongs to the outer cond form or the inner cond form? You already know how to figure out the lines occupied by the inner cond form.

Speaking of else clauses, I like how Python allows else clauses even for for loops, such as in the following code (also taken from the documentation):

for n in range(2, 10):
for x in range(2, n):
if n % x == 0:
print(n, 'equals', x, '*', n//x)
break
else:
# loop fell through without finding a factor
print(n, 'is a prime number')


output:

2 is a prime number
3 is a prime number
4 equals 2 * 2
5 is a prime number
6 equals 2 * 3
7 is a prime number
8 equals 2 * 4
9 equals 3 * 3


I like how the inner loop (and its else clause) captures the logic of “If 2 is a factor of n, do this, elif 3 is a factor of n, do this, elif 4 is a factor of n, do this, …., else do that.” Python can be bold like that. (To see an equivalent Lisp code, see Appendix).

## 7. Tools

Any editor good enough for Lisp is bound to provide features or tools for

• highlighting matching parentheses, and
• sexp-based movement commands

## 8. Logical operators being used for conditional statements roles

Sometimes you see C code which uses logical operators in place of conditional statements. This also happens in Lisp. Reading such code can seem hard at first, but did you know that this happens even in English?

“Eat that forbidden fruit and you will be screwed.”

There it is, the logical AND operator! You probably know that that is just another way of saying this conditional statement: “If you eat that fruit, you will be screwed.”

This code is taken from the definition of the Emacs Lisp function browse-url-of-buffer:

(and buffer (set-buffer buffer))


That is an and form and the meaning of that code is simple: if buffer, then do (set-buffer buffer). That is:

(if buffer
(set-buffer buffer))


This is a long campaign slogan: “If you vote for our party, we’ll make square mouse holes. If you don’t, life will be tough.”

The campaign staff decides to shorten the slogan using logical operators: “Vote for us and we’ll make square mouse holes. Or life will be tough.” The shortened slogan is still readable. You will be able to read shortened conditional statements in Lisp code too.

## 9. Prefix arithmetic

Here is the C exrpession for “one plus two”:

1 + 2


Here is the Lisp expression for “one plus two” (maybe more natural to read the following as “sum of one and two”):

(+ 1 2)


It is definitely true that infix arithmetics (in C, Python, …) reads better than prefix arithmetics (in Lisp), when you have a very complicated math formula, deeply nested. Fortunately, encountering a complicated math expression in code is a rare occurrence, more so for beginners.

Here is some complicated (at least to beginners) example taken from the color.el library:

(sqrt (+ (expt (/ ΔL′ (* Sl kL)) 2.0)
(expt (/ ΔC′ (* Sc kC)) 2.0)
(expt (/ ΔH′ (* Sh kH)) 2.0)
(* Rt (/ ΔC′ (* Sc kC)) (/ ΔH′ (* Sh kH)))))


That is a kind of expression you won’t encounter often. Arithmetics you do encounter often in code is mostly just:

• increasing the loop counter, or
• adding up lengths of things

and they are simple and you will get used to them.

## 10. How to find arguments of a form

Simple case first. We have a lalala form and it has three arguments:

(lalala mamama
papapapa
nanana)


Notice that mamama, papapapa, nanana are aligned along to the left.

Another lalala form:

(lalala mamama
(if foo
aaa
bbb)
nanana)


It has three arguments but this time the second argument is an if form. Notice that the three arguments are still aligned along to the left in some sense, that is, the following three are on the same column:

• the first letter of mamama
• the first letter of the if form
• the first letter of nanana

That observation is usually how you can spot the starting positions of arguments of some very long multi-line form (longer than our example.).

Let’s see some variations. For example:

(lalala mamama1 mamama2
a b c d e
(if foo
aaa
bbb)
nanana1 nanana2)


That lalala form has these arguments: mamama1, mamama2, a, b, c, d, e, and then an if form, and then nanana1 and nanana2. Still nicely aligned. Readable.

What about that if form? Is that aligned good?

A simple if form:

(if (bed-net-exists-p)
(use-bed-net)
(bring-a-fan)
(turn-on-the-fan))


(Mosquitoes are in your room and you want to sleep. The code says “If there is a bed net, use it, else, bring a fan and turn on the fan (with wind blowing toward you. It’s a trick to make sure that little vampire helicopters can’t land on you)”)

The reason why the else clause (two lines) is indented less than the then clause (that is, (use-bed-net)), at least for Emacs Lisp code, is that it’s good to be able to visually distinguish the else clause and the then clause. The text editor usually remembers this by saying “The first two arguments of an if form shall be treated special (specially indented) and unlike the rest of the arguments”. The first two arguments of our if form are (bed-net-exists-p) and (use-bed-net).

The let forms are like this too. The text editor will treat the first argument of a let form specially. This let form:

(let ((a 1) (b 1))
(message "hello")
(message "%d" (+ a b)))


can be alternatively written as:

(let
((a 1) (b 1))
(message "hello")
(message "%d" (+ a b)))


Notice how the first argument (in the alternatively written one) is indented deeper than the rest of the arguments (two arguments).

If this were written using more lines like this:

(let
((a 1)
(b 1))
(message
"hello")
(message "%d"
(+ a b)))


you can still spot the starting positions of the three arguments. You see the distinguished argument (the first argument) with its starting position being deep, and then you see the two non-distinguished arguments with their starting positions vertically aligned nevertheless. This observation will help you spot the arguments in more complicated let forms.

If you are curious, in general with other forms, there are just two cases:

• It has no distinguished arguments and all arguments are aligned to the same level (if they are all on different lines), or
• The first N arguments are distinguished and they are aligned to a common level, say D1, and the rest of the arguments are aligned to a separate common level, say D2, and D1 is deeper than D2.

Some quick exercises (answers in footnotes). Without counting parens and only looking at indentation, figure out how many non-distinguished arguments the following let form has2:

(let ((x (- 2
1))
(y 100)
(z (+ 1
1)))
(lalala (or z
x)
y)
(moo x y)
(foo x
y
z))


By the way, did you see that the three expressions within the first argument are aligned as well?

Without counting parens, figure out how many lines the non-distinguished arguments of the following if form occupies, and figure out how many lines the then clause occupies3:

(if (bed-net-exists-p)
(progn
(install-bed-net)
(get-inside)
(go-to-sleep))
(bring-a-fan)
(turn-on-the-fan)
(go-to-sleep))


Without counting parens, figure out how many non-distinguished arguments are in the following if form and how many lines they span, and also figure out how many “statements” are in the then clause.4

(if (progn blah
(progn blah
blah))
(progn
(blah (+ blah
blah))
(blah)
(blah (+ blah
blah)
blah))
(blah blah
blah)
(blah (+ blah
blah)))


## 11. Too many close parens?

So when you are reading Lisp code, by now it should be clear that there is no reason to fixate your eyes on that )))...))) thing (those close parens (a.k.a. right parentheses)), unless you are working with Positive Lisp, a revolutionary new dialect of Lisp which always uses smileys instead of simple parens, designed to promote smile, positive thinking and cross-platform happiness in your workplace. Sample code:

(: defun blah (: a b c :)
(: blah :)                           ;-) comment
(: x y z :)                          ;-) comment
(: blah
(: foo bar :) :) :)


## 12. Names

Knowing some commonly used prefix and postfixes can help.

p is a postfix commonly used for function names which are predicates. Examples:

• numberp (“Is it a number”)
• zerop (“Is it zero”)
• string-or-null-p (“Is it string or null”)

def is a prefix used for functions that define things. Examples:

• defvar (for defining a variable)
• defun (for defining a function)
• defmacro (for defining a Lisp macro)

cl is a prefix used for functions and variables from the CL library for elisp.

• cl-mapcar
• cl-union

Asterisk is sometimes used as a postfix for variations of some functions (or macros). Examples:

• let* is a variation of let
• cl-letf* is a variation of cl-letf

f is a postfix for Lisp macros that support “places”. Examples:

• setf is a generalized version of setq
• letf (in Common Lisp) is a generalize version of let
• incf (in Common Lisp) (“inc” stands for “increment”)

.

### 12.1. Places?

Python code:

vec = [10, 20]
vec[0] = 7
vec[1] += 2
print(vec)

# output: [7, 22]



equivalent Emacs Lisp code:

(setq vec (vector 10 20))
(setf (elt vec 0) 7)
(cl-incf (elt vec 1) 2)
(print vec)

;; output: [7 22]



That Python code does not evaluate the expression vec[0] and likewise the Emacs Lisp code does not evaluate the expression (elt vec 0). Instead, what the code does is.. I think you can already see what it does. That’s what it means to support “places”.

## 13. How to read Emacs Lisp code

You probably know what

C-h f


and

C-h v


do in Emacs Lisp buffers.
(if you don’t know, check them out with C-h k)

Also see Emacs Symbol Notation which explains what all those mysterious characters are about.

Use the command find-library to read source code of a particular elisp library. Use the elisp-slime-nav package if you want quick access to definition of a function (at point), without having to press C-h f and then clicking on the link.

Use eldoc-mode (a minor mode) to display information about a function or a variable (at point), without having to manually press C-h f or C-h v

### 13.1. Variables name too long?

Use the command my-simplify-prefix in this link.

### 13.2. Deeply nested data

Sometimes you’ll see code that uses some deeply nested data (like a list of lists of lists) written in a somewhat compact way. For example:

(defface nobreak-space
'((((class color) (min-colors 88)) :inherit escape-glyph :underline t)
(((class color) (min-colors 8)) :background "magenta")
(t :inverse-video t))
"Face for displaying nobreak space."
:group 'basic-faces
:version "22.1")


Or this example:

(font-lock-add-keywords
nil
((,(rx "\$") (0 'my-dim t))
(,(rx "\\" (or "(" ")" "[" "]")) (0 'my-dim t)))
t)


You can use your editor’s sexp-based movement commands to get a feel for how the nested data is shaped, or you can use something like rainbow-delimiters (which is an Emacs package, but I have a feeling that other editors have similar things as well) to assign colors to parens to help you read, without having to manually invoke movement commands.

Furthermore, it is not hard to edit or write Lisp code. To see how, see the how to edit Lisp code article from the Living with Emacs Lisp series.

## 15. Appendix

The dynamic “if .. elif .. elif … else ..” in Emacs Lisp:

(cl-loop for n from 2 below 10
do
(cl-loop for x from 2 below n
do
(when (zerop (% n x))
(print (format "%d equals %d * %d" n x (/ n x)))
(cl-return))
finally
(print (format "%d is a prime number" n))))


output

"2 is a prime number"

"3 is a prime number"

"4 equals 2 * 2"

"5 is a prime number"

"6 equals 2 * 3"

"7 is a prime number"

"8 equals 2 * 4"

"9 equals 3 * 3"


## Footnotes:

1

In the old days, there was no pastebin and no github gist, and many blog engines did not preserve indents in comments.

2

it has three non-distinguished arguments.

3

The else clause occupies three lines. The then clause occupies three lines, if you exclude the beginning line of the progn form, or four lines, if you include it.

4

The else clause consists of two statements and they span four lines in total. The then clause consists of three statements.

## Checking Windows version with Emacs Lisp

elisp code example for programmatically checking the version of Microsoft Windows on which Emacs is running:

(when (eq system-type 'windows-nt)
(print "Hello, MS Windows.")
(let ((winversion
(when (string-match (rx "nt"
(group (+ digit))
"."
(group (+ digit))
"."
(+ digit)
eos)
system-configuration)
(list
(string-to-number (match-string 1 system-configuration))
(string-to-number (match-string 2 system-configuration))))))
(when (null winversion)
(warn "(8qzv4lwb) Strange, some unexpected form of system-configuration."))
(when (version-list-<= '(5 1) winversion)
(print "Hello, MS Windows XP or higher."))
(when (version-list-<= '(6 1) winversion)
(print "Hello, MS Windows 7+ or Windows Server 2008 R2+."))
(when (version-list-<= '(6 2) winversion)
(print "Hello, MS Windows 8+ or Windows Server 2012+."))))


If you want to enable something only for Windows XP and higher, you can replace the line:

(print "Hello, MS Windows XP or higher.")


You might also want to look into feature detection instead of checking the version of Windows.

• To see how the string-match, rx, match-string idiom works, visit the relevant link in Living with Emacs Lisp, if any.
• For checking other system stuff, visit: OS Environment (in the elisp manual).

## Small introduction to Hausdorff distance

The goal of this post is to introduce the notion of Hausdorff distance (a.k.a. Hausdorff metric) and give some sense of intuition and motivation for it and for how to work with it and some exercises.

Before we start, I need to mention something about my liberal use of the vague words like small, nearby, close. Recall the following two statements:

• A function $f: M \to N$ (from a metric space to another metric space) is continuous at $x$ if $d(f(x), f(y))$ is small whenever $d(x,y)$ is small.
• A function $f: M \to N$ is uniformly continuous if $d(f(x), f(y))$ is (uniformly) small whenever $d(x,y)$ is small.

Despite using the vague word small, the two statements do have precise meanings if you interpret them using epsilon delta arguments. So I am going to use those words liberally here and there, but of course some care must be taken, but as long as ambiguous statements (such as statements that might be begging the question “do you mean uniformly?”) are never used in theorems or proofs, things will be fine.

## 1. motivation and intuition

Recall this fact: Two sets $A$, $B$ are same if and only if the following two conditions holds:

• for each $a \in A$, there is $b \in B$ with $a = b$
• for each $b \in B$, there is $a \in A$ with $a = b$

Let $(M, d)$ be a metric space. In analogy to the above fact, we want to assign some topology (a pseudo-metric, in particular) to the collection of all non-empty subsets of $M$ such that two non-empty subsets $A$ and $B$ are close to each other (in that topology) if and only if there is a small number $\epsilon > 0$ such that the following two conditions holds:

• for each $a \in A$, there is $b \in B$ with $d(a, b) < \epsilon$
• for each $b \in B$, there is $a \in A$ with $d(a, b) < \epsilon$

The reason we are excluding the empty set is for minor convenience of not having to deal with cases involving $\sup \emptyset$ later. (It would be tedious if you had to divide into two cases $A = \emptyset$ and $A \ne \emptyset$ every time you had to prove something about this topology.)

Intuition for this topology is that when $A$ and $B$ are close to each other, while we may not demand that all $a \in A$ be in $B$ (and vice versa), we demand that for each $a \in A$, there be at least a nearby point $b$ that is in $B$. That is, given any point $a \in A$, we can perturb it a bit to make it a point in $B$. In other words, $A$ and $B$ look same if you look at $M$ with blurry vision.

## 2. coming up with the two definitions of the Hausdorff distance

Notice that the following four conditions are interchangeable, given two non-empty $A, B$:

• There is a small $\epsilon > 0$ such that for each $a \in A$ there is $b \in B$ with $d(a, b) < \epsilon$.
• There is a small $\epsilon > 0$ such that for each $a \in A$ there is $b \in B$ with $d(a, b) \le \epsilon$.
• $\inf \{ \epsilon > 0 : A \subset B^\epsilon\}$ is small, where $B^\epsilon := \{ x \in M : d(x, b) < \epsilon, \exists b \in B \}$.
• $\inf \{ \epsilon > 0 : A \subset B_\epsilon\}$ is small, where $B_\epsilon := \{ x \in M : d(x, b) \le \epsilon, \exists b \in B \}$.

Why would someone come up with the third and the fourth condition? If you want to define some pseudo-metric, then it is necessary for you to transition from “there is a small something such that ..” to “this quantity relating A and B is small.”, and since you have a kind of condition that it holding for some $\epsilon$ implies it holding for all $\epsilon' > \epsilon$, so it is natural for you to take the infimum of all such $\epsilon$ to implement that transition. On the other hand, there is another way to do that transition which we will get to soon, but for now let’s talk about this particular transition.

This observation that the four conditions are interchangeable motivates the following definition.

Given two non-empty subsets $A, B$ of $M$, define $d^1_H(A, B)$ to be the maximum of the following two quantities:

• $\inf \{ \epsilon > 0 : A \subset B_\epsilon\}$
• $\inf \{ \epsilon > 0 : B \subset A_\epsilon\}$

It is also equally natural to take the sum of those two quantities instead of taking the maximum, but let’s go with the maximum.

We don’t restrict to bounded subsets: for example, we might want to say that $\mathbb Z$ and $\mathbb Z + 0.01$ (as subsets of $\mathbb R$) are close to each other

Exercise. Prove that the alternative definition of $d^1_H$ using $A^\epsilon, B^\epsilon$ in place of $A_\epsilon, B_\epsilon$ is equivalent to our definition of $d^1_H$.

Now the other transition. Notice that the following conditions are interchangeable, given two non-empty subsets $A,B$.

• There is a small $\epsilon > 0$ such that for each $a \in A$ there is $b \in B$ with $d(a, b) < \epsilon$.
• There is a small $\epsilon > 0$ such that for each $a \in A$ we have $\inf_{b \in B} d(a, b) < \epsilon$.
• There is a small $\epsilon > 0$ such that $\sup_{a \in A}\inf_{b \in B} d(a, b) < \epsilon$.
• $\sup_{a \in A}\inf_{b \in B} d(a, b)$ is small.

Compare the above four conditions and you will see that the second condition is replacing the existential quantifier (in the first condition) with taking the infimum and the third condition is replacing the universal quantifier (in the second condition) with taking the supremum, and as a result, we come to the fourth condition which does not have any quantifiers.

In general, when $S$ is some non-empty subset of $\mathbb R$, all elements of $S$ being less than $\epsilon$ does not necessarily imply that $\sup S < \epsilon$, but the second condition and the third condition are nevertheless interchangeable because we are allowed to perturb $\epsilon$.

The fourth condition motivates the following definition.

Given two non-empty subsets $A, B$ of $M$, define $d^2_H(A, B)$ to be the maximum of the following two quantities:

• $\sup_{a \in A}\inf_{b \in B} d(a, b)$
• $\sup_{b \in B}\inf_{a \in A} d(a, b)$

Exercise. Prove that $d^1_H = d^2_H$.

This distance $d^1_H$ (or equivalently $d^2_H$), which we now denote by $d_H$, is the Hausdorff distance. It takes values in $[0,\infty]$.

Exercise. Given two non-empty subsets $A, B$ and two positive reals $t, \epsilon$, prove the following two properties:

• If $d_H(A, B) \le t$, then for all $a \in A$ there is $b \in B$ with $d(a, b) \le t + \epsilon$ and for all $b \in B$ there is $a \in A$ with $d(a, b) \le t + \epsilon$.
• If for all $a \in A$ there is $b \in B$ with $d(a, b) \le t$ and for all $b \in B$ there is $a \in A$ with $d(a, b) \le t$, then we have $d_H(A, B) \le t$.

Think of the two properties as characterizing the event $d_H(A, B) \le t$ (up to some epsilon of room). Use this characterization to solve the following two exercises.

Exercise. Given positive reals $s,t, \epsilon$ and non-empty subsets $A, B, C$, show that if $d_H(A, B) \le s$ and $d_H(B, C) \le t$ then $d_H(A, C) \le s + t + \epsilon$. Then use that to prove the triangle inequality: $d_H(A, C) \le d_H(A, B) + d_H(B, C)$.

Exercise. Given two non-empty subsets $A, B$, we have $d_H(A, B) = 0$ if and only if they have the same closure.

For any collection $\mathcal C$ of non-empty closed subsets of $M$ such that $d_H(A, B) < \infty$ for all $A, B \in \mathcal C$, the space $(\mathcal C, d_H)$ is a metric space.

## 3. more exercises

Exercise. Let $f_1, \dots, f_n: [0,1] \to M$ be curves in $M$ (i.e. each $f_i$ is continuous). For each $x \in [0,1]$, define $f(x) := \{f_i(x) : 1 \le i \le n \}$. Prove that $f$ is a curve too. Provide an example showing that this does not generalize to countably infinitely many curves.

Exercise. Let $f_t: [0,1] \to M$ be a curve for each $t \in [0,1]$ and assume that $(t,x) \mapsto f_t(x)$ is jointly continuous. Prove that the image $f_t([0,1])$ depends continuously on $t$, that is, when a curve dances continuously, its shadow does too. Speaking of shadow and dance, Shadow Dancer is a good movie.

Exercise. Let $n$ be a fixed positive integer. Let $F_n(M)$ be the collection of all non-empty finite subsets of $M$ of size $\le n$. The obvious canonical map from $M^n$ to $F_n(M)$ is a surjective continuous map. Is it a quotient map?

## mod 0 equivalence of sub-sigma-algebras and gotchas

When we are building some theory involving measures, there are cases where we should ignore null sets (sets of measure zero), and in some of those cases, we treat different sub sigma algebras only up to null sets. In this post, I list different characterizations of two sub sigma algebras being equal up to null sets, and related gotchas. This concerns the stage where you work with sub-sigma-algebras of a probability space before you move on to work with measure algebras (directly or indirectly).

Some quick definition before we start: two measurable sets $A$ and $B$ are equal mod 0 or equivalent mod 0 if their symmetric difference is a measure zero set.

## 1. closure of a sub-sigma-algebra

Given a sub sigma algebra $\mathcal A$ (on a not necessarily complete probability space $(\Omega, \mathcal F, \mathbb P)$), consider the following sets:

(1) $\sigma(\mathcal A, \mathcal N)$ where $\mathcal N$ is the set of measure zero elements in $\mathcal F$.

(2) the set of elements in $\mathcal F$ mod zero equivalent to an element in $\mathcal A$

(3) topological closure of $\mathcal A$ w.r.t. the pseudo metric $\rho$ on $\mathcal F$ defined by $\rho(A, B) := \mathbb P(A \Delta B)$

(10) The sigma algebra associated with the completion of $(\Omega, \mathcal A, \mathbb P)$, i.e., the sigma algebra generated by $\mathcal A$ and subsets of measure zero elements in $\mathcal A$.

Exercises.

• Prove that (1), (2), (3) are the same. I will call this set the closure of $\mathcal A$.1
• Under the assumption that the probability space $(\Omega, \mathcal F, \mathbb P)$ is complete (i.e., $\mathbb P$ on $\mathcal F$ is a complete measure), prove that (10), which I will call the completion of $\mathcal A$, is a sub sigma algebra of (1).
• A gotcha. Under the same assumption, give an example of (10) being a proper subset of (1).2

Hints or answers are provided by footnotes at the bottom.

## 2. closed sub sigma algebra

Given a sub sigma algebra $\mathcal A$ (on a not necessarily complete probability space $(\Omega, \mathcal F, \mathbb P)$), consider following conditions:

(1′) it contains $\mathcal N$

(2′) it is closed under replacing with a mod zero equivalent, i.e., if $A \in \mathcal A$ and $A'$ is mod zero equal to $A$, then $A' \in \mathcal A$

(3′) Its closure is itself

(4′) it is closed under moving to an element of $\mathcal F$ arbitrary close (in the sense of the pseudo metric $\rho$) to elements in $\mathcal A$, i.e., any element of $\mathcal F$ arbitrarily close to elements in $\mathcal A$ is in $\mathcal A$.

(10′) $\mathbb P$ is a complete measure w.r.t. it.

Exercises.

• Prove that (1′), (2′), (3′), (4′) are equivalent conditions.
• A gotcha. Assuming complete probability space, prove that (1′) implies (10′) and that (1′) is actually strictly stronger than (10′).3

## 3. mod zero equivalence of sub sigma algebras

Given two sub sigma algebras $\mathcal A$, $\mathcal A'$ (on a not necessarily complete probability space $(\Omega, \mathcal F, \mathbb P)$), consider the following conditions:

(1) they have the same closure

(2) given any set $E \in \mathcal F$, $E$ is mod zero equal to an element in $\mathcal A$ if and only if it is mod zero equal to an element in $\mathcal A'$

(3) each element in one has a mod zero equivalent counterpart in the other

(10) they have the same completion

Exercises.

• Prove that (1), (2), (3) are equivalent conditions. When any of these three conditions hold, we say that the two sub sigma algebras are equivalent mod 0.
• Assuming complete probability space, prove that (10) implies (1).
• Assuming the same, give an example to show that (10) is strictly stronger than (1).4

Nevertheless, the sub sigma algebra $\mathcal A$ and its closure and its completion are equivalent mod 0, so they are interchangeable in some sense, so don’t worry too much about the gotchas.

## Footnotes:

1

To prove that (3) is a subset of (2), recall a proof of Borel-Cantelli lemma

2

Take the probability space of Lebesgue measure on the unit square. The sub sigma algebra to take is the vertical sigma algebra, i.e., the sigma algebra generated by the first-coordinate canonical projection map. The diagonal in the unit square is in (1) but not in (10)

3

strictly stronger because of the aformentioned vertical sigma algebra.

4

Let $(\Omega, \mathcal F, \mathbb P)$ be $(\{1, 2, 3\}, 2^\Omega, \mathbb P)$ where $\mathbb P$ give measure 1/2 to 1 and 2, but measure zero to 3. This is a standard probability space even. Let $\mathcal A$ be the sub sigma algebra generated by $\{1,3\}$ and $\mathcal A'$ by $\{2,3\}$. They are equivalent mod zero. Each is its own completion.

## 1. background

MS Windows users might want to see this link instead for how to make Emacs (emacsclient) the default text editor.

This will be about Ubuntu, the Linux distribution that comes with, I think, the biggest support group. Even if you are not interested in using Emacs on MS Windows, you should read the troubleshoot section in that linked article because it’s applicable to Ubuntu as well.

By default, text files on Ubuntu open in GEdit, which is an easy-to-use feature-packed editor. Normally, to change the default text editor, you would right click on a text file and then open the “Properties” dialog and from there you can change the default association. You can see for example “GNU Emacs 24″ as an item in the “Open with” applications list. If you make that item the default editor, from then on, all text files (including elisp files and org-mode files) will be opened with Emacs, but each time you open a text file, a new instance of Emacs is launched, which is not what you want. What you really want is to reuse an existing Emacs instance, i.e., to reuse the current Emacs session. You might have heard of emacsclient which is born to serve exactly this purpose. But that’s not the end of the story because it turns out that you will want to always pass some command line options to emacsclient.

## 2. create a new desktop file

If you installed Emacs by installing “GNU Emacs editor (metapackage)” from Ubuntu Software Center like I did, you should be able to find its desktop file, the full path of which is something like:

/usr/share/applications/emacs24.desktop


Your mileage may vary; if you are reading this from future, the desktop file’s name may be emacs26.desktop instead. This desktop file corresponds to the item “GNU Emacs 24 ” in the “Open with” list. We need to make a new desktop file that will handle passing some fixed options to emacsclient. Before that, let’s analyze the contents of emacs24.desktop, which follows:

[Desktop Entry]
Version=1.0
Name=GNU Emacs 24
GenericName=Text Editor
Comment=View and edit files
MimeType=text/english;text/plain;text/x-makefile;text/x-c++hdr;text/x-c++src;text/x-chdr;text/x-csrc;text/x-java;text/x-moc;text/x-pascal;text/x-tcl;text/x-tex;application/x-shellscript;text/x-c;text/x-c++;
Exec=/usr/bin/emacs24 %F
TryExec=emacs24
Icon=/usr/share/icons/hicolor/scalable/apps/emacs24.svg
Type=Application
Terminal=false
Categories=Utility;Development;TextEditor;
StartupWMClass=Emacs24


The line MimeType=text/english.... is basically saying that the application should be allowed to open text files and other text-like files. The Exec field is the command to call, sometimes with fixed arguments. The line TryExec=emacs24 is saying that GNU Emacs 24 should be considered as installed when emacs24 can be found through PATH. The line StartupWMClass=Emacs24 seems to be about classification of windows.

Open that desktop file with an editor, and copy its contents to a new desktop file, the full path of which could be something like:

~/.local/share/applications/emacsclient24orgedit.desktop


and then modify just two lines, like this:

[Desktop Entry]
Version=1.0
# # Name=GNU Emacs 24
Name=GNU Emacs Client 24 or GEdit
GenericName=Text Editor
Comment=View and edit files
MimeType=text/english;text/plain;text/x-makefile;text/x-c++hdr;text/x-c++src;text/x-chdr;text/x-csrc;text/x-java;text/x-moc;text/x-pascal;text/x-tcl;text/x-tex;application/x-shellscript;text/x-c;text/x-c++;
# # Exec=/usr/bin/emacs24 %F
Exec=/usr/bin/emacsclient.emacs24 -c --no-wait --alternate-editor=gedit %F
TryExec=emacs24
Icon=/usr/share/icons/hicolor/scalable/apps/emacs24.svg
Type=Application
Terminal=false
Categories=Utility;Development;TextEditor;
StartupWMClass=Emacs24


Let me help you spot the differences; original lines are commented out with two number signs and the new lines are inserted just after the commented out lines. You can make these changes easily with GEdit (some might say the quickest way would be with VI). Save it and restart your Ubuntu machine. Now there should be a new item “GNU Emacs Client 24 or GEdit” in the “Open with” list. Make that item the default editor; you can easily figure out how to do that if you open the “Properties” dialog after right clicking on a text file. Make Emacs server start automatically whenever you start Emacs. That can be done by simply adding (server-start) to your Emacs init file. Restart Emacs.

Now whenever you open a text file, it will open in an existing instance of Emacs if any, otherwise it will open in GEdit.

Let’s take a look at the Exec field:

Exec=/usr/bin/emacsclient.emacs24 -c --no-wait --alternate-editor=gedit %F


I wrote /usr/bin/emacsclient.emacs24 there because running the command whereis emacsclient on my system told me of /usr/bin/emacsclient and /usr/bin/emacsclient.emacs24 and some others. The file /usr/bin/emacsclient is a symbolic link to a symbolic link to /usr/bin/emacsclient.emacs24. Some of you might want to write /usr/bin/emacsclient instead, in which case you should also change the Name field accordingly.

The option -c is there so that each text file is opened in a new Emacs frame (of an existing Emacs instance) rather than in an existing Emacs frame. You can leave out this option if you want.

The option --no-wait is there so that the emacsclient process quits itself as soon as it’s done the job of telling the Emacs instance to open the text file.

OK, we are done. Read that troubleshoot section.

Some day, you might hear about Emacs Daemon and --alternate-editor=emacs which you should try later, but not right now if you are a beginner. As for why not right now, see the relevant sections in the linked article.