|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 ((<var1> <init1> <step1>)
(<var2> <init2> <step2>)
. . .
(<varn> <initn> <stepn>))
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
<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.
DO loops in both ALGOL and SCHEME, we may express
FACT by means of iteration.
integer procedure fact(n); value n; integer n;
integer m, ans;
ans := 1;
for m := n step -1 until 0 do ans := m*ans;
fact := ans;
(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 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.