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

### Continuation-Passing RecursionContinuation-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:
* 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}
* 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 Hewitthack}
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.
   (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 ScopingDynamic 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. ​ ​ ​ ​ ​ ​
Cite error: <ref> tags exist for a group named "note", but no corresponding <references group="note"/> tag was found