Now that our toolbox contains structure mutation and assignment 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 iterative versions of the sorting algorithms in chapter 10 of the textbook involve repeated mutations on the vectors to be sorted.
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 vector 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. Remember the
display-countdown procedure from the lab on tail-call elimination? It is
supposed to take one argument, a non-negative integer, and print out the
positive integers equal to or less than its argument, in descending order,
one per line. As its value, it should return the string "Blast
off!".
(define display-countdown
(lambda (start)
(do ((remaining start (- remaining 1)))
((zero? remaining) "Blast off!")
(display remaining)
(newline))))
Let's trace through the execution of a call to this procedure, say
(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.
> (display-countdown 3) 3 2 1 "Blast off!"
Write a procedure display-count that takes two arguments,
start and finish, and counts upwards from
start to finish, displaying each number on a
separate line. (The preconditions are that start and
finish must both be exact integers and start must
be less than or equal to finish.) The
display-count procedure should return the number of lines of
output it produces.
Let's look at two more examples of the use of do-expressions:
first, a procedure that takes as arguments two vectors of equal length
containing numbers and returns a similar vector in which the elements are
the sums of the corresponding elements of the argument vectors:
(define vector+
(lambda (augend addend)
(let* ((len (vector-length augend))
(result (make-vector len)))
(do ((position 0 (+ position 1)))
((= position len) result)
(vector-set! result position (+ (vector-ref augend position)
(vector-ref addend position)))))))
> (vector+ '#(3 1 4 1 5 9) '#(2 7 1 8 2 8))
#(5 8 5 9 7 17)
Second, here is a version of the vector-reverse! procedure
that uses a do-expression. (Compare it with program 9.26 on
page 287 of the textbook.) The vector-reverse! procedure
takes any vector as its argument and destructively rearranges its elements
into the reverse order:
(define vector-reverse!
(lambda (vec)
(do ((left-index 0 (+ left-index 1))
(right-index (- (vector-length vec) 1) (- right-index 1)))
((<= right-index left-index) vec)
(let ((temp (vector-ref vec left-index)))
(vector-set! vec left-index (vector-ref vec right-index))
(vector-set! vec right-index temp)))))
This time there are two loop-control variables: left-index
starts with the lowest-numbered position of the vector and increases by 1
on each iteration, and right-index starts with the
highest-numbered position (one less than the length of the vector) and
decreases by 1 on each iteration. The iteration stops when
right-index is less than or equal to left-index
(because the indices have met or crossed in the middle of the vector). On
each iteration, the body of the do-expression swaps the
elements in the positions marked by the indices. The
vector-reverse! procedure returns the mutated vector (because
the only expression in the postlude, the variable vec, has
this vector as its value).
> (define foo '#(3 1 4 1 5 9 2 6 5)) > (vector-reverse! foo) #(5 6 2 9 5 1 4 1 3) > foo #(5 6 2 9 5 1 4 1 3)
Define a Scheme procedure that takes any non-empty vector of real numbers
as its argument and returns the number that is the greatest element of the
vector. Use a do-expression to run through the positions of
the vector.
Rewrite the definition of the vector-map! procedure (from the
lab on structure mutation), iterating
with a do-expression instead of using the named
let-expression to manage the recursion.
Do-expressions can be used for clarity and concision in many
of the situations where we have previously employed named
let-expressions. For example, here is a version of the
copy-file procedure from the second lab on files.
(Copy-file takes two strings, the first of which is the name
of an existing file and the second the name of a file to be created, and
copies the existing file into the new file character by character.)
(define copy-file
(lambda (source-file-name target-file-name)
(let ((source (open-input-file source-file-name))
(target (open-output-file target-file-name)))
(do ((next-character (read-char source) (read-char source)))
((eof-object? next-character) (close-input-port source)
(close-output-port target))
(write-char next-character target)))))
Notice that the initialization expression for the loop-control variable
next-character is the same as the updating expression. This
is not unusual in procedures that operate on files.
Finally, here is yet another version of the sum procedure,
which takes any list of numbers as its argument and returns their sum:
(define sum
(lambda (ls)
(do ((rest ls (cdr rest))
(so-far 0 (+ so-far (car rest))))
((null? rest) so-far))))
In this example, there are two loop-control variables, rest
and so-far. The variable rest is initially the
entire list of numbers; but it is changed on each iteration to become the
cdr of its value in the preceding iteration. So-far is
initially 0; at the end of each subsequent iteration, the first element of
the old value of rest is recovered and added to the old value
of so-far to yield its new value. The iteration stops when
rest has been reduced to the null list; at that point the
final value of so-far is returned.
This do-expression has zero expressions in its body! All the
work is done in the updating and exit-testing parts of the expression.
This too is a common pattern in Scheme.
This example also reveals that the loop-control variables are updated
simultaneously (as in a let-expression), not successively (as
in a let*-expression); the identifier rest in
both updating expressions refers to the old value of
rest, not the new one.
Define a procedure named gibber that takes two arguments,
a natural number count and a string str at least
one character long, and uses display to write out
count characters, each one selected randomly, independently,
and with equal probability from positions in str. Finish with
a call to (newline). (Hint: You'll need Chez Scheme's
random procedure. Recall that, when given an exact positive
integer k, the call (random k) returns an integer
in the range from 0 up to, but not including, k.)
> (gibber 15 "This is the forest primeval.") rihse.siosv f. > (gibber 15 "This is the forest primeval.") etisrTsT Th pie > (gibber 50 "HT") HTHTTHTHHTTTTHTHHTHHHHHHTHHHHHHTTHTHHTTTHHHTTHHTTT > (gibber 24 "123456") 513562513545333364113622
Define a procedure Cartesian-square that takes any list
ls as its argument and returns a list of pairs that contains
every pair that can be formed from elements of ls (repetitions
allowed).
> (Cartesian-square '(a b)) ((a . a) (a . b) (b . a) (b . b)) > (Cartesian-square '(0 1 0)) ((0 . 0) (0 . 1) (0 . 0) (1 . 0) (1 . 1) (1 . 0) (0 . 0) (0 . 1) (0 . 0)) > (Cartesian-square '() ()
For those who have completed exercise #3:
Using a do-expression, write a procedure that plays one round
of jeu-vain, returning #t if the player wins and
#f if she loses.
This document is available on the World Wide Web as
http://www.math.grin.edu/courses/Scheme/spring-1998/iteration.html
created April 21, 1997
last revised June 21, 1998