Page:Scheme - An interpreter for extended lambda calculus.djvu/8

From Wikisource
Jump to: navigation, search
This page has been proofread, but needs to be validated.
Sussman and Steele December 22, 1975 7 SCHEME Programming Examples

The semantics of this are that the variables are bound and initialized to the values of the <initi> expressions, which must all be evaluated in the environment outside the DO; then the predicate <pred> is evaluated in the new environment, and if TRUE, the <value> is evaluated and returned. Otherwise the body is evaluated, then each of the steppers <stepi> is evaluated in the current environment, all the variables made to have the results as their values, and the predicate evaluated again, and so on.

For example, the following MacLISP function:

(DEFUN REV (L)
       (DO ((L1 L (CDR L1))
            (ANS NIL (CONS (CAR L1) ANS)))
           ((NULL L1) ANS)))

computes the reverse of a list. In SCHEME, we could write the same function, in the same iterative style, as follows:

(DEFINE REV
    (LAMBDA (L)
        (LABELS ((DOLOOP (LAMBDA (L1 ANS)
                             (IF (NULL L1) ANS
                                 (DOLOOP (CDR L1)
                                         (CONS (CAR L1) ANS))))))
                (DOLOOP L NIL))))

From this we can infer a general way to express iterations in SCHEME in a manner isomorphic to the MacLISP DO:

(LABELS ((DOLOOP
          (LAMBDA (<dummy> <var1> <var2> ... <varn>)
              (IF <pred> <value>
                  (DOLOOP <body> <step1> <step2> ... <stepn>)))))
        (DOLOOP NIL <init1> <init2> ... <initn>))

This is in fact what the supplied DO AMACRO expands into. Note that there are no side effects in the steppings of the iteration variables.

Another Way To Do Recursion

Now consider the following alternative definition of FACT. It has an extra argument, the continuation [Reynolds], which is a function to call with the answer, when we have it, rather than return a value; that is, rather than ultimately reducing to the desired value, it reduces to a combination which is the application of the continuation to the desired value.