last revised February 2, 2005 by Henry M. Walker
| CSC 153: Computer Science Fundamentals | Grinnell College | Spring, 2005 |
| Laboratory Exercise Reading | ||
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.
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
let-expression),
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. |