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.

13 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?

pubg mobile said...
This comment has been removed by the author.
snoop dogg said...

Very good information. Lucky me I ran across your site by accident (stumbleupon). I have saved it for later!Dr Dre net worth
beyonce net worth
kanye-west Net Worth
kim-kardashian net worth

Unknown said...

If you're trying to lose pounds then you absolutely need to try this totally brand new tailor-made keto diet.

To create this keto diet, certified nutritionists, fitness couches, and professional chefs joined together to develop keto meal plans that are productive, convenient, cost-efficient, and delightful.

Since their launch in January 2019, 100's of clients have already remodeled their body and well-being with the benefits a certified keto diet can provide.

Speaking of benefits: in this link, you'll discover eight scientifically-proven ones given by the keto diet.

메이저-토토사이트 said...

Your article has proven useful to me.

gostopsite.com said...

Wonderful web site. Plenty of useful info here.

sportstotomen.com said...

This is my first visit to your blog!

19guide03.com said...

I was surprised, I have to say. Equally.

casinosite.zone said...

It’s very simple to find out any matter on net as compared to books, as I found this post at this site.