An Operational Foundation for Delimited Continuations in the CPS Hierarchy

An Operational Foundation for Delimited Continuations in the CPS Hierarchy
We present an abstract machine and a reduction semantics for the lambda-calculus extended with control operators that give access to delimited continuations in the CPS hierarchy. The abstract machine is derived from an evaluator in continuation-passing style (CPS); the reduction semantics (i.e., a small-step operational semantics with an explicit representation of evaluation contexts) is constructed from the abstract machine; and the control operators are the shift and reset family. We also present new applications of delimited continuations in the CPS hierarchy: finding list prefixes and normalization by evaluation for a hierarchical language of units and products.
...or in other words - a view on the delimited continuations from another side (as compared to "A Monadic Framework for Subcontinuations" or Oleg's posts on Hakell list). I find it useful to learn about the same concept from different sources - and the delimited continuations are still promising to become an important concept.

Also, I suspect that defunctionalized approach might be more straightforward for people coming from imperative languages.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Simple question I expect but

Could someone briefly explain to me what a delimited continuation actually /is/ ? (as opposed to a plain old continuation... think I got those pretty much down :)

I've googled on this and not found a clear stand-alone definition of the term, just lots of very technical-looking papers...

Comments on draft welcome

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)
Contexts are captured by shift and delimited by reset. More specifically,
shift captures the current context up to the nearest dynamically enclosing
reset, replaces it abortively with the empty delimited context [_], and binds f
to the captured delimited context as a functional value. For example, the
program

(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).

Ah thanks

that was very helpful!