Common Lisp the Language, 2nd Edition
In contrast to loop, do and do* provide a powerful and general mechanism for repetitively recalculating many variables.
[Macro]
do ({(var [init [step]])}*)
(end-test {result}*)
{declaration}* {tag | statement}*
do* ({(var [init [step]])}*)
(end-test {result}*)
{declaration}* {tag | statement}*
The do special form provides a generalized iteration facility, with an arbitrary number of ``index variables.'' These variables are bound within the iteration and stepped in parallel in specified ways. They may be used both to generate successive values of interest (such as successive integers) or to accumulate results. When an end condition is met, the iteration terminates with a specified value.
In general, a do loop looks like this:
(do ((var1 init1 step1)
(var2 init2 step2)
...
(varn initn stepn))
(end-test . result)
{declaration}*
. tagbody)
A do* loop looks exactly the same except that the name do is replaced by do*.
The first item in the form is a list of zero or more index-variable specifiers. Each index-variable specifier is a list of the name of a variable var, an initial value init, and a stepping form step. If init is omitted, it defaults to nil. If step is omitted, the var is not changed by the do construct between repetitions (though code within the do is free to alter the value of the variable by using setq).
An index-variable specifier can also be just the name of a variable. In this case, the variable has an initial value of nil and is not changed between repetitions. As a matter of style, it is recommended that an unadorned variable name be written only when that variable will be stored into (such as by setq) before its first use. If it is important that the initial value be nil rather than some undefined value, then it is clearer to write out (varj nil) if the initial value is intended to mean ``false,'' or (varj '()) if the initial value is intended to be an empty list.
X3J13 voted in January 1989
(VARIABLE-LIST-ASYMMETRY)
to regularize the binding formats for do, do*, let,
let*, prog, prog*, and compiler-let.
In the case of do and do* the first edition was inconsistent;
the formal syntax fails to reflect the fact that a simple variable
name may appear, as described in the preceding paragraph. The
definitions should read
[Macro]
do ({var | (var [init [step]])}*)
(end-test {result}*)
{declaration}* {tag | statement}*
do* ({var | (var [init [step]])}*)
(end-test {result}*)
{declaration}* {tag | statement}*
for consistency with the reading of the first edition and the X3J13 vote.
Before the first iteration, all the init forms are evaluated, and each var is bound to the value of its respective init. This is a binding, not an assignment; when the loop terminates, the old values of those variables will be restored. For do, all of the init forms are evaluated before any var is bound; hence all the init forms may refer to the old bindings of all the variables (that is, to the values visible before beginning execution of the do construct). For do*, the first init form is evaluated, then the first var is bound to that value, then the second init form is evaluated, then the second var is bound, and so on; in general, the initj form can refer to the new binding vark if k < j, and otherwise to the old binding of vark.
The second element of the loop is a list of an end-testing predicate form end-test and zero or more result forms. This resembles a cond clause. At the beginning of each iteration, after processing the variables, the end-test is evaluated. If the result is nil, execution proceeds with the body of the do (or do*) form. If the result is not nil, the result forms are evaluated in order as an implicit progn, and then do returns. do returns the results of evaluating the last result form. If there are no result forms, the value of do is nil. Note that this is not quite analogous to the treatment of clauses in a cond form, because a cond clause with no result forms returns the (non-nil) result of the test.
At the beginning of each iteration other than the first, the index variables are updated as follows. All the step forms are evaluated, from left to right, and the resulting values are assigned to the respective index variables. Any variable that has no associated step form is not assigned to. For do, all the step forms are evaluated before any variable is updated; the assignment of values to variables is done in parallel, as if by psetq. Because all of the step forms are evaluated before any of the variables are altered, a step form when evaluated always has access to the old values of all the index variables, even if other step forms precede it. For do*, the first step form is evaluated, then the value is assigned to the first var, then the second step form is evaluated, then the value is assigned to the second var, and so on; the assignment of values to variables is done sequentially, as if by setq. For either do or do*, after the variables have been updated, the end-test is evaluated as described above, and the iteration continues.
If the end-test of a do form is nil, the test will never succeed. Therefore this provides an idiom for ``do forever'': the body of the do is executed repeatedly, stepping variables as usual. (The loop construct performs a ``do forever'' that steps no variables.) The infinite loop can be terminated by the use of return, return-from, go to an outer level, or throw. For example:
(do ((j 0 (+ j 1)))
(nil) ;Do forever
(format t "~%Input ~D:" j)
(let ((item (read)))
(if (null item) (return) ;Process items until nil seen
(format t "~&Output ~D: ~S" j (process item)))))
The remainder of the do form constitutes an implicit tagbody. Tags may appear within the body of a do loop for use by go statements appearing in the body (but such go statements may not appear in the variable specifiers, the end-test, or the result forms). When the end of a do body is reached, the next iteration cycle (beginning with the evaluation of step forms) occurs.
An implicit block named nil surrounds the entire do form. A return statement may be used at any point to exit the loop immediately.
declare forms may appear at the beginning of a do body. They apply to code in the do body, to the bindings of the do variables, to the init forms, to the step forms, to the end-test, and to the result forms.
Here are some examples of the use of do:
(do ((i 0 (+ i 1)) ;Sets every null element of a-vector to zero
(n (length a-vector)))
((= i n))
(when (null (aref a-vector i))
(setf (aref a-vector i) 0)))
The construction
(do ((x e (cdr x))
(oldx x x))
((null x))
body)
exploits parallel assignment to index variables. On the first iteration, the value of oldx is whatever value x had before the do was entered. On succeeding iterations, oldx contains the value that x had on the previous iteration.
Very often an iterative algorithm can be most clearly expressed entirely in the step forms of a do, and the body is empty. For example,
(do ((x foo (cdr x))
(y bar (cdr y))
(z '() (cons (f (car x) (car y)) z)))
((or (null x) (null y))
(nreverse z)))
does the same thing as (mapcar #'f foo bar). Note that the step computation for z exploits the fact that variables are stepped in parallel. Also, the body of the loop is empty. Finally, the use of nreverse to put an accumulated do loop result into the correct order is a standard idiom. Another example:
(defun list-reverse (list)
(do ((x list (cdr x))
(y '() (cons (car x) y)))
((endp x) y)))
Note the use of endp rather than null or atom to test for the end of a list; this may result in more robust code.
As an example of nested loops, suppose that env holds a list of conses. The car of each cons is a list of symbols, and the cdr of each cons is a list of equal length containing corresponding values. Such a data structure is similar to an association list but is divided into ``frames''; the overall structure resembles a rib cage. A lookup function on such a data structure might be
(defun ribcage-lookup (sym ribcage)
(do ((r ribcage (cdr r)))
((null r) nil)
(do ((s (caar r) (cdr s))
(v (cdar r) (cdr v)))
((null s))
(when (eq (car s) sym)
(return-from ribcage-lookup (car v))))))
(Notice the use of indentation in the above example to set off the bodies of the do loops.)
A do loop may be explained in terms of the more primitive constructs block, return, let, loop, tagbody, and psetq as follows:
(block nil
(let ((var1 init1)
(var2 init2)
...
(varn initn))
{declaration}*
(loop (when end-test (return (progn . result)))
(tagbody . tagbody)
(psetq var1 step1
var2 step2
...
varn stepn))))
do* is exactly like do except that the bindings and steppings of the variables are performed sequentially rather than in parallel. It is as if, in the above explanation, let were replaced by let* and psetq were replaced by setq.