A Language Feature to Rule Them All
The expressive power of Monads and Algebraic Effects.
Some language features are too powerful for their own good.
Do you know what a Monad is1? People have struggled to explain what they are, which is not particularly surprising since it is a very abstract concept. There’s even a timeline recording the history of (in)famous monad tutorials. Many try to explain monads through analogy, which really doesn’t work. The tutorials got so bad someone wrote an article complaining about them and unintentionally created a meme that monads are like burritos.
Here’s what a monad is, as far as a programmer (not a mathematician) is concerned, in some Rust-like pseudo code:
trait Monad<M, A> {
fn new(v: A) -> M<A>;
fn and_then<B>(m: M<A>, f: fn(A) -> M<B>) -> M<B>;
}That’s it, that’s all it is. The names of the two functions vary, “new” is sometimes called “pure” or “return”2, while “and_then” is often called “bind” or “flat_map”. This is a higher-kinded type, meaning that it is generic over a type constructor (the M above), something most languages can’t natively express3.
The important part is that “and_then” function, the other function just means there’s a way to construct the type. The “and_then” function lets you sequence callbacks that stay “trapped within the monad”, so to speak. What’s that useful for you ask? Well it appears in many different contexts:
Rust’s
Option<T>is a Monad: here’s and_then. Lets you sequence callbacks that work with values if there are any and abort early if one is missing.C#’s
Task<T>is a Monad: and_then is ContinueWith. Lets you sequence asynchronous callbacks. Promises in JavaScript are the mainstream example.Java’s
Stream<T>is a Monad: and_then is flatMap. Lets you sequence callbacks that produce streams of values into producing one big stream.
If you have never used these functions/methods, don’t worry too much about it, they aren’t that useful most of the time, but now you know the pattern.
What the “Monad trait/typeclass/protocol/interface” makes possible is to write code that is generic over all of these different types.
But why on earth would you want to generalize over these very distinct types?
For most programmers the fact that these types share a common structure is utterly useless, I honestly struggle to think of any practical use case. BUT, for a language developer, it enables some neat tricks.
Haskell has something called do notation that works with any monad. It turns imperative-looking code into calls to “and_then” (which is called >>= in haskell):
If you use it with the Maybe/Either monads (Option/Result in Rust), you get behavior similar to checked exceptions or the ? operator, but not hardcoded into the language.
If you use it on MonadYield from the yield package, you get generators that aren’t hardcoded into the language.
If you use it on MonadAsync from the async package, you get async/await that isn’t hardcoded into the language.
But also logic programming, constraint programming, probabilistic programming, etc. Here’s an example of async in Haskell (from an async package test case):
async_poll = do
a <- async (threadDelay 1000000)
r <- poll a
when (isJust r) (assertFailure "")
r <- poll a -- poll twice, just to check we don't deadlock
when (isJust r) (assertFailure "")The async above is not a keyword, it is not built into the language. This is the async monad plus the do notation syntax sugar. It gets expanded to something like:
async_poll =
-- (\x -> foo) is how you make anonymous functions in haskell
async (threadDelay 1000000) >>= (\a ->
poll a >>= (\r ->
when (isJust r) (assertFailure "") >> (
poll a >>= (\r ->
when (isJust r) (assertFailure "")))))The >>= (bind/and_then) operators are sequencing the callbacks. The >> operator is just a wrapper that doesn’t pass along any value. This is similar to how async/await in JavaScript is essentially just syntax sugar for callback hell, but here the syntax sugar works for any type that defines the >>= operator.
F# has a similar feature in its Computation Expressions. It can’t represent the Monad concept as a type, so it just directly checks for a method called Bind (our friend and_then). As with Haskell’s do notation, this gets you checked exception-like early returns, async, generators, etc. with one language feature.
Isn’t this neat? A two method interface plus some rather trivial syntax sugar lets you implement all these other fancy language features as regular library code. Monads + “do notation” creates a sort of “uber language feature” that lets you implement other language features.
By implementing just one language feature, you get all those other fancy language features “for free”, even ones you haven’t thought of yet.
Sadly, however, you don’t get their combinations for free.
Monads don’t compose very well by default. If you want to mix async with exceptions, you either need to implement the combined Monad manually, or you need to use something called Monad Transformers. The simplicity is not so simple anymore4.
Thankfully, there is another language feature that shares this magical ability to model nearly any crazy language feature you can think of, is even easier to understand, and composes extremely well: Algebraic Effects.
Algebraic Effects
An algebraic effect is a conceptual framework in programming that separates the declaration of a side effect (what the code wants to do) from its execution (how it actually happens). A function raises (for example) a yield effect, and then an effect handler installed higher up the callstack handles the request.
What’s an effect and what is an effect handler, you ask? Unlike Monads where analogies quickly break down, the easiest way to describe effects is as a generalization of exceptions:
exception → effect
exception handler → effect handler
The main difference being that effects are resumable, potentially multiple times. Exceptions can be modeled as effects that just never resume.
Two caveats about this conceptual generalization:
Resumable exceptions are a pretty awful idea, don’t do that.
Performance would suck if implemented as exceptions are usually implemented.
Alongside the runtime aspect, there is also a type system aspect to effects. They’re a bit like fixed checked exceptions in that regard, you’ll see what I mean below.
The closest thing to a mainstream language that supports effects is OCaml, though it only implements them as a runtime feature. Haskell also supports them as a library by implementing them using monads. Remember what I said about monads letting you implement nearly any crazy language feature you can think of? Well, that happens to include algebraic effects too somehow.
Research languages like Koka, Eff and Effekt are where most of the action is happening. We’ll use Effekt here since it can run in the browser and has a rather familiar looking syntax, if you want to try it out.
First, the exception effect which will look very familiar:
effect throw(msg: String): Nothing
// We use double in the example because int division already does this
def div(n: Double, m: Double): Double / { throw } = {
if (m == 0.0) {
do throw("Division by zero")
} else {
n / m
}
}This gets you something like Swift’s approach to error handling, which requires adding a throws annotation to any function that can throw an exception, except here the throw annotation is an effect annotation like any other.
The effects a function performs are recorded in a set after the return type. Effekt can infer the set of effects, so you don’t have to explicitly write it out, but it’s always a good idea to do so. Effects are triggered with the “do” keyword, and indirectly by calling a function that performs effects.
Handling an effect can be done as follows:
def zdiv(a: Double, b: Double): Double / {} = {
try {
div(a, b)
} with throw { msg =>
0.0
}
}Notice how the effect is discharged from the effect set after the return type. So far, this is little more than improved checked exceptions. Let us do generators next:
effect yield[A](x: A): Unit
def fib(limit: Int): Unit / { yield[Int], throw } = {
if (limit < 0) {
do throw("expected positive limit")
}
var last = 0
var current = 1
while (limit == 0 || current < limit) {
do yield(current)
val next = last + current
last = current
current = next
}
}Here’s a generator of infinite Fibonacci numbers with an optional limit. I have an article explaining how to do this with coroutines in C if you prefer, but here we’re using effects. It also throws an “exception” if the given limit is a negative number.
Let’s create a silly function that uses the yield effect: it keeps printing the sums of the Fibonacci numbers until they exceed the given limit.
def sumFibs(limit: Int): Int / {} = {
var sum = 0
try {
fib(limit)
} with yield { i =>
sum = sum + i
println(sum)
resume(())
} with throw { msg =>
println(msg)
// no resume
}
}The language has no support for yield built-in nor “exceptions” in the traditional sense, we did all of this as a library. If we wanted we could also allow yield to return a value, so the handler can feed values into the function creating bi-directional communication.
I only code in C sir, why do I care?
Have I got a treat for you, Algebraic Effects in C: libhandler.
There’s also a newer library from the same authors that builds on top of multi-prompt delimited control (another one of these uber features): libmpeff.
They’re not the nicest thing in the world to use but it’s amazing how some assembly tricks are enough to make this work in a language very much not designed for it.
Ok, neat, how do I implement these?
If you want to handle it at the level of the compiler, rather than delegating the runtime to libhandler/libmpeff, the most efficient way is with evidence passing.
It basically involves rewriting functions into a monadic form and passing in the handlers as a hidden argument. A bit hard to explain (even I struggle to understand exactly how it works) but we can implement a limited form of algebraic effects (one-shot resume, resume is a keyword not a function) without too much pain, by translating functions that do effects to coroutines.
First, we define effects and their signatures. We’ll use a tagged union of effects for simplicity (great for the “internal to the compiler” case), but if we wanted it extensible it’s pretty easy to do as well, just more code.
typedef enum EffectKind {
EFF_NONE,
EFF_THROW,
EFF_YIELD_INT,
} EffectKind;
typedef struct Effect {
EffectKind kind;
union {
struct { const char* msg; } throw;
struct { int v; } yield_int;
};
} Effect;
#define DONE (Effect){EFF_NONE}
#define do_throw(msg) (Effect){EFF_THROW, .throw = {msg}}
#define do_yield_int(v) (Effect){EFF_YIELD_INT, .yield_int = {v}}Next we turn fib into a coroutine. Every time an effect is triggered it “pauses” and returns a request for the effect to be performed (or the NONE effect when finished). We’ll use GCC’s first class label extension for clarity and to make the code shorter, but it is not necessary (see my article on generators in C to see what to do instead).
typedef struct FibFrame {
// "program counter", tracks where we are in the coroutine
void* pc_;
// args
int limit;
// locals
int last;
int current;
int next;
} FibFrame;
Effect fib(FibFrame *f) {
if(f->pc_) goto *f->pc_;
if (f->limit < 0) {
f->pc_ = &&after_throw_1;
return do_throw("expected positive limit");
after_throw_1:
}
f->last = 0;
f->current = 1;
while(f->limit == 0 || f->current < f->limit) {
f->pc_ = &&after_yield_1;
return do_yield_int(f->current);
after_yield_1:
f->next = f->last + f->current;
f->last = f->current;
f->current = f->next;
}
// reset the function
f->pc_ = NULL;
return DONE;
}Finally, let us convert sumFib. It triggers no effects of its own and handles all effects of the functions it calls, so it does not need to be a coroutine, but for consistency we will also turn it into one.
typedef struct SumFibsFrame {
void* pc_;
int limit;
int sum;
FibFrame fib_frame_1;
// final return value
int return_;
} SumFibsFrame;
Effect sum_fibs(SumFibsFrame* f) {
if (f->pc_) goto *f->pc_;
f->sum = 0;
// try block 1
{
Effect effect = {EFF_NONE};
f->fib_frame_1 = (FibFrame){.limit = f->limit};
resume_fib_1:
effect = fib(&f->fib_frame_1);
if (effect.kind != EFF_NONE) goto handlers_1;
goto try_end_1;
handlers_1:
switch(effect.kind) {
case EFF_YIELD_INT:
f->sum += effect.yield_int.v;
printf("%d\n", f->sum);
goto resume_fib_1;
case EFF_THROW:
printf("%s\n", effect.throw.msg);
break;
}
try_end_1:
}
f->return_ = f->sum;
f->pc_ = NULL;
return DONE;
}Phew… even for this simplified version the code gets quite gnarly, but this is meant as something a compiler generates. If multi-shot continuations are allowed, the code becomes a lot more complicated as it requires managing heap allocated copies of the frames AND of the handlers because when the function is resumed and it triggers an effect it needs to be handled by the try block that originally captured the resumption5.
Out of scope for an already very large blog article.
Absolute Power Corrupts Absolutely
These two features, Monads + “do notation” and Algebraic Effects, are a little too powerful. The main problem with putting this sort of power in the hands of library developers rather than the language developer is that it can cause a large splintering of the ecosystem: multiple ways to do exceptions, multiple ways to do async, multiple ways to do generators, multiple ways to do implicit contexts, etc.
You don’t really want competing implementations of these features, you want those things standardized. This is also a problem in languages like Lisp where everyone makes their own little domain-specific languages using macros.
So I’m not sure exposing this as a user-facing language feature is a particularly good idea. What I would do is implement it in the compiler, and then implement user facing features (exceptions, generators, async, etc.) in terms of it. That way their interactions are well define and the implementation far simpler.
I would also expose the feature publicly but only if an “-experimental” flag is passed to the compiler. That allows the community to experiment with interesting uses of effects (like implementing a Prolog-like backtracking engine within the language) before they are standardized, but making it clear it’s not meant for production code.
Conclusion
Two fancy language features demystified in one blog post, aren’t I ambitious?
I really think these features are too powerful, having them widely used and abused will lead to a messy ecosystem. Most code should be made up of simple function calls.
But if you’re making a new language and you want to take it as far as it will go, here are two new tools for your tool-belt.
It’s a concept from Category Theory that happens to be rather useful in programming, mainly (but not exclusively) in functional programming.
The use of the name “return” for what is really just a constructor probably led to a lot of the confusion IMO. Bad mistake on the part of Haskell.
Haskell and Scala can, for two mainstream-ish languages.
Implementing the combination of the two in the compiler is not particularly easy either.
These are called “deep handler” semantics. There are also “shallow handler” semantics which redirect to whatever handler is around the resume call. Most effect languages have deep handler semantics.