Common Lisp shared structure confusion

Question

I am reading the book Practical Common Lisp, and in the footnote5 of chapter22, page284, I saw a code snippet that made me confused.

I know that the variable list and tail have a list structure in common, but I am confusing that since tail will be assigned the value of 'new' each time during the iteration, why (setf (cdr tail) new) would affect the state of the variable list？

(do ((list nil) (tail nil) (i 0 (1+ i)))
    ((> i 10) list)
  (let ((new (cons i nil)))
    (if (null list)
        (setf list new)
        (setf (cdr tail) new))
    (setf tail new)))

;;; => (0 1 2 3 4 5 6 7 8 9 10)

score 3 · Accepted Answer · answered May 17 '19 at 11:12

The invariant is that tail is always the last cons cell of list.

On each iteration, a new cons cell is created holding the new value as car. The first time through, list is set to this cons cell, and tail too. In all subsequent iterations, the new cons cell is appended by setting the cdr of the last cell to it, then setting tail to the new cell, to recreate the invariant.

After first iteration:

 [ 0 | nil ]
   ^- list
   ^- tail

After second:

 [ 0 | -]--->[ 1 | nil ]
   ^- list     ^- tail

Third:

 [ 0 | -]--->[ 1 | -]--->[ 2 | nil ]
   ^- list                 ^- tail

score 2 · Answer 2 · answered May 17 '19 at 12:01

The do form in your example keeps a pointer to the tail cons to make appending an element to the end of the list a cheap operation. Otherwise one would need to traverse the list all the time to find the last cons - for example by using appendor nconc. Another way would be to collect new elements on the head and at the end to reverse the result list.

One would expect that the LOOP macro implements something efficient by transforming a higher level loop expression into efficient code.

The macro form

(loop for i upto 10 collect i)

might expand into something that works internally similar as your do example. The advantage of loop is that you don't need to implement the logic to track the tail, since that's what the macro should do for you.

Common Lisp shared structure confusion

2 Answers2