Safe, extensible interrupts/syscalls, a.k.a. Algebraic Effects

Interacting with the unpure outside world has always been a pain issue for FP folks. Slowly and painfully, the Functional Programming community is realizing that reinventing interrupts and interrupt handlers in a type-safe way is the way to go. Unfortunately, the FP community has consistently sucked at naming things, leaving poor Haskell newcomers bumping their heads against unergonomic monads and monad transformers, without realizing that much more ergonomic alternatives such as Koka are quickly becoming available.

(Note: the notion of algebraic effects being interrupts has been already stated in this paper here. Kudos to DANEL AHMAN and MATIJA PRETNAR from University of Ljubljana, Slovenia. This article aims to draw the parallels between interrupts and algebraic effects in an intuitive manner.)

Most of you probably haven’t heard about algebraic effects (which I would prefer to call algebraic interrupts); some of you might have heard of React Hooks; many of you should have heard about software interrupts or system calls.

It turns out that declaring your type-safe extensible interrupts (or micro-syscalls) is an immensely powerful abstraction. It decouples your code into two parts: the code that may call these interrupts, and the interrupt handlers (or micro-operating-systems).

It’s an almost too powerful abstraction that covers nearly all control primitives that you can think of: exceptions, generators, async/await, fork, dependency injection… the list goes on. Additionally, the powerful type system will ensure that as long as you handle your interrupts properly, your micro-program executed by your micro-operating-system will be well-behaving like the simplest pure functions — no surprises would happen.

Simple interrupts

Let’s say I want to eat ice-creams. If the first ice-cream costs more than 2 bucks I’ll stop eating, otherwise I’ll eat one more. Eventually I need to know how much I spent on ice-creams.

Now, a problem that I have is that I do not know the concrete pricing of the ice cream shop that I visit. It could be a flat pricing. It could be 50% off for the second one. It could be a buffet. It could require a database read to check the ice-cream price in real time. There’s no way to know the exact pricing ahead of time, so we’d have to express our intent of eating ice-creams in the most general way possible: defining two interrupts (or effects, or micro-syscalls) called eat-icecream and check-cost (I’ll be using Koka syntax):

effect control eat-icecream() : ()
effect control check-cost() : int // returns the cost in int

Then, we define our intent of eating ice-creams using these interrupts:

fun my-eat-icecream() {
    eat-icecream();
    val cost = check-cost();
    if (cost > 2)
    {
        return cost
    }
    else {
        eat-icecream();
        return check-cost()
    }
}

We already have definitions of the interrupt and mini-programs that make use of the interrupt, but the concrete implementations of the interrupt handlers are left to be decided. Providing interrupt handlers is equivalent to providing a runtime for our mini-program.

The most simple interrupt handlers for ice-cream price calculations is a buffet. We simply ignore eat-icecream and always return the same cost:

fun buffet() {
    with fun eat-icecream() { () } // the eat-icecream handler does nothing
    with fun check-cost() { 2 } // the check-cost handler always returns 2
    my-eat-icecream()
}fun main() {
    println(buffet()); // prints 2
}

A slightly more sophisticated approach is to give a flat pricing, i.e. every ice-cream costs the same. We use a local mutable variable for this purpose:

fun flat-pricing(price: int) {
    var total-cost := 0;
    with fun eat-icecream() { total-cost := total-cost + price }
    with fun check-cost() { total-cost }
    my-eat-icecream()
}fun main() {
    println(flat-pricing(1)); // prints 2, i.e. two $1 ice-creams
    println(flat-pricing(3)); // prints 3, i.e. a $3 ice-cream
}

Although flat-pricing seemingly involves a mutable variable, the mutability isn’t visible from the outside because the mutable variable cannot exit the scope where it’s defined. Therefore, the compiler guarantees that flat-pricing is a pure function without any surprises, i.e. it always turns an int into another int. Let’s load our file into the REPL and see the inferred type for ourselves:

> :l icecream.kk
...
> :t flat-pricing
check  : interactive
(price : int) -> int

Handling all of the interrupts at once isn’t even really needed. In fact, you could handle only part of the interrupts, or turn a lower level interrupt into a higher level one. For example, we could handle the eat-icecream interrupt by triggering another add-cost(price) higher level interrupt, so that every next ice-cream gets cheaper:

effect fun add-cost(cost: int) : ()fun decreasing-pricing(price: int) {
    var current-price := price;
    with fun eat-icecream() {
        add-cost(current-price);
        if (current-price > 0) {
            current-price := current-price - 1
        }
    }
    my-eat-icecream()
}

and then handling the add-cost interrupt and check-cost interrupt at the top level:

fun decreasing-pricing-full(price: int) {
    var total-cost := 0
    with fun check-cost() { total-cost }
    with fun add-cost(price) { 
        total-cost := total-cost + price
    }
    decreasing-pricing(price)
}fun main() {
    println(decreasing-pricing-full(2)) // prints 3, i.e. a $2 and a $1 ice-cream
}

This allows flexibly expressing more complex pricing schemes.

EXERCISE: Change the program so that the price of every ice-cream is read from a file.

EXERCISE: If you were to model such behavior in an algebraic-interrupt-less system (using callbacks, first-class function parameters, monad transformers, etc), what ergonomic difficulties may appear? Enumerate the ergonomic difficulties.

Exception handling and resuming from exceptions

So far we have covered normal ice-cream shops. But what if I’m wanted by FBI and the ice-cream shop owner recognizes me? In that case the shop owner needs to immediately stop serving me ice-creams and call the police: this is an exceptional scenario!

It turns out that interrupt handlers aren’t just “functions defined from the outside”. They can dynamically turn interrupts into exceptions. Suppose the cop determines whether I’m a suspect by, well, tossing a coin (which definitely shouldn’t happen in real life, but for explanatory purposes let’s pretend that it happens). If it’s head then I’m going to jail (i.e. terminating the ice-cream-eating mini-program), and if it’s tail then I can keep on eating my ice-cream. The big difference here is that unlike exceptions, interrupts can be a function or an exception at the same time, and the behavior is determined by handlers, i.e. the surrounding runtime.

fun with-fbi() {
    var innocent := False;
    with control eat-icecream() {
        if (!innocent) {
            val is-suspect = choose(True, False) // toss a coin
            if ( is-suspect ) {
                println("🚓"); //  no more ice-creams for you!
                return 0 // of course we won't charge you for any
                // ice-cream, if that matters to you
            } else {
                innocent := True;
                resume(()) // you can keep on eating ice-creams
            }
        } else {
            resume(()) // We already know that you're not a suspect
        }
    }
    with fun check-cost() { 2 } // buffet
    my-eat-icecream()
}fun main() {
    println(with-fbi()) // prints "🚓 0" or 2, depending on the cop's coin toss
}

Notice how we went from with fun to with control for the eat-icecream handler. in addition to acting like a function that returns a value with resume, with control also allows you to treat the eat-icecream interrupt as a thrown exception, in which case you would handle the exception with println("🚓");, skip the rest of the my-eat-icecream program, and return the overall cost, which is zero. return and resume are different here: return short-circuits the underlying my-eat-icecream mini-program and provides the final result of the mini-program directly; resume, on the other hand, gives a value back into the underlying mini-program and makes the eat-icecream interrupt handler itself work like a regular function call.

If we look at the type signature of with-fbi , we’ll see that it has two kinds of interrupts: interrupts involving console (caused by uses of println) and interrupts involving some sort of random number generator (caused by use of choose), but the exception-like interrupt eat-icecream of our my-eat-icecream program has been handled and invisible from the outside:

> :t with-fbi
check  : interactive
() -> <console,ndet> int

Superpowered fork()

So far we’ve covered some ice-cream shop scenarios, but there’s still one category of ice-cream shops that we haven’t considered yet: the ones involving lucky draws. Let’s say that each time I eat an ice-cream, a lucky draw determines whether I should pay 1 buck or 3 bucks for it.

We could go straight into the ice-cream shop and let the random number generator decide how much the ice-cream would cost us, but we could also think through all possible outcomes before testing our luck.

Every time we take a lucky draw, our ice-cream eating forks into two trajectories or worldlines: one in which we’re lucky and only needs to spend $1, and one in which we’re unlucky and have to spend $3. When we’re lucky and decide to draw a second time, the trajectory will fork into another two trajectories.

Recall that in Unix systems, fork() returns twice: once in the parent process and once in the child process. Within fork(), the parent process (i.e. the registers, program counter and the stack) is captured and copied. Within an algebraic interrupt handler, the mini-program’s state, or the mini-process, or continuation (a name popular among FP folks but is actually my least favorite name) is captured and saved in resume() . The ultra superpower of algebraic interrupts is that you can resume() multiple times, effectively fork() ing into multiple processes.

Our my-eat-icecream mini-program’s return value, or exit code (under the operating-system-and-process allegory) is the total money spent. When we resume() multiple times or fork into multiple mini-processes, We’ll have multiple return values or exit codes for each process, and we need to somehow collect them together into “a list of all possible amount of money spent”. The way of doing that is to “hook” into the return value or the exit code handling and turn a single return value (let’s say 2, i.e. two $1 draws) into a list of return values (e.g. [2]) and then concatenating them together.

fun lucky-draw()
{
    with fun check-cost() { 0 } // initial cost
    with handler {
        return(x) {[x]}
        control eat-icecream() {
            val current-cost = check-cost();
            val cost-lucky = {
                with override fun check-cost(){current-cost + 1}
                resume(())
                };
            val cost-unlucky = {
                with override fun check-cost(){current-cost + 3}
                resume(())
                };
            cost-lucky ++ cost-unlucky
        }
    }
    my-eat-icecream()
}fun main() {
    with total-cost = lucky-draw().foreach
    println(total-cost) // prints 2 ($1 + $1), 4 ($1 + $3), 3 ($3)
}

EXERCISE: change the program so that it returns all possible outcomes and their associated probabilities. Merge outcomes with the same amount of money spent.

Caveats

Unfortunately, with reinventing interrupts comes rediscovering problems that Unix programmers have known since antiquity: things like fork()-ing after fopen() could mess things up. Care should be taken when dealing with resources: you might have to do manual reference-counting, and you need to take care of how interrupt handlers interact with each other.

But there is more…

The full source code is available here. To know more about Koka’s implementation or black-magicy performance optimizations, you can check out Koka’s website to learn more.