Robert A. Uhl

GitHub’s Semantic team recently wrote:

An example of [dynamic control flow] is the concept of resumable exceptions. During Semantic’s interpretation passes, invalid code (unbound variables, type errors, infinite recursion) is recognized and handled based on the pass’s calling context. Because Semantic is, at its heart, an interpreter, this feature is essential for rapid development: we specify, when constructing interpretation and analysis passes, how GHC should handle errors while executing untrusted and possibly-invalid code, simply by specializing our call sites. Porting this to Java would require tremendous abuse of the try / catch / finally mechanism, as Java provides no way to separate control flow’s policy and mechanism. And given Go’s lack of exceptions, such a feature would be entirely impossible.

I agree with them that resumable exceptions are great — they’re one of the things I love about Common Lisp¹. But I don’t agree with them that such a feature would be ‘entirely impossible’ in Go.² As a counterproof, I’ll just note that one could, if one wished, implement a Haskell interpreter in Go … Turing-complete languages can calculate the same things.

One might think that’s cheating, though. Is it possible to implement resumable exceptions in Go, without resorting to interpreting some other language? It turns out that it is — although it’s a bit complex.

Resumable exceptions

What are resumable exceptions anyway? They are a neat technique in which low-level code can signal an exceptional condition, higher-level code can provide possible ways to resolve the exception, higher-level-still code can determine which way to proceed — and processing can resume execution where it left off. With Java exceptions the stack is unwound searching for an exception handler, and thus that handler can’t reach down into the stack, nor can it fix things and continue — but with resumable exceptions it can.

Signalling

A resumable exception is signalled by code; once it’s signalled, the exception-handling machinery examines the call stack and looks for all handlers capable of handling the exception, then runs them in order until one of them actually handles it.

Handling

Handling simply consists of transferring control to some other point in the call stack; declining to handle thus consists of returning.

Resumption

Resumption consists of catching a transfer of control and continuing from that point as normal.

What’s the point?

The point is that a high-level exception handler can choose to resume execution at a point lower in the call stack, which means that calculation can continue without losing state.

Prerequisites

So, what do you need in order to implement resumable exceptions?

Exceptions

You might think that you need exceptions in order to have resumable exceptions. After all, they’re right there in the name! Surprisingly, you actually don’t: the entire point of a traditional exception is to dynamically unwind the stack, while the entire point of a resumable exception is not to unwind the stack.

You do need some sort of data structure to represent the exception. In a nod towards Lisp, I’m going to call this a condition.

Control transfer

I kinda of lied in the previous section — while you don’t need traditional exceptions for the exception part of resumable exceptions, you do need them (or some other control-flow primitive) to handle them, so that handlers can transfer control and resumption can occur.

The Semantic team seem to think that Go doesn’t have exceptions — but it does! The only thing is that Go spells throw as panic and catch as defer + recover, and that there’s a culture on not exposing a library’s use of panic to client code.

We’ll wrap up our use of panic so that clients don’t have to know about it. I’m going to call these resumption points restarts, again in a nod to Common Lisp.

Dynamic context

If you’re going to be mucking about with stuff on the call stack, you need some form of dynamic context (or scope). What’s that? Well, it’s call-stack-scoped context, as opposed to the lexical (or block) scope that most of us are familiar with³. This is what the exception-handling machinery uses to search for handlers and restarts.

Go supports this as well, in the form of context.Context. We just need to stash information about restarts & handlers into the context, and find them later when needed.

Implementation notes

For full details, look at my code. Here are some brief notes.

Conditions

In Lisp conditions are types; I chose to go with an interface because it felt more idiomatic. Go already specifies that errors are just types which implement the error interface, which consists of a method Error which returns a string. It makes sense to me that a condition interface would be similar. Lisp’s conditions do something similar, writing a description to a stream rather than returning a string.

Handlers

I spent a bit of time thinking about what a handler might look like. It has to be called, so it should either be a function or an object implementing a method. I don’t know that it makes sense for client libraries to create their own handler objects, but it would be neat if a handler could choose to only handle certain types of condition. OTOH, this isn’t strictly necessary: a handler could just run for every condition it sees, and just not choose to handle conditions it doesn’t understand.

Since it’s simpler to implement, that’s exactly what we’ll do: a handler is just a function which takes a context and a condition. It can decline to handle the condition just by returning — if it never returns, the condition is thus handled.

This raises the question of which context the handler should receive: the context in which it was declared, or the context where the condition was signalled. We don’t want the handler to be active while it’s executing, but we do want intervening restarts to be visible.

Restarts

A restart is a function which can receive some arguments and perform any actions the client code desires. After the restart is executed, control is transferred to the point where the restart was established. We achieve this by panicking with a sentinel value, then catching all panics and resuming if we recognise the sentinel, otherwise repanicking. This is extraordinarily unidiomatic Go — but it works.

In Lisp, restarts are indicated with symbols; I chose to use strings instead.

Conclusion

Would I want to use this library in production? No, not really — it’s ungainly. But it does work, demonstrating that the Semantic team were entirely incorrect when they said that resumable exceptions are ‘entirely impossible’ in Go. All it required was tremendous abuse of panic / defer / recover!

As to why you’d want resumable exceptions it in the first place — that’s a topic for another blog entry. I’ve only shown that it’s possible, not that it’s desirable☺