An Operational Foundation for Delimited Continuations in the CPS Hierarchy

Magorzata Biernacka
Dariusz Biernacki
Olivier Danvy

December 2004

Abstract:

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. At level $n$ of the CPS hierarchy, programs can use the control operators shift$_i$ and reset$_i$ for $1 \leq i \leq n$, the evaluator has $n+1$ layers of continuations, the abstract machine has $n+1$ layers of control stacks, and the reduction semantics has $n+1$ layers of evaluation contexts.

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.

Available as PostScript, PDF, DVI.

 

Last modified: 2005-01-19 by webmaster.