-
Notifications
You must be signed in to change notification settings - Fork 11
Reading List
(1987) Beyond Continuations - Matthias Felleisen, Daniel Friedman, Bruce Duba, John Merrill.
This is the original paper that introduces the "composable" continuation as in improvement over call/cc. They use CPS semantics and provide a CEK machine.
(1988) The Theory and Practice of First-Class Prompts - Matthias Felleisen
This paper introduces the # (prompt) operator, giving the first treatment of delimited continuations. It is argued that the calculus has the Church-Rosser property. A CEK machine is described for the new calculus.
(1990) Abstracting Control - Olivier Danvy, Andrzej Filinski
It describes the semantics of lambda calculus with shift/reset using twice-CPS transformed code. This paper shows how to use shift/reset to implement a CPS transformer in direct style for lambda calculus plus shift/reset!
(1990) Control Delimiters and Their Hierarchies - Dorai Sitaram, Matthias Felleisen
(1993) Handling Control - Dorai Sitaram
This is a scheme paper. It shows how to implement prompt and control using call/cc, then how to implement a bunch of stuff like exceptions, unwind-protect, streams, engines with it. Then addresses the problem of how these operators would interact wrongly with each other. To solve the problem he proposes multiple-prompts indexed by integers.
The next paper goes a bit further with similar stuff.
This paper relates stack overflow and underflow with handling continuation operations (which is also used by delimcc). It mentions the "heap model" for implementing continuations, using a linked list for the control stack but this method is a bit expensive (for example, stack frames are garbage collected instead of simply popped), so the remainder of the paper is how to improve on this. They get the best of both worlds using a linked list of stack segments.
In their system, creating a continuation seals off the current stack segment and starts a new one. This is a constant time operation as opposed to copying the whole stack up to the current point. This 'linked list of stacks' approach seems to be more efficient than just a stack with stack copying for continuation operators, and more efficient than using the heap all the time so that continuation operations are free but reclaiming stack frames would be done by GC in that model.
The second paper continues this work by identifying a common use of continuations that can be implemented more efficiently. The "one-shot" continuation: these are the cases where the continuation is invoked at most once. The main uses of multi-shot continuations are prolog like nondeterminism and generators. They benchmark the new call/1cc operator to measure how much more efficient it is.
(1994) Representing Monads - Andrzej Filinski
This shows how to turn direct style code in scheme into monadic code using delimited continuations. It also provides a CPS translation for (typed) lambda calculus + shift/reset into a monadic CPS language (essentially double CPS).
(1994) Subcontinuations - Robert Hieb, R Keny Dybvig, Claude Anderson III
The Subcontinuations paper is aimed at making control operators work together with concurrency. They do this with a spawn operator that is somewhat similar to (\p. #_i (p F_i)) with the idea that we have an indefinite supply of matched # and F operators. Basically it's a type of multiprompt continuations.
This is the first work to introduce multiple prompt delimited continuations and give it a rigorous treatment. They reference the [Theory and Practice of First-Class Prompts] paper, saying that it provided a single untyped prompt and that they introduced the idea of having multiple typed prompts (in order to make everything work in a well typed fashion). This is done with the new_prompt operator. Rather than control/prompt or shift/reset, they use set/cupto (control up to) operators. It is discussed that previous multiprompt work used integers instead of an abstract type: this has the disadvantage that of being able to write bad programs (making use of prompts you shouldn't be able to).
(1995) Continuation-Based Partial Evaluation - Julia Lawall, Olivier Danvy
This paper shows a practical application of delimited continuations. It's about partial evaluation for lambda calculus with let. The specific problem they address is how to do a "binding time improvement" that enables a dynamic let whose innards are static to be specialized away. An example to make this clear: 1 + (let x = d in 3) is difficult to specialize down to 4 but let x = d in (1 + 3) is much easier. Making a partial evaluator capable of doing this has been solved before by Bondorf, by writing the partial evaluator in CPS. The contribution of this paper is to show how to do without CPS, using shift/reset instead. This allows a much more direct implementation that's easier to understand. At the end they discuss some other binding-time improvements that may be possible, like applications and conditionals.
(1997) Threads yield continuations - Sanjeev Kumar, Carl Bruggeman, R Kent Dybvig
This paper uses the relationship between programs using one-shot continuations and tree structured concurrency to implement one-shot "subcontinuations" (delimited continuations) in terms of threading primitives.
(1997) A Syntactic Theory Of Dynamic Binding - Luc Moreau
My focus for this paper was that it showed how to implement exceptions using a dynamically scoped variable and shift/reset. The main purpose of the paper is to give a formal treatement for lambda calculus plus dynamic binding.
(2000) An Implementation of Transparent Migration on Standard Scheme - Eijiro Sumii
This is a clever hack. I'd be interested in other approaches to mobile code that use delimited continuations. Unfortunately I couldn't find the source on the authors page. Eijiro is also the author of MinCaml!
This may be the first direct implementation of shift/reset, it documents the implementation in the bytecode based system Scheme48.
(2002) Online Partial Evaluation for Shift and Reset - Kenichi Asai
Unlike [Continuation-Based Partial Evaluation] this paper use any control operators in its implementation. But it does implement a partial evaluator for a lambda calculus with shift/reset. The paper includes SML source.
(2004) Axioms for Delimited Continuations in the CPS Hierarchy - Yukiyoshi Kameyama
This paper has some very helpful equations regarding shift/reset. It also breaks down shift into 2 parts: aborting and delimiting. The equations will help people understand these operators as well as be useful for making test cases. It uses a CPS transform to prove the equations they came up with are sound and complete.
The sequel develops the idea further by applying it to a an indexed hierarchy of control operators. This paper covers the CPS hierarchy, an integer indexed sequence of shift_i/reset_i operators. They motivate the need for this by showing how nondeterminism and stream generators don't compose if they use the same shift/reset. The i'th operator is described in terms of the i'th iterated CPS transformation. At the end he asks whether or not such a hierarchy has any application.
Axioms
- S-elim:
S(\k.k M) = M - reset-S:
<F[S M]> = <M(\x.<F[x]>)> - S-reset:
S(\k.<M>) = S(\k.M)
Derived equations:
- S-nat:
F[S M] = S(\k.M(\x.<k F[x]>)) - S_eta:
S(\k.M k) = S M - S-tail:
(\x.S(\k.N))M = S(\k.(\x.N)M)
(2005) A Monadic Framework for Delimited Continuations - Kent Dybvig, Simon Peyton Jones, Amr Sabry
I think this is the second paper that addresses multiple first class prompts [(1995) A generalization of exceptions and control in ML-like languages] was the first. They create a monad with newPrompt, pushPrompt, withSubCont, pushSubCont operators. These operators can implement callcc, shift/reset (as well as shift-at/reset-at), control/prompt, abort and so on. The provide semantics using an abstract machine, CPS and monadically.
Here is how to define the usual control operators from the ones in this paper, taken from here:
let reset e = let p = new_prompt () in push_prompt p (fun () -> e p)
let shift p f = take_subcont p (fun sk -> push_prompt p (fun () -> f (fun c -> push_prompt p (fun () -> push_subcont sk c))))
let control p f = take_subcont p (fun sk -> push_prompt p (fun () -> f (fun c -> push_subcont sk c)))
let shift0 p f = take_subcont p (fun sk -> f (fun c -> push_prompt p (fun () -> push_subcont sk c)))
let control0 p f = take_subcont p (fun sk -> f (fun c -> push_subcont sk c))
let abort p e = take_subcont p (fun _ -> e)
(2004) Revisiting Coroutines - Ana Lucia de Moura, Roberto Ierusalimschy
Introduces the concept of "full asymmetric coroutines", shows it's equivalent to one shot (delimited) continuations. One of the major contributions of this paper was providing formal semantics for coroutines, the authors talked about how the lack of precise semantics has been an obstacle for study and use of coroutines. In section 2 they decide on and justify the following properties for the coroutine system: first class, stackful, asymmetric. It was shows how to implement call/1cc in terms of coroutines and pointed out that this is an efficient implementation, whereas it is not as efficient to implement coroutines in terms of one shot continuations. There is a colletion of very useful example applications in this paper too.
(2006) Delimited Dynamic Binding - Oleg Kiselyov, Chung-chieh Shan, Amr Sabry
This is a great application of multiprompt delimited continuations. It shows how to implement dynamic variables, similar to rackets parametrize. Because prompts were used it interacts smoothly with other control operator based constructs.
This is a report on integrating control operators into PLT scheme/racket in so that they interact correctly with the rest of the language: exceptions, dynamic-wind, dynamic binding. It is pointed out that continuations can implement exceptions but not if the language already has call/cc, because of interference. To solve this problem they build a system of prompts and implement exception handling with it. Hieb's control-filters idea from [Subcontinuations] is referenced for dynamic-wind.
(2007) A static simulation of dynamic delimited control - Chung-chieh Shan
This is a useful paper for showing the relationship between the different pairs of control operators. It includes scheme macros to define them in terms of the others.
(2007) Delimited continuations in operating systems - Oleg Kiselyov, Chung-chieh Shan
Application. They implement a virtual filesystem with zipper based cursors done by multiprompt continuations.
(2007) Polymorphic Delimited Continuations - Kenichi Asai, Yukiyoshi Kameyama
This is the first paper to formalize a polymorphic type system for shift/reset continuations that supports answer type modification. They demonstrate this using the type safe printf example.
(2007) Logical Relations for Call-by-value Delimited Continuations - Kenichi Asai
This paper shows how to use the technique of logical relations to prove correct a partial evaluation like the one in [(1995) Continuation-Based Partial Evaluation - Julia Lawall, Olivier Danvy] that performs the let binding time improvement. They also extend the partial evaluator to handle shift/reset.
(2009) Direct Implementation of Shift and Reset in the MinCaml Compiler - Moe Masuko, Kenichi Asai
(2011) Caml Light + shift reset = Caml Shift - Masuko, M., and K. Asai
Direct implementation of shift/reset in MinCaml. It's mentioned that Scheme48 and delimcc previously implemented it directly in terms of bytecode VMs, this is the first direct implementation in assembly. The paper basically goes over in detail the 3 important points: How the stack and heap are affected by reset, shift k and calling k. Benchmarking is performed and some key optimizations are identified.
In the sequel they repeat the work for Caml Light which (unlike MinCaml) has data types.
This is one of my favorite implementation papers. They show, with source code rather than mathematical formulations a step by step process of converting a basic evaluator for lambda calculus with shift/reset into a compiler + virtual machine to execute the language directly.
(2011) Yield Mainstream Delimited Continuations - Roshan James, Amr Sabry
This shows how to define shift/reset in terms and yield/run and vice versa.
(2012) A Systematic Approach to Delimited Control with Multiple Prompts - Paul Downen, Zena M. Ariol
This paper presents a minimal lambda calculus theory for multi-prompt delimited continuations. The connection with dynamic binding is stressed.
Section 6 points out that nested (integer indexed) shift/reset from the CPS hierarchy is different to the usual type of multi-prompt delimited continuations (that we're interesed in).
- Matthias Felleisen
- Gordon Plotkin
- Andrzej Filinski
- Olivier Danvy
- Marek Materzok
- Kenichi Asai
- R. Kent Dybvig
Good overview of some of the early papers: https://pdfs.semanticscholar.org/ce2b/170225dbcd0e453817a8efa9c5bfddc6edc2.pdf
Some modern directions things are going in are:
- Handling these control operators in a dependently typed setting
- algebraic effect handlers which seem to be more powerful than monad transformer stacks