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