1. はじめに

Algebraic effectsとは､2001年くらいに提唱されてから､爆流行らずともにわかに盛り上がりを見せつつある言語機能である｡極めて雑に説明すると､継続を取ってこれる例外である｡ Plotkin氏(またお前か)が代数学的アプローチによる基盤を作り､そこにハンドラが付いてプログラム言語の機能として考えられるようになった｡ボクの話のうち1〜10割間違っていることは確かなので､誤った情報を一切入れたくない人は[1]を読んでください｡

1-1. algebraic effects実装の有名どころ

Eff

algebraic effectsを言語機能として初めて設計された言語｡ MLスタイルのシンタックスでHindley-Milner型推論がある｡
- impls
  - matijapretnar/eff
    
    OCaml製Effのインタープリタ
  - athnos-org/eff
    
    ScalaのDSLとして実装されている
  - 『Eff Directly in OCaml』[2]
    
    Oleg氏(またお前か)によるEffを､delimited continuationライブラリを使ってOCamlのDSLとして実装したもの｡ Effはdelimited continuationをエミュレートできるが､実はEff を delimited continuationでエミュレートできることがわかる｡
Koka

MS Researchがやっていってる言語｡手続き型っぽいシンタックスと､Row-typesというeffectsが型に滲み出る､さながらモナドみがある型システムを持っている｡
multicoreOCaml

OCamlに直接algebraic effects & handlerを追加した方言｡ continuationがoneshotとなっており､明示的にクローンしないと2回使えない｡この"2回使えない"はlinear typeを導入して弾いてほしいが､実際はランタイムエラーである｡

2. さっそく試す

algebraic effects界隈ではスタンダードなEff言語を例に見てみる｡

(* effect definition *)
effect Eff : int -> int

let _ =
  handle 3 + perform(* invoke *) (Eff 4) with
  | x -> print_int x (* value handler *)
  | effect (Eff x) k (* continuation *) -> print_int x; k x

これを実行すると､47という表示が得られる｡どういうことなんや｡素直な心を使うと､(+)はint -> int -> int､3 + perform (Eff 4)はint､perform (Eff 4)もintということが考えられる｡なるほどEffのシグネチャint -> intは､矢印の左辺がeffectの引数､右辺はcontextのholeの型か｡ performは何??? ……じゃあEffはint -> int effということにしてperformは'a eff -> 'aでどうだ､これでいいだろう!!! という感じで推理していくと4という表示はeffect (Eff x) k -> print_int x; k xという箇所で発射されたんじゃないかという感じがある｡ 7はx -> print_int xですね｡前回の記事を読んでもらえると分かるが､handle e with (handlers)がdelimiterで kが切り取られた継続になる｡だいたいそう｡

わかった｡念のため他の例も見ておこう｡

effect Choose : ('a * 'a) -> 'a

let choose (x, y) = perform (Choose (x, y))

let chooseh f =
  handle f () with
  | x -> x
  | effect (Choose (x, y)) k -> k x; k y

let f () =
  let x = choose (3, 5) in
  print_int x;
  let y = choose (10, 20) in
  print_int y

let _ = chooseh f

3102051020という表示になる｡継続を複製してる感ありますね｡

同じChoose effectでも型さえ合ってれば異なる処理が書ける､つまり定義と実装を分けることができるのが特徴となっている｡ここでHaskellerは｢Freeモナドやんけ!｣となるらしいですがボクはHaskellをやっていってないのでわかりませんでした｡型だけ定義して､interpretationはユーザに任せるということなので確かに同じようだ｡そもそもalgebraic effectのalgebraicは"free algebra"から来てるそう³なので､袂を分かつ存在である｡実際EffインタプリタはFreeモナドを使って実装しているようだ｡

そしていろんなeffectsをいっぺんにハンドルするぜ!

let h = handler
  | x -> x
  | effect (Eff i) k -> k i
  | effect (Choose (x, y)) k -> k x

手軽だ｡ HaskellではFreeモナドを発展させたextensible effects[4][5]といったものが流行っているそうで､確かにモナドトランスフォーマーガン積みして爆重になるという困難から抜け出せるらしい｡

3. 応用

delimited continuationが扱えるうえにCPS的な書き方ではなくdirect-styleで記述できるため､ syntacticにきれいに､バグらず簡単に書ける､というありがたみがある｡ボクの語彙が少ないので詳細は文献[6][7]を読んでください｡

4. おわりに

また情報量が0になってしまった……!!!

追記20181030

ReactにHooksという機能が追加されたがこれはまさにAlgebraic Effectsということで､ReactはさておきAlgebraic Effectsに関してもう少し実例を交えて詳しいものをQiitaに発射した｡

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

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

追記おわり

Matija Prentar. "An Introduction to Algebraic Effects and Handlers." Electronic Notes in Theoretical Computer Science 319. 2015. ↩
Oleg Kiselyov, K. C. Sivaramakrishnan. "Eff directly in OCaml." ML Workshop. 2016. ↩
Andrej Bauer. "What is algebraic about algebraic effects and handlers?." eprint arXiv:1807.05923. 2018. ↩
快速のExtensible effects -- モナドとわたしとコモナド https://fumieval.hatenablog.com/entry/2017/08/02/230422 ↩
Oleg Kiselyov, Amr Sabry, Cameron Swords. "Extensible Effeects: An Alternative to Monad Transformers." ACM SIGPLAN Notices. Vol. 48. No. 12. ACM, 2013. ↩
Anderj Bauer, Matija Prentar. "Programming with algebraic effects and handlers." Journal of Logical and Algebraic Methods in Programming, 84(1), pp.108-123. ↩
Dolan, Stephen, Spiros Eliopoulos, Daniel Hillerström, Anil Madhavapeddy, K. C. Sivaramakrishnan, Leo White. "Concurrent system programming with effect handlers." International Symposium on Trends in Functional Programming, pp. 98-117. Springer, Cham, 2017. ↩