Swanson: Branches in linear continuations

I’m going to follow the lead of several other folks I follow, and use this newsletter for rougher drafts of posts that will eventually end up on my Web and Gemini sites.

One of the defining features of Swanson, my programming language framework, is that it uses linear continuations for control flow.

The continuation part means that there’s no implicit control flow. For instance, when calling an operation, you have to pass in a “return” continuation which the operation will hand control back to when it’s done. There’s no implicit stack of control flow like you’d get from function calls in a typical language.

The linear part means that every continuation you create must be invoked exactly once. This gives us a language to describe things that must happen — memory that must be freed, files that must be closed, etc.

But, if all control flow is expressed via continuations, and all continuations must be invoked exactly once, how do you handle an if statement? Your typical if statement will need three continuations: one for the then branch, one for the else branch, and one for the join point that occurs after the statement. The whole point of an if statement is that either the true branch or the else branch is invoked, but not both. How do you do this if both continuations are linear?

In Swanson, the answer is that the then and else branches aren’t separate continuations at all — they’re separate branches of a single continuation. That is, a Swanson continuation does not consist of one single block of code — it consists of one or more named branches of code.

The continuation is still linear — you’re guaranteed that it will be invoked exactly once. But moreover, you’re guaranteed that only one of the branches will be invoked. For an if statement, this is exactly what we want! We don’t know which of the two branches will be invoked, since we presumably don’t know in advance the value of the statement’s conditional. But we do know that either the then branch or the else branch will be invoked, and not both!

All that’s left is to handle the join point. For that, we create a separate continuation, with a single branch. Importantly, we create it first, so that we can then close over it when creating the then/else continuation. The join point belongs to the continuation as a whole — to all of its branches — and to satisfy linearity, each branch is independently responsible for invoking the join point at some point. This gives us a static guarantee that, regardless of which branch is selected, control will eventually return back to the join point.

In S₁, it might look like this:

module test {
  entry:
  containing ()
  receiving (boolean_value, halt) {
    join = closure containing (halt) -> join;
    branches = closure containing (join) -> branches;
    boolean_value~>evaluate(branches);
  }

  branches:
  containing (join)
  ::true receiving () {
    # We can do different things in the two branches, but
    # both branch must eventually call join!
    join();
  }
  ::false receiving () {
    join();
  }

  join:
  containing (halt)
  receiving () {
    finish();
  }
}