Common Lisp provides a number of iteration constructs. The loop construct provides a trivial iteration facility; it is little more than a progn with a branch from the bottom back to the top. The do and do* constructs provide a general iteration facility for controlling the variation of several variables on each cycle. For specialized iterations over the elements of a list or n consecutive integers, dolist and dotimes are provided. The tagbody construct is the most general, permitting arbitrary go statements within it. (The traditional prog construct is a synthesis of tagbody, block, and let.) Most of the iteration constructs permit statically defined non-local exits (see return-from and return).
The loop construct is the simplest iteration facility. It controls no variables, and simply executes its body repeatedly.
Each form is evaluated in turn from left to right. When the last form has been evaluated, then the first form is evaluated again, and so on, in a never-ending cycle. The loop construct never returns a value. Its execution must be terminated explicitly, using return or throw, for example.
loop, like most iteration constructs, establishes an implicit block named nil. Thus return may be used to exit from a loop with specified results.
There is an extension of loop. See chapter 26.
In contrast to loop, do and do* provide a powerful and general mechanism for repetitively recalculating many variables.
The do special operator 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:
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 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
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:
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:
The construction
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,
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:
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
(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:
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.
The constructs dolist and dotimes execute a body of code once for each value taken by a single variable. They are expressible in terms of do, but capture very common patterns of use.
Both dolist and dotimes perform a body of statements repeatedly. On each iteration a specified variable is bound to an element of interest that the body may examine. dolist examines successive elements of a list, and dotimes examines integers from 0 to n − 1 for some specified positive integer n.
The value of any of these constructs may be specified by an optional result form, which if omitted defaults to the value nil.
The return statement may be used to return immediately from a dolist or dotimes form, discarding any following iterations that might have been performed; in effect, a block named nil surrounds the construct. The body of the loop is implicitly a tagbody construct; it may contain tags to serve as the targets of go statements. Declarations may appear before the body of the loop.
dolist provides straightforward iteration over the elements of a list. First dolist evaluates the form listform, which should produce a list. It then executes the body once for each element in the list, in order, with the variable var bound to the element. Then resultform (a single form, not an implicit progn) is evaluated, and the result is the value of the dolist form. (When the resultform is evaluated, the control variable var is still bound and has the value nil.) If resultform is omitted, the result is nil.
An explicit return statement may be used to terminate the loop and return a specified value.
X3J13 voted in January 1989 to restrict user side effects; see section 7.9.
dotimes provides straightforward iteration over a sequence of integers. The expression (dotimes (var countform resultform) . progbody) evaluates the form countform, which should produce an integer. It then performs progbody once for each integer from zero (inclusive) to count (exclusive), in order, with the variable var bound to the integer; if the value of countform is zero or negative, then the progbody is performed zero times. Finally, resultform (a single form, not an implicit progn) is evaluated, and the result is the value of the dotimes form. (When the resultform is evaluated, the control variable var is still bound and has as its value the number of times the body was executed.) If resultform is omitted, the result is nil.
An explicit return statement may be used to terminate the loop and return a specified value.
Here is an example of the use of dotimes in processing strings:
Altering the value of var in the body of the loop (by using setq, for example) will have unpredictable, possibly implementation-dependent results. A Common Lisp compiler may choose to issue a warning if such a variable appears in a setq.
See also do-symbols, do-external-symbols, and do-all-symbols.
Mapping is a type of iteration in which a function is successively applied to pieces of one or more sequences. The result of the iteration is a sequence containing the respective results of the function applications. There are several options for the way in which the pieces of the list are chosen and for what is done with the results returned by the applications of the function.
The function map may be used to map over any kind of sequence. The following functions operate only on lists.
[Function]
mapcar function list &rest more-listsFor each of these mapping functions, the first argument is a function and the rest must be lists. The function must take as many arguments as there are lists.
mapcar operates on successive elements of the lists. First the function is applied to the car of each list, then to the cadr of each list, and so on. (Ideally all the lists are the same length; if not, the iteration terminates when the shortest list runs out, and excess elements in other lists are ignored.) The value returned by mapcar is a list of the results of the successive calls to the function. For example:
maplist is like mapcar except that the function is applied to the lists and successive cdr’s of those lists rather than to successive elements of the lists. For example:
mapl and mapc are like maplist and mapcar, respectively, except that they do not accumulate the results of calling the function.
These functions are used when the function is being called merely for its side effects rather than for its returned values. The value returned by mapl or mapc is the second argument, that is, the first sequence argument.
mapcan and mapcon are like mapcar and maplist, respectively, except that they combine the results of the function using nconc instead of list. That is,
and similarly for the relationship between mapcan and mapcar. Conceptually, these functions allow the mapped function to return a variable number of items to be put into the output list. This is particularly useful for effectively returning zero or one item:
In this case the function serves as a filter; this is a standard Lisp idiom using mapcan. (The function remove-if-not might have been useful in this particular context, however.) Remember that nconc is a destructive operation, and therefore so are mapcan and mapcon; the lists returned by the function are altered in order to concatenate them.
Sometimes a do or a straightforward recursion is preferable to a mapping operation; however, the mapping functions should be used wherever they naturally apply because this increases the clarity of the code.
The functional argument to a mapping function must be acceptable to apply; it cannot be a macro or the name of a special operator. Of course, there is nothing wrong with using a function that has &optional and &rest parameters as the functional argument.
X3J13 voted in June 1988 to allow the function to be only of type symbol or function; a lambda-expression is no longer acceptable as a functional argument. One must use the function special operator or the abbreviation #’ before a lambda-expression that appears as an explicit argument form.
X3J13 voted in January 1989 to restrict user side effects; see section 7.9.
Lisp implementations since Lisp 1.5 have had what was originally called “the program feature,” as if it were impossible to write programs without it! The prog construct allows one to write in an Algol-like or Fortran-like statement-oriented style, using go statements that can refer to tags in the body of the prog. Modern Lisp programming style tends to use prog rather infrequently. The various iteration constructs, such as do, have bodies with the characteristics of a prog. (However, the ability to use go statements within iteration constructs is very seldom called upon in practice.)
Three distinct operations are performed by prog: it binds local variables, it permits use of the return statement, and it permits use of the go statement. In Common Lisp, these three operations have been separated into three distinct constructs: let, block, and tagbody. These three constructs may be used independently as building blocks for other types of constructs.
The part of a tagbody after the variable list is called the body. An item in the body may be a symbol or an integer, in which case it is called a tag, or an item in the body may be a list, in which case it is called a statement.
Each element of the body is processed from left to right. A tag is ignored; a statement is evaluated, and its results are discarded. If the end of the body is reached, the tagbody returns nil.
If (go tag) is evaluated, control jumps to the part of the body labelled with the tag.
The scope of the tags established by a tagbody is lexical, and the extent is dynamic. Once a tagbody construct has been exited, it is no longer legal to go to a tag in its body. It is permissible for a go to jump to a tagbody that is not the innermost tagbody construct containing that go; the tags established by a tagbody will only shadow other tags of like name.
The lexical scoping of the go targets named by tags is fully general and has consequences that may be surprising to users and implementors of other Lisp systems. For example, the go in the following example actually does work in Common Lisp as one might expect:
Depending on the situation, a go in Common Lisp does not necessarily correspond to a simple machine “jump” instruction. A go can break up catchers if necessary to get to the target. It is possible for a “closure” created by function for a lambda-expression to refer to a go target as long as the tag is lexically apparent. See chapter 3 for an elaborate example of this.
There are some holes in this specification (and that of go) that leave some room for interpretation. For example, there is no explicit prohibition against the same tag appearing more than once in the same tagbody body. Every implementation I know of will complain in the compiler, if not in the interpreter, if there is a go to such a duplicated tag; but some implementors take the position that duplicate tags are permitted provided there is no go to such a tag. (“If a tree falls in the forest, and there is no one there to hear it, then no one needs to yell ‘Timber!’ ”) Also, some implementations allow objects other than symbols, integers, and lists in the body and typically ignore them. Consequently, some programmers use redundant tags such as — for formatting purposes, and strings as comments:
In certain implementations of Common Lisp they get away with it. Others abhor what they view as an abuse of unintended ambiguity in the language specification. For maximum portability, I advise users to steer clear of these issues. Similarly, it is best to avoid using nil as a tag, even though it is a symbol, because a few implementations treat nil as a list to be executed. To be extra careful, avoid calling from within a tagbody a macro whose expansion might not be a non-nil list; wrap such a call in (progn ...), or rewrite the macro to return (progn ...) if possible.
The prog construct is a synthesis of let, block, and tagbody, allowing bound variables and the use of return and go within a single construct. A typical prog construct looks like this:
The list after the keyword prog is a set of specifications for binding var1, var2, etc., which are temporary variables bound locally to the prog. This list is processed exactly as the list in a let statement: first all the init forms are evaluated from left to right (where nil is used for any omitted init form), and then the variables are all bound in parallel to the respective results. Any declaration appearing in the prog is used as if appearing at the top of the let body.
The body of the prog is executed as if it were a tagbody construct; the go statement may be used to transfer control to a tag.
A prog implicitly establishes a block named nil around the entire prog construct, so that return may be used at any time to exit from the prog construct.
Here is a fine example of what can be done with prog:
which is accomplished somewhat more perspicuously by
The prog construct may be explained in terms of the simpler constructs block, let, and tagbody as follows:
The prog* special operator is almost the same as prog. The only difference is that the binding and initialization of the temporary variables is done sequentially, so that the init form for each one can use the values of previous ones. Therefore prog* is to prog as let* is to let. For example,
returns the car of the value of z.
I haven’t seen prog used very much in the last several years. Apparently splitting it into functional constituents (let, block, tagbody) has been a success. Common Lisp programmers now tend to use whichever specific construct is appropriate.
The (go tag) special operator is used to do a “go to” within a tagbody construct. The tag must be a symbol or an integer; the tag is not evaluated. go transfers control to the point in the body labelled by a tag eql to the one given. If there is no such tag in the body, the bodies of lexically containing tagbody constructs (if any) are examined as well. It is an error if there is no matching tag lexically visible to the point of the go.
The go form does not ever return a value.
As a matter of style, it is recommended that the user think twice before using a go. Most purposes of go can be accomplished with one of the iteration primitives, nested conditional forms, or return-from. If the use of go seems to be unavoidable, perhaps the control structure implemented by go should be packaged as a macro definition.