Home

A Monadic Framework for Delimited Continuations

A Monadic Framework for Delimited Continuations (PDF), R. Kent Dybvig, Simon Peyton Jones, Amr Sabry. TR, June 2005.

Delimited continuations are more expressive than traditional abortive continuations and they apparently seem to require a framework beyond traditional continuation-passing style (CPS). We show that this is not the case: standard CPS is sufficient to explain the common control operators for delimited continuations. We demonstrate this fact and present an implementation as a Scheme library. We then investigate a typed account of delimited continuations that makes explicit where control effects can occur. This results in a monadic framework for typed and encapsulated delimited continuations which we design and implement as a Haskell library.

A fascinating paper about delimited control. I'm very much a newbie to delimited control, but this paper has been enormously helpful - despite the title. ;)

The basic idea of the paper is to represent the execution context as a sequence containing prompts (control delimiters) and the (partial) continuations between prompts. This model is formalized with an operational semantics, which was insightful even though it's the first operational semantics I've studied.

The authors then present an implementation of the model in terms of call/cc in Scheme. The basic idea here is to always perform user code after aborting to a context near the bottom of the stack, just above a call to an underflow function - this means that even though we use undelimited call/cc, we only ever capture our (small, partial) execution context. The whole execution context (the "metacontinuation") is maintained as a sequence data structure in a global variable (basically, a list containing prompts and Scheme continuations). The underflow function destructures the metacontinuation, and executes (returns to) the partial continuations stored in it. Pushing a prompt adds a delimiter to the metacontinuation, capturing a delimited continuation splits the metacontinuation at a delimiter, and composing a continuation appends to the metacontinuation.

I haven't even gotten to the later parts of the paper yet, but this model and the Scheme implementation alone is worth a look.

(The paper seems to be a reworked version of A Monadic Framework for Subcontinuations, discussed previously.)

By Manuel J. Simoni at 2011-08-24 18:00 | Implementation | Theory | other blogs | 12664 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

We show that this is not

We show that this is not the case: standard CPS is sufficient to explain the common control operators for delimited continuations. We demonstrate this fact and present an implementation as a Scheme library.

This paper seems to spell out my previous intuition for you for a simple library-level implementation of delimited continuations on top of (simple) established undelimited continuation support

Edit: I see that you edited your post there to say as much :)

By lmeyerov at Thu, 2011-08-25 01:20 | login or register to post comments

I think the model offered by

I think the model offered by the paper is extremely helpful, and in the hare-brained heap-allocated implementation of the stack I'm currently using, this indirect Scheme implementation should not be much worse, performance-wise, than a direct implementation. I can see however, what Oleg meant when he said don't implement undelimited continuations: many of the more performant call/cc implementation strategies (e.g. Hieb, Dybvig, Bruggeman) are essentially delimited already - implementing delimited control on top of undelimited control which uses delimited control under the covers seems a travesty! :-)

By Manuel J. Simoni at Thu, 2011-08-25 11:01 | login or register to post comments

implementing delimited

implementing delimited control on top of undelimited control which uses delimited control under the covers seems a travesty!

Actually, this is exactly what I love about CS!

By Ehud Lamm at Thu, 2011-08-25 20:11 | login or register to post comments