To iterate means to perform an action more than once, or until some terminating condition has been meet. Iteration may also be referred to as looping or mapping, depending on the context in which it occurs. Mapping means to apply a function (the action) to individual elements in a sequence of data. For a full discussion of sequences and mapping functions in Lisp, consult (the book) Common Lisp the Language, chapters 14-17.
Iteration lends itself to tasks that can be broken down into the repetition of a series of steps. Consider this program that counts the number of even integers from 0 to 3. Without using iteration, the program looks like:
(setf int 0 sum 0) (when (evenp int) (setf sum (1+ sum))) (setf int (1+ int)) (when (evenp int) (setf sum (1+ sum))) (setf int (1+ int)) (when (evenp int) (setf sum (1+ sum))) (setf int (1+ int)) (when (evenp int) (setf sum (1+ sum))) (setf int (1+ int))
Except for the first line, the example consists of two actions performed over and over again: testing the current value of the stepping variable int and incrementing sum if it is even; then incrementing int. This program works but it has a number drawbacks. First, it is a tedious textual repetion of two ideas. Second, changing the program (to count oddness, say) means making changes in four different places. Third, the program is not a genenal solution; it cannot test the numbers 0 to 9, even though the same basic idea applies.
These deficiencies can be eliminated if we express the task using iteration. Most languages like C and Lisp provide "interation constructs", or "templates" for describing repetative tasks. These templates typically handle everything but the actual task definition:
Establishing variables and incrementing values
Repeatedly execting the task steps.
Testing for completion and returning values.
Here are three different solutions to the program using the interative constucts discussed in this document:
(setf sum 0) (dotimes (int 4) (when (evenp int) (incf sum))) (setf sum 0) (dolist (int '(0 1 2 3)) (when (evenp int) (incf sum))) (setf sum 0) (loop for int below 4 when (evenp int) do (incf sum))
Common Lisp provides the dotimes and dolist macros for performing simple iteration.
|
dotimes (var times [value]) {forms}* |
[Macro] |
dotimes executes forms in its body times number of times. var is a variable that dotimes sets to the current iteration count, from 0 to times-1. value is an optional value to return as the result of the dotimes expression. dotimes returns nil if value is not supplied.
;; print the value of i ten times. (dotimes (i 10) (print i)) ;; return the number of times i equals random number choice (setf sum 0 max 50) (dotimes (i max sum) (when (= i (random max)) (incf sum)))
|
dolist (var list [value]) {forms}* |
[Macro] |
dolist is similar to dotimes, except that the variable var receives succesive elements from list. Iteration stops when all the elements from list have been enumerated.
The loop macro is the most flexible facility for defining iterative processes in Lisp. A loop expression consists of a series of clauses strung together in an English-like syntax; each clause combines a loop operator with expressions that produce values. loop supports several types of clauses. The three most important are iteration clauses, action clauses, and conditional clauses. An iteration clause establishes local variables and their starting and/or ending conditions. An action clause executes task statements and (possibly) gathers values to return as the result of the loop expression. Conditional clauses allows contraints to be placed on the scope of the iteration or on the applicability of action clauses.
An iteration clause declares local varibles and/or establish limits for the iterative process. If iteration limits are not established a loop process will never stop. For example, this loop will print random numbers until the process was explicitily aborted by typing Command-. (MCL) or C-c C-c (ACL, Clisp).
(loop do (print (random 1000)))
Here are the most common iteration clauses:
(loop repeat 10 collect (random 40))
(loop for v in '(a c b d) collect (list v v))
(loop for v on '(a c b d) by #'cddr collect v)
(loop for i below 10 collect i) (loop for i from 1 to 2 by .1 collect i) (loop for i from 10 downto 0 collect i) (loop for i from 10 by .5 above 8 collect i)
(loop for x = (random 10) repeat 5 collect x)
Action clauses perform tasks and (possibly) return values from the loop expression when it terminates.
(loop repeat 10 do (print (random 50)))
(loop repeat 10 collect (random 50))
(loop repeat 10 count (evenp (random 50)))
(loop repeat 10 sum (random 50))
(loop repeat 10 minimize (random 50))
(loop repeat 10 maximize (random 50))
Conditional clauses place contraints on the applicability of action clauses, or on how many times the loop itself will iterate.
(loop for i below 10 when (evenp n) collect i)
(loop for i below 0 unless (evenp n) collect i)
(loop for n = (random 10) while (evenp n) collect n)
(loop for n = (random 10) until (evenp n) collect n)
The iteration possibilities afforded by loop are almost limitless. The following discussion points out some of the more common ones.
The with clause allows local loop variables to be declared and initialized.
(loop with i = 10 and j and k = (random 100000)
repeat i
for r = (random i)
collect (list r j k))A single loop expression may contain more than one iteration and/or action clause. The first clause that terminates defines the scope of the iteration.
(loop for i below 10
for j = (random 10)
collect i collect j)do clauses are often used in conjunction with other actions:
(loop with i = -100
for j below 10
do (decf i j)
collect (list j i))Parallel clauses may be made dependant on a single condition using the and conjunction:
(loop for i below 10
for j = (random 10)
when (evenp j) collect i and collect j)If specified, a finally clause is executed after the iteration has terminated. Use an explicit return expression to force loop to return a value from its finally clause. finally is often used in conjunction with the into modifier for action clauses that accumulate values.
(loop repeat 10
collect (random 10) into res
finally (return (remove 3 res))