OCaml 5.0のEffect HandlersでComposable Interpreter
前回のコードをベースに「任意のExtensionハンドラを変更なしで組み合わせて作る」Composable Interpreterを実装する。
問題
前回のコードの何がComposabilityを阻害していたかというとインタプリタを拡張するハンドラが、拡張前のインタプリタ関数を使っている点だ。
例えばhandler2を見ると：
let rec handler2 : 'a. 'a D.effect_handler = { D.effc = fun (type b) (eff : b Effect.t) -> match eff with | Extension (Mul(e1,e2)) -> Some (fun (k: (b,_) D.continuation) -> let n1 = D.try_with eval1 e1 handler2 in let n2 = D.try_with eval1 e2 handler2 in D.continue k (n1 * n2)) | Extension (Div(e1,e2)) -> Some (fun (k: (b,_) D.continuation) -> let n1 = D.try_with eval1 e1 handler2 in let n2 = D.try_with eval1 e2 handler2 in D.continue k (n1 / n2)) | _ -> None }
MulとDivの両方でlet n1 = D.try_with eval1 e1 handler2といった形でeval1が使われている。これがあるかぎりhandler2はhandler1を使ったeval1に依存し、handler3はhandler2を使ったeval2に依存し、handler4は・・・とすべてのハンドラが他の何らかのハンドラに依存しあっていて、変更なしでは任意のハンドラを選択して組み合わせることができない。
そもそもなぜhandler2でlet n1 = D.try_with eval1 e1 handler2というコードが必要になるのか。Mul(e1,e2)のような項を評価するときにTree Walkingインタプリタなので部分項e1とe2を個別に評価してから組み合わせる処理になるからだ。そしてその部分項に関してもすべてのExtensionハンドラがかかった状態で評価しないといけない。エフェクトが発生してhandler2に捕捉された時点でhandler1とhandler2からは既に「抜けている」（handler3はまだかかっている）。だからこそD.try_with eval1 e1 handler2でhandler2とeval1に含まれるhandler1の両方を掛け直した形で部分項を評価しているわけだ。
前回のコードではExtensionハンドラが部分項の評価の時に「自分だけではなく、エフェクトスタックから自分より先にpopされたハンドラをすべてかけ直す」という責務を負っている。
この「項の評価の時にハンドラをすべてかける」という責務を分離できないだろうか？できる。そう、エフェクトならね。
Evaluateエフェクト
というわけで「ハンドラをすべてかけた状態で評価する」という処理を新たなエフェクトとして定義してしまう：
type _ Effect.t += | Extension : 'a expr -> 'a Effect.t | Evaluate : 'a expr -> 'a Effect.t
今まで見てきたExtensionエフェクトに加えてEvaluateエフェクトを追加。Evaluateはバリアントとして'a expr型の値（つまり項）を保持し、Evaluateエフェクトが処理されるとその限定継続に'a型の値が返される。
ヘルパ関数を作っておく：
let eval_effect e = Effect.perform (Evaluate e)
eval_effectだとエフェクト「を」評価しているともとれてややこしいが、「評価というエフェクトを発生させる」関数の意だ。
ExtensionハンドラからEvaluateエフェクトを使う
またしてもhandler2を例にとってみる：
let handler2 = { D.effc = fun (type b) (eff : b Effect.t) -> match eff with | Extension (Mul(e1,e2)) -> Some (fun (k: (b,_) D.continuation) -> let n1 = eval_effect e1 in let n2 = eval_effect e2 in D.continue k (n1 * n2)) | Extension (Div(e1,e2)) -> Some (fun (k: (b,_) D.continuation) -> let n1 = eval_effect e1 in let n2 = eval_effect e2 in D.continue k (n1 / n2)) | _ -> None }
let n1 = D.try_with eval1 e1 handler2がlet n1 = eval_effect e1になっている。eval1への依存だけでなく、自分自身をかける責務もeval_effectに移譲しているのがわかる。なのでhandler2が非再帰になり'a. 'a D.effect_handlerという明示的な多相型注釈が必要なくなった。
インタプリタを作る
これらExtensionハンドラを組み合わせ、Evaluateのハンドラを作成して、最終的なインタプリタを作り上げる。
まずExtensionハンドラの組み合わせ方：
let eval_base e = Effect.perform (Extension e) let eval1 e = D.try_with eval_base e handler1 let eval2 e = D.try_with eval1 e handler2 let eval3 e = D.try_with eval2 e handler3
Effect.perform (Extension e)するだけのものから順次ハンドラをtry_withで重ね掛けするように関数を作っていく。この部分の各行をみると前回のコードと変わらないように見えるが、しかしeval1とeval2の間にhandler2の定義を挟む必要がなくなったのは大きい。ハンドラの定義とインタプリタの組み上げが分離されていて、何ならハンドラはすべて別々のモジュールで定義されていても問題ない。またこのインタプリタの組み上げ部分はハンドラのリストに対するfold_leftとして書くことも可能だ。
これでできたeval3関数をEvaluateのハンドラに包んで最終的なインタプリタとする：
let eval e = let rec handler : 'a. 'a D.effect_handler = { D.effc = fun (type b) (eff : b Effect.t) -> match eff with | Evaluate e -> Some (fun (k: (b,_) D.continuation) -> D.continue k (D.try_with eval3 e handler)) | _ -> None } in D.try_with eval_effect e handler
Evaluateエフェクトを捕捉するhandlerはEvaluateで渡される項eに対してD.try_with eval3 e handlerと「自身を再帰的に含むすべてのハンドラをかけた上で評価（eval_baseの中のD.perform (Extension e)）する。まさに「すべてのハンドラをかけ直して評価」という責務を集中的に負うハンドラである。
最終的なインタプリタのeval関数はD.try_with eval_effect e handlerで、そのハンドラの影響下でD.perform (Evaluate e)する。
handlerはこのeval関数に依存しないので関数外に出してもいいのだが、他のハンドラと違ってeval以外で使うことはなさそうなのでこのままにしてある。
使ってみる
このeval関数を使うコードは以前と同様：
let _ = let e = Gt(Mul(Int 2, Int 3), Add(Int 2, Int 3)) in let handler = { D.effc = fun (type b) (eff : b Effect.t) -> match eff with | Extension _ -> failwith "Unknown syntax" | _ -> None } in let b = D.try_with eval e handler in print_endline @@ string_of_bool b
このコード自体は前回、前々回とほぼ同じ（eval3がevalになったくらい）。しかし実際に実行される流れはかなり違う。
- まず「ハンドラが存在しないExtension構文をすべて捕捉してエラーにするハンドラ」をかけた上でeval関数に項eが渡される
- eval関数で「自分自身と（eval3に含まれる）すべてのExtensionハンドラをかけるハンドラ」をかけた上でeval_effectする
- eval_effectでEvaluateエフェクトが発生し、eval内で定義された「すべてのハンドラをかけるハンドラ」に捕捉される
- 「すべてのハンドラをかけるハンドラ」がすべてのハンドラをかけた上でeval_baseに項eを渡す
- eval_baseでExtensionエフェクトが発生し、いずれかのExtensionハンドラに捕捉される（このテストケースの場合handler3に
Extension (Gt(e1, e2))が捕捉される）。この時点でそのExtensionハンドラより内部のハンドラは抜けてきていてかかっていない - 部分項を順次eval_effectに渡すとeval_effectでEvaluateエフェクトが発生し、残っていたすべてのExtensionハンドラ（ただし未定義構文を捕捉するcatch-all以外）を抜けて「すべてのハンドラをかけるハンドラ」に捕捉される（部分項がないIntやBoolなどの場合はそのままその値が結果となり、ステップ９に飛ぶ）
- 部分項e'に関して再帰的にステップ４から処理される。
- 必要な部分項が評価されたら、それらを組み合わせて項の評価結果とする
- 限定継続にその評価結果を渡す（部分項の場合はステップ６に戻る、全体の項の場合はそのままevalから返される）
といった処理になる。ややこしい。
一つの項だけに絞ると：
- ある項が評価されるときはまず必ずeval_effectでEvaluateエフェクトが発生する
- その結果、Extensionハンドラはすべて抜けてEvaluateハンドラに捕捉される
- Evaluateハンドラは自身を含むすべてのハンドラをかけ直した状態で項をeval_baseし、その結果Extensionエフェクトが発生する
- ExtensionエフェクトがいずれかのExtensionハンドラに捕捉されて処理される
という流れになっている。
前回までのコードでは「項の構文を扱えるハンドラが、自身と抜けてきたハンドラだけをかけ直す」という処理になっていたのが「項の構文を扱えるハンドラは上の方にいるEvaluateハンドラに投げてすべてのハンドラをかけ直してもらう」となっている。
雑考
面白いからやってみたが、このコードは実際どうなんだろうという気持ちが拭えない。
ハンドラスタックの上に飛んだり下に潜ったりで制御フローがかなり動き回っていて、これはライブラリで隠蔽されている分にはいいかもしれないが実際の開発で剥き出しで使うのはきつそう（Effect全体に言えることかもしれないが）。
このような項一つ一つですべてのハンドラを一旦抜けてかけ直して、とやっているのは効率面でどうなのかも気になる。まあtree walkingインタプリタをさらに抽象的な機構でextensible/composableにしている時点で効率をあれこれ言っても仕方ないところではあるが、effect handlerに対する知見としてもどれくらいのオーバーヘッドが加わるのか、今度調べてみたい。
Evaluateエフェクトを使わずにhandler2のeval1に対する依存をなくすやり方としてはhandler2をレコードを返す再帰関数にしてeval1を引数として取るようにするというものがある。こちらの方が素直で、多分OCamlではエフェクト・システム（エフェクト関連のエラーを静的に検出する型システムの拡張）が入るまでは実際のコードではEvaluateエフェクトを使わずhandlerの関数化で乗り切るのが推奨であろうとは思う。
今回の実装ではEvaluateハンドラは最上位に一つだけだったが、一つである必要はまったくない。極端なことを言えばすべてのExtensionハンドラの上に専用のEvaluateハンドラを入れてもいい。こうすると「項ごとにすべてのハンドラを抜けてかけて」という挙動から「ExtensionハンドラからEvaluateエフェクトが生じた時に必要なだけのハンドラがかけ直される」という挙動になる。ただしハンドラの総数は倍近くになるが・・・。
と否定的な考えをいろいろ述べたが、ハンドラの処理中に「すべてのハンドラをかけ直して実行する」処理のために別のエフェクトを用意する、というのはExtensible Interpreter以外でも使えるパターンなのでは？と期待している。
次回
次回はprint関数を作ることでeffect handlerによるExpression Problemの解決を見ていく。
