Understanding and Implementing Algebraic Effects

Algebraic effects are kind of like exceptions that you can resume from. They can be used to express computational effects like non-determinism, generators, multi-threading, and of course, exceptions. They are a slightly less confusing alternative to using raw continuations via operators like call/cc and have other benefits like dynamic interpretation.

In this post, we will discover and implement algebraic effects using continuations in Racket. I will assume you are familiar with Racket and continuations. If you’re not, I have the perfect post for you!

Let’s start out with generators. In case you’re not familiar, here’s an example:

The function range creates a generator that yields integers between start and stop, excluding stop, like in-range.

The interesting thing about generators is that when we yield a value, the body of the generator actually stops running! If this was normal code, the moment we created the generator, we’d see "yielding!" printed 4 times. But as we can see from the order of events, it only resumed the body of the generator when we asked for the next element. The control flow exits the body every time we yield and it resumes when we fetch the next element. This is, of course, powered by continuations.

Essentially, we surround the generator body in a reset and shift when we yield, with some extra book-keeping and indirection to wire it all up the right way.

But instead of reset and shift, we will use % and fcontrol. Here is an example:

% and fcontrol are like reset and shift respectively. % establishes a handler procedure so that when fcontrol is called, it is handled by that handler procedure. With reset and shift, reset doesn’t really do much and shift is where the action happens. It’s the opposite with % and fcontrol. fcontrol doesn’t even get access to the continuation, it just bubbles some value up to the nearest % handler and that handler controls what happens next. This is very reminiscent of exception handling, except instead of just getting the exception, the handler also gets a continuation which it can use to resume from where the exception was thrown! This is the essence of algebraic effects.

Now let’s implement generators. Our generator is going to look slightly different. We’re going to build a lazy stream of values instead of a generator to make things simpler.

One strange thing is that in the handler, we must recursively call my-generator. This is because % establishes what is called a shallow hanndler. This means once an effect is performed and the body resumes from someone calling k, the handler is no longer active and needs to be re-established. So when we use k, we must recur to re-establish the handler.

Like raising an exception, the code that "performs" an effect like yielding doesn’t need to know how it is going to be handled. The handling can be dynamically configured:

By changing the handler, the behavior of the generator can be changed. Even though we’re using the exact same generator body with the same my-yield, the behavior is different because of the different handler. It’s a lot like how the same function can run under different exception handlers.

In fact, we could’ve put the generator body in a function:

yield-integers doesn’t care how its yields will be handled.

As another example, let’s implement non-determinism. Non-determinism allows us to "fork" the program to try different things without having to explicitly loop. It is useful for searches.

In the body of the nondet, we can call choose to make a non-deterministic choice between a list of items. This "forks" the search, running it against all choices. Even though the code will try all possible combinations, the code looks flat! We can terminate the current branch of the search by choosing between an empty list of choices. If the body reaches its end, that means we found what we were looking for, so we push it onto the results list. In the end, the entire nondet returns the list of all search matches.

The magic of the implementation is in the handler. k is a function that resumes the body, filling in the hole of the fcontrol with its argument. Since we want to try every possible choice, we loop through the choices and call k with each choice! The rest is just book-keeping to collect all the search matches and making sure the handler stays active.

You might be wondering why choosing between an empty list of choices terminates the search branch. What will happen in the handler? We’ll loop through an empty list of choices, so we’ll never call k. This means we’ll never resume in the body!

In our implementation of generators, to make sure we have deep effect handling (as opposed to the default shallow handling that % and fcontrol provides), we recurred in the handler. Our implementation of non-determinism doesn’t lend itself to that kind of recursion, so instead, we call % in the handler to re-establish only the effect handling, and not the book-keeping. There is still some recursion though, since the handler passes itself to %.

Alright, let’s make some abstractions!

perform is just fcontrol. with-effect-handler is like %, but has deep effect handling instead of shallow effect handling. The way we achieved deep effect handling is slightly different here than what we did for non-determinism. Instead of using % in the handler directly, we provide the handler with a wrapped continuation k^ which uses % when called. This has a few benefits: if the user-supplied handler performs an effect during handling, it won’t be handled by the handler that they’re writing, it’ll bubble out to whatever handler is outside of the whole with-effect-handler. Another benefit of this is that if the k^ ends up being used outside of the dynamic extent of the with-effect-handlers, it’ll re-establish effect handling as expected.

Let’s re-implement nondet using these abstractions just to get a feel for them:

We no longer have to worry about re-establishing the handler since with-effect-handler takes care of that for us.

Nice! But there is one big problem with this implementation: you can’t use two effects at the same time. If we want to use non-determinism inside of a generator, it won’t work because if we my-yield inside of a non-det, the effect will be handled like a choose effect, not a yield. How do we get around this?

One idea is to make structs for our effects and only handle effects that match a certain predicate, like what racket does for exceptions. This would work, but a much simpler way is to use continuation prompt tags. These essentially allow us to have independent delimited continuations that don’t interfere with each other in the ways we’re worried about. We’d just make a continuation prompt for generators and our generator handlers/operators would use that prompt tag, and the same story for other effects.

Now we can use effects together!

Before we go, I want to show you one more cool example of algebraic effects: A compiler!

Let’s say we’re writing a compiler targeting some assembly language. Our language is very simple, only containing addition, multiplication, numbers, variables, and let. Let’s say we’re trying to compile (+ (* 2 3) (* 4 5)). In assembly, we can’t perform deep calculations like this, all we can do is add the contents of two registers or multiply the contents of two registers. In other words, we can only perform operations on two immediately available numbers, no sub-computations, so we need to fully simplify the two arguments to + before we can add them. But those two arguments could be the results of big computations too! Ideally, our program would only ever add two immediately available values. An equivalent, easier-to-compile program would look like this:

In this program, the only arguments to + and * are numbers or variables (variables are ok, just not complex sub-computations). Fortunately, we don’t have to force the users of our language to write this way, we can just translate their program into an equivalent, nicer one like this. This is called A-normal form, or ANF for short. The idea is, if we are performing an operation and the argument is a complex expression, create a temporary variable to evaluate the argument first and replace the expression with that variable instead. And we do this recursively, so each addition and multiplication only ever has variables or constant arguments and variables are bound before use, of course. Let’s write a translator:

Our translator helpers return an expression and the bindings that are necessary for it. We build up our list of bindings, carefully maintaining its order such that variables are definitely bound before use and we maintain the desired order of evaluation. Every time we encounter a complex expression that needs simplification, we replace some of that expression with variables and bind those variables outside of the expression we’re building.

This is very awkward and doesn’t lend itself to nice structural recursion. We can’t recursively transform each sub-expression to ANF and then easily combine those two results since we need the bindings from both to combine, which involves putting part of one expression inside of another, but not the whole thing. Instead of trying to do that, we accumulate the list of bindings that will eventually surround the whole expression and at the very end, add all the lets around it.

Here’s another way to think about what’s going on here: We’re recursively diving into this expression to simplify it. The innermost parts of the expression will create the outermost bindings since the results of the inner expression are needed first. The innermost part of the input corresonds to the outermost part of the output, unlike typical structural recursion where the innermost part of the input corresponds to the innermost part of the output. Typical recursion doesn’t combine in the way that we want, so we have to make our own little system where we keep track of bindings throughout our computation. Haskellers among you might smell a monad in the air. This is a special type of computation, like non-determinism and generators, where we could benefit from an alternative control flow using continuations.

Here is the same translation implemented using algebraic effects:

We created a new effect, bind!, which binds an expression to a variable by wrapping the result of the rest of the computation in a let and returns the variable. If the expression is an immediate, it is returned as-is. Let’s think about why this works: The leftmost innermost expression is the one which should get evaluated, and thus bound, first, which means it should be bound in the outermost let. Since the structure of our recursion matches the desired order of evaluation, the first call to bind! will correspond to the expression that will be evaluated first. So we’ll wrap the whole rest of the computation in that first let. Remember, the "computation" here is the translation itself. The rest of the computation includes subsequent calls to bind!, which will create let bindings inside of this outer one, as they should. The result is a lot of nested lets with an ANF expression at the center for the final result of the supplied program.

We also have an effect lift! which is like bind!, but we supply the variable instead of generating a fresh one. This allows us to lift a user-specified let binding into the big nesting that we’re building.

This is confusing, but it allows our code to be so much more concise. We don’t have to track bindings and combine them everywhere. We don’t even have to worry about bindings at all except for calling bind! and lift!. The rest of the code can just be structurally recursive as if there was nothing weird going on.

This idea of the effects not "polluting" or "infecting" the code around it is very special. If you’ve used JavaScript’s promises or Haskell’s monads, you’ve felt the pain of what is sometimes called colored code. If you need to use the result of a promise, your whole function needs to be async, which means everything that uses that function needs to be async too, and so on. This "colors" your code. JavaScript code is either async or not, and async code infects non-async code. In Haskell, monads can be similarly infectious and color your code. There is some syntactic sugar, like JavaScript’s async and await and Haskell’s do notation, but your code is still colored. If some part of your computation deep down needs to be async, the whole thing needs to be async.

In an ideal world, when calling a function, you shouldn’t have to care if something async happens. Any effects in sub-computations should be abstracted away and not require code-changes in the caller. Algebraic effects allow us to do exactly this. They can model promises, monads, and more without coloring your code.

So should every language use algebraic effects? No, probably not. They are confusing, they make code reasoning non-local since you’re jumping all over the place, they are hard to statically type, and multi-shot continuations like with non-determinism are not performant. In order for a language to support algebraic effects, it pretty much has to transform to CPS, which isn’t right for every language. For now, it will be one of those cool features of niche languages like Racket.

Algebraic effects give us the power of continuations, wrapped up in an abstraction that lends itself to clearer code compared to raw use of call/cc, reset, shift, etc. Now you know what they are, how to use them, and how to implement them yourself.