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
`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*enclosed by`TAGBODY``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`.