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); valuen; integern;

fact:= ifn=0 then 1 elsen*fact(n-1);

The invocation

computes the product of the integers from 1 to *fact*(*n*)*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