1. はじめに

最近のエフェクトシステム2大ホットトピックといえばAlgebraic EffectsとExtensible Effectsだろう [要出典]｡

度々この2つの違いは何なのかという質問を見ます｡

比較というわけでも無いんですが､今回はこの2つを並べて見比べてみましょう｡

そいうえばだいぶ前の発表でこんなこと言ってましたけど

こんなこと

図1.1. 雑な比較

本当かしら

2. Algebraic Effects and Handlers

PlotkinとPowerによりもたらされた､計算エフェクトを代数的に表現するという考え方[1]に､PlotkinとPretnarがハンドラを追加したもの[2]である｡

詳細はカツアイしますんで､本ブログをご巡回ください｡ 簡単にまとめると､

  • 新たな言語機能
    • エフェクト(仕様)とハンドラ(実装)が分離できるモジュラーな手法
    • エフェクトシステムによって計算中にどのようなエフェクトが現れるのかが分かる
  • shallow/deep handler, set/row-based effect system, polymorphic/parameterized effects など様々なヴァリアントがある｡
  • 言語プリミティブやライブラリ実装がある
    • 【余談】しばしば型(エフェクト)システムについてはないがしろにされがちな印象がある｡ たまに見る擬似コードにはvalue handlerがなく､議論すらされていない｡ computationの結果の型を調整したりするための重要なclauseなのに……｡ まあ入門用にはそんなに必要な概念ではないかもしれない｡ ボクも簡単な説明のときには省略することがある｡
Kokaの例
effect reader<a> {
  fun ask() : a
}

// `e` は起きうる他のエフェクト(の列)
fun run<s, a, e>(v : s, th : () -> <reader<s> | e> a) : e a {
  handle(th) {
    ask() -> v . resume()
  }
}

fun main() : console () {
  run("hello, ") {
    val e = ask()
    // print : string -> console ()
    // なので↑のエフェクト列変数 `e` は `<console>` にinstantiateされる
    print(e + "world")
  }
}

3. Extensible Effects

Kiselyovらにより考案された､Monad Transformerに代わるエフェクトをガチャガチャやる方法である[3]｡ 論文を読むと分かるとおり､こちらは計算体系のようなコンセプトではなく､いい感じのライブラリの実装手法である｡

耳タコだと思いますが､簡単に言うと､Freeモナドのお手軽monadic interpreter作成機能にOpen Unionで型安全に拡張性をゲット(のちにFreerとかTASeqが盛られて早くなったり)という感じです｡

筆者はあまり詳しくないんですがまとめてみるとこんな所感

  • モナドトランスフォーマーに代わる新たなモナドの合成手法
    • lift地獄やインスタンス大量生成地獄からの解放
    • Free(-er)モナド+Open Unionを使って1つのモナドに拡張的に押し込む
  • リッチな型システムを利用している
    • HaskellとScalaのライブラリ実装が活発ですね
    • むしろ他に実装できる言語あるんかいな

Unionを二分探索したりするのはまあいいかな､ハンドラのあたりをちょっと論文から引用します｡ Eff e wというのがエフェクトeが発生しうるw型の値です｡

Fig3.1. run
run :: Eff Void w -> w
run m = case admin m of Pure x -> x

プログラム3.1はVoidエフェクトが発生する(つまりエフェクトが発生しない)値からコンストラクタを剥がす操作です｡ adminは論文のターミノロジーを使えば､コルーチンをグルグル走らせて最終的な結果まで実行する関数です｡

続いて Readerエフェクトを追加してみましょう(図3.2)｡

Fig3.2. Readerエフェクト
newtype Reader e v = Reader (e -> v)
                     deriving (Typeable, Functor)

ask :: (Typeable e, Member (Reader e) r) => Eff r e
ask = send (inj . Reader)

----

handle_relay :: Typeable t => Union (t :> r) v -> (v -> Eff r a) -> (t v -> Eff r a) -> Eff r a
handle_relay u loop h =
             case decomp u of
               Right x -> h x
               Left u  -> send (`fmap` u) >>= loop

runReader :: Typeable e => Eff (Reader e :> r) w -> e -> Eff r w
runReader m e = loop (admin m) where
    loop (Val x) = return x
    loop (E u) =
        handle_relay u loop (\(Reader k) -> loop (k e))

まず Reader エフェクトを定義します｡ e -> v というのは継続と読めばいいのかしら｡ e型のholeがあるので､Readerっぽく何かe型の値を毎度渡していって最終的にv型の値が戻ってきます｡

askがスマコンというかエフェクトが発生する項です｡ sendでReaderエフェクトをハンドラまで飛ばします｡

ハンドラはrunReaderがハンドラです｡ admin mでコルーチンを回しまくって度々suspendされるのをloop関数で拾う､という流れです｡ ValとEというのが､内部で使われているFreeのようなデータ構造です｡Eはなにかエフェクトが発生したときで､handle_relayでuが分解されて第2引数か第3引数に分解された値が渡されていきます｡ 補助関数handle_relayに味があって4､エフェクトをハンドルしたいけどハンドルできないエフェクトだったときに適宜上位のハンドラに再送してくれる奴です｡ このへんでTypeableとかがガチャガチャやって､Readerエフェクトだったときにdecomp uがRightを返すようになっていい感じにハンドルされます｡

こんな感じでエフェクトごとのハンドラ関数を定義していって､関数合成で様々をハンドルする関数を作ります｡

-- あんま自信ない､雰囲気ね雰囲気
run :: Eff (Reader Int :> Exc String :> Void) a -> Either String a
run = run . runExc . runReader 42

このハンドラにReaderエフェクトとExcエフェクトだけが発生する項を渡すと､これらエフェクトをいい感じに処理してくれて最終的にEither String aが出てくる｡

result :: Either String Int
result = run $ do
  v <- ask
  if v < 10 then
    throwError "the env should return the value more than 10"
  else
    return 3 + v -- 45

4. 二者の違い

ご覧の通り全然違うと思うんですが､では逆に 実現可能そうなこと はだいたい同じにみえます｡

いずれもエフェクトを定義してから､ハンドラを別途定義して意味を与えています｡

このことはいずれもFree(-er)モナドを利用した実装方法がある(Extensible EffectsはむしろFreeが必須ですが)ことからも感じ取れると思います｡

というかそこ以外は全部違うんじゃないかしら Iが違う 星が違う 違うだろ すべてが

4-1. 概念的な違い

Algebraic Effects (and Handlers)はMoggiの提唱した$\lambda_{c}$よりもいい感じに計算エフェクトを扱うための概念として考えられた｡

一方Extensible EffectsはMonad Transformerに代わるモナドの合成方法として提案された実装手法である｡

  • Algebraic Effectsは概念
    • 概念なのでライブラリや言語組み込みの機能として考えることができる
  • Extensible Effectsは実装手法
    • ライブラリとしての実装方法にアイデンティティを持つので､言語組み込みの機能みたいなことはそもそも考えられない

4-2. 実装の違い

Extensible EffectsにはFreeが必須でした｡ ではAlgebraic Effectsの実装はどうかというと色々考えられます｡

詳細はこちらに!!!!(隙あらば我田引水)
How do you implement Algebraic Effects? - lilyum ensemble
lily, Aikatsu, Programming language, and more
  • Algebraic EFfectsは実装が色々考えられる
  • Extensible EffectsはFreeとOpen Unionを使った実装方法しかない
    • そもそもFreeとOpen Unionを使った実装方法を指してExtensible Effectsと呼んでるので……

4-3. その他

Algebraic Effectsはエフェクトハンドラおよびvalue handlerを1つのハンドラオブジェクトとして定義できる｡ 一方Extensible Effectsはそれぞれのエフェクトにたいして関数を定義し､関数合成で1つにまとめる｡ 前者は各エフェクトが協調するようなハンドラを書きやすい｡ 一方後者はハンドラをよりモジュラーに定義できる｡

他にもいろいろありそうだが､本日はこの辺で……｡

5. おわりに

Extensible Effectsは必須のデータ構造があるので､図1.1はまあなんとなくあたってるようなそうでもないような……｡ ま､ユーザにとっちゃああんま関係ねえ話にゃんですが……(おわり)

  1. Plotkin, Gordon, and John Power. "Adequacy for algebraic effects." International Conference on Foundations of Software Science and Computation Structures. Springer, Berlin, Heidelberg, 2001. ↩

  2. Plotkin, Gordon, and Matija Pretnar. "Handlers of algebraic effects." European Symposium on Programming. Springer, Berlin, Heidelberg, 2009. ↩

  3. Kiselyov, Oleg, Amr Sabry, and Cameron Swords. "Extensible effects: an alternative to monad transformers." ACM SIGPLAN Notices 48.12 (2013): 59-70. ↩

  4. なんでこの関数だけキャメルケースなんだろう｡写経してるときにhlintにも怒られた｡ ↩