Page:AIM-353.djvu/5

 Steele and Sussman March 10, 1976 3 LAMBDA: The Ultimate Imperative

simultaneous stepping of these variables by arbitrary functions at each iteration step. The loop is terminated by an arbitrary predicate, and an arbitrary value may be returned. The `DO` loop may have a body, a series of expressions executed for effect on each iteration. A version of the MacLISP `DO` construct has been adopted in SCHEME.

The general form of a SCHEME `DO` is:

(DO ((<var1> <init1> <step1>)
(<var2> <init2> <step2>)
. . .
(<varn> <initn> <stepn>))
(<pred> <value>)
<optional body>)

The semantics of this are that the variables are bound and initialized to the values of the `<initi>` expressions, which must all be evaluated in the environment outside the `DO`; then the predicate `<pred>` is evaluated in the new environment, and if `TRUE`, the `<value>` is evaluated and returned. Otherwise the `<optional body>` is evaluated, then each of the steppers `<stepi>` is evaluated in the current environment, all the variables made to have the results as their values, the predicate evaluated again, and so on.

Using `DO` loops in both ALGOL and SCHEME, we may express `FACT` by means of iteration.

integer procedure fact(n); value n; integer n;
begin
integer m, ans;
ans := 1;
for m := n step -1 until 0 do ans := m*ans;
fact := ans;
end;

(DEFINE FACT
(LAMBDA (N)
(DO ((M N (- M 1))
(ANS 1 (* M ANS)))
((= M 0) ANS))))

Note that the SCHEME `DO` loop in `FACT` has no body — the stepping functions do all the work. The ALGOL `DO` loop has an assignment in its body; because an ALGOL `DO` loop can step only one variable, we need the assignment to step the the variable "manually".

In reality the SCHEME `DO` construct is not a primitive; it is a macro which expands into a function which performs the iteration by tail-recursion. Consider the following definition of `FACT` in SCHEME. Although it appears to be recursive, since it "calls itself", it is entirely equivalent to the `DO` loop given above, for it is the code that the `DO` macro expands into! It captures the essence of our intuitive notion or iteration, because execution of this program will not produce internal structures (e.g. stacks or variable bindings) which increase in size with the number of iteration steps. 