# Lambda: The Ultimate Imperative/Continuations

== 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 RecursionEdit

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); valuen,c;

integern; procedurec(integer value);

ifn=0 thenc(1) else

begin

proceduretemp(a) valuea; integera;

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

integerans;

proceduretemp(x); valuex; integerx;

ans:=x;

fact(3,temp);

commentNow 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:

- 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]}

- 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

xinr

to evaluate the expression

in an environment such that the variable *r*

is bound to an *x*__escape function__. If the escape function is never applied, then the value of the escape expression is the value of

. If the escape function is applied to an argument *r**a*, however, then evaluation of

is aborted and the escape expression returns *r**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

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

begin

real procedureharmsum(a,n,escfun);

real arraya; integern; real procedureescfun(real);

begin

realsum;

sum:= 0;

fori:= 0 untiln-1 do

begin

ifa[i]=0 thenescfun(0);

sum:=sum+ 1/a[i];

end;

real arrayb[0:99];

print(escapexin 100/harmsum(b, 100,x));

end

If

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.
*harmsum*

`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 ScopingEdit

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.

## NotesEdit

- ↑
**{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))

2 _{1}means (LAMBDA (A) (A (LAMBDA (B C) B)))

2 _{2}means (LAMBDA (A) (A (LAMBDA (B C) C)))

where 2

_{1}e.g. selects the first element of a pair. (Note that these functions are isomorphic to`CONS`

,`CAR`

, and`CDR`

!) - ↑
**{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:- A variable, which evaluates to its bound value in the current environment.
- A constant, which evaluates to itself. Primitive operators such as
`+`

are constants. - A lambda expression, which evaluates to a closure.
- 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.
- 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.
- A combination, which must evaluate all its elements recursively before performing the application of function to arguments. The elements may be any SCHEME expressions.

__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. - ↑
**{Jrsthack}**

This statement is equivalent to the well-known "`JRST`

hack", which states that the sequence of PDP-10 instructionsPUSHJ P,FOO POPJ P,

is equivalent to JRST FOO

except no stack slot is used.

- ↑
**{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]