Common Lisp iteration

Created Monday 23 November 2020

Each of the following definitions of a factorial function demonstrate a way to iterate in Common Lisp, with brief notes. I hope that by demonstrating many different ways that the same thing can be written, you can develop a sense for the character of the constructs afforded by the language, and of the variety of possible styles. Common Lisp is famously syntactically extensible via macros, so keep in mind that my examples are by no means the only ways to iterate.

For further reading on the iteration and control structures of Common Lisp, I heartily recommend:

• Chapter 7 and Chapter 22 of Practical Common Lisp by Peter Siebel.
• A reasonably-priced used copy of ANSI Common Lisp by Paul Graham.

Note: several of the examples return nonsensical results for negative inputs. The addition of (assert (not (minusp n))or similar is a good idea, but I have omitted it here for clarity.

DOTIMES

(defun factorial-dotimes (n &aux (prod 1))
  (dotimes (i n prod)
    (setq prod (* prod (1+ i)))))

• &aux lambda list keyword names a local variable prod. LET could also be used for this purpose, but at the cost of more indentation.
• DOTIMES binds i successively from 0 to 1-n and finally evaluates to prod.

DO

(defun factorial-do (n)
  (do ((i 1 (1+ i))
       (prod 1 (* prod i)))
      ((> i n) prod)))

• DO binds i to 1 and then to (1+ i) in subsequent iterations. prod is bound first to 1 and then to (* prod i) in subsequent iterations.
• When the test clause (> i n) becomes true, prod is returned. Contrast with the test clause of for loops in other languages, which terminate the loop when they become false.
• I like the way Paul Graham explains DOandDO* in ANSI Common Lisp.

LOOP

(defun factorial-loop (n)
  (loop
     for i from 1 to n
     for prod = 1 then (* prod i)
     finally (return prod)))

• i is bound from 1 to n inclusive.
• prod is bound to 1 and then (* prod i) in subsequent iterations in a manner similar to DO.
• In the finally clause, prod is returned by RETURN once iteration is complete. The BLOCK named NIL established by LOOP is the point of return.
• LOOP supports a comprehensive iteration and accumulation DSL. Chapter 22 of Practical Common Lisp offers a great introduction.

The preceding example demonstrates the "extended" form of LOOP. There's also "simple" form:

(defun factorial-simple-loop (n &aux (i 0) (prod 1))
  (loop
    (when (eql i n)
      (return prod))
    (setq prod (* prod (incf i)))))

Recursion

(defun factorial-recursive (n)
  (if (zerop n)
      1
      (* n (factorial-recursive (1- n)))))

• FACTORIAL-RECURSIVE calls itself, but when n exceeds the maximum stack size supported by the implementation, an error is signaled.

  (defun factorial-tail-recursive (n) (labels ((recur (n prod) (if (zerop n) prod (recur (1- n) (* n prod))))) (recur n 1)))

• FACTORIAL-TAIL-RECURSIVEdoes not call itself directly.

• Instead, it defines with LABELS an internal and recursive helper function, recur.

• recur calls itself in tail position and the stack never overflows in implementations that implement tail-call elimination.

  (defun factorial-tail-recursive-opt (n &optional (prod 1)) (if (zerop n) prod (factorial-tail-recursive-opt (1- n) (* n prod))))

• FACTORIAL-TAIL-RECURSIVE-OPT is also tail recursive, but uses the &OPTIONAL lambda list keyword to maintain prod across iterations. This approach has the downside of exposing prod as part of the public interface of the function. Arguably, prod is an implementation detail, best kept internal.

PROG

(defun factorial-prog (n)
  (prog ((i 0) (prod 1))
   begin
   (when (eql i n)
     (return prod))
   (setq prod (* prod (incf i)))
   (go begin)))

• PROG supports both declaring local lexical variables (i and prod) and naming GO tags (begin).
• begin names a label within the implicit TAGBODY enclosed by PROG that may be jumped to.
• WHEN i is EQL to n, RETURN returns prod.
• GO jumps to begin.

TAGBODY

(defun factorial-tagbody (n &aux (i 0) (prod 1))
  (tagbody
     begin
     (when (eql i n)
       (return-from factorial-tagbody prod))
     (setq prod (* prod (incf i)))
     (go begin)))

• TAGBODY is the most general but also the lowest-level and most verbose iteration construct.
• &aux lambda list keyword names local variables i and prod, initializing them to 0 and 1, respectively.
• WHEN i is EQL to n, RETURN-FROM returns prod from the BLOCK named after the function by DEFUN.
• GO jumps to begin.