Another effect handler design for Rust

1

Hi,

what if effect handlers were done like this?

let effect = Effect::new(); // needs to be pinned to stack somehow

// create delimited continuation
let mut effResult = effect.handle( || { // dynamic check: can only do once
     .....
     let b = effect.perform(a); // can be in a function down the stack
     ...
});

// k in EffInvoked(a, k) sits on the stack as if alloca-ed
// stack pointer marks where it ends
// dynamic check: can only be resumed if stack pointer
// is at exactly the same position
while let EffInvoked(a, k) = effResult {
   .... // handle effect
   effResult = k.resume(b)
}
let result = if let Done(r) = effResult {r}
else {unreachable!();}

A sketch of the types involved

struct Continuation<A, B, Res> { ... }
enum EffResult<A, B, Res> {
    Done(Res),
    EffInvoked(A, Continuation<A, B, Res>)
}
impl<A, B, Res> Continuation<A, B, Res> {
    fn resume(self, b : B) -> EffResult<A, B, Res> {...}
}
struct Effect<A, B> {..}
impl<A, B> Effect<A, B> {
    pub fn handle<RES>(&self, f : F) where F : FnOnce() -> EffResult<A, B, RES> {...}
    pub fn perform(&self, a : A) -> B {..}
}

Some trick is needed to ensure Effect instances remain pinned to the stack.

The existing stateless continuations in Rust allow the invoking function to grow stack as it pleases but continuation can only yield always from the same “stack frame”. The proposed design is the reverse of that: a continuation can grown and shrink the stack as it likes but the handler can only resume that continuation from exactly the same stack frame where it originally created it.

There’s a difference from OCaml nascent design for algebraic effects: the loop in this design is explicit. It is felt an explicit loop is better suited for zero-cost abstractions language :slight_smile:

If some explicit trickery is invented to jump between different stacks perhaps full cooperative multi-tasking could be developed on top of this.

One wants to ensure effect.handle can only be invoked once. Perhaps instead of a dynamic check that could be achieved by allowing handle() to consume one member of the Effect struct. The resulting code is less clear so this option is not shown in the sketch above.

There is probably a limitation within this design… the continuation might want to pass references to objects on its stack inside of A but it won’t be able to satisfy the lifetime requirement… not sure if anything can or should be done about it.

2

to make Effect::handle be called only once, you could instead do something like

struct Token(());

struct UnhandledEffect<E: RawEffect>(E);

struct Effect<E: RawEffect>(E);

impl<E: RawEffect> UnhandledEffect<E> {
    pub fn new(e: E) -> Self {
        Self(e)
    }
    
    pub fn handle<F: FnOnce() -> E::Result>(self, f: F) -> Effect<E> {
        self.0.handle(f);
        Effect(self.1)
    }
}

impl<E: RawEffect> Effect<E> {
    // no way to call handle here
    ...
}

trait RawEffect {
    type Result;
    
    pub fn handle<F>(&self, f : F) where F : FnOnce() -> Self::Result;
}
3

Plug: I’m experimenting with eff, a library implementation of algebraic effects. The design is inspired by Futures, and I could utilize generators for async fn-like transformations.

1 Like
4

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.