return when desugaring to closures

Dave Herman dherman at ccs.neu.edu
Mon Aug 25 19:24:46 PDT 2008


Brendan Eich wrote:
>> Dave, is the violent transform of the for-loop above the kind of
>> rest-of-the-language transform you were referring to?
> 
> Answering for Dave: yes.

Sorry for the delay-- yes, any kind of construct in the language other 
than function/method/constructor call would require CPS. This makes for 
a pretty violent change to the language, though admittedly less violent 
than if generators captured more than one activation frame.

In essence, you can think of the language as split between two kinds of 
continuation: the "function activation stack" and the "local expression 
stack". Only the latter can be suspended by `yield', so only the latter 
needs to be representable in the semantics as a storable data structure. 
(If you're familiar with Landin's SECD machine, I think the activation 
stack corresponds to the [D]ump and the local expression continuation to 
the [S]tack.)

>> If so, isn't
>> this only an issue for control structures (including &&, ||, and ?:)?
>> What other elements of the language might need to be turned inside out
>> this way? Or have I misunderstood what you're getting at.

It would be an issue for all the other binary operators, too (=, ==, 
===, +, *, >>>, %, ^, etc.). Also sequences, blocks, and declarations. 
Any context that a `yield' expression may occur is fodder for capture.

I do understand what you're saying; it's not as big a change as having 
to CPS function calls. But in light of the (useful!) exhortations to 
emphasize specification by desugaring, I want to make it clear that a 
CPS transform is not a desugaring, i.e. a local rewrite; it's a 
reimplementation of (a portion of) the semantics.

Mark S. Miller wrote:
> I find continuations, delimited or otherwise, very hard to reason
> about. Generally, my best route to understanding what's going on is by
> CPS transform anyway. YMMV.

I hear you. Advanced control constructs can definitely get thorny. I 
find operational semantics with evaluation contexts much easier to 
understand than CPS, but as you say tastes vary.

As it turns out, the use of delimited continuations for generators is 
pretty straightforward-- you install a delimiter (`reset') when you 
enter the generator function (think of this like installing an exception 
handler) and capture the continuation (`shift') upon `yield'. This 
effectively captures and aborts the local continuation up to the 
delimiter, popping back up to the caller. That captured continuation, 
then, is in essence just a function; when you invoke it later, you're 
just pushing that suspended function activation back on the control stack.

> I didn't know SML has delimited continuations.

It doesn't officially; SML/NJ and MLton implement callcc, which you can 
use to implement shift and reset. So it's admittedly on the edge of ML's 
semantics. But these are all very well-understood control operators and 
easy to add to the formal semantics of SML. We went that route so we 
could write the reference implementation in direct style.

> But I'd still rather not try to understand generators
> by CPS-transforming the relevant bits of the RI.

A little confused here-- was that an errant "not"?

Dave


More information about the Es-discuss mailing list