Next: Simple Iteration Constructs Up: Iteration Previous: Indefinite Iteration
Common Lisp the Language, 2nd Edition
Next: Simple Iteration
Constructs Up: Iteration
Previous: Indefinite
Iteration
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.
Compatibility note: ``Old-style’’ MacLisp
do loops, that is, those of the form
(dovarinitstepend-test.body),
are not supported in Common Lisp. Such old-style loops are considered
obsolete and in any case are easily converted to a new-style
do with the insertion of three pairs of parentheses. In
practice the compiler can catch nearly all instances of old-style
do loops because they will not have a legal format
anyway.
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.
Next: Simple Iteration
Constructs Up: Iteration
Previous: Indefinite
Iteration
AI.Repository@cs.cmu.edu