Thursday, August 18, 2011

Notes on delimited continuations

Delimited continuations are one of those topics where you need to spend months or maybe even years in the cloud of unknowing, until it suddenly makes click. At least, that's this autodidact's experience.

Delimited continuations are awesome, because they let us abstract over control flow - as I like to put it one man's control flow is another man's data, or as Chung-chieh Shan puts it: delimited continuations liberate control flow.

Continuations as we know them (i.e. those created by call/cc) are undelimited, they represent the whole rest of the computation. Delimited continuations represent the rest of a sub-computation up to a given prompt. They come from investigating REPLs: when you capture an undelimited continuation, the continuation includes the REPL's control flow! Generally, you don't want that, so with delimited continuations, the REPL can install a prompt before executing code entered by the user, and then you can capture a delimited continuation just up to that prompt, excluding the REPL's code.

My favorite description of delimited continuations is offered right at the start of A Monadic Framework for Delimited Continuations, even though the rest of the paper is quite over my head. Their API for delimited continuations is:
  • newPrompt --- creates a fresh prompt, distinct from all other prompts. It's just an object that we use as an identifier, basically. Some systems simply use symbols for prompts.
  • pushPrompt p e --- pushes prompt p on the stack, and executes expression e in this new context. This delimits the stack, so we can later capture a delimited continuation up to this part of the stack.
  • withSubCont p f --- aborts (unwinds the stack) up to and including the prompt p, and calls the function f with a single argument k representing the delimited continuation from the call to withSubCont up to but not including the prompt. This captures a delimited continuation, analogous to how call/cc captures an undelimited continuation.
  • pushSubCont k e --- pushes the delimited continuation k on the stack, and executes expression e in this new context. This composes the stack of k with the current stack, analogous to how calling the function representing a continuation in Scheme swaps the current stack with the stack of that continuation.
Now to the example! Delimited continuation examples are always hair-raising!! Brace yourself!!!
So, the first thing we do is call newPrompt (at the bottom) to obtain a fresh prompt, and then we pipe that into the function (at the top), so that we have a name, p, for the prompt. Inside that function we have the addition of 2 to a second expression, that pushPrompt's p on the stack, i.e. delimits the stack at this point. The if is called inside the new context delimited by p. Now it gets hairy: The if's test expression is a withSubCont, so it immediately aborts up to the outer pushPrompt and then calls the function that is its second argument with k bound to the rest of the computation between the withSubCont and the pushPrompt. What's the rest of that computation?? Well, by the magic of delimited control, k is now equivalent to the function λb. if b then 3 else 4. This is what I meant when I said that delimited continuations allow us to abstract over control flow - we have just turned an arbitrary, dynamic control flow sequence into a function. (Well, it's not really a function, but we can use it like one.) OK, so we have aborted back up to pushPrompt, and in k we have the rest of the computation as a function. What do we do with it? Well, we call it using pushSubCont once with False and once with True as argument, and we add the two results, giving us 7. Note that we just called the delimited continuation twice! We can not only abstract over arbitrary control flows, we can also call them as many times as we like. Now the whole shebang inside pushPrompt is over, and we return to the addition of 2 to our result of 7, giving us 9.

6 comments:

Uroš Dimitrijević said...

( A similarly mind-bending example, but doubly so : )

(\p. pushPrompt p
( withSubCont p (\k. [pushSubCont k 1, pushSubCont k 2 ])
+ withSubCont p (\k. [pushSubCont k 10, pushSubCont k 20]))) newPrompt

=> [[11, 21], [12, 22]]

One thing that I find peculiar here (probably due to my being completely new to delim-c's and not having read nearly enough about them) is how the return type of every k changes purely due to the second argument of whatever calls to withSubCont may happen in the prompt's dynamic extent. So it occurred to me that the above example may not be possible in a statically typed implementation of delimited continuations (such as one where withSubCont : 'a prompt -> (('b -> 'a) -> 'a) -> 'b, and so on).

John Shutt said...

I disagree with the common claim that ordinary continuations entail replacing the whole rest of computation. Rejecting this claim was key to the design of the control vau-calculus in my dissertation; in that calculus, a throw is a side-effect frame that propagates upward until it reaches its matching catch (at which point it can be canceled out). What makes the whole thing work is that the matching catch frame is also a side-effect frame, and when it propagates upward it causes changes to all its matching throws (by a non-lambda form of substitution).

Manuel Simoni said...

Uroš: withSubCont aborts up to and including the prompt. Are you sure that your example works under this mechanism?

Uroš Dimitrijević said...

Manuel: it quite likely doesn't!

Disclaimer: pretty much all I know about delimited continuations has been glarked from one set of slides (http://www.cs.rutgers.edu/~ccshan/dynscope/talk.pdf) and my intuition :) I am led to believe that the shift operator used there is not the same as withSubCont here (but that the former is probably implemented in terms of the latter... as I said, I have so much more reading to do!).

That said, after I read those slides I wrote a quick and naïve implementation of new_prompt/push_prompt/shift in terms of Scheme's call/cc, based on how I thought it should behave. My example worked in it as expected, but I'm almost certain that I screwed it up somewhere... for example, the implementation of dset as provided in the slides did not work.

Manuel Simoni said...

Yes, see the Monadic Framework paper, page 6: shift "both leaves the prompt behind and includes it in the subcontinuation".

Manuel Simoni said...

John: I'll have another look. I found it interesting that you don't mention delimited continuations in your dissertation.