Implementing continuations in JavaScript

In computer science and computer programming, a continuation is an abstract representation of the control state of a computer program. A continuation reifies the program control state, i.e. the continuation is a data structure that represents the computational process at a given point in the process’ execution; the created data structure can be accessed by the programming language, instead of being hidden in the runtime environment. Continuations are useful for encoding other control mechanisms in programming languages such as exceptions, generators, coroutines, and so on.

- Wikipedia

Continuations is a fairly complex construct used in some programming-languages to change the flow of the program. For instance, imagine the following program:

function getA() {
    return 5;
}

function getB() {
    return 10;
}

var a = getA();
var b = getB();
var c = a + b;
alert(c);

If this was run on a regular JavaScript runtime, it’s fairly easy to imagine how the code would execute, but just to make sure let’s walk the execution step by step (ignoring method-detection/registering).

1. Execute getA();
2. assign 5 to return-field.
3. assign return-field to a.
4. Execute getB();
5. assign 10 to return-field.
6. assign return-field to b.
7. calculate a + b and assign to return-field.
8. assign return-field to c.
9. alert c.

Now, this explanation is dumbed down and in some cases do not explain well how some things are done. For instance, the “return-field” is normally only the top of some stack, and there’s all sort of framing and other stuff going on with regards to the function-calls, but this is enough to illustrate my point. And the point is that the code basically executes like this:

1. Run getA();
2. Run getB();
3. Addition
4. Alert

However, in other languages, this might not hold true. In some languages, things are (explicitly or implicitly) not computed until they are needed. In such cases, the execution might look like this:

1. Set a to a lazy computed getA result.
2. Set b to a lazy computed getB result.
3. Request a (at this point, the value of a get's computed and set to 5).
4. Request b (at this point, the value of b get's computed and set to 10).
5. Addition
6. Alert

Now, if we run this on a system using a simple construct like Lazy with polling, this example holds little value, however, if you run this on a system using scheduling (and lazy is implemented using said scheduling), things become a lot more interesting. These values (a and b) might for instance be computed on a completely different thread altogether. To illustrate how this might be executed I’ll show a javascript-example that does roughly the same (as how this might have been implemented on some systems).

var a = function() {
    a = 10;
};
var b = function() {
    b = 5;
};
var rest = function() {
    var c = a + b;
    alert(c);
};
setTimeout(a, 0);
setTimeout(b, 0);
setTimeout(rest, 0);

As you can probably see, the execution of the script is quite different. But the point is that in the original code, when you get to the point where you actually need “a”, you say to the system: ok, go ahead and compute “a”, and run the rest of this method when you are finished with that. You can extend this even further. For instance, the system might simply assign the “computation of a + b” to c, and neither a, b, nor c would get computed until you called alert. And the cool part is that if you didn’t call alert, it wouldn’t even get computed at all! That’s one of the ways continuations might work. And as you can see, rewriting regular code to work like continuations requires quite a bit of change to the code. There is also a loss in code-readability and performance.

Another, more used form of continuations is the yield, or generators in general. Take for instance this code (written in Augmented JavaScript):

function test() {
    yield 0;
    alert(10);
    yield 1;
}

var gen = test();
alert(gen.next());
alert(gen.next());

The code above alert first 0 then 10 and lastly 1. If I remove the second call to “gen.next”, only 0 is alerted. As you can see, the test-method is “suspended” in the middle of the method, and is “continued” at the exact point where it left, variables and state being retained.

Turning yield into goto

I’ve already written a post on generating generators, so I’m not going to get too much into that. The post is about generating yield-like behavior in C# (which already supports yield natively), but the steps taken are mostly the same in Augmented JavaScript. The main difference is that javascript has functions instead of classes, so instead of creating a class with class-members for the method-variables, you simply create an enclosing function and hoist the variables into that function instead. Thus state can be retained in a fairly simple manner.

There is however one small problem with the solution presented as to how to make generators in C#. JavaScript do not support goto-statements. The solution provided is fairly dependent upon gotos. They are what enables the method to continue execution where it left off, without having to start at the beginning each and every time, thus a solution cannot be implemented without the use of goto. At least not using the algorithm described. Now, I’ve been told there are other, more elegant solutions to solving this problem in JavaScript that splits the function-body into multiple functions, but I’m unable to mentally picture how such an algorithm would deal with if’s and loops, etc., and as such I have not used it. Instead, I used the same algorithm provided in the C# example, and came up with an algorithm on how to implement goto in JavaScript.

Now, before people start screaming about how evil goto is, let me state a few things. The algorithm I use is not a generic goto-resolver. It can not deal with any and all gotos, only those that follow a few rules. For instance, all jumps must be made forward. Also, Augmented JavaScript does not, in and of itself, support goto. You cannot write goto in your code and expect it to process it. The gotos are only used at an intermediate stage when rewriting a function into a generator, and is subject to the fact that since we generate them, we know how which formats they appear in. And it’s in all actuality only a single type of gotos that are used, it’s a forward-jumping goto placed in a switch-statement at the top of a function. A prime example of this displayed below.

// Augmented JavaScript
function myGenerator() {
    yield 0;
    yield 1;
}

// Rewritten using goto
function myGenerator() {
    var state;
    function moveNext() {
        switch(state) {
            case 1: goto state1;
            case 2: goto state2;
        }

        state = 1;
        return [false, 0];

        state1:;
        state = 2;
        return [false, 1];

        state2:;
        state = -1;
        return[true];
    }
    return new Generator(moveNext);
}

Just to be clear, the steps taken to rewrite a yield-function into a generator-function using goto has been simplified here. In reality, there’s a bunch of exception-handling and making sure the state is ok, but this still shows the general algorithm used.

Resolving the gotos

To solve a simple goto-function like this is rather easy. You simply turn the code into a switch-statement with fallthrough, and you get something like this (enclosing function omitted):

function moveNext() {
    var _goto = false;
    switch(state) {
        case 1: _goto = "state1";
        case 2: _goto = "state2";
    }

    switch(_goto) {
        case "state1":
            state = 2;
            return [false, 1];

        case "state2":
            state = -1;
            return [true];

        default:
            state = 1;
            return [false, 0];
    }
}

Notice however, that the first case from the previous sample (yield 0) got thrown at the bottom. This is because we have fallthrough on the switch-statement (notice the distinct lack of break-statements). Now, you might argue that because all the cases ends in a return-statement, this doesn’t matter (and you would be right), but there are cases where it does matter. I’ve found 2 ways to resolve this issue. One is to set _goto to something like “state0″ on default (in the switch on state), and the other is to put the switch in a loop. While the first one might be easier to read, the second one seems to me to handle nesting of scopes (I’ll get back to that in a bit) a lot better. But, since we’re inside a switch, we can’t simply exit the loop by breaking, so we need to put a label on the loop to handle this. Also, after the default case is done, what we want to happen is the “state1″ case (because, that’s the normal execution-flow if you look on the original code), and the way to make this happen is to introduce a new “special” _goto-state that will always enter the first switch-statement (as having been flowed into from the last one).

The resulting code after taking the actions described above looks like this:

function moveNext() {
    var _goto = false;
    switch(state) {
        case 1: _goto = "state1";
        case 2: _goto = "state2";
    }

    scope0: while(true) {
        switch(_goto) {
            case "enter":
            case "state1":
                _goto = false;
                state = 2;
                return [false, 1];

            case "state2":
                _goto = false;
                state = -1;
                return [true];
                break scope0;

            default:
                state = 1;
                return [false, 0];
                _goto = "enter";
        }
    }
}

There are a few things to notice here. First of all, there is unreachable code at several locations. For instance, in this example, _goto will never be set to “enter”, simply because default has a return-statement. The “break scope0;” will also never be reached, as it is also after a return-statement. However, there are cases where this is not true, and as I’m not that good at three-traversal to figure out what is definitely dead code, I’m adding them allways, just to make sure. Also, the JavaScript-compiler/interpreter in your browser/environment should hopefully optimize the dead code away.

The algorithm thus far is more robust than before, but there are still things it cannot handle well. Let’s take a look at another example, shall we?

'
// Augmented JavaScript
function test() {
    var testVar = true;
    if(testVar) {
        testVar = false;
        yield 0;
        yield 1;
    }
}

// Rewritten - testVar exists outside the scope of moveNext
function moveNext()
{
    var _goto = false;
    switch(state) {
        case 1: _goto = "state1";
        case 2: _goto = "state2";
    }

    // What to do here?
}

This example is mostly the same as the previous one, however there is one big difference, everything that happens happens inside an if-statement. The way to resolve this is first by looping through all scopes (starting by the innermost ones), and check if they contain any jump-labels (like “state1:;”), and if they do, run gotorewriting inside that scope. So, let’s do that one step at a time, starting with rewriting the inner if-scope.

function moveNext()
{
    var _goto = false;
    switch(state) {
        case 1: _goto = "state1";
        case 2: _goto = "state2";
    }

    if(testVar) {
        scope0: while(true) {
            switch(_goto) {
                case "enter":
                case "state1":
                    _goto = false;
                    state = 2;
                    return [false, 1];

                case "state2":
                    _goto = false;
                    state = -1;
                    return [true];
                    break scope0;

                default:
                    testVar = false;
                    state = 1;
                    return [false, 0];
                    _goto = "enter";
            }
        }
    }
}

The algorithm is the same as last time, only we run it inside the inner scope this time, and left the if-test as-is. One of the problems you might notice is that after we enter the if-test for the first time, there is no simple way to reenter it. To solve this, all tests have to be rewritten to allow through in states where they should begin in the middle of a guarded block (like an if, if-else, while, for, etc). The rewriting-rules for the test is simple. Simply find all states that are inside, and allow those to get through (without actually running the original test, as this might have side-effects). So instead of “if(testVar)” we get “if((_goto == ‘state1′ || _goto == ‘state2′) || testVar)”.

The current code is almost done. All we have to do is rerun the same algorithm on the outer scope, although we need to pretend that all the state-labels inside the if lies just ahead of it.

The resulting code looks like this:

function moveNext()
{
    var _goto = false;
    switch(state) {
        case 1: _goto = "state1";
        case 2: _goto = "state2";
    }


    scope1: while(true) {
        switch(_goto) {
            case "enter":
            case "state1":
            case "state2":
                if((_goto == "state1" || _goto == "state2") || testVar) {
                    scope0: while(true) {
                        switch(_goto) {
                            case "enter":
                            case "state1":
                                _goto = false;
                                state = 2;
                                return [false, 1];

                            case "state2":
                                _goto = false;
                                state = -1;
                                return [true];
                                break scope0;

                            default:
                                testVar = false;
                                state = 1;
                                return [false, 0];
                                _goto = "enter";
                        }
                    } // end scope 0
                }
                break scope1;

            default:
                // nothing here. The if was the first-statement.
                _goto = "enter";
        }
    } // end scope 1
}

And there we have it. Continuation in plain old JavaScript. If I haven’t overlooked anything this should be equal in functionality to the original snippet. There are some cases I haven’t covered though, like loops, but they are mostly the same. Another thing I omitted to (try to) keep things short, is the fact that you have to make sure that _goto = “enter” don’t “leak” into inner scopes. As you can see, the end-result isn’t pretty, and this isn’t even that complex an example, so the sourcecode generated from Augmented JavaScript isn’t supposed to be read too intently (unless you are searching for bugs in the preprocessor itself).

I hope this has been educating, or that at least a few people might have gotten a thing or two from this ^^.

Until next time.

2 thoughts on “Implementing continuations in JavaScript

  1. Hmm it seems like your website ate my first comment (it was extremely long) so I
    guess I’ll just sum it up what I had written and say, I’m thoroughly enjoying your blog.
    I too am an aspiring blog blogger but I’m still new to the whole thing. Do you have any tips and hints for beginner blog writers? I’d really appreciate it.

    • Sorry, but I’ve been busy at work lately, so I haven’t been able to check my blog-comments (and thus approve of your comment, which was pending approval). I was unable to find your previous comment in both pending/approved and spam, so I don’t know what happened to it. Maybe WordPress screwed up? Anyways, I don’t have many tips or hints as to blogging. This blog has been “active” for about 7 years (I think), and I’ve still only posted about 30-50 or so posts (and some of them are shorter than your average SMS). I just find content I think the world should know, and I force myself to write it. Sometimes it’s great fun, other times it’s a big hassle, but the fact that people like you come and comment on the content and say you like it makes it all worth it.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s