CODEWITHSUNDEEP
loopsmacroscommon-lisp
Baggers
Baggers

Reputation: 3231

Understanding loop macro expansion

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?

Upvotes: 7

Views: 290

Answers (1)

Lars Brinkhoff
Lars Brinkhoff

Reputation: 14335

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.

Upvotes: 10

Related Questions