An Operational Foundation for Delimited Continuations in the CPS Hierarchy

Authors

  • Malgorzata Biernacka
  • Dariusz Biernacki
  • Olivier Danvy

DOI:

https://doi.org/10.7146/brics.v12i24.21890

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 <= i <= 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.

Downloads

Published

2005-08-11

How to Cite

Biernacka, M., Biernacki, D., & Danvy, O. (2005). An Operational Foundation for Delimited Continuations in the CPS Hierarchy. BRICS Report Series, 12(24). https://doi.org/10.7146/brics.v12i24.21890