The DO iterative form in Lisp is very flexible, with a simple syntax and clean semantics. Many students however have trouble when they first begin trying to use it. The following method are intended to help you get from an iterative algorithm to a well-formed and efficient DO loop.

Why Do DO?

Here are two examples of simple loops, in DOLIST and DO form.

Find first odd number
(dolist (x lst)
  (when (oddp x)
    (return x)))
(do ((ll lst (cdr ll)))
  ((oddp (car ll)) (car ll)))
Collect odd numbers
(let ((odds nil))
  (dolist (x lst odds)
    (when (oddp x)
      (push x odds))))
(do ((ll lst (cdr ll))
     (odds nil
          (if (oddp (car ll)
              (cons (car ll) odds)
            odds))))
  ((null ll)) odds))

Clearly there is nothing hard to read or understand about the DOLIST versions. It is also the case that there is nothing hard to read about the DO versions, if you know DO. If you don't, then the lack of symbols like WHEN and RETURN can be confusing.

So why do I push all students to master DO? Because

DOLIST and DOTIMES are great when you need to loop over one list or N times and do some side effect, like printing or updating an array. As soon as you need to manage several variables, or iterate in a non-standard way, use DO. And the best way to know how to write a clean DO in complicated cases, is to practice writing them in simple cases.


The Structure of DO

The syntax of DO is

(DO ((var1 init1 incr1)               ; the variable clauses
     (var2 init2 incr2)
     ...)
   (exit-test exit-exp exit-exp ...)  ; the exit clause
  body-exp                            ; the body
  body-exp
  ...)

The semantics is


Turning an Iterative Algorithm into a DO

First, you need to identify the following elements of your algorithm.

Identify the steppers

A stepper is a variable that controls how long the loop runs. It might be a variable stepping through a list or a counter stepping from 0 up or N down. Each stepper has

Many loops have only one stepper, but they might have several, e.g., a loop that steps through a list and also has a counter.

What are the accumulators?

An accumulator is a variable or variables into which you collect your answer. Each accumulator has

Most loops have at most one accumulator, but you can have more, e.g., a loop that collects odd numbers into one list and even numbers into another.

Normally, test results, e.g., finding an item with a particular property, should not be thought of as accumulators. There's a better way to handle them.

What are the exit tests?

An exit test says when the loop should stop. There are two kinds of exit tests. First, there are tests for the end points of the steppers, e.g.,

You always have at least one stepper exit test. You rarely have more, even with two or more steppers, because usually just one stepper, e.g., the list stepper, is in charge.

Second, there may be exit tests for special conditions, e.g., finding an odd number. If you have this situation, then make the exit test an OR. The stepper exit test comes first, then the special test, e.g.,

(OR (NULL L) (ODDP (FIRST L)))

Use exit tests instead of a pseudo-accumulator holding the result of some test.

What is the return value?

Every loop returns something. Typically, it will be the value of some accumulator. If you have a loop with no accumulator, i.e., you have a loop that exits when some special test is true, then the return value will be determined by whether the test was ever true or not.

Make sure you understand what the return value should be if the loop executes 0 times.

Putting the pieces together

Make a DO variable clause for each stepper. The init should be the start value, and the incr should be whatever expressions "bumps" the stepper appropriately. We'll get to where to put the end expression shortly. Some examples:

Make a DO variable clause for each accumulator. The init should be the initial "empty" value. It should be the value you would return if the loop were to execute zero times. A common mistake here is forgetting about the empty loop case, but it's essential to building a clear and general DO.

The incr should be whatever expressions adds to the accumulator appropriately on every iteration. A common mistake here is writing an expression that returns the correct value sometimes but returns NIL in other cases, where, normally, NIL is not the right value.

Some examples:

Now put your exit tests in the exit clause. If you have both stepper end tests and special end tests, then make the exit test an OR. Put the stepper exit test first, then the special test, e.g.,

(OR (NULL L) (ODDP (FIRST L)))

Finally, put in the exit expression in the exit clause. This is task-dependent, but for loops without a special exit test, the exit value is usually is one of the following forms:

For loops with a special exit test, the exit value is based on whether or not we reached the end of a stepper or the special condition. Typical return values with loops involving special exit tests, from simplest on, are:

Note that the above method never generates a DO body. A DO body is only needed when your loop is not just accumulating a value or stopping on a special case. If instead your loop is being used to perform a side effect operation (printing, changing an array or table, ...), the side effect should go in the body, BUT it's probably the case a DOLIST or DOTIMES would be a better choice.

Faculty: Chris Riesbeck
Time: Monday, Wednesday, Friday: 1pm - 2pm
Location:Annenberg G15

Contents

Important Links