An Operational Foundation for Delimited Continuations in the CPS
We present an abstract machine and a reduction semantics for the -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 of the CPS hierarchy, programs can use the control operators shift and reset for , the evaluator has layers of continuations, the abstract machine has layers of control stacks, and the reduction semantics has 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.