Open AccessAn Operational Foundation for Delimited Continuations in the CPS Hierarchy
Author(s) -
Małgorzata Biernacka,
Dariusz Biernacki,
Olivier Danvy
Publication year - 2005
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v12i11.21877
Subject(s) - programming language , computer science , hierarchy , prefix , operational semantics , abstract machine , continuation , normalization (sociology) , reduction (mathematics) , semantics (computer science) , theoretical computer science , mathematics , linguistics , philosophy , geometry , sociology , economics , anthropology , market economy
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 1We 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.