Caterpillar

Let's revisit my earlier thought on the problems with ad-hoc effects in Rust, and see how an algebraic effect system can solve those. Here's the initial example again:

let name = names().find(|name| name.is_available());

Remember, when I changed is_available to be both asynchronous and fallible, that turned into this monstrosity:

let name = stream::iter(names())
    .filter_map(|name| async move {
        name.is_available()
            .await
            .map(|is_available| is_available.then_some(name))
            .transpose()
    })
    .next()
    .await
    .transpose()?;

(Again, I'm not claiming that this is the best way to do it, and my point is not how bad it is. My point is that it's not possible in Rust to write a find function that can be used unchanged, with an asynchronous and/or fallible function argument .)

Before we see how algebraic effects can improve on that, let's look at the definition of find. A simplified version could look something like this:

fn find(&mut self, f: fn(&Self::Item) -> bool)
    -> Option<Self::Item>

It takes a function as an argument, uses it to search the iterator that find is defined on, then returns a result, if any.

Let's re-imagine that using an algebraic effect system. Here I'm inventing a with syntax that can be used to annotate any function, defining which effects this function has:

fn find<effects X>(&mut self, f: fn(&Self::Item) -> bool with X)
    -> Option<Self::Item>
    with X

I've given find a type parameter called X, which represents any number of (including zero) effects. The new signature states that the function parameter f can have any effect, and that the find function has those same effects (with X on both). So, if f is async, find is async. If f is fallible, find is fallible. But find doesn't have to change to accommodate that.

Let's go one step further by leaning more into the effect system. That find might or might not return a value, can also be an effect. Let's call that effect None, because it would be triggered if there's no return value:

fn find<effects X>(&mut self, f: fn(&Self::Item) -> bool with X) -> Self::Item
    with None, X

Now we state that find has the None effect, in addition to any effects that X brings in. I don't know if it would be a good idea to do it this way. I just want to demonstrate what we could do with an effect system.

But how does this with syntax help? Well, as a caller, we can now use this single find function in every situation. Whether is_available is asynchronous, fallible, or whatever else; it'll work. Here's how that could look, if f itself had no effects, and we just have to handle the None effect of find:

let name = try names().find(|name| name.is_available()) {
    None => {
        "Anonymous"
    }
};

I've invented this try syntax for handling effects, inspired by the existing match syntax. If find doesn't find a name (it triggers the None effect), then we fall back to the name "Anonymous".

How would that look, if is_available was both asynchronous and fallible? It depends! Is our code in a position to handle these effects, or does it just want to pass them on to its own callers?

let name = try names().find(|name| name.is_available()) {
    None => {
        "Anonymous"
    }
    Error(DatabaseError(err)) => {
        log!("Database error. Retrying...");
            database.reconnect();
            continue; // looks we are in some kind of loop
    }
    // not handling `Async`; some other code up the call stack will do that
};

This is a mixed scenario, where our code handles the database error, but not the asynchrony (because it's asynchronous itself). And if our code had all of the combined effects of the code it calls (None, Error, Async), then it wouldn't have to do anything! It would look exactly like it did in the initial example.

Would any of this be a good idea for Rust? Maybe; I don't know. I haven't put a lot of thought into that, honestly, because this is not a proposal to improve Rust. This is about demonstrating how algebraic effects can solve a real problem in a real language. Rust is just an example, because it's the language I happen to know best.