Page:AIM-353.djvu/10

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