Home

Generic implementation of all four *F* operators: from control0 to shift

Unlike the previous approaches, the latest implementation is generic. Shift and control share all the same code, and differ in only one boolean flag. Therefore, it becomes possible to mix different control operators in the same program. Furthermore, the latest implementation is direct rather than emulation (in terms of an object-level shift), therefore, it has the best performance. The code is surprisingly simple, compared with the previous implementation of 'control' by Sitaram and Felleisen, and does not require equality on continuations. All four delimited control operations do indeed reduce to call/cc and one global mutable cell, and hence have a quite simple CPS transform. That has been known since the paper by Chung-chieh Shan (Scheme Workshop, 2004). The current code shows that result more directly.

Oleg's implementation provides all four Friedman-Felleisen delimited control operators: from -F- (similar to cupto) to +F- (aka control) to +F+ (aka shift). The R5RS Scheme code is parameterized by two boolean flags: is-shift and keep-delimiter-upon-effect. All four combinations of the two flags correspond to four delimited control operators.

By Ehud Lamm at 2005-09-13 14:05 | Theory | other blogs | 39071 reads

Comment viewing options

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

Unfathomable?

I'm surprised how little code this actually is. Why did it take so long before somebody discovered this? Imho this shows only one thing: the operators are too hard to comprehend in full detail.

At first I wanted to say: why not make it easier. But of course it is widely known that it is hard to make things easy. We can only hope that Oleg or someone else can use this result to create equivalent headache-free operators.

By Sjoerd Visscher at Tue, 2005-09-13 21:46 | login or register to post comments

Re: Unfathomable?

joerd_visscher wrote:
I'm surprised how little code this actually is. Why did it take so long before somebody discovered this? Imho this shows only one thing: the operators are too hard to comprehend in full detail.

Some things just take time. It was indeed surprising how little code was required. As to your conclusion, multiplication of two-three digit numbers was considered, up to some 300-400 hundred years ago, advanced art accessible to few. Now a middle-school kid can do that (OK, I don't know if they still can do that now, given the proliferation of calculators).

Delimited continuations aren't that complex, if viewed from the favorable point of view. The reduction semantics is very illuminating. When you look at an expression, try to see the closest dynamically-enclosing prompt. Then you can find the context C[], the captured continuation. That immediately gives you the reified continuation, (lambda (x) (reset C[x])). The rest is trivial. The must-read Scheme2004 paper by Chung-chieh Shan gives several examples of such reasoning in the first two sections. The reasoning is not very hard: for each test in the file delim-control-n.scm I computed the result in my head, while looking at the code. I verified the results later in a Scheme interpreter.

A good point of view was also responsible for the simple and direct generic implementation of control, shift, etc. It seemed beneficial to view delimited continuations as contexts with a hole. I hope to get a chance to explain that in some detail...

By Oleg at Thu, 2005-09-15 03:29 | login or register to post comments

Maybe it's not the same

leg wrote:

Delimited continuations aren't that complex

Maybe causing headaches is not the same as being complex. Proper naming might help a lot in this case. shift, reset, prompt, control, let alone *F* are not very illuminating.

By Sjoerd Visscher at Thu, 2005-09-15 16:13 | login or register to post comments

Thanks!

This elegant and concise implementation gave me the incentive to finally work through this stuff, and for the first time, I feel like I'm really beginning to understand these control operators. (I don't know why I found them so mystifying before...)

By Matt Hellige at Tue, 2005-09-27 22:59 | login or register to post comments