Single frame continuations proposal

Kris Zyp kris at sitepen.com
Tue Mar 30 13:30:04 PDT 2010


-----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:
https://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 = {};
    }
})();

- -- 
Thanks,
Kris


- -- 
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/
 
iEYEARECAAYFAkuyX0wACgkQ9VpNnHc4zAz0YwCgihc5Ui7YxvTPp70YnHyls2jc
s+sAoKP6BMGnoyTh5S04hIwgAMcytEeh
=ekM1
-----END PGP SIGNATURE-----

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20100330/23d5c7cc/attachment-0001.html>


More information about the es-discuss mailing list