Loops in Lisp Part 2: Loop

This is part 2 of Loops in Lisp. Click here to view the previous post on how you can build any iteration abstraction you want out of just goto and macros.

The loop macro is probably the most well known of all macros. It provides a DSL for performing any kind of iteration imaginable. To give you an idea of just how powerful loop is, here are the first two Project Euler problems, solved using just loop:

;; Solution for problem #1.
(loop for i from 1 below 1000
      if (or (= 0 (mod i 3))
             (= 0 (mod i 5)))
        sum i)

;; Solution for problem #2.
(loop for a = 1 then (+ a b)
      and b = 0 then a
      while (< a 4000000)
      if (evenp a)
        sum a)

The coolest part of loop is that it is just a macro! That means it would be possible to build loop in Common Lisp, even if it wasn’t provided as a builtin (here is one such implementation). That also means any loop code is eventually compiled down to goto! For example, here is the expansion of the solution to the first Project Euler problem:

(block nil
  (let ((i 1))
    (declare (type (and real number) i))
    (let ((#:loop-sum-2482 0))
      (declare (type number #:loop-sum-2482))
      (tagbody
       sb-loop::next-loop
        (if (>= i '1000)
            (progn (go sb-loop::end-loop))
            nil)
        (if (let ((#:g2483 (= 0 (mod i 3))))
              (if #:g2483
                  #:g2483
                  (the t (= 0 (mod i 5)))))
            (setq #:loop-sum-2482 (+ #:loop-sum-2482 i)))
        (setq i (1+ i))
        (go sb-loop::next-loop)
       sb-loop::end-loop
        (return-from nil #:loop-sum-2482)))))

If you look carefully, the expansion is nothing more than a mix of a few gotos and conditionals. Also, even though the generated code is a complete mess, you are able to work with it through interface provided by loop. Even though loop is fairly complex, it is still much simpler than raw gotos. If you think about it, loop is really just a convenient way of specifying a combination of patterns of gotos and conditionals.

I don’t have much to add about loop that others haven’t already said. If you are looking for a basic introduction to loop you should read Peter Seibel’s guide which can be found here. If you are looking for a more complete reference, check out the loop chapter in Common Lisp the Language which can be found here.

While all of the features of loop compose well with each other, they do not compose well with the rest of Common Lisp. You cannot embed a loop clause (e.g. collect) within ordinary lisp code. That brings us to what will be next week’s topic, iterateIterate is basically a more lispy version of loop. It allows you to seamlessly go between iterate clauses and regular Lisp code. More importantly, iterate allows you to define macros that then become part of the iterate DSL!

Leave a Reply

Your email address will not be published. Required fields are marked *