Strange Lisp Quoting scenario - Graham's On Li

Question

I'm working my way through Graham's book "On Lisp" and can't understand the following example at page 37:

If we define exclaim so that its return value
incorporates a quoted list,

(defun exclaim (expression)
  (append expression ’(oh my)))

>  (exclaim ’(lions and tigers and bears))
(LIONS AND TIGERS AND BEARS OH MY)
> (nconc * ’(goodness))
(LIONS AND TIGERS AND BEARS OH MY GOODNESS)

could alter the list within the function:

> (exclaim ’(fixnums and bignums and floats))
(FIXNUMS AND BIGNUMS AND FLOATS OH MY GOODNESS)

To make exclaim proof against such problems, it should be written:
(defun exclaim (expression)
  (append expression (list ’oh ’my)))

Does anyone understand what's going on here? This is seriously screwing with my mental model of what quoting does.

Answer 1

The observation that your mental model of quoting may be flawed is an excellent one—although it may or may not apply depending on what that mental model is.

First, remember that there are various stages to program execution. A Lisp environment must first read the program text into data structures (lists, symbols, and various literal data such as strings and numbers). Next, it may or may not compile those data structures into machine code or some sort of intermediary format. Finally, the resulting code is evaluated (in the case of machine code, of course, this may simply mean jumping to the appropriate address).

Let's put the issue of compilation aside for now and focus on the reading and evaluation stages, assuming (for simplicity) that the evaluator's input is the list of data structures read by the reader.

Consider a form (QUOTE x) where x is some textual representation of an object. This may be symbol literal as in (QUOTE ABC), a list literal as in (QUOTE (A B C)), a string literal as in (QUOTE "abc"), or any other kind of literal. In the reading stage, the reader will read the form as a list (call it form1) whose first element is the symbol QUOTE and whose second element is the object x' whose textual representation is x. Note that I'm specifically saying that the object x' is stored within the list that represents the expression, i.e. in a sense, it's stored as a part of the code itself.

Now it's the evaluator's turn. The evaluator's input is form1, which is a list. So it looks at the first element of form1, and, having determined that it is the symbol QUOTE, it returns as the result of the evaluation the second element of the list. This is the crucial point. The evaluator returns the second element of the list to be evaluated, which is what the reader read in in the first execution stage (prior to compilation!). That's all it does. There's no magic to it, it's very simple, and significantly, no new objects are created and no existing ones are copied.

Therefore, whenever you modify a “quoted list”, you're modifying the code itself. Self-modifying code is a very confusing thing, and in this case, the behaviour is actually undefined (because ANSI Common Lisp permits implementations to put code in read-only memory).

Of course, the above is merely a mental model. Implementations are free to implement the model in various ways, and in fact, I know of no implementation of Common Lisp that, like my explanation, does no compilation at all. Still, this is the basic idea.

Answer 2

In Common Lisp.

Remember:

'(1 2 3 4)

Above is a literal list. Constant data.

(list 1 2 3 4)

LIST is a function that when call returns a fresh new list with its arguments as list elements.

Avoid modifying literal lists. The effects are not standardized. Imagine a Lisp that compiles all constant data into a write only memory area. Imagine a Lisp that takes constant lists and shares them across functions.

(defun a () '(1 2 3)

(defun b () '(1 2 3))

A Lisp compiler may create one list that is shared by both functions.

If you modify the list returned by function a

• it might not be changed
• it might be changed
• it might be an error
• it might also change the list returned by function b

Implementations have the freedom to do what they like. This leaves room for optimizations.

Answer 3

nconc is a destructive operation that alters its first argument by changing its tail. In this case, it means that the constant list '(oh my) gets a new tail.

To hopefully make this clearer. It's a bit like this:

; Hidden variable inside exclaim
oh_my = oh → my → nil

(exclaim '(lions and tigers and bears)) =
    lions → and → tigers → and → bears → oh_my

(nconc * '(goodness)) destructively appends goodness to the last result:
    lions → and → tigers → and → bears → oh → my → goodness → nil
so now, oh_my = oh → my → goodness → nil

Replacing '(oh my) with (list 'oh 'my) fixes this because there is no longer a constant being shared by all and sundry. Each call to exclaim generates a new list (the list function's purpose in life is to create brand new lists).