TL;DR: Local programmer is inconvenienced by error-handling boiler plate, 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 usingcatch_unwind
. The catch with catching is that unwinding is slow and unpredictable. In fact, programs compiled withpanic = "abort"
will never catch a panic. -
Go nuclear. Make a copy of
MagicNumber
specifically for the case of fallible implementations ofmagic_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();
// compile error! baz() calls foo(), which has effect Bar, but baz() cannot Bar!
}
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 {} {
// Bar was handled, so no compile error
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
may only call functions which also have the effect
. Then const
would be one such contravariant effect, but, honestly, it's not worth the hassle.
Effect polymorphism comes in
In the same way that a function could be polymorphic over types (as with generics), why not have functions be
polymorphic over effects? If we return to our original example of my_sum
, we can fold all
the possible versions of my_sum
from
variants to just one.
trait MagicNumber {
effect Effect;
fn magic_number(x: u32) -> u32 can Self::Effect;
}
fn my_sum<N: MagicNumber>() -> u32 can N::Effect {
let mut total = 0;
for i in 0..10 {
total += N::magic_number(i);
}
total
}
I'm pretty happy with this! There's very little ceremony involved, and we get to express vastly more things than we could before!
Of course, once we have something like this system, there are a lot of obvious questions:
- Is there a complement to
type _ = impl Trait
for effects? - How should effects compose?
- Can we treat effects like data?
- Can we do introspection or reflection on effects?
- Can we do dynamic-dispatch on effects at runtime?
- If Rust also got linear types, how would they compose with cancellation in effect handlers?
For now, though, it would be really nice to just write code which is polymorphic over its effects.
I'm no closer to fixing my Python issues
It's one thing to muse about a solution to my problem and another thing entirely to actually solve it. As much as I would like to go completely down the rabbit hole and implement a dream language with algebraic effects, linear types, trait-based polymorphism, and zero-cost abstraction, I also have to get my projects done some time this century.
There's been a lot of ink spilled about efficiently compiling algebraic effects, but at the time of writing there's no mainstream programming language that does so. Koka is probably the closest thing that we have to such a language, but it's admittedly not production-ready.
For now, I will probably end up just making code that has weird effects panic. It's not the best choice, but it's good enough for now.
Thanks to Aedan, Shreyas, and Wisha for reviewing this post!