Today I looked through the dependents of my litte async stream generator library I, oh so nicely, called asynk-strim.

It’s a stream generator that works with 0 allocations and on no_std environments without any proc-macros.

But that’s besides the point. I went looking to see how users integrate them and I saw DataStar helpers in Rust using it in a way I hadn’t thought about.

They store the Yielder object into the state, allowing to yield items from deeply within the call-stack up to the stream and then continue execution.

And then I squinted hard. Really hard. And realized “hey, those look like algebraic effects without return of values..”.

Then I had a mission: make a crate that kinda works like algebraic effects and make it work on stable Rust, on no_std (alloc is fine) and without any proc-macros.

And I succeeded

Welcome to algebraic-effects-poc, a crate that does exactly that.

It uses async oneshots to communicate back to the sender. This could probably be stack allocated. (This is left as an exercise to the reader. No really! If you implement it, feel free to PR it.)

I just wanted to prove that this is possible.

The API is also not the nicest but it does work!

use algebraic_effects::Effect;
use futures_lite::{future, StreamExt};

struct PrintEffect {
    message: &'static str,
}

impl Effect for PrintEffect {
    type Return = ();
}

fn main() {
    future::block_on(async {
        let print_effect = algebraic_effects::effect_fn::<_, PrintEffect, _>(|| async {
            PrintEffect::process(PrintEffect {
                message: "hello world",
            })
            .await;
        });

        futures_lite::pin!(print_effect);

        while let Some(effect) = print_effect.next().await {
            println!("received print effect");
            println!("printed this: {}", effect.item().message);

            effect.resume(());
        }
    })
}

To handle effects, you simply handle the effect callbacks as they get produced by the stream. The resumption is then done automatically as soon as the next loop iteration begins.

Elegant and simple enough as a proof-of-concept.

But how?

Actually it’s pretty simple!

In our stream implementation we wrap the waker we get passed in via poll_next. And in the data section of the waker we pass in the TypeId of the effect we want to yield, as well as an Option<EffectItem<T>>.

That way we can thread the option aaaaaaaaaall the way through the call stack. The TypeId is put there for two reasons:

  1. Assurance we don’t accidentally pass an i32 and the caller expects a String, making the API unsound
  2. Identifying which stream we should yield this item to

The second point is very important to allow for nested effects.

Then upon yielding, we check the waker. Is the VTable our waker VTable? For that we simply check for pointer equality. That’s fine because our VTable is allocated as a static, making the memory address static.

Then we check whether the TypeId matches.

If it does, then extract the Option pointer and set it. If it doesn’t then check the wrapped waker just like you checked this one. This is essentially a linked list of wakers. So the time to find the correct waker grows linearly with the amount of wakers.

The EffectItem has two components. The item that is yielded, and a async_oneshot::Sender allowing the effect handler to return a value.

This is essentially the same approach Embassy uses for its task references!

Look: https://github.com/embassy-rs/embassy/blob/2a79c55d4d38e95f90a8efcf93a3e28f4d6ad35f/embassy-executor/src/raw/waker.rs#L34-L44

What is this then really?

It’s a TypeId addressed async stream with the ability to return values and resume execution. Or, as known to nerds, algebraic effects.

It might look different to what stuff like Koka since Koka can assert which effects it wants to use in its type system.

This is really cool but not feasible for us without using proc-macro magic. And I explicitly wanted to avoid that.

So we are just using good ol’ runtime checks. But through the Rust type-system, you still can’t return an i32 to a handler that expects a string.

Prior art

Obviously there’s already other libraries, such as effing-mad which is genuinely beautiful and makes great use of Rust nightly features.

The differentiators here are that effing-mad only runs on nightly and uses proc-macros, which is what I set as a goal to explicitly avoid.

Conclusion

I really just wanted to prove that this is possible. no_std+alloc effect systems on stable Rust by piggy-backing off of async Rust. And it’s available today!

Yes, we could probably somehow remove the allocations but, as mentioned, feel free to PR!