Thinking about continuations

Following up on my previous posts about continuations and Harmony, I want to show how I use the modeling tools of evaluation contexts and operational semantics to sketch out informal designs. I'll use a plausible syntax for a new Harmony operator (based on Neil Mix's NarrativeJS) and start with a reasonably simple semantics based on the well-known shift/reset operators, and sort of work out from there.

I'll keep this as light and informal as possible. To stay on point, I'll ignore most of the ES features-- no mutation (so we don't have to model the heap / object graph), and not even scope chains. For a faithful and precise model, we'd need all of these things. But for design sketches, I can afford to be sloppier.

Stacks and activations

I'll model the stack as a non-empty sequence of function activations:

S ::= A | S(A)

An activation is a function body, but we want to highlight the current statement being executed or expression being evaluated (aka the code pointer). So I'll model the activation as two things: the next bit of code to execute (a statement or expression), and the function body without that bit of code. If the code pointer is at an expression, the activation is a function body with a placeholder that I'll spell () (an "expression hole"); if it's a statement, the activation is a function body with {()} (a "statement hole") in place of the current statement.

For the curious, what I just did was -- informally -- define evaluation contexts for ES.

If that was a little too opaque, here's an example. Let's say we have a function

function foo(x) { f(x); g(x, 2 * x, null); return x + 4; }

If we call foo(42), then at first, our current code is f(42); and our activation is

{ {()} g(42, 2 * 42, null); return 42 + 4; }

When we're about to evaluate the second argument to g, then the current code is 2 * 42 and the current activation is

{ g(42, (), null); return 42 + 4; }

When we get to the return statement, current code is return 42 + 4; and the current activation is

{ {()} }

Notice how after we execute some code, it's gone from the activation; the activation just needs to keep track of the code we have left to run.

For talking about the activation and the current code together, I'll write A(expr) or A{stmt}. This is what people call "plugging" code into the hole of a context. Essentially, it's just a modeling trick that makes it convenient to call out where the current code pointer is, but it also turns out to be really natural for talking about first-class control operators-- because it explicitly models the very things we want to manipulate.

Operational semantics

The above is more or less enough to start writing simple transition rules that describe how programs run, e.g.:

S(A{return val;}) → S(val)

In English, this rule says: "in a stack starting with S and with activation A on top, when the next code to execute is the statement return val; (for some value val), then remove the current activation and place val in the expression hole of the stack."

One thing to make clear: this transition arrow describes a runtime state transition of the program, not a compile-time transformation.

Starting with shift and reset

Here's how a design based on shift and reset might work, specified in one line:

S(A(val->(val1, ..., valn))) → S(val(val1, ..., valn, function(x) A(x)))

The special syntax of a capturing function call comes is from NarrativeJS. The transition rule describes several things:

1. After evaluating the callee and its arguments, the operator immediately aborts the current activation and saves it in a function.
2. Next, it calls the callee with its arguments along with the captured continuation value as an additional argument.
3. If the captured continuation is called, it executes the captured function activation, with its new argument plugged into the hole of that activation.

There's a serious problem with this semantics for ECMAScript: exception handlers. Aborting A will discard any try or finally blocks in A before we call the function. So you'd get surprising behavior like:

function mightFail(k) {
  // ...
  throw "boo!";
}
function main() {
  try {
      mightFail->()
  }
  catch (x) {
      return 42
  }
}
main() // uncaught exception: "boo!"

A pretty clear violation of principle of least astonishment.

When to abort

Having the semantics in such a concise format makes it easy to tweak and experiment with. Let me modify the above semantics in the following way: instead of aborting before we call the callee, let's abort the activation after we return from the call. That way, if it throws exceptions, they'll be caught by any handlers in A.

We'll have to invent an expression form that aborts the current function activation after evaluating an expression. This is pretty much just like return, exception it's an expression form.

S(A(val->(val1, ..., valn)))
→ S(A(RETURN val(val1, ..., valn, function(x) A(x))))

Actually, we could do this without positing a magic RETURN operator if we have something like the newly-proposed let expressions, which allow you to execute statements inside an expression. Then we'd have:

S(A(val->(val1, ..., valn)))
→ S(A(let (x = val(val1,..., valn, function(x) A(x))) {return x;}))

So that's a brief demo of using evaluation contexts and operational transition rules to sketch the semantics of continuation operators.

Edit: I forgot to mention, it's easy enough to specify the behavior of RETURN:

S(A(RETURN val)) → S(val)

As I say, just like return statements, but as an expression form. To be clear, this is just a specification mechanism, not something I'd suggest as a language feature.