# Lambda: The Ultimate Imperative/Simple Loops

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