Lambda: The Ultimate Imperative/Imperative Programming

by Guy L. Steele, Jr. and Gerald Jay Sussman

Imperative Programming

Lambda calculus (and related languages, such as "pure LISP") is often used for modelling the applicative constructs of programming languages. However, they are generally thought of as inappropriate for modelling imperative constructs. In this section we show how imperative constructs may be modelled by applicative SCHEME constructs.

Compound Statements

The simplest kind of imperative construct is the statement sequencer, for example the compound statement in ALGOL:

begin
       S1:
       S2;
end

This construct has two interesting properties:

1. It performs statement S1 before S2, and so may be used for sequencing.
2. S1 is useful only for its side effects. (In ALGOL, S2 must also be a statement, and so is also useful only for side effects, but other languages have compound expressions containing a statement followed by an expression.)

The ALGOL compound statement may actually contain any number of statements, but such statements can be expressed as a series of nested two-statement compounds. That is:

begin
       S1;
       S2;
       ...
       Sn-1;
       Sn;
end

is equivalent to:

begin
       S1;
       begin
              S2;
              begin
                     ...
                            begin
                                   Sn-1;
                                   Sn;
                            end;
                     ...
              end;
       end;
end

It is not immediately apparent that this sequencing can be expressed in a purely applicative language. We can, however, take advantage of the implicit sequencing of applicative order evaluation. Thus, for example, we may write a two-statement sequence as follows:

((LAMBDA (DUMMY) S2) S1)

where DUMMY is an identifier not used in S2. From this it is manifest that the value of S1 is ignored, and so is useful only for side effects. (Note that we did not claim that S1 is expressed in a purely applicative language, but only that the sequencing can be so expressed.) From now on we will use the form (BLOCK S1 S2) as an abbreviation for this expression, and (BLOCK S1 S2 ... Sn-1 Sn) as an abbreviation for

(BLOCK S1 (BLOCK S2 (BLOCK ... (BLOCK Sn-1 Sn)...)))

The GO TO Statement

A more general imperative structure is the compound statement with labels and GO TOs. Consider the following code fragment due to Jacopini, taken from Knuth: [Knuth 74]

begin
L1: if B1 then go to L2;
    SI;
    if B2 then go to L2;
    S2;
    go to L1;
L2: S3;
end

It is perhaps surprising that this piece of code can be syntactically transformed into a purely applicative style. For example, in SCHEME we could write:

(LABELS ((L1 (LAMBDA ()
                     (IF B1 (L2)
                         (BLOCK S1
                                (IF B2 (L2)
                                    (BLOCK S2 (L1)))))))
         (L2 (LAMBDA () S3)))
        (L1))

As with the DO loop, this transformation depends critically on SCHEME's treatment of tail-recursion and on lexical scoping of variables. The labels are names of functions of no arguments. In order to "go to" the labeled code, we merely call the function named by that label.

Simple Assignment

Of course, all this sequencing of statements is useless unless the statements have side effects. An important side effect is assignment. For example, one often uses assignment to place intermediate results in a named location (i.e. a variable) so that they may be used more than once later without recomputing them:

begin
   real a2, sqrtdisc;
   a2 := 2*a;
   sqrtdisc := sqrt(b↑2 - 4*a*c);
   root1 := (- b + sqrtdisc) / a2;
   root2 := (- b - sqrtdisc) / a2;
   print(root1);
   print(root2);
   print(root1 + root2);
end

It is well known that such naming of intermediate results may be accomplished by calling a function and binding the formal parameter variables to the results:

((LAMBDA (A2 SQRTDISC)
         ((LAMBDA (ROOT1 ROOT2)
                  (BLOCK (PRINT ROOT1)
                         (PRINT ROOT2)
                         (PRINT (+ ROOT1 ROOT2))))
          (/ (+ (- B) SQRTDISC) A2)
          (/ (- (- B) SQRTDISC) A2)))
 (* 2 A)
 (SQRT (- (↑ B 2) (* 4 A C))))

This technique can be extended to handle all simple variable assignments which 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).

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.