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

Most LISP compilers compile `DO`

expressions by macro-expansion. We have already seen one way to do this in SCHEME using only variable binding. A more common technique is to expand the `DO`

into a `PROG`

, using variable assignments instead of bindings. Thus the iterative factorial program:

(DEFINE FACT

(LAMBDA (N)

(DO ((M N (- M 1))

(ANS 1 (* M ANS)))

((= M 0) ANS))))

would expand into:

(DEFINE FACT

(LAMBDA (N)

(PROG (M ANS)

(SSETQ M N

ANS 1)

LP (IF (= M 0) (RETURN ANS))

(SSETQ M (- M 1)

ANS (* M ANS))

(GO LP))))

where `SSETQ`

is a simultaneous multiple assignment operator. (`SSETQ`

is not a SCHEME (or LISP) primitive. It can be defined in terms of a single assignment operator, but we are more interested here in `RETURN`

than in simultaneous assignment. The `SSETQ`

's will all be removed anyway and modelled by lambda binding.) We can apply the same technique we used before to eliminate GO TO statements and assignments from compound statements:

(DEFINE FACT

(LAMBDA (N)

(LABELS ((L1 (LAMBDA (M ANS)

(LP N 1)))

(LP (LAMBDA (M ANS)

(IF (= M 0) (RETURN ANS)

(L2 M ANS))))

(L2 (LAMBDA (M ANS)

(LP (- M 1) (* N ANS)))))

(L1 NIL NIL))))

We still haven't done anything about `RETURN`

. Let's see...

`==>`

the value of `(FACT 0)`

is the value of `(L1 NIL NIL)`

`==>`

which is the value of `(LP 0 1)`

`==>`

which is the value of `(IF (= 0 0) (RETURN 1) (L2 0 1))`

`==>`

which is the value of `(RETURN 1)`

Notice that if `RETURN`

were the __identity function__ `(LAMBDA (X) X)`

, we would get the right answer. This is in fact a general truth: if we just replace a call to `RETURN`

with its argument, then our old transformation on compound statements extends to general compound expressions, i.e. `PROG`

.