JavaScript
algebra

Algebraic Effectsとは? 出身は? 使い方は? その特徴とは? 調べてみました!

ReactのHooksが実質algebraic effectsなんじゃないかということでalgebraic effectsに関する怪文書が流布して鼻白んでしまう、そんな未来を阻止するため、曲がりなりにもalgebraic effectsを研究している者としてalgebraic effectsについて書こうと思います。

当方React全く知らないしJSにも明るくない侍ですが、プログラム片にはJSっぽいシンタックスを使っていこうと思います。

イントロ

Algebraic Effectsとは、Plotkinらによって提唱された、computational effectsを代数的に扱おうという試みである。それにeffect handlerが後付けされ、現在はalgebraic effects and handlers を略してalgebraic effectsと呼んでいることが多い。非常に直感的な説明としては、継続を取ってこれる例外である。
チュートリアルとしては、こちらの論文1の内容に尽きるわけですが……。

algebraic effectsは、エフェクトの定義、発生、そしてハンドラに分かれる。

// effect invocation
effect Foo /* : int -> int */;

// handler
handle(console.log(perform/* invocation */ Foo(3) + 10)) {
    case x: {
       x;
    }

    case Foo(x), k: {
        k(x * x);
    }
}

//==> prints `19`

うそうそシンタックスですが大丈夫ですか?

Fooという名前のint -> intというシグネチャを持つエフェクトを定義します。JSは型がないので雰囲気出ないですが、一般にエフェクトは名前とシグネチャ(型)を持ちます。

エフェクトの発生はperform エフェクト(引数...)というシンタックスです。エフェクトの引数の型は、シグネチャの矢印->の左辺に対応します。ここではintの引数に3を渡してるので、確かに型は一致します。

ハンドラはhandle(exp){ case エフェクト(仮引数), 継続: {...}... }という感じ。exp内で発生したエフェクトをハンドルします。
例ではFooエフェクトが発生したので、case Foo(x), k: ...という部分でキャッチされます。x3が渡されそうですが、kとは一体…?
ここがalgebraic effectsのミソで、kには継続が渡されます。出、出〜www継続奴という感じですがJSerの皆さんにはおなじみのはずです。継続とは"残りの計算 "であり、Promiseでthenに渡してる関数はまさに継続といって差し支えありません。具体的にkに入るものは、この場合(h) => console.log(h + 10)となります。なるほど確かに残りの計算だ。
したがって、このハンドラによってconsole.log(perform Foo(3) + 10)console.log(3 * 3 + 10)となります。
限定継続が分かる方は、このhandle(exp){...}が継続のdelimiterといえばイメージが湧くかと思います。限定継続に関して一筆したためているので、詳細はこちらをご覧ください。

case x: x;は何やねんということですが、これはvalue handlerと呼ばれる部分です。今回はconsole.logの戻り値がvoidなので雰囲気出ませんが、exp部分が値になるまで評価されきったあとに、その値をハンドルする部分です。value handlerはエフェクトのハンドル部分と異なり継続を取りません。

かなり雰囲気はつかめたんじゃないでしょうか。

特徴

algebraic effectsの特徴としては、

  • エフェクトの抽象化, 実装の分離
  • コントロール操作

が挙げられる。

エフェクトの抽象化、実装の分離

エフェクトの抽象化はまさにalgebraic effectsのやりたいことである。エフェクトの抽象化は即ちインタフェースと実装を分離することになる。

effect Write /* : string -> void */;

// 標準出力に書き込む
const print_handler = (th) => {
    handle(th()){
        case x: x;
        case Write(str), k: {
            k(console.log(str));
        }
    }
}

// ファイルに書き込む
const write_file_handler = (file, th) => {
    handle(th()){
        case x: x;
        case Write(str), k: {
            fs.writeFile(file, str, k);
        }
    }
}


print_handler(() => {
    perform Write("Hello");
    perform Write("World");
});
// ==> prints `Hello\nWorld`

write_file_handler("hoge.txt", () => {
    perform Write("Hello");
    perform Write("World");
});
// ==> write "Hello" and "World" to hoge.txt

なるほどね。

ハンドラの変更がそのまま実装の差し替えになる。例えばDI注入にも使えるのではないだろうか。
例えばなにかの顧客DBを取ってくるエフェクトGetAccountListを考えてみる。filterは述語pを取ってDBをフィルタする関数であり、内部でGetAccountListエフェクトを発生している。

effect GetAccountList /* : void -> DB */;

const filter = (p) => {
    const list = perform GetAccountList();
    list.filter(p);
}

例えばテスト用DBのためのハンドラは

const test_handler = (th) => {
    handle(th()){
        case x: x;
        case GetAccountList(), k: {
            k(db_for_test());
        }
    }
}

また本番のDBを返すハンドラは

const production_handler = (th) => {
    handle(th()){
        case x: x;
        case GetAccountList(), k: {
            k(db_for_production());
        }
    }
}

あとは実際にfilter関数を使うシチュエーションごとにハンドラを変えればいい。

const test_main = () => {
    ......
    const filtered_accounts = filter(p);
    ......
}

assert(test_handler(test_main))

ハンドラの合成

エフェクトハンドラは例外ハンドラと同様に、unhandledなエフェクトはより上位のハンドラに捕捉されます(あるいはされずにランタイムエラー)。この性質を利用することでハンドラを合成することができます。
先程のWriteを引っ張ってみます。

effect Write /* : string -> void */;

// 標準出力に書き込む
const print_handler = (th) => {
    handle(th()){
        case x: x;
        case Write(str), k: {
            k(console.log(str));
        }
    }
}

// ファイルに書き込む
const write_file_handler = (file, th) => {
    handle(th()){
        case x: x;
        case Write(str), k: {
            fs.writeFile(file, str, k);
        }
    }
}

WriteがあるならReadもしたいのが人間の性です。

effect Read /* : void -> string */;

そしてやるだけ。

const scan_handler = (th) => {
    handle(th()){
        case x: x;
        case Read(), k: {
            k(readline())
        }
    }
}

const scan_file_handler = (file, th) => {
    handle(th()){
        case x: x;
        case Read(), k: {
            readFileAsync(file, k);
        }
    }
}

標準入出力とファイルの入出力をごっちゃにするシーンはあまり多くないので1つのハンドラにしたいと思います。せっかくハンドラをそれぞれ書いたのでこれを使ってみます。

const stdio_handler = (th) => {
    print_handler(() => scan_handler(th));
}

const fileio_handler = (file, th) => {
    write_file_handler(file, () => scan_file_handler(file, th));
}

オッええやん。stdio_handlerの受け取るサンクの中でWriteが発生した場合、scan_handlerを突き抜けてprint_handlerによりハンドルされます。これが合成だ、花京院。
もちろんいちどきに一つのハンドラも実装できます。

const stdio = (th) => {
    handle(th()){
        case x: x;

        case Write(str), k: {
            k(console.log(str));
        }

        case Read(), k: {
            k(readline())
        }
    }
}

// fileも同様に(略)

また、同じエフェクトのハンドラをネストすることで、部分的に実装を変えることができる。

fileio_handler(file, () => {
    perform Write("hoge");  // fileに"hoge"を書き込む
    let str = perform Read();  // fileから読む
    print_handler(() => perform Write(str));  // *標準出力に*書き込む
})

同じWritefileio_handler内で発生させているが、2つ目のWriteはさらにprint_handlerに包んで発生させている。このエフェクトの発生を最初に捕捉するハンドラはprint_handlerになるため、strはファイルではなく標準出力に書き込まれる。

ちなみに、サンク1行目のWriteがハンドラによって捕捉されるので、2行目以降はハンドラ内の継続として実行されます。2行目のReadもしっかりfileio_handlerにより捕捉されるが、これはつまり継続もfileio_handlerによりハンドルされていることになる。このように継続も追随してハンドルしてくれるハンドラをdeep handler、明示的に継続をハンドルしないといけないハンドラはshallow handlerと呼ばれる。deep handlerのほうが一般的だが、shallow handlerのほうが動作が軽量(のはず)である。

コントロール操作

継続を取ってこれるのが例外処理と決定的に異なる。このおかげで例外の発生から復帰することができる2
また継続はハンドラ側でよしなにしてくれるので、記述自体は直接形式で記述できる。このためcallback hellが解消される。例えばscan_file_handler関数はまさにコールバックを取る関数をラップすることで直接形式にしている。

簡単のため、ファイル名と文字列を受け取るエフェクトWriteToFileを定義して様子を見る。

effect WriteToFile /* : (string, string) -> void */;

handle((() => {
    ......
    perform WriteToFile(file, "hogehoge");
    ......
})()){
    case x: x;
    case WriteToFile(file, str), k: {
        writeFile(file, str, k);
    }
}

なるほど確かに、ファイルに書き込んで残りの処理はコールバックにやらせるwriteFileをラップして、見かけ上は直接形式で記述することに成功している。

継続が取ってこれるので、2にあるように、async/awaitをalgebraic effectsで実装することができる!!
これはコントロールオペレータのヒエラルキーとしてalgebraic effectsがasync/awaitと等価、またはそれ以上の表現力であることを示唆しています。
実際algebraic effectsはあるがasync/awaitのない言語ではうれしい…のかもしれません。

Algebraic Effectsのある言語や実装

algebraic effectsにはいくつか実装が存在する。たとえば言語機能にalgebraic effectsを組み込んだ言語、あるいはライブラリ。フレームワークを自称しつつ実際は言語を拡張しているReactなど。

  • Eff

    algebraic effectsの計算モデルとしてよく使われる言語。MLスタイルのシンタックスでHindley-Milner型推論がある。

    • matijapretnar/eff

      OCaml製Effインタプリタ。エフェクトが単相なのが惜しい以外はopamで簡単に導入できてシンタックスもOCamlに毛が生えた感じで様々な面でコストが低い。

    • atnos-org/eff

      ScalaのDSL実装

    • 『Eff Directly in OCaml』3

      OCaml+delimccライブラリによるEffの実装。shift/resetとalgebraic effectsの関係が分かる。
      この論文を元に、Racketによる実装をおこなってみた。

  • Koka4

    Microsoft Researchが作っている言語。エフェクトの型が明示されておりモナドみがある。

    • koka-lang/koka

      Haskell製。ランタイムにJSまたはC#にコンパイルされて実行される。
      stackによるビルドをできるようにしたのでぜひ使ってください。

  • Multicore OCaml

    OCamlにalgebraic effectsをぶっこんだOCaml方言。継続がワンショットなことが特徴となっている。

他にもC言語による実装5などがあり、確かにコールスタックなどをバコッといければなんとかなりそう。


  1. Pretnar, Matija. "An introduction to algebraic effects and handlers. invited tutorial paper." Electronic Notes in Theoretical Computer Science 319 (2015): 19-35. 

  2. Dolan, Stephen, et al. "Concurrent system programming with effect handlers." International Symposium on Trends in Functional Programming. Springer, Cham, 2017. 

  3. Oleg Kiselyov, K. C. Sivaramakrishnan. "Eff directly in OCaml." ML Workshop. 2016. 

  4. Leijen, Daan. "Algebraic Effects for Functional Programming. Technical Report." 15 pages. https://www.microsoft.com/en-us/research/publication/algebraic-effects-for-functional-programming, 2016. 

  5. Leijen, Daan. "Implementing Algebraic Effects in C." Asian Symposium on Programming Languages and Systems. Springer, Cham, 2017.