Back to Direct Style II: First-Class Continuations

Olivier Danvy
Julia L. Lawall

June 1996

Abstract:

The direct-style transformation aims at mapping continuation-passing programs back to direct style, be they originally written in continuation-passing style or the result of the continuation-passing-style transformation. In this paper, we continue to investigate the direct-style transformation by extending it to programs with first-class continuations.

First-class continuations break the stack-like discipline of continuations in that they are sent results out of turn. We detect them syntactically through an analysis of continuation-passing terms. We conservatively extend the direct-style transformation towards call-by-value functional terms (the pure tex2html_wrap_inline21 -calculus) by translating the declaration of a first-class continuation using the control operator call/cc, and by translating an occurrence of a first-class continuation using the control operator throw. We prove that our extension and the corresponding extended continuation-passing-style transformation are inverses.

Both the direct-style (DS) and continuation-passing-style (CPS) transformations can be generalized to a richer language. These transformations have a place in the programmer's toolbox, and enlarge the class of programs that can be manipulated on a semantic basis. We illustrate both with two applications: the conversion between CPS and DS of an interpreter hand-written in CPS, and the specialization of a coroutine program, where coroutines are implemented using call/cc. The latter example achieves a first: a static coroutine is executed statically and its computational content is inlined in the residual program.

Available as PostScript, PDF, DVI.

 

Last modified: 2003-06-08 by webmaster.