revisiting "shift"

David Herman dherman at mozilla.com
Tue Apr 27 07:57:57 PDT 2010


One of the semantics I suggested and then dismissed for single-frame continuations was based directly on the operators "shift" and "reset" from the PL research literature.[1] To my eye, when we dressed them up to look like a function call (with "->"), they suggested that we were calling a function in the current exception handlers when they weren't.

But if we stop being creative with syntax and just use a more traditional prefix operator:

    UnaryExpression ::= ... | "shift" UnaryExpression

then let's revisit the semantics. Evaluating one of these expressions in the stack S(A) -- ie, a base stack S with current function activation A -- would do the following:

    1. Evaluate the argument expression to a value v.
    2. Suspend and capture A as a continuation value k.
    3. Remove A from the stack, leaving S as the stack.
    3. Call v with k as its single argument in the stack S.

We have the same representation choices for k; it could simply be a function, or it could be an object with a few methods, most likely "send", "throw", and "close". (I still think we couldn't accommodate anything more powerful than one-shot continuations, mostly because of "finally".) Re-entering the activation simply pushes it on top of the stack, including its suspended exception handlers (just the ones installed in the function body). It also closes over its scope chain, of course.

My original quibble with this semantics and the old notation had been that when you said:

    try { f->(x,y,z) } catch (e) { ... }

it looked like any exceptions thrown by f would be caught by the try-block, but that wouldn't be the case. But I think this was more a syntactic issue. Just like other powerful control operators like "fork" and "call/cc", a continuation operator overrides the ordinary flow of control. As long as the notation doesn't hide this fact, it's something programmers would have to be aware of-- just like they have to with "yield", "return", "break", and "continue".

Example:

    function f() {
        try {
            for (let i = 0; i < K; i++) {
                farble(i);
                // suspend and return the activation
                let received = shift (function(k) { return k });
                print(received); // this will be 42
            }
        }
        catch (e) { ... }
    }

    let k = f(); // starts running and return the suspended activation
    ...
    k.send(42); // resume suspended activation

It wouldn't be hard to show a proof-of-concept implementation of JS 1.7 generators with this construct, as well as a Lua-style coroutine API (one frame only, though, of course).

Notice that, unlike the CPS people normally have to write in, "shift" essentially flips around the control flow so that the callback is what's evaluated immediately, whereas the remainder of the function is delayed for later. Because shift expects a function argument, programmers/library writers could come up with conveniences for common idioms.

Also notice that, unlike JS 1.7 "yield", a function that uses "shift" is not special in that it doesn't immediately suspend its body when you first call it. But because it's a syntactic operator, it's more manageable for implementors of high-performance ES engines, since they can trivially detect whether a function may need to suspend its activation.

One last thought: a variation you sometimes see is something like:

    Expression ::= ... | "shift" "(" Identifier ")" Expression

(with the precedence worked out-- yadda yadda), which avoids the function indirection and simply binds the continuation to the identifier and evaluates the argument expression. This would be slightly more wonky in JS, because of the lack of "TCP" -- it's unclear what the "arguments" array should be bound to, and if we had something like let expressions with statement bodies, "return" would be weird.

It's also likely that retaining the function indirection makes it more convenient to use handlers, e.g.:

    function sleep(ms) {
        return function(k) {
            window.setTimeout(function() { k.send() }, ms)
        }
    }

    function iamtired() {
        ...
        shift sleep(100);
        ...
    }

Dave

[1] http://en.wikipedia.org/wiki/Delimited_continuation



More information about the es-discuss mailing list