One-shot continuations

Neutrino has two basic control structures: method calls and one-shot continuations. In my last blog post I outlined how method calls work. In this one I’ll outline one-shot continuations.

You may already be thinking: continuations? Seriously? But it’s not as hairy as it sounds. First of all, these are one-shot, not fully general call/cc. It’s really just a convenient way to define all the usual control structures, including break, continue, and local and non-local return, in terms of one fundamental construct. In particular, one-shot continuations are, even in the most general case, no more expensive in terms of implementation complexity than non-local returns.

In the current syntax (I’ll get back to the topic of syntax and why you shouldn’t focus too much on that later) a one-shot continuation use looks something like this:

with_1cc (return) {
for (i : 0 .. 10) {
if found_it(i)
then return(i)
}
-1;
}

What’s happening here is: at the beginning of the with_1cc statement we capture the current continuation and store it in a variable called return. We then loop from 0 to 9 and, if a condition holds, invoke the continuation and immediately yield the specified value as the result of the with_1cc expression without executing any more of the body. If the condition doesn’t hold then the continuation is implicitly invoked with the result of the body which is -1. Invoking a one-shot continuation more than once is an error and the final implicit call ensures that you’ll get an error if you try to invoke the continuation after the with_1cc expression has completed.

That’s all there is to with_1cc: it gives you a function that you can call — once — to bail out of an arbitrarily nested computation and yield a value to the whole expression. Cases like above where the capture and use of the continuation occur together in a single function are easy for the compiler to recognize and for those it can generate code that doesn’t actually materialize the continuation but simply uses a jump to leave the expression. This will work in any situation where you could use break, continue or local return in a standard C-family language:

def my_function() {
with_1cc (return) {
// ... prepare loop ...
with_1cc (break) {
for (i : 0 .. n) {
with_1cc (continue) {
// ... loop body ...
}
}
}
// ... finish ...
}
}

The above code is obviously very verbose and luckily you wouldn’t have to actually write that in neutrino — the syntax is flexible and the compiler is free to automatically introduce with_1ccs when required. The point is that this can be used to implement any of the basic local jumps from the C-like languages, except for goto, and generate as efficient code for each of them as in languages where they’re built-in. In addition to mimicking other control structures it also allows patterns that are not possible on C-like languages, like expression-local returns:

def matching_entry := with_1cc (leave) {
for (entry : this.entries) {
if entry.name = name
then leave(entry);
}
}
print("Found entry: ${matching_entry}");

This code loops over a list of entries and leaves the loop, but not the whole function, immediately when the appropriate one has been found. This can be simulated in various ways: creating a utility method that uses normal return, assigning to matching_entry and breaking out of the loop, or inlining the action to be performed with the result at the place where the result is identified. Using with_1cc you can express the behavior directly without the need for workarounds. And, again, this comes without any performance penalty since the control flow can be resolved statically and the continuation doesn’t have to be materialized.

In the case where the continuation is not used locally it behaves similarly to non-local returns in language that support that, like Smalltalk. The difference is that where non-local return ties the return to a method call, with_1cc lets you return to an arbitrary expression. Other than that they are completely equivalent.

As mentioned, the syntax of neutrino is flexible and there’s every reason for libraries to introduce shorthands based on this construct that allows it to be used without the full syntactic complexity. This is a basic building block that the base language supports, not something you’re likely to see that often in its naked form.

Update: Kevin Millikin points out that just calling the continuation on exit isn’t enough to ensure that it won’t get called more than once. Kevin’s counterexample is

def get_me_back_in := with_1cc (get_me_out) {
with_1cc (invoke_me_later) {
get_me_out(invoke_me_later);
}
}
print("hest");
get_me_back_in(...);

Here we escape the implicit invocation of invoke_me_later by leaving via a surrounding continuation. Bummer. This issue is present in any language with non-local return that can be captured, for instance SmallTalk:

outer
| innerReturn |
innerReturn := self inner.
^ innerReturn value: 5.

inner
^ [ :v | ^ v ]

(I just tried this in Squeak; you get a BlockCannotReturn exception.)

The solution is to enclose the body of the with_1cc in an unwind-protect that ensure that no matter how we leave the with_1cc, the corresponding continuation will be disabled. Divorcing calling a continuation from disabling it does mean that the name “one-shot continuation” stops being accurate so I’ll probably have to come up with a more fitting name.

One thing I haven’t written about yet are coroutines, which neutrino also supports. Mixing not-really-one-shot-continuations-anymore with those is also interesting but that is a future blogpost.

Leave a Reply

Your email address will not be published.


*