Discuss
  • Single frame continuations proposal

Single frame continuations proposal

# Kris Zyp (15 years ago)

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

I wanted to propose the addition of a new syntax and API for single-frame continuations in ES6. The use of callback functions to continue the execution of code is extremely common pattern in JavaScript, particularly with asynchronous operations where a callback is necessary to notify code that an action has completed and execution can resume. 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. 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.

Traditional continuations were proposed for ES4, and rejected for a couple of very important reasons. First, it adds a great burden on implementors. ES VMs need to be able to capture and reify call stacks, prepare optimizations to deal with possible exits for any calls, and native functions that may call non-native functions (Array's forEach, map, etc, String's replace, and so on) must be rewritten to handle continuations. Second, it introduces interleaving hazards. Functions that were written with the run-to-completion expectation would suddenly be exposed to possibility of being executed across multiple event turns. This proposal avoids these problems by being restricted to a local single-frame of execution. An EcmaScript function body can only span pause and resume across multiple event turns if an explicit yielding call is used.

This proposal is based on the concepts from Mozilla's JavaScript 1.7 generators, Neil Mix's Narrative JavaScript project, and the promise-based approach to asynchronous coding. I believe that generators demonstrate a form of single-frame continuations that are exactly what we need in terms of providing elegant alternate to CPS code while avoiding introducing concurrency hazards. These allow for functions to yield control and later resume the natural flow of the function. JS 1.7 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. On the otherhand, the yielding call proposal I am suggesting composes well. We need a form of single-frame continuations that is sufficiently generalized that we can build generators, elegant promises, and much more in EcmaScript. This proposal actually closely resembles the continuations of Narrative JavaScript, using the same yielding call syntax and providing similar behavior, but with a different API that is more suitable for a broad array of use cases.

With this design, the intention is that instead of writing code like this:

xhrGet({ url:"my-data", load: function(data){ // the callback for when the data is loaded if(data.additionalInformation){ // there is additional data we need to get, load it too xhrGet({ url:data.additionalInformation, load: function(additionalData){ data.additionalData = additionalData; render(data); } }); } else{ // ready now, go ahead and render render(data); } function render(data){ someElement.innerHTML = template.process(data); } } });

With proper library adjustments this could be written instead as:

var data = xhrGet->({url:"my-data"});

if(data.additionalInformation){ // there is additional data we need to get, load it too data.additionalData = xhrGet->({url:data.additionalInformation}); } someElement.innerHTML = template.process(data);

= The proposal for single frame continuations through yielding call syntax =

The actual specification of the syntax and semantics of proposal:

syntax: <expr> ::= ... | <expr> "->" <arg-list>

semantics:

  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).
  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.
  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.

This proposal does not define how one creates convenience apis for continuations, promises, or otherwise. It simply defines the semantics of a new call syntax and thereby defines an interface for creating objects that can be used with the new yielding calling syntax. Specifically one creates continuation objects by having them implement a "continueWith" function. One can implement the "continueWith" function as part of a promise library, for onload syntax, for creating a generator library, and any other form that one would use CPS-based flow. There are a broad variety of object types that could implement this interface and interact with yielding calls. We could potentially provide a default Continuation constructor OOTB, but it certainly wouldn't be necessary.

Some key premises behind this proposal for how improved facilities for how continuations could be added to EcmaScript:

  • Don't mess with the current concurrency model - EcmaScript's current shared-nothing event-loop concurrency model is ideal for preventing concurrency hazards.
  • Don't introduce traditional continuations - Traditional full-stack splitting continuations have been rejected for good reasons from EcmaScript. They violate the run-to-completion model expectation of functions and thus introduce interleaving hazards. They also incur extra burden on implementations.
  • Consequently, I don't want to suggest any new runtime semantics (like VM level stack interruption and resumption), only new syntax that can be expressed as a local translation.. What I would like to see:
  • Easy construction of code flow that must span event turns through explicit single-frame continuations.
  • Composable API - The API for single-frame continuations should be adequate that one could build promise-based asynchronous calls, callback-parameter-based asynchronous calls, and (JS 1.7-style) generators (potentially with the help of libraries). In fact, I put together a sample generator library (similar to JS1.7 generators) built on top of this proposal [1].
  • Preservation of causality - Provide a means for preserving normal call stacks as execution "resumes" is important for sane debuggability.

= Example expressed as translation =

An example yielding call usage: function foo(){ var a = bar->(10); // asynchronous yielding call

return a + 2; }

This could be roughly expressed as ES5 translated code like: function foo(){ // make the initial call var $result = bar(10); // process the result, returning the completion of the function's // execution, or a continuation object if it is not yet complete. return $handleResult($result); function $handleResult($result){ if($result && typeof $result.continueWith === "function"){ // the return value is a continuation, register to be a part of // the resumed call stack var $waiting = true; return $result.continueWith(function($resumeNextFrame){ if($waiting){ // ensure that the callback is only called once $waiting = false; // resume the next function in the stack return $handleResult($resumeNextFrame()); } // already called throw new Error("The stack can not be resumed again"); }); } else { // execute the continuation of the function var a = $result; return a + 2; } } }

= Considerations = This proposal has been discussed by a few of us offlist for a while, so I am sharing a few questions/points from other discussions:

  • What happens if you call a normal synchronous function with the yielding call syntax?

It still works. One of the key aspects of this design is following the separation of concerns principle from promises where the arguments passed to a function do not need to be conflated with the concerns of asynchronicity and callback continuation. Therefore when you use the func->(value) syntax, the func is called with value just as with a

normal function call. Also, the yielding call semantics include a check on the return value to determine if it is a normal "sync" value, or if it is a continuation object (has a "continueWith" property) and thus requires special asynchronous processing. If you call Math.min->(1,2),

it would will behave exactly the same as Math.min(1,2).

This is very valuable in providing sync/async normalization. One can call MyMath.sqrt->(2), and be prepared for a synchronous result or

asynchronous result. One could then initially implement MyMath.sqrt synchronously and then later reimplement it to use a worker for asynchronous processing, and MyMath.sqrt->(2) would continue to work.

  • Why does this require a call to resumeNextFrame? Why can't we just have callback that is called with a result?

Normal CPS style results in inverted call stacks when you resume. The top of the original call stack usually receives the initial notification, which calls its caller, and which calls it caller, etc. Using this resumeNextFrame callback technique from this proposal preserves the upright call stack on resume, making it easy to debug asynchronous applications with a standard familiar debugger (and one does not need to introduce any new tools for preserving casuality).

  • Does this require special magic to preserve call stacks?

No, the way the callback pattern is structured, when it is time to resume, the original caller is first called, which calls the next callee, which calls the next callee, and so on. This recreates the call stack without any magic needed from the VM.

  • What happens when one uses a standard call to call a function that expects to be called with yielding syntax (returns a continuation object)?

A continuation object will be returned from the call. The function will not be suspended (as this would break the run-to-completion expectation of that function). However, depending on how the continuation provider implemented the continuation, they may still be able to use the continuation object in a useful way. For example, if the continuation object was also a promise, one may be able to register a callback that will be called with result of the eventual completion of the asynchronous callee.

  • There are other suggestions/proposals for using lambda and other keystroke reducing techniques for inline functions. Why not use that for easing callback usage?

It falls short of helping with the real complexity of passing callbacks. Saving users from typing "function(" is mildly helpful, but I think the real value of single-frame continuations is in expressing complex flows without having to completely rewrite in with CPS. Functions like this: function findParentWithName(start, name){ var parent = start; while(parent){ parent = parent.getParent(); if(parent && parent.name == name){ return parent; } } }

If we changed getParent()'s implementation to be asynchronous, we could certainly rewrite this with callbacks with sugar, but it would be a vastly more significant change than simply changing the parent.getParent(); to parent.getParent->();

  • But I like my promise/deferred/continuable library X, why not standardize on that?

Of course EcmaScript doesn't generally standardize on one library's API. This proposal is intentionally designed to be generic enough that numerous libraries, existing and yet to be created, could build on top of this syntax, including ref_send, Dojo's Deferreds, JSDeferred, onload handlers, and even Mozilla's JS1.7 generators could be implemented (with minor syntax change) as JS library on top of it (see below). Using a single-frame continuations is suitable for wide-range of capabilities that would otherwise require callback-based mechanism. For example, I could easily imagine libraries leveraging this to improve their existing APIs: JQuery: $.ready->(); doSomethingInJQueryAfterPageIsLoaded();

Dojo: dojo.waitForLoad->(); doSomethingInDojo();

LABjs: script("a.js").script("b.js").wait->(); nowUseSomethingFromA();

[1] Generator library: generator-example.js: /* This is taken from the generator example at: developer.mozilla.org/en/New_in_JavaScript_1.7#Generators And converted to using -> call syntax with a generator library. The

main differences between JS1.7 generators is that the function has to be wrapped with a generator converter and the yield is a little different syntax (yield->(i) instead of yield i). This is a slightly more

keystrokes than JS1.7 generators, but I think this is actually useful explicitness. It is clear what functions are generators, and the breaks in execution in the function are easy to spot with the ->()

operator.

fib = generator(function() {
var i = 0, j = 1;
while (true) {
yield->(i);
var t = i;
i = j;
j += t;
}
});

var g = fib();
for (var i = 0; i < 10; i++) {
document.write(g.next() + "<br>\n");
} */

// roughly compiles to (omitting a lot of the security checks and branches): fib = generator(function() { var i = 0, j = 1;
var continuing = false; function next(){ while(true){ if(!continuing){ continuing = true; return yield(i).continueWith(next); } var t = i; i = j;
j += t; continuing = false; } } return next(); });

var g = fib();
for (var i = 0; i < 10; i++) {
document.write(g.next() + "<br>\n");
}

generator.js: /**

  • An implementation of JS1.7 style generators using the proposed ES6 yielding calling API */ (function(){
    var yieldedCallback, yieldedValue; var yieldReturn = {}; // special marker to indicate that it was a yield call yield = function(value){ // intended to be called with yielding syntax, like yield->(v); yieldedValue = value; return { continueWith: function(resume){ yieldedCallback = resume; return yieldReturn; } }; }

    generator = function(func){ return function(){ var args = arguments, self = this, callback, throwing;

          var executeNext = function(value){
          if(typeof value !== "undefined"){
              throw new TypeError("Can not pass a value on the

initial call to a generator"); } // first time call the function checkReturn(func.apply(self, args)); // all subsequent calls, we execute the next callback provided by the yielding call executeNext = function(value){ checkReturn(callback(function(){ // the value that is asynchronously returned by yield->(); if(throwing){ throwing = false; throw value; } return value; })); } } function send(value){ executeNext(value); callback = yieldedCallback; return yieldedValue; } function checkReturn(returnValue){ // checks to see if the function returned (instead of calling yield) if(yieldReturn !== returnValue){ throw StopIteration; } } // return the iterator for this generator return { send: send, next: function(){ return send(); }, "throws": function(error){ throwing = true; send(error); } }; }; }; if(typeof StopIteration === "undefined"){ StopIteration = {}; } })();

# David Herman (15 years ago)

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?

  1. Set an internal flag waiting to true for this call.
  2. 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.
  3. Exit the function returning continueWithResult
  4. If and when resume is called, store the first argument as resumeNextFrame and proceed to step 10.

This is an infinite loop...

  1. If internal flag waiting is false, throw an Error "The stack can not be resumed again".
  2. Set the internal flag waiting to false.
  3. 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.

  • Don't mess with the current concurrency model - EcmaScript's current shared-nothing event-loop concurrency model is ideal for preventing concurrency hazards.

Agreed (other than the word "ideal").

  • Don't introduce traditional continuations

Agreed.

  • Consequently, I don't want to suggest any new runtime semantics

You have. :) </pedant>

But I would support a claim that you've held the line and suggested a very modest change to the runtime semantics.

What I would like to see:

  • Easy construction of code flow that must span event turns through explicit single-frame continuations.
  • Composable API.
  • Preservation of causality

Agreed.

It'd be helpful to understand is why you felt these should be restricted to one-shot continuations (i.e., callable at most once).

Thanks,

# Kris Zyp (15 years ago)

-----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
    1. 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

  1. 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.

  1. 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.

  1. 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.

# David Herman (15 years ago)

I've been poring over this for a while, and it's still really, really confusing. Could I ask you to show how you would write the following example with your proposal?

function setup() {
    setFlashing(document.getElementById("notificationArea"));
    alert("done setup!");
}

var flashingElts = [];

function setFlashing(elt) {
    var toggle = true;
    window.setTimeout(function() {
        elt.style.background = toggle ? "red" : "white";
        toggle = !toggle;
    }, INTERVAL);
    flashingElts.push(elt);
}

And then would you mind showing a rough translation of your implementation to ES5 code (similar to the translation of your `foo' function)?

  1. 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

That can't be true, can it? If step 6 continues to step 7 then we get:

// step 5
if (!($result && typeof $result.continueWith === "function")) {
    // do step 6
}
// fall through
var $waiting = true;
var $continueWithResult = $result.continueWith($resume);

But we established in step 5 that there's no $result.continueWith function.

# Kris Zyp (15 years ago)

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

On 3/31/2010 10:56 AM, David Herman wrote:

Hi Kris,

I've been poring over this for a while, and it's still really, really confusing. Could I ask you to show how you would write the following example with your proposal?

function setup() { setFlashing(document.getElementById("notificationArea")); alert("done setup!"); }

var flashingElts = [];

function setFlashing(elt) { var toggle = true; window.setTimeout(function() { elt.style.background = toggle ? "red" : "white"; toggle = !toggle; }, INTERVAL); flashingElts.push(elt); }

I am not exactly sure what that intent is here, but I am guessing it is supposed to flash several times before showing the alert. So maybe we could do it with something like:

function setup() {
    setFlashing->(document.getElementById("notificationArea"));
    alert("done setup!"); // called after 10 flashes
}

function setFlashing(elt) {
    for(var i = 0; i < 10; i++){ //toggle 10 times
        var toggle = true;
        sleep->(INTERVAL); // yield for each sleep
        elt.style.background = toggle ? "red" : "white";
        toggle = !toggle;
    }
}

And then would you mind showing a rough translation of your implementation to ES5 code (similar to the translation of your `foo' function)?

However, before getting more into the translation and implementation of a delay function, something you said earlier...

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:

This really lead me to think about if it would be possible to meet the goals of this proposal and make this fully compatible (syntax and default behavior) with JS 1.7 generators. That is make it compatible with generators and still making it sufficiently extensible to meet the broad range of needs that could utilize single-frame continuations/coroutines. And I believe it is, and it could done in a way that this proposal could be implemented in JavaScript as well generators. Do you think it would be worth exploring that possibility? I'll put a sketch together in another email for this alternate approach, (if it doesn't sound good, we can revert back to digging into this one).

  1. 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

That can't be true, can it? If step 6 continues to step 7 then we get:

// step 5 if (!($result && typeof $result.continueWith === "function")) { // do step 6 } // fall through var $waiting = true; var $continueWithResult = $result.continueWith($resume);

But we established in step 5 that there's no $result.continueWith function.

You are right, once the continuation is resumed the algorithm is completed.

# Dave Herman (15 years ago)

I am not exactly sure what that intent is here, but I am guessing it is supposed to flash several times before showing the alert.

No, sorry that I meant window.setInterval rather than window.setTimeout, but otherwise I think I wrote what I meant. I wanted it to alert "done setup!" immediately after installing the animation, not after the animation finishes. Similarly, I wanted setFlashing to add itself to an array immediately after setting up the animation. Don't worry about only doing it 10 times, just let it flash forever. :)

This really lead me to think about if it would be possible to meet the goals of this proposal and make this fully compatible (syntax and default behavior) with JS 1.7 generators. That is make it compatible with generators and still making it sufficiently extensible to meet the broad range of needs that could utilize single-frame continuations/coroutines. And I believe it is, and it could done in a way that this proposal could be implemented in JavaScript as well generators. Do you think it would be worth exploring that possibility?

I actually have already sketched such a translation, albeit using the semantics I proposed. I'm including it below. Essentially, you have to translate two things: 1) the yield' expression form, and 2) generator functions. The latter is necessary because generator functions don't start executing their function body until the firstsend'. So the translation is:

yield <expr> ~~> this.receive(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);
    });
}

Actually, I think this probably gets this' wrong; I don't have the time ATM to look up what the semantics ofthis' is within a generator body. But that should be pretty easily fixable.

At any rate, this is relatively clean and I think's a plausibility check that single-frame continuations should be simpler and more general than generators, and likely compatible with them.

I'll put a sketch together in another email for this alternate approach, (if it doesn't sound good, we can revert back to digging into this one).

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; }

// [[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));
},

next: function() {
    return this.send(void(0));
},

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

close: function() {
    if (this.state === RUNNING)
        throw "already running";
    this.state = CLOSED;
    this.suspended = null;
}

};

return [StopIteration, Generator]; })();

# Kris Zyp (15 years ago)

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

On 4/1/2010 9:45 AM, Dave Herman wrote:

I am not exactly sure what that intent is here, but I am guessing it is supposed to flash several times before showing the alert.

No, sorry that I meant window.setInterval rather than

window.setTimeout, but otherwise I think I wrote what I meant. I wanted it to alert "done setup!" immediately after installing the animation, not after the animation finishes. Similarly, I wanted setFlashing to add itself to an array immediately after setting up the animation. Don't worry about only doing it 10 times, just let it flash forever. :) In order to utilize leverage continuations with a function that execute multiple we would need to eliminate single-shot restriction. You could then create some library function that passed the continuation to the setInterval function to do something like: var toggle = true; intervalling->(INTERVAL); elt.style.background =...

But in this case, using the yielding call would be confusing and provide very little benefit. This is definitely not the type of scenario that it is designed for, normal anon functions work great here. This is geared for when a callback is used to execute the remainder of a sequence after the completion of an asynchronous that we see so often in JavaScript.

This really lead me to think about if it would be possible to meet the goals of this proposal and make this fully compatible (syntax and default behavior) with JS 1.7 generators. That is make it compatible with generators and still making it sufficiently extensible to meet the broad range of needs that could utilize single-frame continuations/coroutines. And I believe it is, and it could done in a way that this proposal could be implemented in JavaScript as well generators. Do you think it would be worth exploring that possibility?

I actually have already sketched such a translation, albeit using the

semantics I proposed. I'm including it below. Essentially, you have to translate two things: 1) the yield' expression form, and 2) generator functions. The latter is necessary because generator functions don't start executing their function body until the firstsend'. So the translation is:

yield <expr> ~~> this.receive(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);
    });
}

Actually, I think this probably gets `this' wrong; I don't have the

time ATM to look up what the semantics of `this' is within a generator body. But that should be pretty easily fixable.

At any rate, this is relatively clean and I think's a plausibility

check that single-frame continuations should be simpler and more general than generators, and likely compatible with them.

Yes, I believe that should work.

Do you prefer basing single-frame continuations on new non-latin character syntax instead of using the "yield" keyword (hadn't realized it was already reserved in ES5 strict-mode when I did the first proposal)?

# David Herman (15 years ago)

[BTW, your quoted text got garbled.]

In order to utilize leverage continuations with a function that execute multiple we would need to eliminate single-shot restriction. You could then create some library function that passed the continuation to the setInterval function to do something like: var toggle = true; intervalling->(INTERVAL); elt.style.background =...

Your answers keep leaving out the definition of the function that you're calling via ->', which is supposed to be the part that creates the requisite object withcontinueWith' etc. Examples don't do much good if they skip the part they were supposed to illustrate!

But in this case, using the yielding call would be confusing and provide very little benefit. This is definitely not the type of scenario that it is designed for, normal anon functions work great here. This is geared for when a callback is used to execute the remainder of a sequence after the completion of an asynchronous that we see so often in JavaScript.

I know. I wanted an example that had both asynchronous and synchronous statements, to understand the control flow of your proposal better, but I also was trying to keep it short. Maybe you'd prefer this example, which more clearly separates the parts that would be expressed with `->':

function setup() {
    getThreeThings(URL1, URL2, URL3);
    alert("done setup!");
}

function getThreeThings(url1, url2, url3) {
    getAndFrob(url1);
    getAndMunge(url2);
    getAndGrok(url3);
}

function getAndFrob(url) {
    var xhr = new SimpleXHR(url);
    xhr.get(function(data) {
        window.setTimeout(function() {
            frob(data);
        }, TIMEOUT);
    });
}

function getAndMunge(url) {
    var xhr = new SimpleXHR(url);
    xhr.get(function(data) {
        window.setTimeout(function() {
            munge(data);
        }, TIMEOUT);
    });
}

function getAndGrok(url) {
    var xhr = new SimpleXHR(url);
    xhr.get(function(data) {
        window.setTimeout(function() {
            grok(data);
        }, TIMEOUT);
    });
}

Would you mind writing out how to express this program with your proposal? I'm just trying to understand. If you can help me with some examples I think I maybe able to help clarify your ideas.

Do you prefer basing single-frame continuations on new non-latin character syntax instead of using the "yield" keyword (hadn't realized it was already reserved in ES5 strict-mode when I did the first proposal)?

I don't follow you. Non-latin?

# Kris Zyp (15 years ago)

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

On 4/5/2010 10:26 AM, David Herman wrote:

[BTW, your quoted text got garbled.]

In order to utilize leverage continuations with a function that execute multiple we would need to eliminate single-shot restriction. You could then create some library function that passed the continuation to the setInterval function to do something like: var toggle = true; intervalling->(INTERVAL); elt.style.background =...

Your answers keep leaving out the definition of the function that you're calling via ->', which is supposed to be the part that creates the requisite object withcontinueWith' etc. Examples don't do much good if they skip the part they were supposed to illustrate!

But in this case, using the yielding call would be confusing and provide very little benefit. This is definitely not the type of scenario that it is designed for, normal anon functions work great here. This is geared for when a callback is used to execute the remainder of a sequence after the completion of an asynchronous that we see so often in JavaScript.

I know. I wanted an example that had both asynchronous and synchronous statements, to understand the control flow of your proposal better, but I also was trying to keep it short. Maybe you'd prefer this example, which more clearly separates the parts that would be expressed with `->':

function setup() { getThreeThings(URL1, URL2, URL3); alert("done setup!"); }

function getThreeThings(url1, url2, url3) { getAndFrob(url1); getAndMunge(url2); getAndGrok(url3); }

function getAndFrob(url) { var xhr = new SimpleXHR(url); xhr.get(function(data) { window.setTimeout(function() { frob(data); }, TIMEOUT); }); }

function getAndMunge(url) { var xhr = new SimpleXHR(url); xhr.get(function(data) { window.setTimeout(function() { munge(data); }, TIMEOUT); }); }

function getAndGrok(url) { var xhr = new SimpleXHR(url); xhr.get(function(data) { window.setTimeout(function() { grok(data); }, TIMEOUT); }); }

Would you mind writing out how to express this program with your proposal? I'm just trying to understand. If you can help me with some examples I think I maybe able to help clarify your ideas.

OK, here is some code:

function setup() {
    getThreeThings->(URL1, URL2, URL3);
    alert("done setup!");
}

function getThreeThings(url1, url2, url3) {
    getAndFrob->(url1);
    getAndMunge->(url2);
    getAndGrok->(url3);
}

function getAndFrob(url) {
    var xhr = new SimpleXHR(url);
    var data = xhr.get->();
    sleep->(TIMEOUT);
    return frob(data);
}

Translated:

function setup(){ var $result = getThreeThings(URL1, URL2, URL3); return $handleResult($result); function $handleResult($result){ if($result && typeof $result.continueWith === "function"){ var $waiting = true; return $result.continueWith(function($resumeNextFrame){ if($waiting){ $waiting = false; return $handleResult($resumeNextFrame()); } throw new Error("The stack can not be resumed again"); }); } else { // execute the continuation of the function alert("done setup!"); } } }

function getThreeThings(url1, url2, url3) { var $codePointer = 0; var $result = getAndFrob(url1); return $handleResult($result); function $handleResult($result){ if($result && typeof $result.continueWith === "function"){ var $waiting = true; return $result.continueWith(function($resumeNextFrame){ if($waiting){ $waiting = false; return $handleResult($resumeNextFrame()); } throw new Error("The stack can not be resumed again"); }); } else { // execute the continuation of the function if($codePointer == 0){ $codePointer++; return $handleResult(getAndMunge(url2)); } if($codePointer == 1){ return $handleResult(getAndGrok(url3)); }

}

} }

function getAndFrob(url) { var $codePointer = 0; var xhr = new SimpleXHR(url); var data = xhr.get(); return $handleResult(data); function $handleResult($result){ if($result && typeof $result.continueWith === "function"){ var $waiting = true; return $result.continueWith(function($resumeNextFrame){ if($waiting){ $waiting = false; return $handleResult($resumeNextFrame()); } throw new Error("The stack can not be resumed again"); }); } else { // execute the continuation of the function if($codePointer == 0){ $codePointer++; return $handleResult(sleep(INTERVAL)); } if($codePointer == 1){ return frob(data); }

}

} }

getAndFrob, getAndMange, and getAndGrok are all basically the same.

// very simple continuation implementation function Continuation(){ var resolvedValue; var bottomFrame = function(){ return resolvedValue; }; var continuation = { continueWith: function(next){ var nextFrame = bottomFrame; bottomFrame = function(){ return next(nextFrame); } return continuation; }, resume: function(value){ resolvedValue = value; bottomFrame(); } }; return continuation; } // sleep function that uses a continuation function sleep(ms){ var continuation = new Continuation(); setTimeout(function(){ continuation.resume(); }, ms); return continuation; } function SimpleXHR(url){ var xhr = new XMLHttpRequest(); return { get: function(){ var continuation = new Continuation(); xhr.open("GET", url); xhr.onload = continuation.resume; xhr.send(); return continuation; } }; }

Also, if you want to see what this would look like with the "yield" keyword based alternative:

var startCoroutine = simpleContinuationHandler;
function setup() {
    yield getThreeThings(URL1, URL2, URL3);
    alert("done setup!");
}

function getThreeThings(url1, url2, url3) {
    yield getAndFrob(url1);
    yield getAndMunge(url2);
    yield getAndGrok(url3);
}
/* Note these could be done in parralel with:
function getThreeThings(url1, url2, url3) {
    var frobbed = getAndFrob(url1);
    var munged = getAndMunge(url2);
    var grokked = getAndGrok(url3);
    yield frobbed, yield munged, yield grokked;
}
*/

function getAndFrob(url) {
    var xhr = new SimpleXHR(url);
    var data = yield xhr.get();
    yield sleep(TIMEOUT);
    return frob(data);
}

...

Translated:

function setup(){ var $pointer = 0; // used to keep track of where we are // create the controller var $controller = { suspended: true, resume: function(getValue){ var nextValue; if(getValue){ nextValue = getValue(); } if($pointer == 0){ // start of function $pointer++; // execute until the yield operator and return the value passed to yield return getThreeThings(URL1, URL2, URL3); } if($pointer == 1){ // continuation from the yield $pointer++; // continue execution until the return operator $controller.suspended = false; // no more yield, function is done alert("done setup!"); return; } if($pointer > 1){ throw new Error("Can not resume a function that has returned"); } } }; // call the startCoroutine function return startCoroutine($controller); }

function getThreeThings(url1, url2, url3) { var $pointer = 0; // used to keep track of where we are // create the controller var $controller = { suspended: true, resume: function(getValue){ var nextValue; if(getValue){ nextValue = getValue(); } if($pointer == 0){ // start of function $pointer++; // execute until the yield operator and return the value passed to yield return getAndFrob(url1); } if($pointer == 1){ // continuation from the yield $pointer++; return getAndMunge(url2); } if($pointer == 2){ // continuation from the yield $pointer++; // continue execution until the return operator $controller.suspended = false; // no more yield, function is done return getAndGrok(url3); }

  if($pointer > 2){
    throw new Error("Can not resume a function that has returned");
  }
}

}; // call the startCoroutine function return startCoroutine($controller); }

function getAndFrob(url) { var $pointer = 0; // used to keep track of where we are // create the controller var $controller = { suspended: true, resume: function(getValue){ var nextValue; if(getValue){ nextValue = getValue(); } if($pointer == 0){ // start of function $pointer++; // execute until the yield operator and return the value passed to yield var xhr = new SimpleXHR(url); return xhr.get(); } if($pointer == 1){ // continuation from the yield $pointer++; var data = nextValue; return sleep(TIMEOUT); } if($pointer == 2){ // continuation from the yield $pointer++; // continue execution until the return operator $controller.suspended = false; // no more yield, function is done return frob(data); }

  if($pointer > 2){
    throw new Error("Can not resume a function that has returned");
  }
}

}; // call the startCoroutine function return startCoroutine($controller); }

// Implementation of the continueWith proposal using the yield/startCoroutine proposal

function simpleContinuationHandler(controller){ function handleResult(value){ if(!controller.suspended){ return value; } if(value && typeof value.continueWith === "function"){ var waiting = true; return value.continueWith(function(resume){ if(!waiting){ throw new Error("can't resume stack"); } waiting = false; return handleResult(resume()); }); } else{ return handleResult(controller.resume(function(){ return value; })); }

} return handleResult(controller.resume());

}

And the library functions defined above (Continuation, sleep, and SimpleXHR) would work with this startCoroutine implementation and translation.

Do you prefer basing single-frame continuations on new non-latin character syntax instead of using the "yield" keyword (hadn't realized it was already reserved in ES5 strict-mode when I did the first proposal)?

I don't follow you. Non-latin?

Dave

I just meant "yield" vs "->()".

# Waldemar Horwat (15 years ago)

David Herman wrote:

Your answers keep leaving out the definition of the function that you're calling via ->', which is supposed to be the part that creates the requisite object withcontinueWith' etc. Examples don't do much good if they skip the part they were supposed to illustrate!

I have the same comments as David here. I don't understand what you're trying to do here with the many levels of closures that take closures that take closures that take closures that ... ad infinitum. I have yet to see the case that bottoms the whole thing out. The thing that makes your proposals so painful to read is that the examples quickly blow up into too much code to figure out your intent.

Waldemar
# Kris Zyp (15 years ago)

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

On 4/5/2010 7:05 PM, Waldemar Horwat wrote:

David Herman wrote:

Your answers keep leaving out the definition of the function that you're calling via ->', which is supposed to be the part that creates the requisite object withcontinueWith' etc. Examples don't do much good if they skip the part they were supposed to illustrate!

I have the same comments as David here. I don't understand what you're trying to do here with the many levels of closures that take closures that take closures that take closures that ... ad infinitum. I have yet to see the case that bottoms the whole thing out. The thing that makes your proposals so painful to read is that the examples quickly blow up into too much code to figure out your intent.

That is kind of the point, continuation passing style quickly becomes extremely complicated for non-trivial code flows. However, if my coding examples are poorly organized or unnecessarily complicated, I'd be glad to change them. Maybe it would help if you translated some JS1.7 code (I assume you know how JS1.7 generators work), and I could use that as a basis for my samples. How about: function foo(){ var a = bar(); if(yield a) yield hi(); bye(); }

Once again my primary intention is that JS1.7 generators provide the type of continuations/coroutines support that we want, they just need a more generalizable API, so they can be used for more than just generators.

# David Herman (15 years ago)

We've given this quite a bit of time, and I don't know how far we're going to get in understanding all the details of your proposal. But I think I can address some of my disagreements.

  1. I'm skeptical whether the requirement you stated of future-proofing code for async implementations is likely to happen, and in fact, I think it would be harmful. Take your example: someone writes an Arrayish API, and maybe it's concurrent, maybe it's not, maybe it changes to become concurrent at some point. So a client writes:

    ... function push3() { arrayish.push->(3); }

Whoever uses push3 now has to be aware that it may or may not happen concurrently, so they have to be concurrency-safe too. Otherwise they might be tempted to do:

push3();
var x = arrayish.pop(); // this is gonna be 3, I'm sure of it!

and sadness would ensue. You're proposing making it easier to create mutable concurrent (or possibly-concurrent) data structures. Greasing the wheels of shared-state concurrency is dangerous and not a good idea for ES.

  1. I don't fully understand why you have so much machinery around chaining continuations. There are two ways in which chaining happens in existing code: nested flows through host-API callbacks (expressed in CPS), and explicit composition. With first-class continuations, the former is already alleviated for free-- there's no need for additional machinery to wire together pieces of the continuation. And if you represent captured continuations as functions, you still get composition on the cheap with good old function composition.

  2. I'm also unsure what you mean by "preserving causality" or "preserving stacks" -- but I thought you meant that you wanted debugging environments to be able to present natural stack traces in the presence of continuations. Again, this seems unproblematic to me with a traditional continuation-capture mechanism. Assuming a semantics where -> causes a continuation capture, if you do:

    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.

  1. 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. ;)

  2. We should also aim for a design that tries to be compatible with existing API's, so that people don't have to write wrappers for all the standard libraries. As much as possible, anyway.

# Waldemar Horwat (15 years ago)

David Herman wrote:

We've given this quite a bit of time, and I don't know how far we're going to get in understanding all the details of your proposal. But I think I can address some of my disagreements.

  1. I'm skeptical whether the requirement you stated of future-proofing code for async implementations is likely to happen, and in fact, I think it would be harmful. Take your example: someone writes an Arrayish API, and maybe it's concurrent, maybe it's not, maybe it changes to become concurrent at some point. So a client writes:

    ... function push3() { arrayish.push->(3); }

Whoever uses push3 now has to be aware that it may or may not happen concurrently, so they have to be concurrency-safe too. Otherwise they might be tempted to do:

push3();
var x = arrayish.pop(); // this is gonna be 3, I'm sure of it!

and sadness would ensue. You're proposing making it easier to create mutable concurrent (or possibly-concurrent) data structures. Greasing the wheels of shared-state concurrency is dangerous and not a good idea for ES.

Yes, a good example of how this proposal doesn't compose. Suppose push3 returned an object which the caller needed:

...
function push3() {
    arrayish.push->(3);
    return someComputation();
}

var r = push3(); var x = arrayish.pop(); // this is gonna be 3, I'm sure of it!

How would you get something like this to work?

  1. I don't fully understand why you have so much machinery around chaining continuations. There are two ways in which chaining happens in existing code: nested flows through host-API callbacks (expressed in CPS), and explicit composition. With first-class continuations, the former is already alleviated for free-- there's no need for additional machinery to wire together pieces of the continuation. And if you represent captured continuations as functions, you still get composition on the cheap with good old function composition.

Ditto.

  1. I'm also unsure what you mean by "preserving causality" or "preserving stacks"

Me too.

  1. We should also aim for a design that tries to be compatible with existing API's, so that people don't have to write wrappers for all the standard libraries. As much as possible, anyway.

Yes, that bothers me too. I'd want a simple continuation, not a continuation that takes a continuation parameter.

  1. If I understand it correctly, another issue I see is that this transformation causes an exponential code size blowup in situations like the following:

while (condition0) { if (condition1) x = a->(x); if (condition2) x = a->(x); if (condition3) x = a->(x); if (condition4) x = a->(x); if (condition5) x = a->(x); if (condition6) x = a->(x); ... }

Waldemar
# Kris Zyp (15 years ago)

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

On 4/6/2010 3:13 PM, David Herman wrote:

We've given this quite a bit of time, and I don't know how far we're going to get in understanding all the details of your proposal. But I think I can address some of my disagreements.

  1. I'm skeptical whether the requirement you stated of future-proofing code for async implementations is likely to happen, and in fact, I think it would be harmful. Take your example: someone writes an Arrayish API, and maybe it's concurrent, maybe it's not, maybe it changes to become concurrent at some point. So a client writes:

... function push3() { arrayish.push->(3); }

Whoever uses push3 now has to be aware that it may or may not happen concurrently, so they have to be concurrency-safe too. Otherwise they might be tempted to do:

push3(); var x = arrayish.pop(); // this is gonna be 3, I'm sure of it!

and sadness would ensue. You're proposing making it easier to create mutable concurrent (or possibly-concurrent) data structures. Greasing the wheels of shared-state concurrency is dangerous and not a good idea for ES.

We definitely have not introduced shared-state concurrency, but if you think choosing to simplifying normalization of sync/async is potentially unhelpful, than certainly the alternate proposal based on "yield" would be better since it pushes the branching of logic on values to user land.

  1. I don't fully understand why you have so much machinery around chaining continuations. There are two ways in which chaining happens in existing code: nested flows through host-API callbacks (expressed in CPS), and explicit composition. With first-class continuations, the former is already alleviated for free-- there's no need for additional machinery to wire together pieces of the continuation. And if you represent captured continuations as functions, you still get composition on the cheap with good old function composition.

  2. I'm also unsure what you mean by "preserving causality" or "preserving stacks" -- but I thought you meant that you wanted debugging environments to be able to present natural stack traces in the presence of continuations. Again, this seems unproblematic to me with a traditional continuation-capture mechanism. Assuming a semantics where -> causes a continuation capture, if you do:

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. Does that makes sense?

  1. 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. ;)

  2. We should also aim for a design that tries to be compatible with existing API's, so that people don't have to write wrappers for all the standard libraries. As much as possible, anyway.

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 :/.

# Dave Herman (15 years ago)

Greasing the wheels of shared-state concurrency is dangerous and not a good idea for ES.

We definitely have not introduced shared-state concurrency

Introduced, no-- it's already there. IMO what this does is make it too easy to trip over. You're talking about a use case where clients can be oblivious to whether something is concurrent or not. I do not ever want to encourage web programmers to be oblivious to whether array mutations are synchronous.

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.

Whatever implementation tricks NarrativeJS had to go through were based on the fact that Neil didn't want to implement a JS engine, so he just did a CPS translation. That's not the case for us.

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. :)

One thing I'd like to do is write up a wiki page with a brief explanation of the design space. I can't afford to spend much time on it but we could churn forever stabbing at proposals if we aren't a little more systematic. But honestly, IMO, this isn't nearly as high a priority as some of the other features and proposals on the table. So I may need to put it on the back burner.

# Kris Zyp (15 years ago)

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

  1. 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.

  1. 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,

# David Herman (15 years ago)

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 afinally' 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' andthrow' 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').

  1. 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.

# Kris Zyp (15 years ago)

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

On 4/14/2010 11:30 AM, David Herman wrote:

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. Exactly, I'm glad we are on the same page about that, I was hoping there wasn't some crazy magic be suggested.

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."

My assertion is that with the proper API, libraries (that understands the call structures) can reconstruct a call stack (collectively using the individual continuations) to make it easy to debug. But due to the complexity and difficulty of demonstrating how this work, I am now convinced that this could and should be a separate API/function rather be integrated into the core semantics of the continuations. Obviously explaining the call stack API needs more effort. I still think it is valuable, but I am fine with it being separate no longer considered for the core semantics. It can be discussed sometime in the future as an extension.

[snip]

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

Oops, my apologies, I didn't realize you were referring to that email, yes that is clear.

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. Indeed, and with the shift in syntax (taking a single value), and API (generator style), I like this.

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 afinally' 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:

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

Don't you preserve this invariant by enforcing single-shot continuations? Not sure why the -> syntax gets in the way of that.

  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' andthrow' methods, a la generators.

Yes, that sounds great to me. And actually that makes easier to add a function in the future for call stack preservation.

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').

  1. 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.

Cool, then I think we are mostly in agreement on how -> could work.

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.

If that approach is still of interest, I'll throw out some ideas on the other thread.