Single frame continuations proposal

David Herman dherman at mozilla.com
Wed Apr 14 10:30:03 PDT 2010


>> function foo(...) { f->(...); g->(...); }
> [snip]
> Of course, and I certainly understand how continuations reify the
> frame(s), and how traditional continuations preserve the stack, but I
> don't follow how to preserve the stack when you have broken the
> continuations apart into separate autonomous single-frame
> continuations.

Single-frame continuations capture a single frame. That's all there is to it-- there's nothing else to preserve. You suspend a single frame, save it in a data structure, and when it comes time to resume it, you place it back on the top of your current stack.

If the frame is on top of some larger continuation, you *cannot* and *must not* save any of the rest of that continuation. That's the whole point of single-frame continuations. They aren't *supposed* to save the rest of the continuation. If you did, they wouldn't be single-frame continuations any more. They'd be full continuations.

If, for the sake of diagnostics, you would like to capture some diagnostic information for e.g. better stack trace information, your VM can certainly take a snapshot of the current full stack (basically, save a stack trace) at the point of suspending the continuation, and carry that around in case an exception gets thrown later on when the continuation is resumed.

But beyond that, I still don't know what you mean by "preserve the stack."

> In the example, when an event triggers resuming the
> execution of g by calling the continuation activation function for g's
> continuation, how does the VM know to put the foo frame underneath it?

In the semantics I proposed, you capture the foo frame and execute g. If g registers an event handler that uses the captured frame, well, that's the foo frame, which you captured. The VM knows to reconstruct the foo frame because that's what it captured.

To frame an answer w.r.t your semantics, I'm afraid I'd need a better understanding.

> foo is supposed to resumed with the value for continuing execution,
> but that isn't available until g's continuation is done. What if there
> is user code between foo and g? For the VM to put this stack back in
> order seems like it would require some type of predictive analysis to
> determine that foo's continuation function is guaranteed to be
> executed and partially resume the continuation of foo, then fully
> resuming after g's completion. This seems really magical or am I
> missing something?

This doesn't make any sense to me.

At any rate, there's never any "prediction." A continuation is just an internal data structure representing the remaining code left to execute in a program-- or with delimited continuations, a portion of a program. A first-class continuation is a reflection of that data structure as a first-class value in the user programming language. If a VM knows what it has left to do *now*, then it can always stop what it's doing, save the information about what it had left to do, and perform it *later*.

>> Earlier in this thread, I demonstrated a simple single-frame
>> semantics and shown how generators could pretty easily be layered
>> on top of it...
> 
> Sorry, I thought you were suggesting that it was difficult to
> understand my specification of the semantics and code translation and
> need it be more clearly written. Your example of the generator library
> provides neither.

My example of the generator library was not the proposed semantics. See

    https://mail.mozilla.org/pipermail/es-discuss/2010-March/010866.html

I wrote:

> semantics of <expr> "->" <arg-list>:
> 
>     1. Evaluate the LHS expression and then the argument expressions
>     2. Let *k* be the current function continuation (including code, stack frame, and exception handlers).
>     3. Exit the current activation.
>     4. Call the LHS value with the argument values followed by *k*.
>     5. Return the result of the call.
> 
> semantics of calling *k* with argument *v* (defaults to the undefined value):
> 
>     1. Create a new function activation using the stack chain from the point of capture.
>     2. Reinstall the function activation's exception handlers from the point of capture (on top of the exception handlers of the rest of the stack that has called *k*).
>     2. Use *v* as the completion of the point of capture.
>     3. Continue executing from the point of capture.

I thought this was reasonably clear, or at least, at the time you sounded like you thought it was clear. Alternatively, I could sketch it out as a rough reduction rule, operational-semantics-style:

      S(A(f->(v1, ..., vn)))
----> S(f(v1, ..., vn, function (x) A(x)))

As I suggested in my blog post, this has the problem that the call to `f' loses the catch and finally blocks of A. In my post I suggested the alternative:

      S(A(f->(v1, ..., vn)))
----> S(A(let (result = f(v1, ..., vn, function (x) A(x))) { return result }))

But, as Waldemar pointed out, this is wrong, too. In fact, I'm about at the point where I don't believe a feature based on function calls will be workable, due to `finally'. I don't see any way of ensuring the invariant (expected by ES programmers) that a `finally' block will be executed at most once per activation while at the same time having *both* the continuation *and* the function called via -> be protected by the same `finally' block.

I've described the issue here:

    http://calculist.blogspot.com/2010/04/single-frame-continuations-for-harmony.html

> 1. The biggest problem with the semantics you propose is that it fails
> to provide a means for resuming a continuation with a thrown error.

I agree it's an omission, but disagree that it's the biggest problem. It's fixable in a couple different ways. Your suggestion is one; another is to represent a continuation as an object with both `send' and `throw' methods, a la generators.

IMO, the biggest problem is `finally'. I have doubts whether it's surmountable at all, at least with a form like `->' (as opposed to something like `yield').

> 2. I am opposed to the notion of appending the continuation resume
> function on to the list of arguments.

I pretty much agree with this point. But the bigger fish to fry is the basic control flow story.

It still might be possible to sketch a simple semantics based on a `yield'-like construct. But I wouldn't be surprised if it ended up looking a lot like JS 1.7 / Python generators.

Dave



More information about the es-discuss mailing list