Indiana University Bloomington

Luddy School of Informatics, Computing, and Engineering

Technical Report TR611:
How to remove a dynamic prompt: static and dynamic delimited continuation operators are equally expressible

Oleg Kiselyov
(Mar 2005), 16 pages pages
[Collaboration with Daniel P. Friedman and Amr A. Sabry on logical programming systems]
Abstract:
We show how to remove a dynamic prompt (aka reset) and thus to turn so-called static delimited continuation operators (shift/reset) into dynamic ones: control, control0, shift0. Our technique extends the continuation captured by shift by composing it with the previous fragments of the `stack'. Composition of context fragments can be done via regular functional composition. We thus demonstrate that all the above delimited continuation operators are macro-expressible in terms of each other --- without capturing undelimited continuations and without using mutable state. Furthermore, the operators shift, control, control0, shift0 are the members of a single parameterized family, and the standard CPS is sufficient to express their denotational semantics.

We give the simplest Scheme implementation of the dynamic control operators. We give a formal simulation proof that control realized through shift indeed has its standard reduction semantics.

Available as: