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