Chapter 5 - Introducing Iteration

Lisp has several ways to do iteration. In this section we'll look at the most common looping constructs. Later, in Chapter 12, we'll look at mapping, then we'll take a brief look at series in Chapter 32; both of these are closely related to iteration.

Simple LOOP loops forever...

The simplest loop in Lisp is just a LOOP form wrapped around whatever you want to repeat. Before you try this next bit of code, know how to interrupt execution of your Lisp system; normally this is Command-period on a Macintosh or Control-Break on a PC.

? (loop
    (print "Look, I'm looping!"))
"Look, I'm looping!" 
"Look, I'm looping!" 
"Look, I'm looping!" 
"Look, I'm looping!" 
"Look, I'm looping!" 
"Look, I'm looping!" 
"Look, I'm looping!" 
"Look, I'm looping!" 
... and so on, until you interrupt execution... 
Aborted
? 

This kind of endless loop has legitimate applications. You're already familiar with one: (LOOP (PRINT (EVAL (READ)))), Lisp's read-eval-print loop.

Actually, your Lisp system does some extra things in its read-eval-print loop:

• it catches all errors to prevent you from inadvertently breaking out of the loop
• it provides a controlled way to exit the loop
• it keeps track of the most recently entered expressions, results, and printed output

But there's a way out!

Most of the time you write a LOOP form, you'd like to have a way out. Fortunately, a RETURN form anywhere inside will cause control to leave the LOOP; any value you specify becomes the value of the LOOP form:

? (loop
    (print "Here I am.")
    (return 17)
    (print "I never got here."))
"Here I am."
17

? (let ((n 0))
    (loop
      (when (> n 10) (return))
      (print n) (prin1 (* n n))
      (incf n)))
0 0
1 1
2 4
3 9
4 16
5 25
6 36
7 49
8 64
9 81
10 100
NIL
?

This example could be done better using a DOTIMES form, see below. But the combination of LOOP and RETURN offers the flexibility to return from the middle of a loop, or even from several places within the loop if need be.

Use DOTIMES for a counted loop

To simply loop for some fixed number of iterations, the DOTIMES form is your best choice. The previous example simplifies to:

? (dotimes (n 11)
    (print n) (prin1 (* n n)))
0 0
1 1
2 4
3 9
4 16
5 25
6 36
7 49
8 64
9 81
10 100
NIL
?

Use DOLIST to process elements of a list

Another common use for iteration is to process each element of a list. DOLIST supports this:

? (dolist (item '(1 2 4 5 9 17 25))
    (format t "~&~D is~:[n't~;~] a perfect square.~%" item (integerp (sqrt item))))
1 is a perfect square.
2 isn't a perfect square.
4 is a perfect square.
5 isn't a perfect square.
9 is a perfect square.
17 isn't a perfect square.
25 is a perfect square.
NIL

In this example, we've done some fancy things with FORMAT. If you want to learn more about what FORMAT can do, you should look ahead now to Chapter 24.

The preceding code used a list of numbers, but Lisp allows a list to contain any kind of object:

? (dolist (item `(1 foo "Hello" 79.3 2/3 ,#'abs))
    (format t "~&~S is a ~A~%" item (type-of item)))
1 is a FIXNUM
FOO is a SYMBOL
"Hello" is a (SIMPLE-BASE-STRING 5)
79.3 is a DOUBLE-FLOAT
2/3 is a RATIO
#<Compiled-function ABS #x1E9CC3E> is a FUNCTION
NIL
? 

Note how we used the backquote and comma to build the list in this example. Do you understand why we did this? All of the list elements up through the ratio 2/3 are self-evaluating; we could have put them in a quoted list as we did in the previous example. But #'abs is equivalent to (function abs) which, when quoted, is just a list of two symbols. To get the function itself into the quoted list, we had to force evaluation of the #'abs form, thus the comma inside the backquoted list.

Like DOTIMES, DOLIST always returns NIL.

DO is tricky, but powerful

The DO form lets you iterate over multiple variables at the same time, using arbitrary forms to step each variable to its next value. Here's an example which both iterates over the elements of a list and runs a counter at the same time:

? (do ((which 1 (1+ which))
       (list '(foo bar baz qux) (rest list)))
      ((null list) 'done)
    (format t "~&Item ~D is ~S.~%" which (first list)))
Item 1 is FOO.
Item 2 is BAR.
Item 3 is BAZ.
Item 4 is QUX.
DONE
? 

To understand this better, let's look at the general syntax of DO, and relate its parts to the example:

(do ((var1 init1 step1)
     (var2 init2 step2)
     ...)
    (end-test result)
  statement1
  ...)

var1       = which
init1      = 1
step1      = (1+ which)
var2       = list
init2      = '(foo bar baz qux)
step2      = (rest list)
end-test   = (null list)
result     = 'done
statement1 = (format t "~&Item ~D is ~S.~%" which (first list))