Wednesday, April 07, 2010

Delimited continuations? In ECMAScript?

Well, no.

Besides breaking a lot of language invariants, first-class continuations would be a nightmare for portability, since different implementations implement different API's natively. Either you mandate capturing continuations across native frames, which is a hardship for implementers and a performance-killer, or you don't, which causes observably different behavior across browsers when they place native delimiters at different points in the continuations-- leading to lots of painful bug reports and nasty market dynamics where everyone has to tailor their implementations to track the most popular.

So that won't happen. But!

JS 1.7 introduced Pythonic generators, which allow you to suspend a single function activation. This alleviates some of the painful CPS patterns people have to use on the web to interact with the event-loop-concurrent, single-thread-of-control semantics of JavaScript on the web. But it's also a little ad hoc. And Kris Zyp recently made the helpful suggestion that we could explore a design for a simpler, more general single-frame continuation-capture operation for Harmony.

What we're talking about here is a restricted version of delimited continuations: the delimiters are implicit--they're at function boundaries. But otherwise it's very much in that space. And there's a loooot of prior work on this topic. I'll post later with a little background and some notes about the design space of delimited continuations for ES.

6 comments:

Mitch said...

I think I understand scheme's call/cc, and I was really excited originally to hear that kind of thing proposed for ES. Then later, on LTU, Brendan explained the script/native/script thing and I was sad.

I don't really get delimited continuations yet, I've seen Oleg Kiselyov posting about them a lot but I don't understand just about everything he writes. Still, it's really exciting to see some kind of continuations show up again in ES context; I haven't really followed the ES email lists for a while but maybe it's time to start reading them again.

TL;DR - Yay!

jto said...

I think Lars Thomas Hansen's complaint about single-frame continuations is that they break lambda abstraction. Beta reduction changes the meaning. What do you think about that?

Dave Herman said...

Lars Thomas Hansen's complaint about single-frame continuations is that they break lambda abstraction.

Well, full continuations certainly do expose details of lambda abstractions. The main issue is if a library function takes a funarg and calls it, the funarg might capture the continuation and use it multiple times. (You can think of this as the funarg "highjacking" the control flow.) Turns out lots of standard Scheme libraries like map are buggy because they don't expect control to return multiple times.

I suspect the situation isn't as bad in the case of single-frame continuations, though. Did Lars tell you this in person, or is he on record somewhere publicly? I'm having drinks with him on Wednesday, so I'll ask him myself. :)

Beta reduction changes the meaning. What do you think about that?

Well, I'm not sure what you mean, exactly. The beta rule stays the same in the presence of call/cc. It just means that some of the invariants about function abstraction are gone.

Dave Herman said...

PS I should say, lots of implementations of standard Scheme libraries. Didn't mean to imply the spec is buggy.

jto said...

The beta rule stays the same in the presence of call/cc, yes. But not in the presence of single-frame continuations (or generators) because there every function call implicitly installs a delimiter.

EXPR

(function () { return EXPR; })()

I'm talking about the difference between these two in terms of what is captured if EXPR contains f->(x).

This is something lth mentioned to me while ES4 was going on. However now I'm a bit worried that I've misrepresented the importance of this objection compared to others; and it's been a year or two.

Dave Herman said...

I see what you're getting at now.

So first of all, there's no beta rule in JS, just an ad hoc semantics of functions, which are already exposed in the semantics: return is a delimited abort operation; arguments is function-specific; Function.arguments; Function.callee... heck, the spec even refers to function calls as "allocating an activation object" whose slots are the local variables.

That said, you're right that this hooks one more piece of semantics into the meaning of functions. If JS hadn't long ago already gone down this road in spades, I would whole-heartedly agree. (For example, it'd be a total non-starter for Scheme. And if the lambdas proposal weren't dead, they'd be specified not to be implicitly delimited.)

Another way of putting it: rather than "changing the beta rule" (which is just a reduction rule), this ruins beta-equivalence. But beta-equivalence already doesn't hold in JS.