Algebraic Effects 自習用資料まとめ
Web記事、論文、発表資料、コード、言語など
最高のリポジトリ
Effects bibliography: https://github.com/yallop/effects-bibliography
もうこれだけあればいいんじゃないか?ってくらい言語実装と論文がまとまってる。あとは「OCaml Weekly News」とかにEffect関連の発表とか論文が紹介されてたりする。ICFPもEffect関連増えてる。
論文
・An Introduction to Algebraic Effects and Handlers by Matija Pretnar
Effを作った人。Computational Effectsの導入にあたって、Effect Handlerを扱えるようなコンパクトな追加の言語仕様を定義してそれをもとに入出力とかState、ロギング、非決定性計算(バックトラック的なアレ)、トランザクションについて紹介していく構成。Operational Semanticsあたりからワケワカメだけど、前半は時間かけて読み解いていけば理解できる。よくわからなかったらEffで動かしてみればよい。
・Algebraic effects for Functional Programming by Daan Leijen
MS ResearchでKoka作った人。前半はAlgebraic Effectsについて概要を述べたあと、例外とかState、Async/Awaitみたいな既存機能をAlgebraic Effectsで再実装してみようね!系なんだけど、パーサコンビネーターをAlgebraic Effects使って実装するとどうなるのん?って感じのどう考えても楽しいやつで、ドメイン特化エフェクト(Domain Specific Effects)を定義して組んでいくのがハイライト。あとは型とか型推論とか、限定継続との関係についても触れてる。
・Handlers of Algebraic Effects by Gordon Plotkin and Matija Pretnar
(ほぼ)原典の論文。なので導入部分が丁寧。あと後続論文でしれっと使われてる用語とかもちゃんと説明が書いてある(理解したとは言ってない)。
・What is algebraic about algebraic effects and handlers? by Andrej Bauer
今戦ってる論文。勝てる気がしない。誰でも疑問に思う「代数的エフェクトの代数ってなんぞ」という気持ちに対して、数学を専門にしてない人向けに答えてくれるらしい。全然勝てる気がしない。これ理解したくて抽象代数学とか代数的構造とかの森に迷い込んだまま帰ってこれない。でも「矢澤にこ先輩といっしょに代数!」がわかりやすくて生きる気力が湧いた。
記事
・Effective Concurrency with Algebraic Effects by KC Sivaramakrishnan
なぜAlgebraic Effectsが必要なのか?が最初に書かれているので好きな記事。Algebraic Effectsを学んでいるのは今後10年でマルチコア活かし切るためだし、他の可能性としてErlang VMみたいな大量プロセスさばけるランタイム+クラスタリングだと思っているのでCizen(解説記事、非同期オートマトンサンプル、チャットサンプル)を学んでいる。
・Algebraic Effectsとは? 出身は? 使い方は? その特徴とは? 調べてみました! by びしょ〜じょ / @nymphium
貴重な日本語での解説記事。これを読むとイメージがつかめると思う。
発表資料
・Dive into Algebraic Effects by びしょ〜じょ / @nymphium
わりと最近あった ML Day #2 での発表。非常にありがたい日本語資料。Algebraic Effectsと無関係だけど登壇された方が書いた記事「つくってかんたんVirtual Machine-based Interpreter」は面白い。「Dragon University 技術書典5」はBOOTHで買える。
言語
Algebraic Effectsを普通に使える言語は少ない。普段使っている言語ではだいたい使えない。でも、とっかかりとして挙動を理解するには実際に動かしてみるのが近道なので以下のいずれかで試してみた方がいい。
各言語共通して、テストコードを読むのが勉強になります。言語別に比べるのもおすすめ。
・Koka
実用に一番近い理想的なEffectを備えたやつ。JavaScriptライクな文法を備えた安定のMS Research製言語。言語名はまんま「効果」から来てる。なぜ実用的なのかというと、Node.js向けのバインディングを書くとなんでも使えちゃうから。唯一残念なのは(ファイル読み込み可能だけど)インタプリタしか提供されてない(ように見える)のでそこまで実用的ではないところ。でも夢が広がる。バインディングについてはまた記事書く。
・Eff
オンラインの実行環境で手軽に試せるのでおすすめ。論文読みながら動かしてみると楽しいです。ただ、あくまで実験的な言語なので、ネットワークなど高度な入出力機能がないのでわかりやすいサンプルを書くことはできなそう。
今そこにあるAlgebraic Effects。わりと昔にOCamlをForkしてマルチコア対応とEffect Systemを備えた実行環境をコツコツ開発しているリポジトリ。尊い。今年の6月に開発ミーティングがあったようで、来年あたりとかには本家にマージできるように準備を進めていくらしい。残念なのは現実的な時間軸で作業を進めるためにいったんマルチコアランタイムだけマージして、Effect部分はいったん切り離す方針みたい。それでも既存ライブラリの対応が必要なので一筋縄ではいかないだろうけど。あとMulticore OCamlが提供するAlgebraic Effectsではcontinuationがone-shotなのでEffとかKokaで書かれてるサンプルがそのまま動かないことがある。特に非決定性計算とかね。one-shotであるという特性を活かして、リソース管理に使ったり、みたいな使用例はあるみたいだけどやっぱりcontinuation何度も呼び出したい。でも今すぐに使えるからその魅力には抗えない。
コード
言語のセクションでも言ったとおり、言語実装のリポジトリにあるテストコード読むのがおすすめです。
・Concurrent Programming with Effect Handlers by Daniel Hillerström and KC Sivaramakrishnan
Multicore OCamlでやるならここが一番。レベル別に練習問題っぽくなってる。
・effect-handlers by slindley
いろんな言語でEffects Handlersのベンチマークを取ってる。「Handlers in Action」という論文のパフォーマンス検証で使ってるコード。
他の資料も教えて!
この記事は追記していきます。今パッとソース思い出せないやつがいくつもあるし、他にも興味深い資料はたくさんあると思うのでぜひコメントで教えてください。もちろん記事内容へのツッコミも大歓迎です。