Wednesday, April 07, 2010

The design space of continuations

I mentioned earlier that the design space for first-class continuations has a lot of historical research behind it. This list of papers on continuations up to around 2005 is a start, but by no means complete. (The history of continuations is actually pretty astoundingly far-reaching. Apparently my PhD advisor's PhD advisor was one of a number of people who independently discovered continuations in different research programs and under different guises.)

The research literature has been helpful to me in understanding the design space of control operators better, particularly because it gives me good models for reasoning, formally or informally, about control effects.

Here are some of the design questions raised by the research literature and good modeling frameworks. This isn't a complete list, and it isn't the place to cite adequately. All I'm interested in is highlighting some of the takeaways.

How much of the continuation can be captured?

Scheme's call/cc allows you to capture the "whole" continuation, up to wherever the language implementor decides is the limit. But delimited continuations make this boundary more explicit, which has a couple benefits. First, by installing a delimiter, you can prevent code that you call from capturing parts of your continuation that you want to keep private. Second, when you capture a continuation, you have a clearer picture of what you're capturing.

What elements of the continuation are captured?

The answer at first seems obvious: you capture the control context and the environment (aka scope chain). But it gets trickier when you have things like exception handlers and other information associated with the dynamic state of the control context.

What kinds of delimiters do you give to users?

In our case, we're only interested in an implicit delimiter at function boundaries. But there are a number of different designs of control delimiters.

What kinds of control-abort operators do you give to users?

Turns out there's at least one in every C-like language: return. That's probably enough for our purposes. But there are several possibilities there, too, and they can get surprisingly subtle.

Does executing a captured continuation install a new delimiter?

This is the key difference between Felleisen's F/# operators [*] and Danvy and Filinski's shift/reset operators. With the former, you capture a continuation up to the nearest delimiter, but when you invoke the captured continuation, there's no new delimiter. With the latter, a captured continuation reinstalls a new delimiter every time you invoke it.

How many times can you enter a continuation?

The most general design allows a captured continuation to be used any number of times. With "one-shot" continuations, you can only enter a continuation once. Notice that "entering a continuation" could mean a number of things: returning normally, unwinding it by throwing exceptions, or calling into it later via a captured continuation.

When do we abort the current continuation?

This one is really, really variable. There are many plausible points in the semantics where an exit can occur, and many of them lead to plausible but distinct designs.

[*] That's pronounced "eff" and "prompt" -- no relation to F#. I just noticed that!


Jizzy said...


Jay Shawn Mendis said...

Thank you for sharing the information. Now I would like to divert you from the topic. We are certified experts in the field of QuickBooks. We provide variety of services to resolve QuickBooks error the user may face while using payroll, inventory, POS, pro, enterprise, company file, single and multiple user mode etc. Your opinion are very interesting, attractive article, so i shared it on my facebook. Promise that a lot of people will enjoy it.
error 1904 quickbooks | write off bad debt in QuickBooks | QuickBooks Error 3371 | QuickBooks Error 15106 | QuickBooks 24/7 Support Phone Number

jorge montiel said...
This comment has been removed by the author.
Alex williams said...

We support all types of HP printer troubleshooting and service. Just enter the model number of your printer in to identify the software and drivers your printer requires. Download and install it in your mac and 'Run' the file. The process is easy however if you have any doubts or queries regarding HP printers contact us.

malina smith said...

It is perfect time to make some plans for the future and it is time to be happy. I've read this post and if I could I desire to suggest you some interesting things or suggestions. Perhaps you could write next articles referring to this article. I want to read more things about it!
visit@- | | | |