Why Algebraic Effects?

Algebraic effects¹ (a.k.a. effect handlers) are a very useful up-and-coming feature that I personally think will see a huge surge in popularity in the programming languages of tomorrow. They’re one of the core features of Ante, as well as being the focus of many research languages including Koka, Effekt, Eff, and Flix. However, while many articles or documentation snippets try to explain what effect handlers are (including Ante’s own documentation), few really go in-depth on why you would want to use them. In this post I’ll explain exactly that and will include as complete a list as possible on all the use-cases of algebraic effects.

A Note on Syntax and Semantics

I’ll be using Ante pseudocode for much of this article. If you’re not familiar with effect handlers or Ante I encourage you to read the documentation link above or read from any of the other effectful languages for a good head start! But I recognize it’s hard to get buy-in to learn something before showing why it is useful first (hence this blog post!). So I’ll give a quick elevator pitch on a good mental model to think about effects.

You can think of algebraic effects essentially as exceptions that you can resume. You can declare an effect function:

You can “throw” an effect by calling the function, and the function you’re in must declare it can use that effect similar to checked exceptions:

And you can “catch” effects with a handle expression (think of these as try/catch expressions):

If you have further questions I again encourage you to read some documentation on effects, but now that we can recognize effects when they’re used I’ll get into why exactly the idea of exceptions-you-can-resume are so useful!

User-defineable control-flow

The most common reason you’ll hear for why to have effect handlers is that they are a single language feature which allow for implementing what would normally be multiple separate language features (generators, exceptions, async, coroutines, etc) as libraries. Moreover, they solve the what color is your function problem by making functions polymorphic over effects. For example, a map function for vectors (growable arrays) can be written once:

This function’s signature says that the input function f can perform any effect(s) e, and that map will perform those same effects e. So we can instantiate this with an f that prints to stdout, an f that calls asynchronous functions, an f that yields elements into a stream, etc. Most languages with effect handlers will let you omit the polymorphic effect variable e as well, giving us the old, familiar signature for map:

Ok, back to the topic though. Effect handlers are cool because we can implement generators, exceptions, coroutines, automatic differentiation, and much more with them. Surely such constructs are difficult to implement, requiring low-level knowledge though, right? Nope. Most of these are pretty straightforward actually.

Let’s consider exceptions. Remember when I described algebraic effects as resumeable exceptions? This actually works pretty well as a hint on how to implement exceptions via effects. How do we do it? Just don’t resume the effect when it is thrown:

How about something more advanced? Surely generators must be more difficult? Well, a little but the code still fits onto a sticky note:

You can similarly implement a cooperative scheduler with a yield: Unit -> Unit effect which yields control back to a handler which switches execution to another function. Here’s an example of that in Effekt.

Basically, algebraic effects get you a lot of expressivity in your language, and as a bonus these different effects compose well with each other. We’ll get into this more later but algebraic effects composing well is a huge usability win over other effect abstractions.

As an Abstraction

Okay, now that the really flashy stuff is out of the way I want to go over some less obvious benefits of algebraic effects. Since discussion on effects can often seem like they’re only for implementing generators, exceptions, async, etc., I want to highlight that even if you don’t personally care for these features, there are still good reasons to use algebraic effects in your run of the mill business application.

One reason to use them in such an application is that effects can be used for dependency injection. Let’s assume we have code that touches a database:

This is all well and fine until we want to use a different database, restrict access to this database, or you know, actually test these functions. What we can do is move the database to an effect:

Now we can swap out the specific database used further up the call stack (let’s say in main) with a different database, or even with a mock database for testing:

We can even redirect print outs into a string:

Or conditionally disable logging output:

Cleaner APIs

Algebraic effects can also make designing cleaner APIs easier. A common pattern in just about any programming language is the use of a Context object which often needs to be passed to most functions in the program or library. We can encode this pattern as an effect. All we need are functions to get the context and to set it:

Most languages call this a state effect and it is generic over the type of state to use.

We can define a handler to provide the initial state value like so²:

And we can use this to help clean up code that uses one or more context objects. Let’s imagine we have code which uses a vector internally and hands out references to elements as indices into this vector. This would normally require passing around the vector everywhere:

Using a state effect essentially threads through the context automatically:

From the above we can see we now have to call get or set to access strings in the primitive operations push_string and get_string, but we no longer have to explicitly pass around strings in code that just uses these primitive operations. Generally speaking, this trade-off works well for libraries and abstractions which will usually completely wrap these operations, eliminating the need for code using these libraries to care about the internal details of how context objects are passed around.

This pattern pops up in quite a few places. Using a Use a effect locks us to passing around a particular context type but we can also abstract the functions we need into an interface. If the interface requires an internal context to implement it will be automatically passed around with the effect handler. This leads us into the next point:

As a substitute for globals

There are a few interfaces programmers may often think of as stateless but actually require passing around state, often by global values for convenience. Some examples of this are generating random numbers or simply allocating memory.

Let’s consider an API for random numbers:

We would have to require users to explicitly thread through the Prng object through their program just to use random numbers for this API. This is perhaps a mild inconvenience but it scales with the size of the program and is notable in that random numbers are usually a small implementation detail to the program logic. Why should such a small implementation detail cost so much to the terseness of the program? If we want to avoid this, we may make the Prng a global, which many languages and libraries do, but this comes with the usual downsides of globals - most notably requiring the object to be thread safe. If we make it an effect like the following:

We gain the ability to thread it through a program mostly for free (users must still explicitly initialize it somewhere up the call stack with a handler). Plus, if we later decide we want to use /dev/urandom or some other source of random numbers instead of the Prng object, we only need to swap out the effect handler. Nothing else in the call stack needs to be changed.

Similarly, let’s consider an Allocate effect:

Such an effect would let us swap how we perform allocations by adding a different effect handler for it somewhere up the call stack. We could use the global allocator for most calls, then in a tight loop swap out each allocation in that loop with an arena allocator by just adding a handler over the loop body.

I could go on with more examples of this (parsers, build systems, …) but I think you get the gist.

Writing in a Direct Style

As a small note, effects being things that are thrown/performed rather than dedicated values does often enable us to write in a more direct style compared to the alternative.

Exceptions are the easy example here, but just know this also applies to asynchronous functions with Future<T> values or other types that are usually some wrapped effect.

So without exceptions we may use an error union or optional value like Maybe t which can be Some t or None. If we have several computations returning results, we’ll need to map the Some value in-between steps:

This is cumbersome enough languages like Rust provide syntax-sugar like ? to automatically return error values and focus on the good path. That isn’t needed with effects though. The direct approach just works:

If we need to go off the good path we can just apply a handler:

Compared to error unions we never have to wrap our data in Some/Ok and we don’t have to worry about error types not composing well either:

And if it gets too cumbersome to type out all those Throw clauses we can make a type alias for the effects we want to handle:

You can think of this as being similar to using an anonymous union type for error returns. We don’t need to define explicit wrappers to combine all the errors we use as with tagged unions, and different error types compose naturally into the union. This also means if a library can Throw String, and our code also can Throw String, these will combine into just one can Throw String effect. If we want to keep them separate we need to use a wrapper type like MyError above.

Guaranteeing Purity

Most languages with effect handlers (barring perhaps only OCaml) also use effects wherever side-effects may occur. You may have noticed the can Print or can IO on previous examples, and it’s true - you can’t use side-effects in Ante without marking that the function may perform them³. Setting aside the cases when IO or print outs are redirected or used for mocking, these effects are usually handled in main automatically - so what benefit does it actually provide by making programmers mark these functions?

For one, a number of functions actually require other non-side-effectful (ie. pure) functions as input. When spawning threads for example, we can’t allow the spawning thread to call into handlers owned by our thread:

There is also a technique for concurrency called Software Transactional Memory (STM) which requires pure functions. It works by running many functions simultaneously and if a value is ever mutated out from under one thread while it was performing a transaction, it just restarts that transaction. For the curious, there’s a proof of concept implementation of it in Effekt here.

Replayability

Another neat aspect of purity is that it can give you replayability similar to the rr debugging utility. This is the tech needed for deterministic network replication and log structured backups used in databases and videogame networking.

To implement this you would need two handlers: record and replay which handle the top-level effect emitted by main. In most languages this is named IO. record would record that the effect occurred, re-raise it to be handled by the built-in IO handler, and record its result. Then, on another run replay would handle IO and use the results from the effect log instead of actually performing them. A particularly smart language could even record by default in debug builds to always get deterministic debugging!

Capability-based Security

The requirement to include all unhandled effects as part of the type signature of a function helps greatly when auditing the security of libraries. When you call a function get_pi: Unit -> F64 you know that it isn’t doing any sneaky IO in the background. If that library is later updated to get_pi: Unit -> F64 can IO you know something suspicious is probably happening, and you’ll get an error in your code as long as the function you’re calling get_pi in doesn’t already require the IO effect⁴⁵. This has parallels with Capability Based Security (bonus paper Designing with Static Capabilities and Effects) where we must pass around capabilities like fs: FileSystem as explicit objects and only functions with these objects can access the file system. With algebraic effects it works similarly except the functions declare effects instead of taking capability parameters. There is a downside to the effect approach though, and its the same one mentioned above: since effects are automatically threaded through your program you won’t get an error if a function like get_pi is updated to require IO if your function also already requires that effect. This can crop up anywhere effects are used. E.g. with a Fail effect if a library function can’t Fail but then was updated to possibly Fail, it’ll propagate upward to your existing Fail handler if used in one of your functions that also can Fail. This may be fine but it may also be unintended depending on the program. For example, perhaps a user may have preferred to handle it by providing a default value.

Whew! That was a lot, but we made it through. Obviously this post focused on the positives of effects and why I think they’re going to be much more pervasive in the future, but there are negatives as well. Aside from the accidental handling of effects issue mentioned above, the main downside with effects has traditionally been efficiency concerns, although it should be said that compilation output of effects has improved greatly in recent years. Most languages with algebraic effects will optimize “tail-resumptive” effects (any effect where the last thing the handler does is call resume) into normal closure calls. This is great because this is already most effects in practice (citation needed - although almost all the examples in this blog post fit in this category! Exceptions being the only, ahem, exception here since they do not resume at all). Different languages also have their own strategies for optimizing the remaining effect handlers: Koka uses evidence passing and bubbles up effects to handlers to compile to C without a runtime, Ante and OCaml limit resume to only being called at most once which precludes some effects like non-determinism but simplifies resource handling and allows the internal continuations to be implemented more efficiently (e.g. via segmented stacks), and Effekt specializes handlers out of the program completely⁶!