16

Could someone explain to me what's going on in this very simple code snippet?

(defun test-a ()
  (let ((x '(nil)))
    (setcar x (cons 1 (car x)))
    x))

Upon a calling (test-a) for the first time, I get the expected result: ((1)). But to my surprise, calling it once more, I get ((1 1)), ((1 1 1)) and so on. Why is this happening? Am I wrong to expect (test-a) to always return ((1))? Also note that after re-evaluating the definition of test-a, the return result resets.

Also consider that this function works as I expect:

(defun test-b ()
  (let ((x '(nil)))
    (setq x (cons (cons 1 (car x)) 
                  (cdr x)))))

(test-b) always returns ((1)). Why aren't test-a and test-b equivalent?

sds
  • 58,617
  • 29
  • 161
  • 278
abo-abo
  • 20,038
  • 3
  • 50
  • 71

3 Answers3

22

The Bad

test-a is self-modifying code. This is extremely dangerous. While the variable x disappears at the end of the let form, its initial value persists in the function object, and that is the value you are modifying. Remember that in Lisp a function is a first class object, which can be passed around (just like a number or a list), and, sometimes, modified. This is exactly what you are doing here: the initial value for x is a part of the function object and you are modifying it.

Let us actually see what is happening:

(symbol-function 'test-a)
=> (lambda nil (let ((x (quote (nil)))) (setcar x (cons 1 (car x))) x))
(test-a)
=> ((1))
(symbol-function 'test-a)
=> (lambda nil (let ((x (quote ((1))))) (setcar x (cons 1 (car x))) x))
(test-a)
=> ((1 1))
(symbol-function 'test-a)
=> (lambda nil (let ((x (quote ((1 1))))) (setcar x (cons 1 (car x))) x))
(test-a)
=> ((1 1 1))
(symbol-function 'test-a)
=> (lambda nil (let ((x (quote ((1 1 1))))) (setcar x (cons 1 (car x))) x))

The Good

test-b returns a fresh cons cell and thus is safe. The initial value of x is never modified. The difference between (setcar x ...) and (setq x ...) is that the former modifies the object already stored in the variable x while the latter stores a new object in x. The difference is similar to x.setField(42) vs. x = new MyObject(42) in C++.

The Bottom Line

In general, it is best to treat quoted data like '(1) as constants - do not modify them:

quote returns the argument, without evaluating it. (quote x) yields x. Warning: quote does not construct its return value, but just returns the value that was pre-constructed by the Lisp reader (see info node Printed Representation). This means that (a . b) is not identical to (cons 'a 'b): the former does not cons. Quoting should be reserved for constants that will never be modified by side-effects, unless you like self-modifying code. See the common pitfall in info node Rearrangement for an example of unexpected results when a quoted object is modified.

If you need to modify a list, create it with list or cons or copy-list instead of quote.

See more examples.

PS1. This has been duplicated on Emacs.

PS2. See also Why does this function return a different value every time? for an identical Common Lisp issue.

PS3. See also Issue CONSTANT-MODIFICATION.

sds
  • 58,617
  • 29
  • 161
  • 278
  • But why does the modification persist? Shouldn't the variable x, which I think is just a pointer to `'(nil)` here, be deleted at the end of the let form? – Tyler May 21 '13 at 17:50
  • @Tyler: the variable is deleted, but the initial value is not. see edit. – sds May 21 '13 at 18:03
  • That makes sense now that you explain it. I never would have made that connection. – Tyler May 21 '13 at 18:12
  • 1
    It's illuminating to call `(symbol-function 'test-a)` both after defining `test-a`, and again after calling it. – phils May 22 '13 at 02:07
  • Thanks, @sds. I accepted your answer, but I still haven't grokked the concept. "its initial value persists in the function object" - this is the part that I don't understand: why is this different in 'test-b? It was declared in exactly the same way. My intuition tells me that it's 'setcar who is at fault here and not the combination of 'let and 'quote. – abo-abo May 22 '13 at 07:57
  • 1
    @abo-abo in test-a, setcar is used to directly modify the list that x is pointing at. X is pointing at a constant in the function definition, so the function itself gets changed. In test-b, the values in the list that x initially points to are used to construct a new list to be assigned to x. The initial value is never directly altered. So you are right, setcar is the key difference. – Tyler May 22 '13 at 11:10
  • @abo-abo While the problem manifests due to `setcar` mutating its value, the culprit is modifying literals. If you modify `test-a` to have `(let ((x (list nil))) ...)` you would not see the problem, because your `(nil)` would be freshly constructed on each call, instead of being a one-off literal that is modified. – Vatine May 24 '13 at 09:12
2

I found the culprit is indeed 'quote. Here's its doc-string:

Return the argument, without evaluating it.

...

Warning: `quote' does not construct its return value, but just returns the value that was pre-constructed by the Lisp reader

...

Quoting should be reserved for constants that will never be modified by side-effects, unless you like self-modifying code.

I also rewrote for convenience

(setq test-a 
      (lambda () ((lambda (x) (setcar x (cons 1 (car x))) x) (quote (nil)))))

and then used 

(funcall test-a)

to see how 'test-a was changing.

abo-abo
  • 20,038
  • 3
  • 50
  • 71
1

It looks like the '(nil) in your (let) is only evaluated once. When you (setcar), each call is modifying the same list in-place. You can make (test-a) work if you replace the '(nil) with (list (list)), although I presume there's a more elegant way to do it.

(test-b) constructs a totally new list from cons cells each time, which is why it works differently.

regularfry
  • 3,248
  • 2
  • 21
  • 27
  • Thanks, your answer does present a work-around, but I still don't understand why this is happening. x inside 'test-a is declared local and indeed it's not visible outside the function, but why does the function retain information about x between calls? – abo-abo May 21 '13 at 13:37
  • 2
    At a guess, I'd say it's because emacs constructs the list when it parses the literal in the let, then refers to the same list each time the function is called. It's like it's using a pointer into the parse tree for the reference to x. – regularfry May 21 '13 at 14:46
  • @abo-abo: emacs does _not_ preserve information about x, but about its initial value. see my answer. – sds May 21 '13 at 18:04