| 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
