Page:AIM-353.djvu/10

From Wikisource
Jump to navigation Jump to search
This page has been validated.
Steele and Sussman March 10, 1976 8 LAMBDA: The Ultimate Imperative

appear as statements in blocks, even if arbitrary GO TO statements also appear in such blocks. {Note Mccarthywins}

For example, here is a program which uses GO TO statements in the form presented before; it determines the parity of a non-negative integer by counting it down until it reaches zero.

begin
L1: if a = 0 then begin parity := 0; go to L2; end;
    a := a - 1;
    if a = 0 then begin parity := 1; go to L2; end;
    a := a - 1;
    go to L1;
L2: print(parity);
end

This can be expressed in SCHEME:

(LABELS ((L1 (LAMBDA (A PARITY)
                     (IF (= A 0) (L2 A 0)
                         (L3 (- A 1) PARITY))))
         (L3 (LAMBDA (A PARITY)
                     (IF (= A 0) (L2 A 1)
                         (L1 (- A 1) PARITY))))
         (L2 (LAMBDA (A PARITY)
                     (PRINT PARITY))))
        (L1 A PARITY))

The trick is to pass the set of variables which may be altered as arguments to the label functions. {Note Flowgraph} It may be necessary to introduce new labels (such as L3) so that an assignment may be transformed into the binding for a function call. At worst, one may need as many labels as there are statements (not counting the eliminated assignment and GO TO statements).

Compound Expressions

At this point we are almost in a position to model the most general form of compound statement. In LISP, this is called the "PROG feature". In addition to statement sequencing and GO TO statements, one can return a value from a PROG by using the RETURN statement.

Let us first consider the simplest compound statement, which in SCHEME we call BLOCK. Recall that

(BLOCK S1 S2)

is defined to be

((LAMBDA (DUMMY) S2) S1)

Notice that this not only performs S1 before S2, but also returns the value of S2. Furthermore, we defined (BLOCK S1 S2 ... Sn) so that it returns the value of Sn. Thus BLOCK may be used as a compound expression, and models a LISP PROGN, which is a PROG with no GO TO statements and an implicit RETURN of the last "statement" (really an expression).