Lambda the Ultimate

I'm revising an introduction to a paper and would love feedback on the following description of undelimited versus delimited continuations versus contexts.

The continuation is a function that maps the intermediate result of a computation to its final result. For example, executing the Scheme program

(cons 'a (cons 'b (cons 'c '())))

first yields an intermediate result for the subexpression (cons 'c '()). The
continuation of the subexpression (cons 'c '()) is to cons the symbol b,
then the symbol a, onto the intermediate result. In other words, the continuation of (cons 'c '()) is the function

(lambda (v) (cons 'a (cons 'b v)))

in Scheme notation. It is popular to represent a continuation by a context, or
an expression with a hole. For example, we may represent the continuation
above by the context (cons 'a (cons 'b _)), where _ is a hole waiting to
be plugged in.



Continuations can exist in a program at two levels. First, code may be written in continuation-passing style (CPS), in which continuations are managed
explicitly as values at all times. Second, the underlying control flow of a program can be treated in terms of continuations. The Scheme programming language provides call-with-current-continuation (hereafter call/cc) to
access these implicit continuations as first-class values. Implicit continuations can be made explicit by a CPS transform on programs; explicit
continuations can be made implicit by a corresponding direct-style transform.



A delimited (or composable, or partial) continuation is a function that
maps the intermediate result of a computation to a later, but not necessarily
final, result. For example, in the program

(cons 'a [(cons 'b (cons 'c '()))])

the continuation of the subexpression (cons 'c '()), as delimited by the
square brackets, is to cons the symbol b onto the intermediate result. In other
words, the delimited continuation is the function

(lambda (v) (cons 'b v))

in Scheme notation. It is popular to represent a delimited continuation by a
delimited context, or an expression—not necessarily an entire program—with
a hole. For example, we may represent the delimited continuation above by
the context [(cons 'b _)].



Delimited continuations, like undelimited ones, can be explicit (in CPS
code) or implicit (in direct-style code). For example, given the CPS factorial
function

(define fact
  (lambda (n c)
    (if (= n 0) (c 1)
      (fact (- n 1) (lambda (a) (c (* n a)))))))

we can compute 6!+1 by (+ (fact 6 (lambda (a) a)) 1). The second
argument (lambda (a) a) to fact is a delimited continuation that excludes
the final step of adding 1.



Felleisen pioneered the use of control delimiters in direct style to access
delimited contexts as first-class values. Following Felleisen's work,
many control operators have been proposed. A typical proposal provides,
first, some way to delimit contexts, and second, some way to capture the
current context up to an enclosing delimiter. For example, Danvy and Filinski
proposed two control operators shift and reset, with the following
syntax.

Expressions E ::= ··· | (shift f E) | (reset E)

(cons 'a (reset (cons 'b
  (shift f (cons 1 (f (f (cons 'c '()))))))))

evaluates to the list (a 1 b b c). This is because shift captures the delimited context [(cons 'b _)] and binds the variable f to the corresponding
value (lambda (x) (reset (cons 'b x))). At the same time, shift also
removes that context (in other words, it aborts the current computation up to
the delimiting reset), so the result is not (a b 1 b b c).