| 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.
