# Page:AIM-353.djvu/4

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

between statements and expressions, escape operators (such as Landin's J-operator [Landin 65] and Reynold's escape expression [Reynolds 72]), and fluid (dynamically bound) variables. The fourth is Parameter Passing Mechanisms, such as ALGOL call-by-name and FORTRAN call-by-location.

Some of the models presented here are already well-known, particularly those for GO TO and assignment. [McCarthy 60] [Landin 65] [Reynolds 72] Those for escape operators, fluid variables, and call-by-need with side effects are new.

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