Single frame continuations proposal

Kris Zyp kris at sitepen.com
Wed Apr 14 09:23:07 PDT 2010


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
 
On 4/6/2010 4:04 PM, Dave Herman wrote:

> function foo(...) { f->(...); g->(...); }
>>>
>>> and the call to g throws an exception, it's perfectly easy for
>>> an implementation to report that this came from the body of
>>> foo.
>>
>> With normal continuation passing style if the exception takes
>> place in the next event turn (for g's event handler), g's event
>> handler would call the callback in foo, resulting in an inverted
>> stack.
> You do realize compilers aren't going to implement this with CPS,
> right? They'd likely reify the activation frame as an internal data
> structure (probably in C++, the poor dears), which they probably
> already have implemented anyway. CPS is just one (poorly
> performing) implementation strategy for first-class continuations.
> This is an implementation concern, not something we need to address
> in the semantics.

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. 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?
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?
> 4) Your design seems to have too much window-dressing and I don't
> have confidence that it's well-specified in the core parts. At
> least, the goto-laden spec with implicit entry points won't cut it.
> I think it's fair to say, if Waldemar can't understand your
> semantics, You're Doing It Wrong. ;)
[snip]
> In addressing your other issues, like I said to Waldemar, would it
> be
>> reasonable to start with a definition and sample translation of
>> JS1.7 generators (since I believe we all understand those) and
>> then look at possible incremental changes to make it more broadly
>> useful? Then maybe my poorly written code wouldn't get in the way
>> :/.
> Earlier in this thread, I demonstrated a simple single-frame
> semantics and shown how generators could pretty easily be layered
> on top of it (not the most important design criterion, but a good
> sanity check). Actually, I started digging into SpiderMonkey this
> weekend and it doesn't look too prohibitively hard to implement.
> Yeah yeah, famous last words. We'll see. :)

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. However, I can reverse engineer your library to
understand the semantics you are suggesting, but it seems a little odd
that we would specify the semantics by creating generator library and
reverse engineering how the continuations work. Regardless, I'll make
suggestions of what I see as critical aspects of usable single frame
continuations demonstrated with small changes to that library.

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. In
your example, you had to coordinate error throwing with a receive()
function. The whole point of throws/exceptions is to avoid the need
for manual error passing/coordination. Forcing every user of single
frame continuations to utilize some type of receive function for error
handling is not acceptable.

There are a few different ways that we could support this. One way
would be to pass two functions to the yielding call function rather
than a single continuation function. The first function could be
called to resume the continuation with a normal value, and the second
function could be called to resume the continuation with a thrown
exception.

Another approach I would prefer would be to continue to use a single
function for resuming the continuation, but rather than passing the
value that is used to resume the continuation, pass a function that
would be executed on reentry to the continuation. The argument passed
to continuation would be a function that can return a normal value or
throw an error to resume the continuation. This makes it easy to
return a value or throw a frame, and helps gives users the ability to
preserve call stacks. Let me try to explain by adjustments to your
generator library:


On 4/1/2010 9:45 AM, Dave Herman wrote:
> yield <expr> ~~> this.receive(this->yield(<expr>))
change to:
yield <expr> ~~> this.yield->(<expr>)
>
> and
>
> function f(x1, ..., xn) body ~~> function f(x1, ..., xn) { return
> new Generator(function () { (function f(x1, ..., xn)
> body).call(this, x1, ..., xn); }); }
>
> I imagine it should be pretty easy to adapt this translation to
> work with your semantics instead, but for my sake it'd be more
> helpful to understand your semantics better first.
>
> Dave
>
> var [StopIteration, Generator] =
>
> (function() {
>
> var NEWBORN = 0; var DORMANT = 1; var RUNNING = 2; var CLOSED = 3;
>
> var StopIteration = {};
>
> function Yield(x) { this.value = x; } function Send(x) { this.sent
> = x; } function Throw(x) { this.thrown = x; }
Send and Throw are no longer needed.
>
> // [[function f(x1, ..., xn) body]] = // function f(x1, ..., xn) {
> //     return new Generator(function() { //         (function f(x1,
> ..., xn) body).call(this, x1, ..., xn); //     }); // } function
> Generator(f) { this.state = NEWBORN; this.suspended = function(x)
> { if (x !== void(0)) throw new TypeError("newborn generator"); //
> no need to bind `this' (will be this generator) return
> f.call(this); }; };
>
> Generator.prototype = {
>
> // [[yield e]] = this.receive(this->yield(e)) yield: function(x, k)
> { if ((this.state !== NEWBORN) && (this.state !== RUNNING)) throw
> "yield from dormant or dead generator"; this.state = DORMANT;
> this.suspended = k; return new Yield(x); },
>
> receive: function(x) { if (x instanceof Send) return x.sent; else
> if (x instanceof Throw) throw x.thrown; },
>
> sendOrThrow: function(x) { switch (this.state) { case RUNNING:
> throw "already running"; case CLOSED:  throw StopIteration;
> default: this.state = RUNNING; var result =
> this.suspended.call(this, x);
>
> // generator yielded if (result instanceof Yield) return
> result.value; // generator returned else { this.state = CLOSED;
> throw StopIteration; } } },
>
> send: function(x) { return this.sendOrThrow(new Send(x));
change to:

send: function(x) {
   return this.sendOrThrow(function(){

       return x;
   });
}
> },
>
> next: function() { return this.send(void(0)); },
>
> throw: function(x) { return this.sendOrThrow(new Throw(x));
change to:

throw: function(x) {
   return this.sendOrThrow(function(){
       throw x;
   });

}
> },
>
> close: function() { if (this.state === RUNNING) throw "already
> running"; this.state = CLOSED; this.suspended = null; }
>
> };
>
> return [StopIteration, Generator]; })();
>

Or stated in terms of translated code, if we had something like:
bar(foo->(2));
with your semantics would be roughly similar to:
foo(2, function(value){
  bar(value);
});
but with this change, I would suggest it should be translated:
foo(2, function(getValue){
  bar(getValue());
});


This change enable throwing or normal values with minimal effort. It
would also help with providing a means for users to preserve call
stacks. There would actually need to be more one more mechanism to
really do call stack preservation with this approach, the callback
function that is executed on reentry to the continuation really would
need a way to be able to refrain from resuming the continuation.
Perhaps a special exception or return value could be provided for this.


2. I am opposed to the notion of appending the continuation resume
function on to the list of arguments. Functions arguments can be
variable in length, so the callee would never know which position the
continuation function will be in, and must always look at the
arguments.length to determine that. In your example, if someone were
to directly use the generator library, calling this.yield->() or
this.yield->(1,2) would cause the function to be in a different place
than the library expected. Making it the first argument is no better,
since it shifts all the other arguments. If we are going to be passing
the continuation function to the yielding callee function, lets drop
the whole notion of trying to make it look like a call, and have the
yielding call operator take a single value for the right operand
rather than an argument list. Then, we could also drop the parenthesis
and make it look a little nicer as well. Your translated generator to
harmony code would then look like:
this.yield-> <expr>
Now the yield function can deterministically expect to receive a value
for the first argument, and the continuation function for the next
argument, and we have a cleaner syntax that avoids the woes of
expecting it act like a normal function call that Waldemar noted.

Thanks,
- -- 

Kris Zyp
SitePen
(503) 806-1841
http://sitepen.com
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
 
iEYEARECAAYFAkvF6+sACgkQ9VpNnHc4zAzGnACguL509xeSRwqnx5VY3eqpy79U
0NoAn18jINco1OWGbLXhv9F8SKCFao/C
=nGuM
-----END PGP SIGNATURE-----



More information about the es-discuss mailing list