Algebraic Effects for Rust

Algebraic Effects for Rust

この記事はKCS Advent Calender 18日目の記事です！
Algebraic Effectsが最近話題ですね！自分は普段Rustというプログラミング言語を使っているのですが，残念ながら（？）Algebraic Effectsの言語レベルサポートはありません．無ければ作るとも言いますし，AEをサポートするライブラリを作ってみたので紹介します．

Algebraic Effectsとは？

自分も良く分かりません．教えてください．

「継続がとれる例外」らしいですね．

どうやって実装したの？

びしょ〜じょさんの記事によると，コルーチンを使うとAEの実装ができるようです．ちょうどRustにはasync/awaitサポートのためにコルーチンが今年入ったので，それを使えば実装できそうですね．詳しい実装方法は次のコミケ（30日日曜日です！）の冊子にこれから書く書いたのでそちらを参考にしてください！

はじめてのAlgebraic Effects

以下で登場するコードはhttps://github.com/pandaman64/hello-effからもダウンロードすることができます．

まずはRustを入手します．新しい機能を利用しているので（特にunsized_locals）最新のNightlyビルドが必要です．

$ rustup update
$ rustup toolchain install nightly

それが済んだら新しいプロジェクトを作りましょう．

$ cargo new hello-eff
$ cd hello-eff

Cargo.tomlのdependenciesに次の行を追加します．まだcrates.ioにはアップロードしていないのでGitHubのURLを書いています．

eff = { git = "https://github.com/pandaman64/effective-rust.git" }

それではmain.rsを下のように書いていきましょう．

#![feature(generators)]

use eff::*;

struct Hello;
impl Effect for Hello {
    type Output = String;
}

struct World;
impl Effect for World {
    type Output = String;
}

fn main() {
    let with_effect = eff! {
        let hello = perform!(Hello);
        let world = perform!(World);

        format!("{} {}!", hello, world);
    };

    run(with_effect, |x| println!("{}", x), handler! {
        H @ Hello[_] => {
            resume!("Hello".into());
        },
        W @ World[_] => {
            resume!("World".into());
        }
    });
}

これをcargo runで実行すると

Hello, World!

と表示されることでしょう．

これは一体何が起きているのでしょうか．
コードを一行一行見ていきましょう．

#![feature(generators)]

これは，このモジュールではジェネレータを使うという宣言です．ジェネレータとはコルーチンのRustでの名称です．Rustでは実験的な機能は明示的にオプトインしなければ使うことができません（feature gateと呼びます）．このライブラリはジェネレータをフルに活用しているので，この宣言が必要です．

use eff::*;

次の行はライブラリのインポートです．自分が書いたAEライブラリはeffという名前で公開されているので，eff::*と書くことによって後ろのeff!・handle・handler!といった関数・マクロをインポートします．

さて，この後に続くのがエフェクトの宣言です．

struct Hello;
impl Effect for Hello {
    type Output = String;
}

ここでは，Helloという名のエフェクトを宣言しています．effではエフェクトの宣言はEffectトレイトを実装することで行います．Effectトレイトの実装にはOutput型を指定する必要があり，Outputはこのエフェクトが解決したときにどの型の値になるかに相当します．

Worldの方も同様にエフェクトの宣言がされています．

それでは，main()の中を見ていきましょう．まずは以下の部分です．

let with_effect = eff! {
    let hello = perform!(Hello);
    let world = perform!(World);

    format!("{} {}!", hello, world);
};

ここでは，eff!マクロを使ってエフェクト付きの計算を定義しています．注意してほしいのは，この時点ではまだeff!内部の計算は実行されていないということです．eff!の中では，perform!を使ってエフェクトを発動することができます．perform!式の結果は上で紹介したEffectトレイトのOutput型となります．
今回の場合はどちらもStringですね．perform!によって取得した値はformatの行のように自由に使うことができます．

eff!で定義したエフェクト付きの計算はrun関数によって実行することができます．

run(with_effect, |x| println!("{}", x), handler! {
    H @ Hello[_] => {
        resume!("Hello".into());
    },
    W @ World[_] => {
        resume!("World".into());
    }
});

run関数は
1. エフェクト付き計算
2. value handler
3. effect handler

の3つを引数にとります．1のエフェクト付き計算は上で紹介したeff!マクロで作った値です．2のvalue handlerはeff!マクロ内の最終的な計算結果を受け取ってあれこれする関数です．今回は|x| println!("{}", x)と標準出力にプリントしてますが，そのままの値が欲しい場合は|x| xとすれば良いでしょう．3のeffect handlerにエフェクトに応じて処理を行うコードを記述します．

effect handlerはhandler!マクロにハンドラを並べることで定義します．一つ一つのハンドラは

ユニークな識別子 @ エフェクトの型 [ パターン ] => 式

という文法で記述します．ハンドラを複数書くときは，カンマで区切って書きます（実装をサボっているので末尾カンマは許容されません）．

エフェクトの型によってこのハンドラがどのエフェクトをハンドルするのかを指定し，ハンドルした結果が式となります．perform!に渡されたエフェクトはパターンによって束縛されます．今回の例ではHelloやWorldといったエフェクトの型が重要で，値自体は不要なので_パターンによって捨てています．ユニークな識別子は実装上の都合（Rustのマクロは識別子を生成できない）で必要です．handler!内でユニークになるよう名前をつけてください．

さて，ハンドル結果の式について見ていきましょう．ここには任意の式を書くことができますが，その中でも特別に扱われるのがresume!マクロです．resume!(式)はエフェクトの発動時点(perform!の時点)から処理を再開します．このとき，perform!の結果はresume!に渡した引数に評価されます．ですので，resume!に渡す式は対応するエフェクトのOutput型の値でなければいけません．これによって，例えば実装の分離ができることでしょう．

ハンドラ内でresume!を行わない場合は，ハンドラの式の結果がrun関数の結果となります．これを使えば，例外のような大域脱出が実装できます．

また，effライブラリはハンドラのexhaustiveness checkを行います．つまり，ハンドラがエフェクト全てを網羅しているかをチェックします．試しに上のコードからWorldのハンドラを削除するとコンパイルエラーとなることでしょう（マクロの内部でエラーが発生するのでエラー自体は読んでも意味が分からないと思います．．．）．

引数をとるエフェクト

エフェクトは引数をとることができます．どうするのかというと，Effectトレイトを実装する型にフィールドを加えるだけです．上のサンプルに下のエフェクト型を追加しましょう．

struct Ask {
    prompt: String
}
impl Effect for Ask {
    type Output = String;
}

次に，eff!部分を下のように置き換えます．Worldエフェクトの代わりにAskエフェクトをperform!するようにしました．

let with_effect = eff! {
    let hello = perform!(Hello);
    let name = perform!(Ask {
        prompt: "What's your name?".into()
    });

    format!("{} {}!", hello, name)
};

さて，扱うエフェクトの型が変わったのでハンドラも書き換えなければいけません．ここでは次のようにしました．

use std::io::{stdin, stdout, Write};
let stdin = stdin();
run(with_effect, |x| println!("{}", x), handler! {
    H @ Hello[_] => {
        resume!("Hello".into());
    },
    A @ Ask[Ask { prompt }] => {
        print!("{} ", prompt);
        stdout().flush().unwrap();

        let mut name = String::new();
        match stdin.read_line(&mut name) {
            Ok(_) => resume!(name.trim().into()),
            Err(_) => eprintln!("failed to read"),
        }
    }
});

Worldのハンドラの代わりにAskのハンドラが追加されています．Askハンドラではpromptをエフェクトから取り出した後（ここで構造体パターンが使われていることに注意），それを表示しユーザからの入力を待ちます．入力が成功した場合には，resume!によって処理を戻します（trimは末尾の改行文字を除くためです）．失敗した場合にはfailed to readと標準エラーに出力して終了します．こっそりstdinをハンドラ外の環境から引っ張ってきているのにも注目してください．

error: recursion limit reached while expanding the macro

というエラーが出た場合には#![recursion_limit="128"]という行を先頭に追加してください．

制約

  • ジェネリックなハンドラ．実装上の都合でジェネリックなハンドラが宣言できません．特に不便な点は，ハンドラで参照をとることができません（参照のライフタイムが宣言できないため）．
  • その他にもライフタイムの不必要な'static制約がいくつかあります．困ったときはとりあえず参照を使うのをやめてください．
    –eff!のネスト．実装のアイデアはあるのでもう少しお待ちください．
  • エフェクトのうち一部だけハンドルするハンドラ．exhaustivenessとこれを両立する実装を考えているところです．型レベル黒魔術が必要かも？

以上，Rust向けAlgebraic Effectsライブラリeffの紹介でした．自分自身良くわからないままやっているので，もっと良くなるところもあると思います．質問・意見等々ある人はhttps://github.com/pandaman64/effective-rustにIssueを立てるかTwitterで@__pandaman64__までぜひメンションを飛ばしてください！

再度の宣伝ですが，KCSはC95の二日目（30日）に同人誌を頒布予定です！
自分もそちらにこのライブラリの仕組みを解説する記事を寄稿しているのでぜひそちらもご覧ください．

Posted on: 2018年12月18日, by :