TL;DR: Local programmer is inconvenienced by error-handling boilerplate, writes uninformed article about experimental programming language features. More at 11.

I’ve encountered lots of pain points when dependency-inverting things, especially when working with combinators. Most recently, I’ve been thinking about how I might expose Python bindings for a half-baked motion planning library I’m building. The chief problem is that I want users to provide their own configuration spaces, samplers, robots, and collision checkers. If those are implemented in Python, they can throw an exception at any time, yielding an error in the corresponding PyO3 API. The problem is that all of my functions which might call into that behavior don’t return an error - what am I to do?

I’m not the only one with this sort of problem! boats has been writing about this for nearly five years, and handling iterators of results is still a pain. As the async story for Rust has improved, we’ve seen similar results on the pain (or lack thereof) of function coloring in Rust. In short, crossing control-flow boundaries in statically typed languages is painful and difficult.

First off, a disclaimer: I am more interested in programming language theory than the average joe, but I’m still not an expert. I’ve only read a little bit on the topic of algebraic effects, so I may get some things wrong - I’m a roboticist, not a category theorist. The purpose of this article is not so much to propose a novel contribution as to draw attention to a common problem and an elegant solution.

Dependency inversion

For the sake of this post, I’ll refer to dependency inversion as the practice of taking a subroutine in a procedure and taking it out as an argument. For example, consider the following Rust code:

fn my_sum() -> u32 {
let mut total = 0;
for i in 0..10 {
total += magic_number(i);
}
total
}

fn magic_number(x: u32) -> u32 { x }

This would be a case of an uninverted dependency; that is, my_sum depends on magic_number and knows it specifically by name. However, if we factored out magic_number into a user provided file, this would invert the dependency:

fn my_sum<N: MagicNumber>() -> u32 {
let mut total = 0;
for i in 0..10 {
total += N::magic_number(i);
}
total
}

trait MagicNumber {
fn magic_number(x: u32) -> u32;
}

This has a lot of benefits, mostly for code reuse. We can now use these generic functions to build simple combinators and compose them into bigger things!

In fact, this toy example is pretty close to what a simple iterator combinator (such as std::iterator::Sum) does. For the most part, people are quite happy with it and it gets the job done.

My problem

What if a user-provided magic_number implementation is fallible? Perhaps it requires file I/O, or has a chance of dividing by zero, or maybe it calls out to some FFI code. In current Rust, we have a few prospects:

• Panic! Whenever magic_number encounters an error state, we can just crash the program. This works fine until you are woken up at 3 A.M. with calls about your broken website.
• Panic, but gracefully. Whatever top-level code calls my_sum can catch the panic using catch_unwind. The catch with catching is that unwinding is slow and unpredictable. In fact, programs compiled with panic = "abort" will never catch a panic.
• Go nuclear. Make a copy of MagicNumber specifically for the case of fallible implementations of magic_number.

The nuclear option would look something like this.

fn try_my_sum<N: TryMagicNumber>() -> u32 {
let mut total = 0;
for i in 0..10 {
total += N::try_magic_number(i)?;
}
total
}

trait TryMagicNumber {
type Error;
fn try_magic_number(x: u32) -> Result<u32, Self::Error>;
}

So, with a little bit of brute force, we’ve come up with an API that can handle fallibility. It’s annoying to maintain, sure, but at least we’ve achieved maximum flexibility. But wait! What if we want to make an implementation of magic_number using an unsafe function! Then we’d have to make a new trait!

trait UnsafeMagicNumber {
type Error;
unsafe fn unsafe_magic_number(x: u32) -> u32;
}

And what if we want to use this functionality with a function that was both unsafe and fallible?

trait TryUnsafeMagicNumber {
type Error;
unsafe fn try_unsafe_magic_number(x: u32) -> Result<u32, Self::Error>;
}

Now imagine if we wanted to make a version of magic_number that worked via dynamic-dispatch. To do so, we’d have to make a new trait ObjectMagicNumber, since MagicNumber is not object-safe. Then we’d need to make even more traits for every version of it!

trait ObectMagicNumber {
fn object_magic_number(&self, x: u32) -> u32;
}

trait TryObjectMagicNumber {  }
trait UnsafeObjectMagicNumber {  }
trait TryUnsafeObjectMagicNumber {  }

Then we have to consider all the many other variations on this once-simple API: mutability, allocations, I/O, blocking, const, async. The list goes on. If we had such properties, we’d need to create traits and functions to handle them all. Each one of these variations is reasonable, but we know that since we can’t accept all of them, we must accept none of them.

What are effects, anyway?

Intuitively, effects are a way of trying to abstract away all these possible variations on a function in a clean and generic way. Every function has some set of effects, and effects are inherited: if has effect , and calls , then also has effect .

To build some examples, let’s make a new fake programming language called RustE (Rust, with Effects). We’ll make only a few syntactic changes, allowing the creation of effects and for effects to be annotated with a can clause describing their effects.

effect Bar {}

fn foo() can Bar {
println!("bar!");
}

If we made a new function baz which called foo, baz would also have to have the effect Bar.

fn baz() {
foo();
}

fn qux() can Bar {
foo();  this is ok though
}

To avoid the function coloring problem, we’ll also allow for handle clauses, which allow a function without an effect to call a function with an effect.

fn baz2() {
handle Bar {} {
foo();
}
}

We can add some texture by letting effects also call procedures which go all the way up to their handlers. The handler can choose to resume, returning execution to the effect caller, or to break, escaping from the handler to the scope outside the handler.

effect GetWidget {
fn make_widget() -> u32;
}

fn eat_widgets() can GetWidget {
loop {
let w = GetWidget::make_widget();
println!("mm, tasty {w}");
}
}

fn feed_widgets() {
let mut widgets = vec![1, 2, 3];
handle GetWidget {
fn make_widget() -> u32 {
match widgets.pop() {
Some(w) => w,
None => break,
}
}
} {
eat_widgets();
}
println!("out of widgets :(");
}

// expected output:
// ----------------
// mm, tasty 3
// mm, tasty 2
// mm, tasty 1
// out of widgets :(

Our final wrinkle: effects and their functions may have generic types!

effect Fail<E> {
fn fail(e: E) -> !;
}

fn do_my_best(x: u32) can Fail<&'static str> {
if x == 0 {
Fail::fail("can't divide by zero");
} else {
println!("{}", 1 / x);
}
}

fn main() {
handle Fail<&'static str> {
fn fail(s: &'static str) -> ! {
println!("{s}");
break;
}
} {
do_my_best(1);
do_my_best(0);
}
}

Effects can model lots of kinds of functions

We can model many language features as special cases pf effects. In fact, the handling the effect Fail in the example above is equivalent to a try-catch statement with checked exceptions!

unsafe is also pretty trivially an effect - any function which is unsafe can have the Unsafe effect, while any unsafe block desugars to a handler. If you added effects to the original Rust language, it might be possible to integrate them in a backward-compatible way into the language.

The same applies for async, I/O, and allocations. If you squint hard enough, you might be able to imagine a case where interior mutability is a sort of effect handler too. Surprisingly enough, const isn’t really an effect, but non-const code is! Non-const code can call const functions, but not the other way around, so running at runtime is the effect. I suppose you could alternately come up with "contravariant" effects, by which any function with contravariant effect ![](data:image/svg+xml,%3Csvg%20class%3D%22typst-doc%22%20viewBox%3D%220%200%2014.727699999999999%2021.878999999999998%22%20width%3D%2214.727699999999999pt%22%20height%3D%2221.878999999999998pt%22%20xmlns%3D%22http%3A%2F%2Fwww.w3.org%2F2000%2Fsvg%22%20xmlns%3Axlink%3D%22http%3A%2F%2Fwww.w3.org%2F1999%2Fxlink%22%20xmlns%3Ah5%3D%22http%3A%2F%2Fwww.w3.org%2F1999%2Fxhtml%22%3E%0A%20%20%20%20%3Cg%3E%0A%20%20%20%20%20%20%20%20%3Cg%20transform%3D%22translate%280%200%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20class%3D%22typst-group%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20transform%3D%22translate%280%2015.379%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20class%3D%22typst-text%22%20transform%3D%22scale%281%2C%20-1%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cuse%20xlink%3Ahref%3D%22%23g1934A050AB59D50EF77DAD6A468C6415%22%20x%3D%220%22%20fill%3D%22%23000000%22%20fill-rule%3D%22nonzero%22%2F%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20transform%3D%22translate%2810.296%2010.660000000000002%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20class%3D%22typst-text%22%20transform%3D%22scale%281%2C%20-1%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cuse%20xlink%3Ahref%3D%22%23g5F7D0A9C96F0A79DE54722163C4D2524%22%20x%3D%220%22%20fill%3D%22%23000000%22%20fill-rule%3D%22nonzero%22%2F%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%3Cdefs%20id%3D%22glyph%22%3E%0A%20%20%20%20%20%20%20%20%3Csymbol%20id%3D%22g1934A050AB59D50EF77DAD6A468C6415%22%20overflow%3D%22visible%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%3Cpath%20d%3D%22M%202.5870001%208.528%20C%202.5870001%208.398%202.73%208.333%203.003%208.333%20C%203.523%208.333%203.783%208.281%203.783%208.1640005%20C%203.783%208.125%203.757%208.034%203.7180002%207.8650002%20L%202.028%201.066%20C%201.963%200.78000003%201.8330001%200.611%201.638%200.546%20C%201.547%200.52%201.3130001%200.507%200.91%200.507%20C%200.624%200.507%200.49400002%200.481%200.49400002%200.208%20C%200.49400002%200.065%200.637%200%200.91%200%20L%207.579%200%20C%207.8910003%200%207.9170003%200.026%208.021%200.24700001%20L%208.541%201.417%20C%208.892%202.223%209.139%202.821%209.282001%203.224%20C%209.2560005%203.341%209.217%203.4190001%209.074%203.4190001%20C%208.983%203.4190001%208.905%203.354%208.853001%203.237%20C%208.528%202.47%208.216001%201.885%207.9040003%201.469%20C%207.3840003%200.767%206.617%200.507%205.395%200.507%20L%203.51%200.507%20C%203.38%200.507%203.289%200.507%203.237%200.52%20C%203.1590002%200.52%203.1200001%200.546%203.1200001%200.58500004%20C%203.1200001%200.611%203.1460001%200.702%203.1850002%200.871%20L%204.043%204.342%20L%205.278%204.342%20C%205.889%204.342%206.214%204.264%206.2790003%204.0950003%20C%206.3050003%204.03%206.3180003%203.9390001%206.3180003%203.809%20C%206.3180003%203.64%206.2920003%203.4320002%206.227%203.1850002%20C%206.201%203.1200001%206.188%203.068%206.188%203.029%20C%206.188%202.8990002%206.2660003%202.834%206.409%202.834%20C%206.526%202.834%206.604%202.938%206.656%203.1330001%20L%207.3840003%206.149%20C%207.3840003%206.2790003%207.3190002%206.3440003%207.176%206.3440003%20C%207.072%206.3440003%206.994%206.2530003%206.955%206.071%20C%206.8250003%205.564%206.656%205.2390003%206.435%205.083%20C%206.214%204.927%205.85%204.849%205.317%204.849%20L%204.173%204.849%20L%204.927%207.8780003%20C%205.031%208.32%205.031%208.333%205.577%208.333%20L%207.3840003%208.333%20C%208.047%208.333%208.502%208.268001%208.749001%208.1380005%20C%209.113%207.9430003%209.295%207.553%209.295%206.968%20C%209.295%206.747%209.282001%206.513%209.243%206.2920003%20C%209.243%206.2660003%209.243%206.227%209.2300005%206.175%20L%209.2300005%206.058%20C%209.2300005%205.915%209.295%205.85%209.425%205.85%20C%209.555%205.85%209.633%205.967%209.659%206.214%20L%209.919001%208.437%20C%209.958%208.801001%209.867001%208.84%209.516%208.84%20L%203.029%208.84%20C%202.73%208.84%202.5870001%208.827001%202.5870001%208.528%20Z%20%22%2F%3E%0A%20%20%20%20%20%20%20%20%3C%2Fsymbol%3E%0A%20%20%20%20%20%20%20%20%3Csymbol%20id%3D%22g5F7D0A9C96F0A79DE54722163C4D2524%22%20overflow%3D%22visible%22%3E%0A%20%20%20%20%20%20%20