Single frame continuations proposal

Kris Zyp kris at sitepen.com
Tue Mar 30 19:51:49 PDT 2010


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
 


On 3/30/2010 4:20 PM, David Herman wrote:
> Kris,
>
> Thanks for this proposal. I think it's got a lot going for it. I
> like the simplicity of the API, although I think it could be
> simplified even further.
>
>> This is often called continuation passing style (CPS) and is
>> quite verbose in JavaScript, difficult to debug, and can be very
>> complicated to use in non-linear control flow.
>
> Yes, I think there's a pretty clear need for better language
> support for programming with event-loop-concurrent API's.
>
>> I propose a new call operator that can expressed as a function
>> local translation that can greatly ease the construction of code
>> that involves resuming flow at a future point in time.
>
> I don't think it *should* be expressed as a translation in the
> spec, but let's keep specification approaches separate from the
> discussion at hand.
>
>> Traditional continuations were proposed for ES4, and rejected for
>> a couple of very important reasons.
>
> Uncontroversial; no one's championing full continuations for ES.
>
>> generators have been successfully implemented in SM and Rhino
>> without any unnecessary burdens on the VM since their semantics
>> are local to a single function and do not introduce interleaving
>> hazarads. But, generators are just too specialized and the API is
>> too difficult to use for other CPS style mechanisms.
>
> Your approach seems nicely Harmony-ous: small, simple, orthogonal.
> It would definitely be a cost, however, if there turned out to be
> some incompatibility with JS 1.7 generators. I don't think there is
> one, but it would be good to know-- and conversely, it'd be awesome
> if generators (minus the syntax) could really be implemented as a
> library, e.g. if "yield <expr>" could be simulated by calling:
>
> GeneratorsAPI->yield(<expr>)
>
>> semantics:
>
> I can't quite make sense of your pseudo-code, and I'm pretty sure
> it's not what you intended. I couldn't quite follow it enough to
> figure out what you meant.
>
>> 1. evaluate the LHS expression and then the argument expressions
>> (just like function calls) 2. Let *continuation* be defined as
>> the capture of the current function activation's continuation 3.
>> call the LHS value with the arguments (like a normal function
>> calls), and let *result* be the value returned from the call 4.
>> If the call throws an exception, throw the exception in the
>> current stack. 5. If *result* is an object and it has a function
>> value in the property named "continueWith", than proceed to step
>> 7. 6. Resume *continuation*, using the value of *result* for the
>> continued evaluation of the current expression (if the
>> continuation is inside an expression).
>
> Is this supposed to fall through?
>
Yes

>> 7. Set an internal flag *waiting* to true for this call. 8. Call
>> the function that is stored in the "continueWith" property of the
>> *result*. The function should be called with one argument, a
>> function value defined as *resume*. Let *continueWithResult* be
>> the value returned from the call. 9. Exit the function returning
>> *continueWithResult* 10. If and when *resume* is called, store
>> the first argument as *resumeNextFrame* and proceed to step 10.
>
> This is an infinite loop...
Should be proceed to step 11.
>
>> 11. If internal flag *waiting* is false, throw an Error "The
>> stack can not be resumed again". 12. Set the internal flag
>> *waiting* to false. 13. Call *resumeNextFrame* and let *result*
>> be set to the value returned from the call. Proceed to step 5.
>
> I think it's more complicated than necessary. NarrativeJS seems
> expressive enough that I bet you could express your semantics as a
> library on top of that. As you say, we're not in the business of
> blessing libraries! :)
>
> I would think the following sufficient and, IIRC, the same as
> NarrativeJS (roughly?):
>
> 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.
>
> This is quite a bit simpler. And I suspect it should be sufficient
> to implement your above semantics as well as JS 1.7 generators. I
> will see if I can sketch a translation.
>

This suggested change actually of three distinct changes that I think
can be considered orthogonally:

1. Remove the one-shot restriction - By removing the waiting flag and
check, the continuation could be called and reactivated multiple
times. I felt that by restricting the continuation to one-shot, it
would keep the proposal safer and more modest, and would retain the
normal invariant that statements within a function that are not in a
loop won't be executed more than once per function invocation, thus
not introducing any new coding hazards. If others don't see multi-shot
continuations as a hazard, I don't really mind if the one-shot
restriction is lifted.

2. Passing the continuation to the callee - As I mentioned before, I
think it is very important to maintain a separation of concerns
between the call arguments and continuation handling, and the call
arguments shouldn't be modified. I believe this presents a much more
consistent model to users. With my proposal, foo->(3) and foo(3) call
the foo function in exactly the same way, they only differ in how they
treat the function's return value. This also makes it possible to use
the yielding operator for sync/async normalization, allowing one to
use yielding call on existing synchronous functions to prepare for the
possibility of a future asynchronous implementation. One can write
code that is explicitly asynchronous ready without coupling to the
sync vs async implementation of the callees. For example, if one
implemented an array list object that could potentially support
asynchronous implementations, one might write:

arrayish.push->(3)

With my implementation, this works fine with a standard push
implementation. If we modify the arguments list and add the
continuation, this call would result in the addition of two elements
to the array (3 and the continuation). Furthermore, the continuation
won't even be resumed, because a standard push() wouldn't call the
callback.

3. Calling the callback/continuation (*k*/*resume*) function with the
value returned from the callee's execution of it's continuation
(instead of calling a function that executes the callee's
continuation) - The primary drawback to this change is that it
eliminates the call stack. With your approach the resumed execution
basically executes in trampolining fashion. My belief is that
retaining a standard call stack is invaluable for debuggability, and
this is retained with the original algorithm.

Also, it is worth pointing out that your simplification is
insufficient to propagate errors to callers. One would need to add a
second callback function that could be called to signal an exception
to be thrown (at least in the case of the yielding operator being
called within a try block). And with this correction, this change
isn't really much simpler, I don't think.


Also, just to be clarify the behavior of NarrativeJS, it uses a much
different call procedure than either of our algorithms (which I don't
think is really suitable for a public API). Functions are called with
an extra argument that is special frame object (I don't think you can
call it directly), and the called function can return a normal value
(hence supporting calling synchronous functions that can ignore the
extra frame object parameter and properly continuing) or a special
"suspension" value. It also recreates call stacks to preserve
debuggability.

Anyway, thanks for the corrections and compelling suggestions.

- -- 
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/
 
iEYEARECAAYFAkuyuMUACgkQ9VpNnHc4zAzC0gCeMY8c4vCxOcM0+ZNTCHLi6JDR
g0gAn2bga0fTcwR2M96piZ4D3loVM19b
=mJFD
-----END PGP SIGNATURE-----



More information about the es-discuss mailing list