How to implement effect handlers

@Quelklef asked:

polaris has algebraic effects, right? how did you implement them?

i know they can be done with free monads but i have a hunch that that’s not the route you opted to take

It doesn’t, actually ^^ I’ve thought about implementing them, but fine grained effects just aren’t very useful for the kinds of scripts you might want to write in Polaris and the extra type level complexity gets in the way too much.

Buut, Vega will have algebraic effects! I’ve also implemented them for a different language before so I have a pretty good idea of how they’re going to work.

So, implementing effects on top of free monads is technically possible, but it’s honestly a pretty terrible idea. I’m not a massive fan of free monads in general, but building up and later traversing a heap allocated tree for every effectful expression is pretty ridiculous.

The standard implementation approaches are much more similar to, or even based on delimited continuations¹. The key insight here is that a continuation is really not much more than a call stack and a delimited continuation (up until an effect handler) is just a delimited part of the call stack. Therefore, capturing a continuation just involves copying parts of the stack and continuing just copies them back. Alexis King has an amazing talk about this.

What I’m going to do is based on what OCaml 5 does though. The idea behind this approach is that if a continuation is used linearly (like the coroutine-like effects that are relevant to Multicore OCaml), the delimited call stack never actually needs to be duplicated. So what one can do is represent the program stack as a hybrid growable/segmented stack where every handler creates a new stack segment that is linked back to the previous through a pointer. Now performing an effect walks the stack to find the closest handler (just like throwing an exception would) and continues execution on its stack segment. Because there is a segment boundary between them, nothing in the suspended continuation will be overriden. When the continuation is resumed, control jumps back forward to the segment where the effect was performed, which is linked back to the point where the handler stack has resumed it.

The diagrams in the paper are prettier than this, but you’ll have to bear with my ASCII art for this example.

Let’s say your program looks something like this, where the expression at the <-- is currently being evaluated

f () = {
    let x = 5
    let returned = handle {
        let y = 6
        let result = perform SomeEffect <---
        result + 1
    } with {
        SomeEffect cont ->
            \x -> continue cont x
        }
    }
    let z = 7
    let w = 8
    returned 9
}

This is a pretty contrived example but all it does is perform an effect that is handled by returning the continuation as a function, which is then called with 9 as an argument.

Initially, the call stack for this is going to look something like this (where stacks grow downwards)

+-------+
| x = 5 |   # the containing function
+-------+
    ^
    |
+-------+
| y = 6 |  # the part inside the handle expression
+-------+ <-- stack ptr

Performing the effect will disconnect the second segment and continue execution on the initial one while jumping to the correct handler code. cont is now given a pointer to the disconnected stack segment (= delimited continuation)

+---------+
| x = 5   |
| cont = ------------------+
+---------+ <-- stack ptr  |
                           |
+---------+                |
| y = 6   | <--------------+
+---------+

The handler further mutates and expands the first stack segment (which is fine since the second one is completely independent of it now!). It even returns the continuation wrapped in a function so at the point just before returned 9, the stack will look like this

+------------+
| x = 5      |
| returned = ---------------> closure
| z = 7      |                   |
| w = 8      |                   |
+------------+ <-- stack ptr     |
                                 |
+---------+                      |
| y = 6   | <--------------------+
+---------+

Now all that continuing the continuation needs to do is link the second stack segment back to the first one and jump to the correct location in the code. It also invalidates the continuation inside returned since the stack segment will now be mutated and so cannot be resumed again.

+------------+
| x = 5      |
| returned = ---------------> closure
| z = 7      |                   |
| w = 8      |                   |
+------------+                   X
    ^                            
    |                            X
+---------+                      |
| y = 6   | <--------------------+
+---------+ <-- stack ptr

And that’s it! Notice how none of this ever had to copy stack frames around or do any operations that were not constant in the size of the call stack (other than finding the handler which can be done very efficiently).

Importantly though this approach only works for one-shot continuations that are only used once. Trying to use the continuation more than once doesn’t work because the call stack has already been used up the first time².

In Vega, I’m going to need to have both linear and non-linear effects anyway since linear resources cannot be carried across calls to non-linear effects, so I can use that to take this fast path in the linear case and copy the continuation segment in the non-linear case so that it can be reused.

Oh and if you’re writing a dumb tree-walk interpreter, CPS is enough to capture the continuation. That’s how I implemented effects in Flora.