Common Lisp the Language, 2nd Edition

Next: Simple Iteration Constructs Up: Iteration Previous: Indefinite Iteration

## 7.8.2. General 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 `(do var init step end-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