Wednesday, April 14, 2010

Single-frame continuations for Harmony, ctd

Continuing last week's series of posts on single-frame continuations for ECMAScript Harmony:

The inimitable Waldemar Horwat points out the flaw in my strawman proposal (strawman strawman?):
Since in the final expression you have A(... A(x)), you'll just end up executing the same finally block twice under certain circumstances.
This program demonstrates the bug:
function captured() {
try {
handler->();
throw "throw";
}
finally {
alert("finally!");
}
}

function handler(k) {
k();
}
The captured function calls handler, with the finally clause on the stack. Then handler invokes the captured continuation, which places the finally clause on the stack again. So after throwing an exception, unwinding the stack passes through two copies of the finally clause.

The takeaway for me is that a capturing mechanism that involves a call to a user function has a pigeonhole problem: the suspended continuation ought to capture the catch and finally clauses of the function activation, but the call to the handler also ought to be protected by those same catch and finally clauses. And yet the finally block should only executed once per activation. Note that generators do not suffer from this problem, since yield immediately suspends and aborts the activation, without calling user code in the middle.

For what it's worth, I tried the above program with NarrativeJS and it died with an internal error. But I didn't investigate further, so that may have been a mistake on my part. (It's difficult to tell what NJS should do since the docs don't really specify its semantics.) Nonetheless, I'm starting to think that finally (and in particular, the intended invariant that finally happens at most once per activation) renders unworkable any attempt to combine continuation-capture with a function call.

Actually, there are two more takeaways: 1) the notation of evaluation contexts is a nice way to describe and demonstrate the bug--notice Waldemar's wording!--and 2) thank goodness for Waldemar.

5 comments:

Anonymous said...

Hey Dave,
check out the first two papers (by Friedman and Haynes) in the list of Stephen's recent HOPL talk:

http://www.ccs.neu.edu/home/matthias/369-s10/Transcript/delimit.pdf

I haven't read the papers, but from what I understood during Stephen's talk, they discuss why you can't do dynamic-wind when you have call/cc.

Dimitris

Dave Herman said...

Hey Dimitri,

A couple points:

1) You can do dynamic-wind with call/cc, but it's very complex -- more complex, I claim, than is appropriate for JavaScript.

2) dynamic-wind is subtly different from finally: the former registers callbacks for every exit and entry to a continuation; AFAICT, the latter is intended to be executed when a continuation is truly "dead" -- which doesn't really make sense for multi-shot continuations, unless it's essentially a finalizer, invoked by the GC.

But I'll check out those papers. I'm a little surprised to hear you say they demonstrate that you can't do dynamic-wind when you have call/cc, given that Schemes have done just that for 25 years since that paper was written. :)

Dave

Dave Herman said...

PS Specifically, I think:

Dorai Sitaram
unwind-protect in portable Scheme
Scheme Workshop 2003

and:

Flatt, Yu, Findler, and Felleisen
Adding Delimited and Composable Control to a Production Programming Environment
ICFP 2007

have more modern takes on dynamic-wind. That said, I still need to read them carefully.

Dave

Anonymous said...

I'm not remembering this correctly then, there was a problem with some other construct. Maybe he was saying how the naive implementation of one-shot continuations using call/cc doesn't work. Sorry about that :)

Dave Herman said...

Or did you mean that you can't implement dynamic-wind when you have call/cc?