Understanding loop macro expansion

Question

I expanded the macro below to see how it worked and found myself a little confused.

(loop for i below 4 collect i)

expands to (I have cleaned it up a little for readability)

(block nil
  (let ((i 0))
    (declare (type (and number real) i))
    (let* ((list-head (list nil))
           (list-tail list-head))
      (tagbody
       sb-loop::next-loop
         (when (>= i 4) (go sb-loop::end-loop))
         (rplacd list-tail (setq list-tail (list i)))
         (setq i (1+ i))

         (print "-------") ;; added so I could see the lists grow
         (print list-head)
         (print list-tail)
         (print "-------")

         (go sb-loop::next-loop)
       sb-loop::end-loop
         (return-from nil (cdr list-head))))))

..and here is the output from running the above..

;; "-------" 
;; (NIL 0) 
;; (0) 
;; "-------" 
;; "-------" 
;; (NIL 0 1) 
;; (1) 
;; "-------" 
;; "-------" 
;; (NIL 0 1 2) 
;; (2) 
;; "-------" 
;; "-------" 
;; (NIL 0 1 2 3) 
;; (3) 
;; "-------"

I just can't see where list-head is modified, I have to assume head and tail are eq and thus modifying one is modifying the other but could someone please break down what is happening on the rplacd line?

Telepathist

Why do you want the list-head modified? See it as a single linked list: head doesn't change, only the tail when you append a new element. However, the print function applied on a list prints the list from the current element to the last element, that's why you see the list-head growing and the list-tail changing. – Laurence

I don't want it modified. I want to understand what is actually happening. If the print output is confusing the situation then that may be why I'm not understanding. You should drop your comment in an answer so I can send karma your way! – Telepathist

+1 for a good question that digs into source, uses macroexpansion, shows clear behavior about which there's a question, etc. Nice! – Fettling

a.k.a. "head sentinel trick". – Vat

Answer 1

list-head and list-tail are initially the same (in the eq sense). list-head is a cons which cdr is the list being collected. list-tail points to the last cons in the list (except initially, see below).

To add an element to the end of the list, replacd modifies the cdr of list-tail to add a new cons, and list-tail is updated to point to the new cons.

When the loop terminates, the result is the cdr of list-head.

Why this complicated business with an extra cons? Because the list appending algorithm becomes easier when list-tail is always a pointer to the last cons of the list. But in the beginning, the empty list has no cons. So the trick is to make the list one cons longer.

Ourself

And just like that it all makes sense! Thanks, turns out I was messing up the order of evaluation in my head. This cleared it all up perfectly. Cheers! – Telepathist

Credits should go to Richard C Waters. See "Implementing Queues in Lisp" in "Some Useful Lisp Algorithms: Part 1" merl.com/publications/docs/TR91-04.pdf (Also check out "Part 2".) – Ourself