[ Home ] [ Index ]

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:

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)))))

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 DO and DO* 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-RECURSIVE does 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)))