Discuss
  • revisiting "shift"

revisiting "shift"

# David Herman (15 years ago)

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] en.wikipedia.org/wiki/Delimited_continuation

# David Herman (15 years ago)

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.

Quick clarification-- "more manageable" than if it were a library function instead of a syntax, not more manageable than "yield". (The "yield" form is also an operator, and is manageable for implementors for exactly the same reason.)

# Peter van der Zee (15 years ago)

On Tue, Apr 27, 2010 at 4:57 PM, David Herman <dherman at mozilla.com> wrote:

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 seems to me like the callback is unnecessary overhead. What happens if you don't supply a function but another type, or none? Would 42 still be "returned" by shift? Or is it actually the returned value in k, that gets a send method augmented to it? It'd be cleaner if it was just shift(), no argument, which returns a callback bound to the continuation which can simply be called without suffix: function x(){ let received = shift(); } var y = x(); y(42);

But maybe I'm knifing an entire API here I don't know about :) Otherwise the send method seems redundant.

# David Herman (15 years ago)

What happens if you don't supply a function but another type, or none?

The simplest thing is to specify it as a runtime error if the argument to shift is not callable. You're right that there's an overhead to constructing a new function. But it gives you flexibility that's otherwise a pain for the programmer. More below.

Would 42 still be "returned" by shift? Or is it actually the returned value in k, that gets a send method augmented to it?

I don't understand this question-- do you mean whatever value the handler function (in the example, function(k) { return k }) returns? Then no, there's no augmentation or mutation here. The continuation is represented as an object with three methods:

  • send(v): pushes the suspended activation back onto the stack and uses v as the result of the shift expression

  • throw(v): pushes the suspended activation and throws v from the shift expression

  • close(): pushes the suspended activation and performs a return (running any relevant finally blocks first)

(This is all just what JS 1.7 generators do.)

A simpler representation for captured continuations is just a function. But as Kris pointed out in an earlier thread, this is inconvenient for the "throw" and "close" cases.

It'd be cleaner if it was just shift()

You might think so, since the semantics seems simpler-- but it would lead to uglier programs. You're not affording the writer of the function doing the shift any ability to specify what to do after the shift, and you're not giving them the ability to communicate any data to the caller. This requires them to coordinate with clients to save any additional action in some side-channel, e.g.:

// library
function gen(thenWhat) {
    ...
    thenWhat.action = function() { ... /* do more stuff */ ... };
    let received = shift();
    ...
}

// client
var k = gen({ action: function() { } });

But maybe I'm knifing an entire API here I don't know about :) Otherwise the send method seems redundant.

I'm not sure what the send method has to do with it-- it sounds like I may not have explained clearly enough. The semantics of shift is to capture and pop the current activation, reify it as an object with the three methods I describe above (send, throw, close) and call the handler function with this reified activation object as its argument. It's then up to the program to decide when/whether to continue the captured function by calling its methods.

Note that this means that when you use the shift operator, the handler function is executed immediately, whereas the rest of the captured function is suspended and not continued until some later time. This is the opposite of patterns like event callbacks and CPS, where the code in the callback is called at some later time, but the rest of the current function is continued immediately.

# Peter van der Zee (15 years ago)

I don't understand this question-- do you mean whatever value the handler function (in the example, function(k) { return k }) returns? Then no, there's no augmentation or mutation here. The continuation is represented as an object with three methods:

Ah, I didn't know that.

It'd be cleaner if it was just shift()

You might think so, since the semantics seems simpler-- but it would lead to uglier programs. You're not affording the writer of the function doing the shift any ability to specify what to do after the shift, and you're not giving them the ability to communicate any data to the caller. This requires them to coordinate with clients to save any additional action in some side- channel, e.g.:

// library function gen(thenWhat) { ... thenWhat.action = function() { ... /* do more stuff */ ... }; let received = shift(); ... }

// client var k = gen({ action: function() { } });

Hm. Maybe you meant to return the function to allow access to the local variable k through a closure? And not a fingerprint mixed shift(function) as I read it at first? In that case sure, fine :)

The shift could also expose the iterated value in the continuation object as a read-only property (or getter). The shift itself would return whatever you give .send as parameters. But maybe this was what you meant in the first place..

Whatever needs to be done before or after the shift should obviously be done from within the loop. I see no problems with that myself, but maybe I'm missing something?

But maybe I'm knifing an entire API here I don't know about :) Otherwise the send method seems redundant.

I'm not sure what the send method has to do with it-- it sounds

That would be the API I didn't know about ;)

On a sidenote; continuations could be implemented much like timers are now. I mean, for timers to work, you would already have to have a way to preserve state and stack because you have to access it when the timer fires. This proposal could just extend the API using the same mechanics as the timers (I read something about this proposal being a possible problem for vendors). But rather than being executed when some time has elapsed, the callback would be fired on demand. After implementing setTimeout and setInterval, this should be quite easy...

I also read syntax using try{}catch(){} as some kind of "continue" mechanism and just wanted to say I find it really ugly and hackish. I've not seen any arguments that justify introducing such a mechanism (but it might not be part of this proposal, I'm sorry and happy if it wasn't :)).

# David Herman (15 years ago)

Hm. Maybe you meant to return the function to allow access to the local variable k through a closure? And not a fingerprint mixed shift(function) as I read it at first?

I don't know what you're saying, but I have already posted the semantics in this thread. I think it should be pretty clear. (If others are confused about it, please do weigh in.)

The shift could also expose the iterated value in the continuation object as a read-only property (or getter). The shift itself would return whatever you give .send as parameters. But maybe this was what you meant in the first place..

If I understand this, it still doesn't give the function that does the shift very much room to do anything interesting after it pops the function activation.

Whatever needs to be done before or after the shift should obviously be done from within the loop. I see no problems with that myself, but maybe I'm missing something?

I think you are. When the shift happens, it pops the activation frame, which means that the rest of the function after the shift stops running. This is what a continuation operator is all about-- suspending control and saving it in a value that can be called later. The purpose of calling the handler function is to do something immediately after popping the activation frame, not later when the activation is resumed.

On a sidenote; continuations could be implemented much like timers are now. I mean, for timers to work, you would already have to have a way to preserve state and stack because you have to access it when the timer fires. This proposal could just extend the API using the same mechanics as the timers (I read something about this proposal being a possible problem for vendors). But rather than being executed when some time has elapsed, the callback would be fired on demand. After implementing setTimeout and setInterval, this should be quite easy...

None of this is true. Closures are not the same thing as continuations.

That said, if this is a hardship for implementers, I'd be interested in having them weigh in.

I also read syntax using try{}catch(){} as some kind of "continue" mechanism and just wanted to say I find it really ugly and hackish.

I'm genuinely baffled by this comment.

# Peter van der Zee (15 years ago)

On Thu, Apr 29, 2010 at 2:21 AM, David Herman <dherman at mozilla.com> wrote:

Hm. Maybe you meant to return the function to allow access to the local variable k through a closure? And not a fingerprint mixed shift(function) as I read it at first?

I don't know what you're saying, but I have already posted the semantics in this thread. I think it should be pretty clear. (If others are confused about it, please do weigh in.)

The shift could also expose the iterated value in the continuation object as a read-only property (or getter). The shift itself would return whatever you give .send as parameters. But maybe this was what you meant in the first place..

If I understand this, it still doesn't give the function that does the shift very much room to do anything interesting after it pops the function activation.

Whatever needs to be done before or after the shift should obviously be done from within the loop. I see no problems with that myself, but maybe I'm missing something?

I think you are. When the shift happens, it pops the activation frame, which means that the rest of the function after the shift stops running. This is what a continuation operator is all about-- suspending control and saving it in a value that can be called later. The purpose of calling the handler function is to do something immediately after popping the activation frame, not later when the activation is resumed.

On a sidenote; continuations could be implemented much like timers are now. I mean, for timers to work, you would already have to have a way to preserve state and stack because you have to access it when the timer fires. This proposal could just extend the API using the same mechanics as the timers (I read something about this proposal being a possible problem for vendors). But rather than being executed when some time has elapsed, the callback would be fired on demand. After implementing setTimeout and setInterval, this should be quite easy...

None of this is true. Closures are not the same thing as continuations.

That said, if this is a hardship for implementers, I'd be interested in having them weigh in.

I also read syntax using try{}catch(){} as some kind of "continue" mechanism and just wanted to say I find it really ugly and hackish.

I'm genuinely baffled by this comment.

Dave

Reading your original post again, more thoroughly this time, it becomes clear to me that I've misinterpreted it. And you indeed stated the send, throw, close "api" there.

I still believe that the callback is redundant, but for now I'll just shut up.

As for the try/catch statement, I was confused with the Iterators and the way they were implemented in JS 1.7. You used try/catch in one example and that's how I got confused.