common-lispsetf

SETF neither terminates nor reports an error


I'm a Common Lisp beginner and came across this piece of code:

(let ((foo (list 42)))
  (setf (rest foo) foo))

The REPL seem to just loop forever when trying to execute it.


Solution

  • What is FOO?

    FOO is initially a fresh list, (42). In Lisp, lists are represented by cons cells, blocks of mutable memory containing each a CAR and a CDR slot. Another way to print it is (42 . NIL), where the CAR and CDR are on each side of the dot. This can also be pictured as follows:

      car  cdr
    ------------
    | 42 | NIL |
    ------------
         ^
         |
        FOO
    

    When you call SETF with the (rest foo) place and the foo value, you are saying that you want the cdr cell of FOO to hold the value FOO. In fact, this occurrence of SETF is likely to macroexpand into a call to RPLACD.

    ------------
    | 42 | FOO |
    ------------
         ^
         |
        FOO
    

    Why does the REPL loop forever?

    The "P" part of the "REPL" (print) tries to print your circular structure. This is because SETF's value is the one being returned from the form being evaluated, and the value returned by SETF is the value of its second argument, namely FOO. Imagine you want to write a cons cell X with a naive algorithm:

    1. PRINT "("
    2. PRINT the CAR of X
    3. PRINT " . "
    4. PRINT the CDR of X
    5. PRINT ")"
    

    However, for foo, step 4 will print the same structure, recursively, and will never terminate.

    What can you do?

    Try setting *PRINT-CIRCLE* to T first:

    (setf *print-circle* t)
    

    And now, your REPL should be happy:

    CL-USER> (let ((foo (list 42)))
               (setf (rest foo) foo))
    #1=(42 . #1#)
    

    The "Sharpsign Equal-Sign" notation allows the reader to affect part of a form to a (reader) variable, like #1=..., and reuse it afterwards, e.g. #1#. This make it possible to represent circular cross-references between data, either during reading or printing. Here, we can see that the variable #1# denotes a cons-cell, where the CAR is 42 and the CDR is #1# itself.