Lambda: The Ultimate Imperative/Simple Loops

by Guy L. Steele, Jr. and Gerald Jay Sussman

1. Simple Loops

By simple loops we mean constructs which enable programs to execute the same piece of code repeatedly in a controlled manner. Variables may be made to take on different values during each repetition, and the number of repetitions may depend on data given to the program.

1.1. Simple Recursion

One of the easiest ways to produce a looping control structure is to use a recursive function, one which calls itself to perform a subcomputation. For example, the familiar factorial function may be written recursively in ALGOL:

integer procedure fact(n); value n; integer n;
   fact := if n=0 then 1 else n*fact(n-1);

The invocation fact(n) computes the product of the integers from 1 to n using the identity n!=n(n-1)! (n>0). If n is zero, 1 is returned; otherwise fact calls itself recursively to compute (n-1)!, then multiplies the result by n and returns it.

This same function may be written in SCHEME as follows:

(DEFINE FACT
   (LAMBDA (N) (IF (= N 0) 1
                   (* N (FACT (- N 1))))))

SCHEME does not require an assignment to the "variable" fact to return a value as ALGOL does. The IF primitive is the ALGOL if-then-else rendered in LISP syntax. Note that the arithmetic primitives are prefix operators in SCHEME.

1.2. Iteration

There are many other ways to compute factorial. One important way is through the use of iteration.

A common iterative construct is the DO loop. The most general form we have seen in any programming language is the MacLISP DO [Moon 74]. It permits the simultaneous initialization of any number of control variables and the 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.

(DEFINE FACT
   (LAMBDA (M)
       (LABELS ((FACT1 (LAMBDA (M ANS)
                           (IF (= M 0) ANS
                                   (FACT1 (- M 1)
                                          (* M ANS))))))
                (FACT1 N 1))))

From this we can infer a general way to express iterations in SCHEME in a manner isomorphic to the MacLISP DO. The expansion of the general DO loop

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

is this:

(LABELS ((DOLOOP
          (LAMBDA (DUMMY <var1> <var2> ... <varn>)
              (IF <pred> <value>
                  (DOLOOP <body> <step1> <step2> ... <stepn>)))))
        (DOLOOP NIL <init1> <init2> ... <initn>))

The identifiers DOLOOP and DUMMY are chosen so as not to conflict with any other identifiers in the program.

Note that, unlike most implementations of DO, there are no side effects in the steppings of the iteration variables. DO loops are usually modelled using assignment statements. For example:

for x := a step b until c do <statement>;

can be modelled as follows: [Naur 63]

begin
    x := a;
 L: if (x-c)*sign(b) > 0 then go to Endloop;
    <statement>;
    x := x+b;
    go to L;
 Endloop:
end;

Later we will see how such assignment statements can in general be modelled without using side effects.