🍣

RustでGeneratorを使って(One-shot) Algebraic Effectsを実装する

2023/07/29に公開

Rust

tech

はじめに

Algebraic Effects (and Handlers)は詳しくは例の如くDan Abramov氏の記事

やこちらの記事

を読んでいただくとして、大雑把に言うと「もとの場所に戻れる例外」で、戻らなくても良いし、また戻った後に何か動作させることもできるし、（multi-shotであれば）複数回もとの場所に戻ることもできます。非同期プログラミング、パーサー、自動微分、確率的プログラミングの応用があります。

今回はGeneratorを使い、RustでAlgebraic Effectsを簡易的に実装します。
Generatorは以下のライブラリを使います。

題材は以下のsum_linesを使います。

つまり、sum_lines("1\n2\nthree\n4\n5")のように改行区切りの文字列をパースして数値を足し合わせるが、変なもの(この場合はthree)が入っていた時の処理を(sum_lines関数は変更せずに)ハンドラで切り替えたい、というケースです。

実装

まず、Effectを定義します。

trait Effect {
    type Output;
}

struct NotAnInteger<'a>(&'a str);

impl Effect for NotAnInteger<'_> {
    type Output = usize;
}

これが変なものに当たった際に発生させるEffectです。
次に計算が終わった時に発生させるEffectを定義します。

struct Done(usize);

impl Effect for Done {
    type Output = usize;
}

こうして、sum_lines関数はNotAnIntegerとDoneの2つのEffectを発生させるわけですが、ここで問題があります。
Generatorでは何でもかんでもyieldできるわけではありません。Pythonの時は考えませんでしたが、今回yieldできる値の型は1つです。しかしyieldしたいEffectはNotAnIntegerとDoneの2つあります。
こういう時便利なのがCopropductです。
frunk crateのCopropductを使うと以下のようなことが可能になります。

// https://docs.rs/frunk/latest/frunk/coproduct/enum.Coproduct.html#examples-1
use frunk_core::Coprod;

type I32F32 = Coprod!(i32, f32);
type I32 = Coprod!(i32); // remainder after uninjecting f32
type F32 = Coprod!(f32); // remainder after uninjecting i32

let co1 = I32F32::inject(42f32);

// You can let type inference find the desired type.
let co1 = I32F32::inject(42f32);
let co1_as_i32: Result<i32, F32> = co1.uninject();
let co1_as_f32: Result<f32, I32> = co1.uninject();
assert_eq!(co1_as_i32, Err(F32::inject(42f32)));
assert_eq!(co1_as_f32, Ok(42f32));

早速これを使ってsum_lines関数を実装します。

fn sum_lines<'a>(s: &'a str) -> Generator<'static, usize, Coprod!(Done, NotAnInteger)> {
    Gn::new_scoped(|mut ss| {
        let lines = s.split('\n');
        let mut sum = 0;

        for line in lines {
            match line.parse::<usize>() {
                Ok(x) => sum += x,
                Err(_e) => sum += ss.yield_(Coproduct::inject(NotAnInteger(line))).unwrap(),
            }
        }

        Coproduct::inject(Done(sum))
    })
}

そうしたらハンドラを定義します。
まずはパースできないものがあったら0に置き換えて計算を続けてみます。その場合は以下です。

fn handle(
    mut co: Generator<'static, usize, Coprod!(Done, NotAnInteger)>,
    r: Coprod!(Done, NotAnInteger),
) -> usize {
    let v: Result<Done, _> = r.uninject();
    match v {
        Ok(v) => v.0,
        Err(_) => {
            let r = co.send(0);
            handle(co, r)
        }
    }
}

実行してみます。

fn main() {
    let mut co = sum_lines("1\n2\nthree\n4\n5");
    let r = co.resume().unwrap();
    let ans = handle(co, r);
    println!("{}", ans);
}

すると12が表示されます。
次にパースできないものに当たったら、それをErrで返すようにしてみます。

fn handle(
    _: Generator<'static, usize, Coprod!(Done, NotAnInteger)>,
    r: Coprod!(Done, NotAnInteger),
) -> Result<usize, String> {
    let v: Result<Done, _> = r.uninject();
    match v {
        Ok(v) => Ok(v.0),
        Err(v) => {
            let word = v.extract();
            Err("Parse Error: ".to_owned() + word.0)
        }
    }
}

実行してみます。

fn main() {
    let mut co = sum_lines("1\n2\nthree\n4\n5");
    let r = co.resume().unwrap();
    let ans = handle(co, r);
    println!("{:?}", ans);
}

するとErr("Parse Error: three")と出ます。このように、sum_lines関数を変更せずに挙動を変更できました。

おわりに

今回の実装はまだ簡易的なもの（特にresendがない）ですが、RustでAlgebraic Effectsをやりたい方のお役に立てれば幸いです。

はじめに

実装

おわりに

Discussion