CSC 153: Computer Science Fundamentals Grinnell College Spring, 2005 Laboratory Exercise Reading

# Iteration

## Abstract

This reading describes a useful approach for repeating processing, called iteration, using Scheme's do-expression. Iteration is useful problem-solving technique when processing must cycle through a sequence of steps, using successive values of variables.

## Discussion

Now that our toolbox contains local bindings to variables, we'll be seeing more and more cases in which it is useful to perform some procedure call or sequence of procedure calls repeatedly, for the sake of the side effects on structures or variables or for input or output. For example, the printing of the table of numbers and their square roots involved the repeated output of a line of a number and its root.

Most of these iterative constructions have a common form, and Scheme provides a special expression type to capture this form concisely and efficiently: the `do`-expression. A `do`-expression has the following structure:

```(do loop-control-list
(exit-test postlude)
body)
```
• The loop-control-list sets up bindings for any local variables that the `do`-expression will use; almost always, there is at least one "loop control variable" that counts off repetitions of the loop or positions in a string or some such thing. A loop-control list is a list of zero or more loop-control specifications, one for each variable that is to be bound locally. A loop-control specification is a list in which

• the first element is the loop-control variable,
• the second is an initializing expression (as in a `let`-expression),
• and the third is an updating expression -- an expression that is evaluated after the body of a loop, to yield a new value of the loop-control variable for the next iteration.
• The exit-test is a single expression that is evaluated to determine when enough iterations have been performed; the loop is finished as soon as the value of exit-test is anything other than `#f`.

• The postlude, which is optional, is a sequence of expressions to be evaluated after the exit test has succeeded; the value of the last of these expressions becomes the value of the entire `do`-expression. (If the postlude is omitted, the value of the `do`-expression is unspecified and only its side effect is of interest.)

• The body, which is also optional, is a sequence of expressions to be evaluated, in order, on each iteration. All of the expressions in the body are evaluated only for their side effects; the values are discarded.

Here's a simple example of a `do`-expression. We write a procedure `display-countdown` that takes one argument, a non-negative integer, and prints out the positive integers equal to or less than its argument, in descending order, one per line. Thus, the interaction might look as follows:

```> (display-countdown 3)
3
2
1
Blast off!
```
The following code demonstrates a simple solution to this problem:
```(define display-countdown
(lambda (start)
;Pre-condition:  start is a nonnegative integer
;Post-condition:  prints the numbers start, ..., 1, 0 on separate lines
(do ((remaining start (- remaining 1)))
((zero? remaining) "Blast off!")
(display remaining)
(newline))))
```

Let's trace through the execution of a call to this procedure, using the above example `(display-countdown 3)`:

• The `do`-expression has just one loop-control variable in this case, namely `remaining`; the first thing that happens is that a local binding for `remaining` is created, with the initial value of `start`, which is 3. The updating expression ```(- remaining 1)``` is ignored at this point, because we haven't completed any iterations of the loop yet.

• Next, the exit test, `(zero? remaining)`, is evaluated. Since 3 is not zero, the exit is not taken.

• Next, the body of the loop is evaluated. The body in this case consists of the two procedure calls `(display remaining)` and `(newline)`. So the number 3 is printed on a line by itself. This completes the first iteration.

• Now the updating expression for the loop-control variable is evaluated. The value of `(- remaining 1)` is 2; this becomes the new value of `remaining` for the next iteration.

• Next, the exit test is evaluated again. 2 is not zero, so the exit is not taken; instead, the loop body is evaluated again, resulting in the printing of the number 2 on a line by itself. This completes the second iteration.

• The loop-control variable `remaining` is updated again, changing from 2 to 1. The exit test comes out `#f` again, since 1 is not zero; the loop body is evaluated once more, so 1 is printed on a line by itself. This completes the third iteration.

• The next updating of `remaining` changes its value from 1 to 0. When the exit test is evaluated this time, its value is `#t`, so the loop is finished.

• The postlude is evaluated. In this case, the postlude is a single string constant, `"Blast off!"`; this string is returned as the value of the `do`-expression, and hence the value of the procedure call.

As at another example of the use of `do`-expressions, here is a procedure that takes a list as argument and returns the list in reverse order. That is, we write out explicit code for Scheme's `reverse` procedure.

```(define reverse-list
(lambda (ls)
;Pre-condition:  ls is a list
;Post-condition:  returns the elements of ls in reverse order on a list
(if (list? ls)
(do ((new-ls '() (cons (car old-ls) new-ls))
(old-ls ls (cdr old-ls)))
((null? old-ls) new-ls)
)
)
)
)

> (reverse-list '(3 1 4 1 5 9))
(9 5 1 4 1 3)
```

This time there are two loop-control variables: `new-ls` provides a list of elements already processed (starting with nil, while `old-ls` contains the list elements not yet processed. The iteration moves an element from `old-ls` to `new-ls` as part of the updating of variables. the body of the `do`-expression is null.

Overall, `do`-expressions can be used for clarity and conciseness in many of the situations.

This document is available on the World Wide Web as

```http://www.walker.cs.grinnell.edu/courses/153.sp05/readings/reading-iteration.shtml
```

 created April 21, 1997 by John David Stone last revised February 2, 2005 by Henry M. Walker  For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.