Continuations and Environments

Environments and Cells

The Scheme report is a bit vague in its description of continuations and in particular the meaning of ‘call-with-current-continuation’. Likewise the notion of ‘environment’ in the context of ‘scheme-report-environment’ is not entirely clear. (It is fairly clear here however.) Note that and that the closure f is over the cell to which q is bound. If we need a closure over the current value of q, then
(let* ((q 3)(f (let ((z q)) (lambda () z)))) (set! q 4) (f)) ⇒ 3 serves. This depends on several facts, some of which may not be in the report where you might look, and others of which may not be in the report. A Scheme symbol denotes a value, but only via a mutable cell which holds different values from time to time. Most cells hold just one value through its lifetime. The expression (lambda (x) (+ x 1)) evaluates to a procedure that conceptually: These cells are more or less behind the scenes and they have no name. (lambda (x) (set! x 7) (+ x 1)) is valid and illustrates that in the scope of ‘set!’ the cell has a name, but what it names cannot be provided by any expression other than a symbol. In Scheme jargon, set! is syntax, not a procedure. In R5RS Scheme the cons cell, returned by the cons procedure, is actually two cells, each able to hold one Scheme value. A vector is actually a row of cells that may be modified by vector-set!.
For this note a map is an internal Scheme mechanism which is a function that maps each symbol from some finite set of Scheme symbols, onto either a cell or some specific syntax. An environment is either empty or a combination of a map and another environment. Notice that this is recursive.

All binding constructs which define new symbols, can be turned into equivalent lambda expressions and the above logic applies. For instance
(let* ((a 4)(b (+ a 2))) (* a b)) turns into
((lambda (a) ((lambda (b) (* a b)) (+ a 2))) 4). Whenever we evaluate an expression we do so in the context of some environment. To evaluate a symbol in an environment we use the map of the environment to seek a cell, and if the map mentions the symbol, the value is the cell contents. If the map does not mention the symbol then we evaluate the symbol in the environment of the environment. The program is invalid if the environment is empty. Numbers and a few other constructs evaluate to themselves without reference to the environment. To evaluate a parenthesized expression, a list, we first evaluate each member of the list. We demand that the first value be either a syntax symbol or a procedure. The other values form a list of arguments. Internally a procedure is an environment and structure that directly reflects the lambda expression: which is a list of symbol parameters and the lambda body. The list of parameters must be the same length as the list of arguments. A new map is produced mapping the parameters to new cells which hold the respective arguments. A new environment if formed consisting of the current environment from the procedure and the new map. The body of the lambda expression of the procedure is then evaluated in this new environment and its value becomes the value of the parenthesized expression.

I lie just a bit. Sometimes the procedure that is the value of the first expression within a parenthesized expression, is a primitive procedure like car. Then the Scheme evaluator takes note of this and does what ever special operation is necessary and the current environment is not involved. These special actions have access to the list of arguments, of course, but not the cells holding them. Also “()” evaluates to “()”. I also do not describe here the useful construct (lambda a … )

Even more special is when the environment declares that the first symbol is syntax. We do not discuss that here except for the topical case where the first symbol is lambda. It must appear as (lambda π β) where π is a list of symbols, called the parameters, and β is an expression called the body of the lambda. The value of this expression is an internal procedure whose environment is the current environment, the parameter list and the body of the lambda. It is a significant property of the rest of the language definition that while evaluating a parenthesized expression it is possible to know whether the symbols therein will identify syntax or cells. While described dynamically the relation of an evaluation to an environment can be determined statically.

Continuations

As the Scheme evaluator evaluates an expression it must remember who wanted the value it is producing and just how to deliver that value. It thus remembers what piece of Scheme code to recommence evaluating when the current new value is ready. Another part of the continuation is the next older continuation, again recursively. When evaluating a parenthesized expression whose first member’s value is a procedure, a new continuation is formed which consists of the current continuation and whatever other information is required to continue the calculation. This new continuation is normally abandoned to garbage collection as the procedure finishes and provides its value. There is one exception when that procedure is call/cc (call-with-current-continuation). In that case the primitive procedure call/cc invokes its argument (which must be a some procedure X) passing the current continuation as an argument. X now has a name for the continuation and can save the continuation for later and return. X now has two ways to return; it can return some value which which is in effect immediately returned by call/cc, or it can invoke the continuation passing a value which will be thereby returned by call/cc. In normal practice, either of those two choices will cause the continuation to be abandoned to GC, but X is at liberty to save the continuation for use subsequent to returning, or invoking the continuation.

Here is a conventional try-catch functionality, explained here, implemented with call/cc.

If routine X has retained the continuation and invokes it later, a time quake may surprise the program as part of the old calculation is commenced again with a new value returned by call/cc.

Perhaps the only clear explanation of continuations appears in the context of ‘CPS’ or ‘Continuation Passing Style’ which is a style you can use in a Scheme where no(!!) routine ever returns. The Wikipedia article has a pretty good explanation and many papers with CPS in their titles are good too. That article fails to emphasize that routines never return in the old sense; they only explicitly invoke the continuations that were explicitly passed as an argument. C programs can also adopt this style but without special hacks the stack grows indefinitely. This probably requires nested routines which C lacks but gcc provides. Several hacks have been proposed for C. When the compiler agrees to apply ‘tail call optimization’ whenever applicable, the stack will not grow for CPS C programs. You can mix the styles so as not to have to replace sqrt with a CPS version.

Some places speak of ‘goto with parameters’. That together with expunging returns, gives you CPS.

This page is devoted to a special style of CPS.

Here is a map from my terminology to that of the report.
Reporthere
<formals>list of parameters
identifiersymbol
locationcell
I tend to describe the semantics of a Scheme value rather than of an S-expression. In other words I describe the meaning of the output of the read procedure instead of its input.
Apropos