Lambda: The Ultimate Imperative/Continuations

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

== Continuations ==

Up to now we have thought of SCHEME’s LAMBDA expressions as functions, and of a combination such as (G (F X Y)) as meaning “apply the function F to the values of X and Y, and return a value so that the function G can be applied and return a value ...” But notice that we have seldom used LAMBDA expressions as functions. Rather, we have used them as control structures and environment modifiers. For example, consider the expression:

(BLOCK (PRINT 3) (PRINT 4))

This is defined to be an abbreviation for:

((LAMBDA (DUMMY) (PRINT 4)) (PRINT 3))

We do not care about the value of this BLOCK expression; it follows that we do not care about the value of the (LAMBDA (DUMMY) ...). We are not using LAMBDA as a function at all.

It is possible to write useful programs in terms of LAMBDA expressions in which we never care about the value of any lambda expressoin. We have already demonstrated how one could represent any “FORTRAN” program in these terms: all one needs is PROG (with GO and SETQ), and PRINT to get the answers out. The ultimate generalizaton of this imperative programming style is continuation-passing. {Note Churchwins}^{[note 1]}

Continuation-Passing Recursion

Consider the following alternative definition of FACT. It has an extra argument, the continuation, which is a function to call with the answer, when we have it, rather than return a value.

procedure fact(n, c); value n, c;
    integer n; procedure c(integer value);
    if n=0 then c(1) else
        begin
            procedure temp(a) value a; integer a;
                c(n*a);
            fact(n-1, temp);
        end;

(DEFINE FACT
   (LAMBDA (N C)
      (IF (= N 0) (C 1)
          (FACT (- N 1)
                (LAMBDA (A) (C (* N A)))))))

It is fairly clumsy to use this version of FACT in ALGOL; it is necessary to do something like this:

begin
    integer ans;
    procedure temp(x); value x; integer x;
        ans := x;
    fact(3, temp);
    comment Now the variable "ans" has 6;
end;

Procedure fact does not return a value, nor does temp; we must use a side effect to get the answer out.

FACT is somewhat easier to use in SCHEME. We can call it like an ordinary function in SCHEME if we supply an identity function as the second argument. For example, (FACT 3 (LAMBDA (X) X)) returns 6. Alternatively, we could write (FACT 3 (LAMBDA (X) (PRINT X))); we do not care about the value of this, but about what gets printed. A third way to use the value is to write

(FACT 3 (LAMBDA (X) (SQRT X)))

instead of

(SQRT (FACT 3 (LAMBDA (X) X)))

In either of these cases we care about the value of the continuation given to FACT. Thus we care about the value of FACT if and only if we care about the value of its continuation!

We can redefine other functions to take continuations in the same way. For example, suppose we had arithmetic primitives which took continuations; to prevent confusion, call the version of "+" which takes a continuation "++", etc. Instead of writing

(- (↑ B 2) (* 4 A C))

we can write

(↑↑ B 2
    (LAMBDA (X)
            (** 4 A C
                (LAMBDA (Y)
                        (-- X Y <the-continuation>)))))

where <the-continuation> is the continuation for the entire expression.

This is an obscure way to write an algebraic expression, and we would not advise writing code this way in general, but continuation-passing brings out certain important features of the computation:

1. The operations to be performed appear in the order in which they are performed. In fact, they must be performed in this order. Continuation-passing removes the need for the rule about left-to-right argument evaluation. {Note Evalorder}^{[note 2]}

2. In the usual applicative expression there are two implicit temporary values: those of (↑ B 2) and (* 4 A C). The first of these values must be preserved over the computation of the second, whereas the second is used as soon as it is produced. These facts are manifest in the appearance and use of the variable X and Y in the continuation-passing version.

In short, the continuation-passing version specifies exactly and explicitly what steps are necessary to compute the value of the expression. One can think of conventional functional application for values as being an abbreviation for the more explicit continuation-passing style. Alternatively, one can think of the interpreter as supplying to each function an implicit default continuation of one argument. This continuation will receive the value of the function as its argument, and then carry on the computation. In an interpreter this implicit continuation is represented by the control stack mechanism for function returns.

Now consider what computation steps are implied by

(LAMBDA (A B C ...) (F X Y Z ...))

When we "apply" the LAMBDA expression we have some values to apply it to; we let the names A, B, C ... refer to these values. We then determine the values of X, Y, Z ... and pass these values (along with "the buck", i.e. control!) to the lambda expression F (F is either a lambda expression or a name for one). Passing control to F is an unconditional transfer. {Note Jrsthack}^{[note 3]} {Note Hewitthack}^{[note 4]}

Note that we want values from X, Y, Z ... If these are simple expressions, such as variables, constants, or LAMBDA expressions, the evaluation process is trivial, in that no temporary storage is required. In pure continuation-passing style, all evaluations are trivial: no combination is nested within another, and therefore no "hidden temporaries" are required. But if X is a combination, say (G P Q), then we want to think of G as a function, because we want a value from it, and we will need an implicit temporary place to keep the result while evaluating Y and Z. (An interpreter usually keeps these temporary places in the control stack!) On the other hand, we do not necessarily need a value from F This is what we mean by tail-recursion: F is called tail-recursively, whereas G is not. A better name for tail-recursion would be "tail-transfer", since no real recursion is implied. This is why we have made such a fuss about tail-recursion: it can be used for transfer of control without making any commitment about whether the expression expected to return a value. Thus it can be used to model statement-like control structures. Put another way, tail-recursion does not require a control stack as nested recursion does. In our models of iteration and imperative style all the LAMBDA expressions used for control (to simulate GO statements, for example) are called in tail-recursive fashion. === Escape Expressions ===

Reynolds [Reynolds 72] defines the construction

escape x in r

to evaluate the expression r in an environment such that the variable x is bound to an escape function. If the escape function is never applied, then the value of the escape expression is the value of r. If the escape function is applied to an argument a, however, then evaluation of r is aborted and the escape expression returns a. {Note J-operator} (Reynolds points out that this definition is not quite accurate, since the escape function may be called even after the escape expression has returned a value; if this happens it "returns again"!)

As as example of the use of an escape expression, consider this procedure to compute the harmonic mean of an array of numbers. If any of the numbers is zero, we want the answer to be zero. We have a function harmsum which will sum the reciprocals of numbers in an array, or call an escape function with zero if any of the numbers is zero. (The implementation shown here is awkward because ALGOL requires that a function return its value by assignment.)

begin
    real procedure harmsum(a, n, escfun);
          real array a; integer n; real procedure escfun(real);
        begin
            real sum;
            sum := 0;
            for i := 0 until n-1 do
                begin
                    if a[i]=0 then escfun(0);
                    sum := sum + 1/a[i];
                end;
            real array b[0:99];
            print(escape x in 100/harmsum(b, 100, x));
end

If harmsum exits normally, the number of elements is divided by the sum and printed. Otherwise, zero is returned from the escape expression and printed without the division ever occurring.

This program can be written in SCHEME using the built-in escape operator CATCH:

(LABELS ((HARMSUM
          (LAMBDA (A N ESCFUN)
              (LABELS ((LOOP
                        (LAMBDA (1 SUM)
                            (IF (= I N) SUM
                                  (IF (= (A I) 0) (ESCFUN 0)
                                      (LOOP (+ I 1)
                                            (+ SUM (/ 1 (A I)))))))))
                      (LOOP 0 0)))))
        (BLOCK (ARRAY B 100)
               (PRINT (CATCH X (/ 100 (HARMSUM B 100 X))))))

This actually works, but elucidates very little about the nature of ESCAPE. We can eliminate the use of CATCH by using continuation-passing. Let us do for HARMSUM what we did earlier for FACT. Let it take an extra argument C, which is called as a function on the result.

(LABELS ((HARMSUM
          (LAMBDA (A N ESCFUN C)
              (LABELS ((LOOP
                        (LAMBDA (I SUM)
                            (IF (= I N) (C SUM)
                                (IF (= (A I) 0) (ESCFUN 0)
                                    (LOOP (+ I 1)
                                          (+ SUM (/ 1 (A I)))))))))
                      (LOOP 0 0)))))
          (BLOCK (ARRAY B 100)
                 (LABELS ((AFTER-THE-CATCH
                           (LAMBDA (Z) (PRINT Z))))
                         (HARMSUM B
                                  100
                                  AFTER-THE-CATCH
                                  (LAMBDA (Y) (AFTER-THE-CATCH (/ 100 Y)))))))

Notice that if we use ESCFUN, then C does not get called. In this way the division is avoided. This example shows how ESCFUN may be considered to be an "alternate continuation".

Dynamic Variable Scoping

In this section we will consider the problem of dynamically scoped, or "fluid", variables. These do not exist in ALGOL, but are typical of many LISP implementations, ECL, and APL. We will see that fluid variables may be modelled in more than one way, and that one of these is closely related to continuation-passing.

Notes

1. {Churchwins}
   Reynolds uses the term "continuation" in [Reynolds 72]. Church clearly understood the use of continuations; it is the only way to get anything accomplished at all in pure lambda calculus! For example, examine his definition of ordered pairs and triads on page 30 of [Church 41]. In SCHEME notation, this is:

   [M, N]	means	(LAMBDA (A) (A M N))
   21	means	(LAMBDA (A) (A (LAMBDA (B C) B)))
   22	means	(LAMBDA (A) (A (LAMBDA (B C) C)))

   where 2₁ e.g. selects the first element of a pair. (Note that these functions are isomorphic to CONS, CAR, and CDR!)

2. {Evalorder}
   We can see that continuation-passing removes the need for the left-to-right rule if we consider the form of SCHEME expressions in continuation-passing style. In the style of Church, we can describe a SCHEME expression recursively:
   1. A variable, which evaluates to its bound value in the current environment.
   2. A constant, which evaluates to itself. Primitive operators such as + are constants.
   3. A lambda expression, which evaluates to a closure.
   4. A label expression, which evaluates its body in the new environment. The body may be any SCHEME expression. Only closures of lambda expressions may be bound to labelled variables.
   5. A conditional expression, which must evaluate its predicate recursively before choosing which consequent to evaluate. The predicate and the two consequents may be any SCHEME expressions.
   6. A combination, which must evaluate all its elements recursively before performing the application of function to arguments. The elements may be any SCHEME expressions.
   We say that an expression evaluates trivially if it is in category (1), (2), or (3); or in category (4) if the label body evaluates trivially; or in category (5) if the predicate and both consequents of the conditional evaluate trivially. Lemma: expressions which evaluate trivially have no side effects. We say that an expression is in continuation-passing form if it is in category (1), (2), (3); or in category (4) if the label body is in continuation-passing form; or in category (5) if the predicate evaluates trivially and the consequents are in continuation-passing form; or in category (6) if all the elements of the combination evaluate trivially, including the function. Theorem: expressions in continuation-passing form cannot depend on left-to-right argument evaluation. Proof: all arguments to functions evaluate trivially, and so their evaluations have no side effects. Hence they may be evaluated in any order. QED It is not too difficult to prove from this that an evaluator for expressions in continuation-passing form can be iterative; it need not be recursive or use a control stack. Another way to look at it is that continuation-passing style forces the programmer to represent recursive evaluations explicitly. What would be the control stack during evaluation of an ordinary expression is represented in environment structures in continuation-passing style.
3. {Jrsthack}
   This statement is equivalent to the well-known "JRST hack", which states that the sequence of PDP-10 instructions

   PUSHJ P,FOO POPJ P,

   is equivalent to

   JRST FOO

   except no stack slot is used.

4. {Hewitthack}
   Not only does an unconditional transfer to F occur, but values may be passed. One may think of these values as "messages" to be sent to the lambda expression F. This is precisely what Hewitt is flaming about (except for cells and serializers). [Smith 75]