Arantium Maestum

プログラミング、囲碁、読書の話題

mapの表現力

最近考えるきっかけがあったので書いておく。

一般的にmapやfoldは再帰を使って実装でき、そして再帰に比べて制約がかかっていて表現力が落ちるとされている。むしろその制約があるからこそそのコードの「何をしたくて何をしないか」という意図が明確になるところが好ましい、と。

しかしこの制約はOCamlのような多機能な言語においては「お作法」的な了解によって成り立っていることであり、mapによる繰り返し作用を他の機能と組み合わせて任意のループ的な処理を実装することができる。

その一例:

exception Done
let x = ref 0
let rec ys = 0::ys
let f _ = if !x < 10 then (print_int !x; incr x) else raise Done
let _ = try List.map f ys with
  Done -> [print_endline @@ string_of_int !x]

状態xと無限リストysと例外による制御フローraise Doneを使っている。

当然ながら処理のキモはmapに渡す関数:

let f _ = if !x < 10 then (print_int !x; incr x) else raise Done

まずポイントになるのは、let f _と引数を無視していること。mapする対象のリストysはlet rec ys = 0::ysと無限に0が続くだけなので、あくまで「必要とあれば無限ループする」ためだけに使っている。

ループで破壊的変更される状態xに対して!x < 10とチェックし、条件が満たされていなければ値を出力してから破壊的にインクリメント。条件が満たされている場合例外Doneを投げることでmap全体の処理から脱出する。この脱出の部分は例外だけじゃなくて継続なり限定継続なりalgebraic effectsなりでももちろん可。

このコードの大まかな形を維持したまま、破壊的に更新していく状態などを複雑にしていけば任意のループが表現できることは想像に難くないと思う。相互再帰的なものであっても、状態にフラグを追加してそのフラグに応じて分岐するようにすればいい。

「mapが再帰に比べて表現力が落ちる」というのは「mapに渡す関数の中で発生しうるエフェクトに意図的に制限をかける」というプログラマ側の作法を前提としたものだと言える。あるいは「純粋関数型なプログラミングにおいて、モナドなどによるエフェクトを持たないmapは再帰に比べて表現力が落ちる」とするのも正確だろう。

このような作法上の制約は実際強固なので、「純粋関数を渡したmap」が再帰に比べて意図をはっきりと表明する効果があるのは間違いない。何がその意図表明を担保しているのかについて自覚的であるのは有用だろう。

『「作ってかんたんAlgebraic Effects」をRustに移植した』を読んだ

ツイッターでalgebraic effectsについての話題を探していたら以下の記事を見つけた:

zenn.dev

Haskellで書かれた「Algebraic Effectsのある処理系の作り方」のRust移植だ。@Nymphiumさんの書かれた元の記事はこちら:

nymphium.github.io

この記事は出た時に拝見したのだが、その頃は私はalgebraic effectsについて何もわかっていなかった。今回両記事を読んで大変面白かったのでつらつらと考えたことを書いていく。

まずAlgebraic Effectsの実装に関しては、型システムなしだと基本的に限定継続の実装ができればほぼ完了な印象だ。限定継続とalgebraic effectsは互いにmacro-expressibleであるという研究があるので当然とも言える。(ついでに言うと同研究ではalgebraic effectsと限定継続はtypeabilityを維持した変換はないという結果も出ている)

限定継続のある(そして静的型付けのない)インタプリタの実装に関しては以前kontlangという処理系を作る話を長々と書いた。これを少し修正すればOCaml版のλeffが作れそう。

algebraic effectを使ったサンプルコードがこちら:

let double = inst () in 
let h = handler double (val x -> x) ((x, k) -> k (k x)) in 
with h handle (perform double 3) + 10

限定継続kを2回使っているのがわかる:k (k x)。これはOCaml 5.0で実装されたeffect handlerではできない。なぜなら限定継続がone-shotだから。

github.com

Didier: some people may want to experiment with multishot continuations. Could they do it now, or could they do it on top of existing continuations? Could the runtime provide low-level support, where people are on their own?

Leo: if you add a duplication function for continuations, it's impossible to use correctly and safely. (Optimizing local "let" into stack variables is broken.) I think this is much better done the Oleg way, by writing low-level C code.

Stephen: the semantics issue is, there is no way in general how much you want to copy.

とのこと。

discuss.ocaml.org

のスレでもいろいろとmulti-shotができなくなったことについてコメントがきている。このスレで挙げられているmulti-shot continuationのライブラリ

github.com

にもstackにアロケートするコンパイラ最適化がおかしくなるという話が書いてあった。

それはさておきサンプルコードをちょっといじって

let double = inst () in 
let h = handler double (val x -> x) ((x, k) -> k (k x)) in 
with h handle (perform double 3) + (perform double 2)

とすると結果が評価順に依存するコードになるのが面白い。上記のコードの評価結果は左から右に評価していく場合(つまりperform double 3を先に評価する場合)は18、OCamlのように右から左に(+)の引数を評価していく場合は17になる。ぱっと見大して難しいこともしておらず副作用もなさそうなコードで結果が評価順依存になる、というのは限定継続やエフェクトの不思議なところだ。

OCaml Effects Tutorialの演習「Async/await」をやってみる

OCaml 5.0にeffect handlerが入った理由の一つである、並行処理をdirect styleで記述できるasync/awaitの実装をやってみる。

この演習:

github.com

演習用のコード・サンプルはこれ:

github.com

Schedulerのインタフェース

この演習ではasync/awaitといった並行プログラミング機能をSchedulerモジュールに実装することになる。

SchedulerのシグニチャSCHEDULERは以下の通り:

module type SCHEDULER = sig
  type 'a promise
  (** Type of promises *)

  val async : (unit -> 'a) -> 'a promise
  (** [async f] runs [f] concurrently *)

  val await : 'a promise -> 'a
  (** [await p] returns the result of the promise. *)

  val yield : unit -> unit
  (** yields control to another task *)

  val run   : (unit -> 'a) -> unit
  (** Runs the scheduler *)
end

Schedulerのインタフェースとして:

  • 並行的に実行されているタスクが最終的に結果を返す「値」を表すpromiseという多相な型
  • thunkされている処理を引数にとり、それを並行的に実行する(そしてすぐにそのタスクの結果のpromiseを返す)async関数
  • promiseに対して「その結果が出るまで一時停止して待つ」ことで値を受け取れるawait関数
  • 並行的に実行されているタスクが一旦停止してコントロールをスケジューラに返すyield関数
  • async/awaitを使っているthunk関数を渡してスケジューラを実行するrun関数

が提供されている。

使用例

使い方としては以下のようになる:

let main () =
  let module S = Scheduler in
  let task name () =
    Printf.printf "starting %s\n%!" name;
    let v = Random.int 100 in
    Printf.printf "yielding %s\n%!" name;
    S.yield ();
    Printf.printf "ending %s with %d\n%!" name v;
    v
  in
  let pa = S.async (task "a") in
  let pb = S.async (task "b") in
  let pc = S.async (fun () -> S.await pa + S.await pb) in
  Printf.printf "Sum is %d\n" (S.await pc);
  assert (S.await pa + S.await pb = S.await pc)

let () = Scheduler.run main

Schedulerの中身

まずSchedulerモジュールはSCHEDULERシグニチャを持ち、Effect.Deepを短いローカル名Dとして使っている:

module Scheduler : SCHEDULER = struct
  module D = Effect.Deep

  ...

end

promiseの定義:

  type 'a _promise =
  | Waiting of ('a,unit) D.continuation list
  | Done of 'a

  type 'a promise = 'a _promise ref

まずイミュータブルな'a _promise型を定義し、それのrefとして'a promiseを定義している。

'a _promiseはWaitingとDoneというバリアントを持つ。Waitingにはこのpromiseの結果を待って一時停止している処理の限定継続がリストとして保持されている。promiseが解決したらこれら限定継続に値を渡して逐次スケジュールしていく必要がある。Doneは単にそのpromiseが解決した結果の値を保持している。

'a promiseがrefである理由は「タスクがそのpromiseに対してawaitする」「promiseの処理が終わって結果が出る」などの状況で内容が動的に変わる必要があるからだ。

async, yield, awaitの定義:

  type _ Effect.t +=
  | Async : (unit -> 'a) -> 'a promise Effect.t
  | Yield : unit Effect.t
  | Await : 'a promise -> 'a Effect.t

  let async f = Effect.perform (Async f)
  let yield () = Effect.perform Yield
  let await p = Effect.perform (Await p)

これらは全部エフェクトとして定義されている。SCHEDULERで定義されている各関数の型とエフェクトのGADTがしっかり合致している。

スケジューラのキュー:

  let q = Queue.create ()
  let enqueue t = Queue.push t q
  let dequeue () =
    if Queue.is_empty q then ()
    else Queue.pop q ()

破壊的変更を加える非関数型なQueueを使っていて、モジュールの保持する値として一つの可変なQueueが作成される。このQueueに対してenqueueで新しいタスクを載せる(タスクはunit -> unitな関数)。dequeueでQueueからタスクを取り出し実行する。タスクが残っていない場合はそのまま()を返す。

エフェクトハンドラを作成するmake_handler関数:

  let rec make_handler : 'a. 'a promise -> ('a, unit) D.handler = fun promise ->
    { D.retc = ...;
      D.exnc = ...;
      D.effc = ...}

handlerをそのまま定義するのではなく何らかのpromiseに対してparametrizeしている。これはasync関数でpromiseを作る際そのpromiseをhandlerに紐づける必要が生じるからだ。またhandlerの中で再帰的にhandlerを作ってmatch_withしたりするので再帰関数になっており、さらに多相である必要があるので明示的な型注釈がついている。

Effect.Deepのドキュメントをみればわかるが、type ('a, 'b) handlerの'a型はhandlerをかけて実行する関数の返り値の型、'bはhandlerのretcでその'a型の返り値を受けてmatch_with f handlerが最終的に返す値の型だ。

なのでmatch_with f x (make_handler promise)という式があってxがa型、promiseがb promise型だった場合、fはa -> b型、make_handler promise(b, unit) handler型でmatch_with f x (make_handler promise)全体はunit型となる。

それではハンドラ内の処理を見ていく。

まずretc:

      D.retc = (fun v ->
          match !promise with
          | Done _ -> failwith "Trying to close a closed promise"
          | Waiting ks ->
                let enqueue_continue k = enqueue (fun () -> D.continue k v) in
                List.iter enqueue_continue ks;
                promise := Done v;
                dequeue ()
          );

retcはmatch_with f x (make_handler promise)f xという関数適用が正常に終わり値を返してきたケースだ。Schedulerモジュールで定義されたhandlerが付いた状態でmatch_withしたということは、特定のpromiseが紐づいている(make_handlerの引数として渡されたpromiseがretcの関数のクロージャに捕捉されている)。f xという処理が正常に終了して値が返ってきた時点で、その値がpromiseの結果の値となる。行う処理は三つ:

  1. このpromiseに対してawaitしている処理すべてに、結果の値を渡して再実行するタスクをスケジュールする
  2. promiseの状態をDoneにする
  3. スケジューラにコントロールを渡して次のタスクを走らせる

これらがmatch !promiseWaiting ksケースで行われている。ちなみにpromiseに紐づくタスクが終了して結果を返すのは最大一回のはずなので、retcが走る時点でpromiseがDoneになっているというのは起きえない(起きたらバグ)。

exncのケース:

      D.exnc = raise;

これは簡単でただ単にmatch_with実行中に上がってきたハンドルされていないエラーは上に投げ直す。

effcに関してはAsync、Yield、Awaitの三種のエフェクトに対してのパターンマッチが書かれている。

まずAsyncエフェクト:

      D.effc = (fun (type b) (eff: b Effect.t) ->
          match eff with
          | Async f -> Some (fun (k: (b,_) D.continuation) ->
                  let promise' = ref (Waiting []) in
                  enqueue (fun () -> D.continue k promise');
                  D.match_with f () (make_handler promise')
          )

x = async fでfが非同期的に実行され、最終的にf ()の結果の値に解決するpromiseに変数xが束縛される。

処理の流れとしては以下の通り:

  1. 新しいpromiseを作成
  2. 「そのpromiseを現在のAsyncエフェクトが発生した地点の限定継続に渡す」という処理をタスクとしてスケジュールする
  3. そのpromiseを使って作ったhandlerをかけてasyncで渡されたthunk関数fを実行する

promiseが限定継続に渡されると、そのpromiseに対してその後awaitする処理が出てきたりする。そしてthunk関数fの処理が正常に終了すると、本記事の上の方で見たretcの部分によって、そのpromiseに登録されているawait中の限定継続に値が渡されていくわけだ。

Asyncエフェクトを処理する際に「async発生元の処理」と「asyncで走らせる処理」の二つが存在していて、上記のコードでは前者をスケジュールして後者をそのまま実行していくようになっている。逆にしてもいいし、何ならどちらもスケジュールして、スケジューラにコントロールを渡してもいい。どうするのが一般的なのかは気になる・・・。

Yieldエフェクト:

          | Yield -> Some (fun k ->
                  enqueue (D.continue k);
                  dequeue ()
          )

yield ()すると自身(現在走っている処理)を一時停止してスケジューラにコントロールを返すことになる。実際の処理としては、「限定継続を再度実行する」タスクをスケジューラに加えて、スケジューラの次のタスクを実行する、というものになる。

Awaitエフェクト:

          | Await promise' -> Some (fun (k: (b,_) D.continuation) ->
            match !promise' with
            | Done v -> D.continue k v
            | Waiting ks ->
                  promise' := Waiting(k::ks);
                  dequeue ()
          )

あるpromiseに対してawaitする場合、もしpromiseが解決済みならその結果の値をすぐに受け取る。もしまだpromiseに紐づいた処理が実行中ならpromiseが解決するまで停止し(スケジューラにコントロールを受け渡して)promiseが解決した時点で結果を受け取り処理再開。

実際の処理としてはAwaitエフェクトに保持されているpromiseに対してパターンマッチ(make_handlerの引数として渡されたpromiseではないことに注意)。Doneならその値を即座に限定継続に渡して続行。Waitingならその限定継続のリストに自身も加えdequeue ()でスケジューラの次のタスクを実行。

Async、Yield、Await以外のエフェクトはハンドルせずにより上位のハンドラに任せる:

          | _ -> None

最後にスケジューラを実際に走らせるrun関数:

  let run main =
    let handler = make_handler (ref (Waiting [])) in
    D.match_with main () handler
end

runに渡されるthunk関数mainもスケジューラで実行する必要があるので、この関数に紐づく空のpromiseを作成してmake_handlerしている。このコードの性質上、このpromiseはawaitされないのでmain関数が正常に終わったらその結果は何にも使われないのだが、ハンドラをつける都合上promiseが必要になる。

run関数の処理は「空のまま使われない新しいpromiseをmake_handlerに渡して作ったhandlerをかけてmain関数をmatch_withで実行する」というもの。

雑考

モナドや特殊構文に頼ることなくdirect styleでasync/awaitなコードを書く機能を、ライブラリ的に作ることができたというのは非常に面白い。このアプローチだとasync/awaitで起こりがちな「colored function」問題、つまりほぼ同じ処理の通常版とasync/await版をいろいろ用意しないといけない状態にならないのもポイント。async/awaitを使う関数を普通の高階関数に渡しても問題なく処理できる。実際にこのアプローチを精緻化して実用的なコードとして提供しているのがEioライブラリだ。このライブラリは近いうちに試してみたい。

未解決のpromiseの中身がそのpromiseに対してawait中の処理の限定継続の束だというのは面白い。promise内部のデータとしては、そのpromiseに紐づいた処理へのリンクが何らなく、handlerのretcのクロージャにpromiseが捕捉されていることから紐づく、というのは非直感的な気もする(悪いと言っているわけではない)。

ミュータブルなQueueがモジュールレベルで単一になっているのが気になる。Schedulerが複数回(あるいは別のスレッドで同時に)使われる場合同じQueueが利用されるのはあまり好ましくない。Queueの作成をrun関数の中で行い、make_handlerの引数の一つとして渡してしまうようなデザインの方が良さそうに思う。

元の演習コードだとrun関数の内部関数としてforkという再帰関数が出てくる(上にhandlerがこの関数の中で定義される)のだが、個人的にはこのforkは消してmatch_withを剥き出しにし、handlerの再帰性とpromiseへの依存を明示した方がわかりやすいように感じたのでリファクタしてある。

Effect Handlerで相互再帰を分割するコードの変遷

前回の記事で書かれたコードに到達するまで、いくつかのアプローチで漸進的に単純化されていったのでその経緯についても書いておく。

第一案

そもそも「相互再帰を分割するサンプルコードを書こう」と思い立ったのはComposable Interpreterで使った「すべてのハンドラをかけ直すのが責務なハンドラ」というパターンを抜き出して一般化しておこうと考えたからだ。なので最初の実装はかなりComposable Interpreterの形に引きずられた形になっていた。

エフェクトに関しては「実際に処理が行われるエフェクト」と「エフェクトハンドラをかけ直すエフェクト」を分けて考えていた:

module Base = struct
  type _ Effect.t +=
  | IsOdd: int -> bool Effect.t
  | IsEven: int -> bool Effect.t
  | IsOddX: int -> bool Effect.t
  | IsEvenX: int -> bool Effect.t
end

名前が微妙だがIsOddXというのは「エフェクトハンドラをかけ直した上でIsOddエフェクトを発生させるエフェクト」だ。

Composable Interpreterと同じく、実際の処理もエフェクトに応じてハンドラによって行われる:

module Odd = struct
  module D = Effect.Deep
  let handler =
  {
    D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Base.IsOdd n -> Some (fun (k: (b,_) D.continuation) ->
          if n=0 then D.continue k false
          else D.continue k (Effect.perform (Base.IsEvenX (n-1))))
      | _ -> None
  }
end

module Even = struct
  module D = Effect.Deep
  let handler =
  {
    D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Base.IsEven n -> Some (fun (k: (b,_) D.continuation) ->
          if n=0 then D.continue k true
          else D.continue k (Effect.perform (Base.IsOddX (n-1))))
      | _ -> None
  }
end

Base.IsOddエフェクトのハンドラの処理中にはBase.IsEvenXエフェクトが生じている(Base.IsEvenではないのがポイント)。

モジュールMでBase.IsOddX、Base.IsEvenXのハンドラが定義されている:

module M = struct
  module D = Effect.Deep
  let rec handler : 'a. 'a D.effect_handler =
  {
    D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Base.IsEvenX n -> Some (fun (k: (b,_) D.continuation) ->
          let f n = D.continue k (Effect.perform (Base.IsEven n)) in
          let f n = D.try_with f n Even.handler in
          let f n = D.try_with f n Odd.handler in
          D.try_with f n handler)
      | Base.IsOddX n -> Some (fun (k: (b,_) D.continuation) ->
          let f n = D.continue k (Effect.perform (Base.IsOdd n)) in
          let f n = D.try_with f n Even.handler in
          let f n = D.try_with f n Odd.handler in
          D.try_with f n handler)
      | _ -> None
  }
  let is_odd n = D.try_with (fun n -> Effect.perform (Base.IsOddX n)) n handler
  let is_even n = D.try_with (fun n -> Effect.perform (Base.IsEvenX n)) n handler
end

Odd、Evenモジュールのハンドラをどちらもかけ直し、さらに自身をかけ直した状態でBase.IsOdd、Base.IsEvenエフェクトを発生させる。

使い方は同じ:

let () = print_endline @@ string_of_bool @@ M.is_odd 72

改善1

Base.IsOddXといった名前が微妙なので修正したいと思ってコードを眺めていたら、そもそもこれらのエフェクトは必要ないことに気づいた。Odd.handler、Even.handlerで捕捉するエフェクトをM.handlerでも捕捉するようにして、後者は「正しいハンドラに捕捉されなかった場合は、全ハンドラをかけ直して同じエフェクトを発生させる」という処理にすればいい。

なのでMモジュールは以下のように変わる:

module M = struct
  module D = Effect.Deep
  let rec handler : 'a. 'a D.effect_handler =
  {
    D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Base.IsEven n -> Some (fun (k: (b,_) D.continuation) -> (* ここ *)
          let f n = D.continue k (Effect.perform (Base.IsEven n)) in
          let f n = D.try_with f n Even.handler in
          let f n = D.try_with f n Odd.handler in
          D.try_with f n handler)
      | Base.IsOdd n -> Some (fun (k: (b,_) D.continuation) ->  (* ここ *)
          let f n = D.continue k (Effect.perform (Base.IsOdd n)) in
          let f n = D.try_with f n Even.handler in
          let f n = D.try_with f n Odd.handler in
          D.try_with f n handler)
      | _ -> None
  }
  let is_odd n = D.try_with (fun n -> Effect.perform (Base.IsOdd n)) n handler  (* ここ *)
  let is_even n = D.try_with (fun n -> Effect.perform (Base.IsEven n)) n handler  (* ここ *)
end

Mモジュール以外の変更として、Base.IsOddX、Base.IsEvenXはなくなり、Odd.handler、Even.handlerの中ではBase.IsEven、Base.IsOddエフェクトが発生するようになる。

改善2

M.handlerでは必ず自身を含むすべてのハンドラをつけているが、そもそもM.handlerには次に何のエフェクトが発生するのかわかっている。必要なハンドラだけをつけるようにできる:

module M = struct
  module D = Effect.Deep
  let rec handler : 'a. 'a D.effect_handler =
  {
    D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Base.IsEven n -> Some (fun (k: (b,_) D.continuation) ->
          let f n = D.continue k (Effect.perform (Base.IsEven n)) in
          let f n = D.try_with f n Even.handler in (* ここ *)
          D.try_with f n handler)
      | Base.IsOdd n -> Some (fun (k: (b,_) D.continuation) ->
          let f n = D.continue k (Effect.perform (Base.IsOdd n)) in
          let f n = D.try_with f n Odd.handler in (* ここ *)
          D.try_with f n handler)
      | _ -> None
  }
  ...
end

改善3

ここで気づくのはM.handlerのやっていることのマッチポンプ性だ。特定の処理を行うハンドラだけをかけてそのハンドラに捕捉されるエフェクトを直接発生させている。これって処理部分はエフェクトとハンドラである必要はまったくないよね?

というわけで前回のコードに行き着く。

OddやEvenモジュールからはhandlerがなくなり、エフェクトを発生させる関数に代わられる。

これが:

module Odd = struct
  module D = Effect.Deep
  let handler =
  {
    D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Base.IsOdd n -> Some (fun (k: (b,_) D.continuation) ->
          if n=0 then D.continue k false
          else D.continue k (Effect.perform (Base.IsEven (n-1))))
      | _ -> None
  }
end

こうなる:

module Odd = struct
  let is_odd n =
    if n=0 then false
    else Effect.perform (Base.IsEven (n-1))
end

そしてM.handlerでは自身を再帰的にかける必要はあるが、実際の処理を行うときにエフェクトを発生させるのではなく単に関数を呼び出す。

これが:

module M = struct
  module D = Effect.Deep
  let rec handler : 'a. 'a D.effect_handler =
  {
    D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Base.IsEven n -> Some (fun (k: (b,_) D.continuation) ->
          let f n = D.continue k (Effect.perform (Base.IsEven n)) in
          let f n = D.try_with f n Even.handler in
          D.try_with f n handler)
      ...
  }
  ...
end

こうなる:

module M = struct
  module D = Effect.Deep
  let rec handler : 'a. 'a D.effect_handler =
  {
    D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Base.IsEven n -> Some (fun (k: (b,_) D.continuation) ->
          D.continue k @@ D.try_with Even.is_even n handler)
      ...
  }
  ...
end

雑考

やはりハンドラに必要なボイラープレートがものすごい印象だ。ハンドラ9行のうち処理のコードは2行、あとはエフェクトや限定継続関連、あるいはレコードにしてあることからきている。今後これがなんとかスッキリしてくれないとつらい。

今回のコードの形はComposable Interpreterとかなりかけ離れている。Extensible Interpreterも含めて、どういう責務をどこに持たせたいとどのような形になるのか、という点についてもうちょっと考えてみたい。

Effect Handlerで相互再帰を分割する

タイトルどおり、OCaml 5.0のeffect handlerを使って相互再帰的な関数を分割して別々に定義できるようにする。

相互再帰な処理

ベタだが今回はis_oddとis_evenという相互再帰な関数を例にとる:

let rec is_odd n =
  if n=0 then false
  else is_even (n-1)
and is_even n =
  if n=0 then true
  else is_odd (n-1)

is_oddは引数が0ならfalse、0以外ならis_even (n-1)としている。is_evenは逆。(0未満の整数が引数だと無限ループになるが・・・)

このような普通の相互再帰let rec ... and ...といった形で同時・同箇所で定義する必要がある。

Effect Handlerによる実現

それではEffect Handlerを使うとこのような相互再帰を別モジュールに分割できることをみていく。

まずはBaseモジュールでIsOddとIsEvenエフェクトを定義する:

module Base = struct
  type _ Effect.t +=
  | IsOdd: int -> bool Effect.t
  | IsEven: int -> bool Effect.t
end

このモジュールでは二つの処理のためのエフェクトが定義されているが、実際の処理の内容はまったく触れられていない。「これらの処理が存在する」と宣言していると見做せる。

実際の処理はOddとEvenという二つのモジュールでそれぞれハンドラとして定義:

module Odd = struct
  let is_odd n =
    if n=0 then false
    else Effect.perform (Base.IsEven (n-1))
end

module Even = struct
  let is_even n =
    if n=0 then true
    else Effect.perform (Base.IsOdd (n-1))
end

元のis_oddとis_even関数の処理がほぼそのまま、ただし分割されて別々のモジュールに現れている。OddとEvenは相互にはまったく依存していないのがポイント。相互再帰的な呼び出しだけエフェクト発生に代わっていて、どちらもあくまでBaseモジュールで定義されたエフェクトを使っているだけ。

最後にこれらを組み合わせて最終的なis_oddとis_even関数を提供するモジュール:

module M = struct
  module D = Effect.Deep
  let rec handler : 'a. 'a D.effect_handler =
  {
    D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Base.IsEven n -> Some (fun (k: (b,_) D.continuation) ->
          D.continue k @@ D.try_with Even.is_even n handler)
      | Base.IsOdd n -> Some (fun (k: (b,_) D.continuation) ->
          D.continue k @@ D.try_with Odd.is_odd n handler)
      | _ -> None
  }
  let is_odd n = D.try_with Odd.is_odd n handler
  let is_even n = D.try_with Even.is_even n handler
end

いいモジュール名が思いつかなかった・・・。

M.handlerはBase.IsOdd、Base.IsEvenのエフェクトを捕捉し、自身をかけた上でOdd.is_odd、Even.is_evenを実行、その結果を元のエフェクトの限定継続に渡す。自身を掛け直す必要があるのはOdd.is_odd、Even.is_evenでまたBase.IsOdd、Base.IsEvenのエフェクトが発生し得るから。

M.is_odd、M.is_evenもこのM.handlerをかけた上でOdd.is_odd、Even.is_evenを実行するだけ。

使ってみる:

let () = print_endline @@ string_of_bool @@ M.is_odd 72
$ ocaml recursion1.ml
false

成功。

雑考

今回の処理のまとめ

Baseモジュールで行う処理の宣言、OddとEvenで実際の処理、そしてMでそれらを組み合わせる、という形になった。Mは正しい処理へのディスパッチと再帰性の追加を責務としていることがわかる。また(今回の例だと簡単すぎてあまり考えにくいが)また違うis_oddの実装を別モジュールOdd'に書いて、Base、Odd、EvenはそのままでMで組み合わせる(あるいは別途M'モジュールを定義する)ということもできる。

相互再帰関数を引数として渡す実装

エフェクトを使わない場合、でこれきさんのこちらの記事のやり方でも(多相バリアントは使わずとも)できる:

qiita.com

こんな感じ:

let is_odd' is_even n =
  if n=0 then false
  else is_even (n-1)

let is_even' is_odd n =
  if n=0 then true
  else is_odd (n-1)

let rec is_odd n = is_odd' is_even n
and is_even n = is_even' is_odd n

let () = print_endline @@ string_of_bool @@ is_odd 72

考え方としては非常に似ていて、実際の処理は別々に定義し、それを組み合わせてディスパッチする役割と再帰性を追加する役割を持つコードが最後にくる形になっている。

正直な話、現在の専用構文なし、エフェクトシステムによる静的検査なし、なOCaml 5.0のeffect handlerを使うよりはこっちの方がはっきりとスッキリしている。専用構文が入ったとしてもどうだろうか。コードの見た目が同じくらいになった時点でエフェクトを使った方がいい理由はあるのか、まだ把握できていない。

トランポリン

今回のコードの挙動はトランポリンと見做すこともできる(末尾再帰のない言語で再帰できる言語のインタプリタを書くときによくやるあれ)。

そもそもeffect handler機能は全般的にトランポリン的だが、ただしネストしているとかなりややこしい。今回はネストなしで、ハンドラがディスパッチを担当しているのでかなり明確なトランポリンの構図になっている。

限定継続の中身と末尾呼び出し最適化

今回のコードだとエフェクト発生の箇所はOdd.is_oddやEven.is_evenの末尾になっている。なのでM.handlerの中でD.continue k ...する場合、エフェクト発生の箇所に戻ってそのスタックをすぐに破棄してその上のスタックに移る、といった処理は本来最適化できるはず。末尾ポジションでエフェクトが発生した場合、そのエフェクトで渡される限定継続は一つ上のスタックを指すようになっているのか、あるいはなっていないとしてできるのか?というランタイムの実装に関してはなかなか面白そうな点だと思う。

エフェクトの名前空間

今まで漠然と「エフェクトって_ Effect.tを拡張しまくるから名前空間がごちゃごちゃしそうだな」と思っていたが、考えてみたら例外と同じでextensible variant typeで追加されるバリアントはモジュール名が前置きされるのでそういった名前空間汚染は起きなさそう。

供養

今回は軽いトピックですぐ書けるだろうと考えていたのだが、蓋を開けてみれば2回ばかり大幅なリファクタを行うという難産だった。勉強になったのでいいのだが、没になったコードもリファクタ込みでちょっと面白いので、供養がてらまた記事にしたい。最初はもっとエフェクトエフェクトしていた。

今回のコード

gist.github.com

Effect Handler、Extensible Interpreter、Expression Problem

前回の記事に書いたとおり、今回はこのExtensible Interpreterの枠組みを使うとExpression Problemを解決できるということを見ていく。

Expression Problem

Expression Problemについては以前この記事で書いた:

zehnpaard.hatenablog.com

かいつまんで説明すると「オブジェクトだと新しいデータを追加するのは既存のコードを変更せずに(新しいクラスを追加するだけで)できるが、新しい処理を追加するのは(すべてのクラスにメソッドを実装する形で)既存のコードを改修する必要がある」「代数的データ型だと逆に処理を追加するのは簡単、新しいデータを(バリアントとして既存の型に)追加すると今まで書いた関数すべても変更が必要になる」というトレードオフの話。

Effect handler(とExtensible Variant Type)を使ったExtensible Interpreterの実装では、このExpression Problemが解決され、元のコードを触らずにデータも処理も追加できる。それを示すため、この記事では:

  • 既存のevalコードを変更することなく項を文字列化するprint関数を追加
  • 既存のevalとprintのコードを変更することなくif構文を追加し新しいeval+printを拡張として定義

の二つを行う。

処理の追加:print

前回のComposable Interpreterのコードに、evalの実装をほぼなぞるような形でprint関数を追加できる。

まずprint用のエフェクト:

type _ Effect.t +=
| PExtension : 'a expr -> string Effect.t
| Print : 'a expr -> string Effect.t

let print_effect e = Effect.perform (Print e)

eval用のExtensionとEvaluateに対応している。既存のExtensionエフェクトは'a expr -> 'a Effect.t型なのでハンドラを変えるだけではダメで、別途PExtensionのような別の'a expr -> string Effect.t型を用意する必要がある。

Printエフェクトとそれを発生させるprint_effect関数はevalでいうところのEvaluateとeval_effectに対応する。「ハンドラをすべてかけて文字列化する」というエフェクトだ。

PExtensionエフェクトのハンドラ:

let print_handler1 =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | PExtension (Int n) -> Some (fun (k: (b,_) D.continuation) ->
          D.continue k (string_of_int n))
      | PExtension (Add(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = print_effect e1 in
          let n2 = print_effect e2 in
          D.continue k (Printf.sprintf "(+ %s %s)" n1 n2))
      | PExtension (Sub(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = print_effect e1 in
          let n2 = print_effect e2 in
          D.continue k (Printf.sprintf "(- %s %s)" n1 n2))
      | PExtension (Mul(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = print_effect e1 in
          let n2 = print_effect e2 in
          D.continue k (Printf.sprintf "(* %s %s)" n1 n2))
      | PExtension (Div(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = print_effect e1 in
          let n2 = print_effect e2 in
          D.continue k (Printf.sprintf "(/ %s %s)" n1 n2))
      | PExtension (Bool b1) -> Some (fun (k: (b,_) D.continuation) ->
          D.continue k (string_of_bool b1))
      | PExtension (Eq(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = print_effect e1 in
          let n2 = print_effect e2 in
          D.continue k (Printf.sprintf "(= %s %s)" n1 n2))
      | PExtension (Gt(e1,e2)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = print_effect e1 in
          let n2 = print_effect e2 in
          D.continue k (Printf.sprintf "(> %s %s)" n1 n2))
      | _ -> None
  }

現在定義されているすべての構文を一つのハンドラで処理している。もちろんevalのように分割してもいい。文字列化の具体構文はS式にしてある。

インタプリタを組み上げる:

let print_base e = Effect.perform (PExtension e)
let print1 e = D.try_with print_base e print_handler1

let print e =
  let rec handler : 'a. 'a D.effect_handler =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Print e -> Some (fun (k: (b,_) D.continuation) ->
          D.continue k (D.try_with print1 e handler))
      | _ -> None
  } in
  D.try_with print_effect e handler

evalとまったく同じで、PExtensionエフェクトを発生させるだけのprint_baseにPExtensionハンドラをかけて、その後Printハンドラも追加することでprint_effect関数が「すべてのハンドラをかけ直して項を文字列化」という処理になるようにする。

使ってみる:

let _ =
  let e = Gt(Mul(Int 2, Int 3), Add(Int 2, Int 3)) in
  let print_handler =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | PExtension _ -> Some (fun (k: (b,_) D.continuation) ->
          D.continue k "???")
      | _ -> None
  } in
  let s = D.try_with print e print_handler in
  print_endline s

Gt(Mul(Int 2, Int 3), Add(Int 2, Int 3))(> (* 2 3) (+ 2 3))と出力される。

evalの時はハンドラの存在しない構文に関してはfailwithでエラーにしていたが、文字列化では試しに???という文字列を返すようにしてみた。もしprint_handler1からPExtension (Int n)のケースを削除するとGt(Mul(Int 2, Int 3), Add(Int 2, Int 3))(> (* ??? ???) (+ ??? ???))と出力される。

というわけで「既存の実装を変えることなく関数を追加」はできた。代数的データ型だから当たり前とも言えるが・・・。これがクラスベースの実装だったら既存のクラス一つ一つにprintメソッドを追加していくことになるだろう。

データの追加:if構文

では代数的データ型の「問題」とされる、「既存の実装を変えることなくデータの種類を追加」のケースを見ていく。

具体的にいうとif構文を追加する:

type 'a expr +=
  | If : bool expr * 'a expr * 'a expr -> 'a expr

ここはextensible variant type様様で、もし普通のバリアント型だったらその時点で「既存の型定義に変更を加える」という形にならざるを得なかった。この型の拡張はたとえば別々にコンパイルされるモジュールでも可能なことに注意。

eval関数の拡張:

let handler_if =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Extension (If(e1, e2, e3)) -> Some (fun (k: (b,_) D.continuation) ->
          let b = eval_effect e1 in
          let x = eval_effect (if b then e2 else e3) in
          D.continue k x)
      | _ -> None
  }

let eval4 e = D.try_with eval e handler_if

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 eval4 e handler))
      | _ -> None
  } in
  D.try_with eval_effect e handler

Composableにしたことが拡張性を損なっていないことがわかる。すでに定義したeval関数をベースにIf構文のExtensionハンドラとそのハンドラで生じるEvaluateエフェクトのハンドラをかける新しいeval関数を定義している。

printもまったく同じ:

let print_handler_if =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | PExtension (If(e1, e2, e3)) -> Some (fun (k: (b,_) D.continuation) ->
          let n1 = print_effect e1 in
          let n2 = print_effect e2 in
          let n3 = print_effect e3 in
          D.continue k (Printf.sprintf "(if %s %s %s)" n1 n2 n3))
      | _ -> None
  }

let print2 e = D.try_with print e print_handler_if

let print e =
  let rec handler : 'a. 'a D.effect_handler =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Print e -> Some (fun (k: (b,_) D.continuation) ->
          D.continue k (D.try_with print2 e handler))
      | _ -> None
  } in
  D.try_with print_effect e handler

evalの実装をなぞるだけ。

こんな感じで使うと:

let _ =
  let e = If(Gt(Mul(Int 2, Int 3), Add(Int 2, Int 3)),Int 0, Int 1) in
  let handler =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | Extension _ -> failwith "Unknown syntax"
      | _ -> None
  } in
  let n = D.try_with eval e handler in
  print_endline @@ string_of_int n;
  let print_handler =
  { D.effc = fun (type b) (eff : b Effect.t) ->
      match eff with
      | PExtension _ -> Some (fun (k: (b,_) D.continuation) ->
          D.continue k "???")
      | _ -> None
  } in
  let s = D.try_with print e print_handler in
  print_endline s
$ ocaml interpreter3.ml
0
(if (> (* 2 3) (+ 2 3)) 0 1)

うまく使えているのがわかる。

雑考

Expression Problemに対する一つの解となっているのは確かだと思う。

しかしそのための道具立てがかなり重い感触ではある。行数からも、そして複雑な言語機能が剥き出しでコード読みにかかるオーバーヘッドからも、「ここまでするか?」という気持ちになる。専用構文などで軽くなったらマシになるだろうか?あるいはこのコードのようにハンドラをレコード(つまりデータ)として自由に扱うのが難しくなる可能性もある。今後effect handlerという言語機能が使われ出して、どのようなhandler compositionのパターンが出てくるのか、そしてそのパターンをどう構文でサポートしていくのか、大変興味深く目が離せない。

今回のExpression Problemの解決法にはEffect Handlerが必須で、Extensible Variant Typeだけでは足りない。後者だけだとバリアント型は既存の定義を触らずに拡張できるのだが、既存のeval関数に手を加えないとその追加されたバリアントに対応できない。

ちなみにExpression Problemとは直接関係ないが、Composable Interpreterを実装する別解としては多相バリアントを使ってやる方法もある。でこれきさん(@dico_leque)が以前書かれていた:

qiita.com

こちらはComposable but not Extensibleになるだろうか。新しいバリアントに対応するためには、既存のevalを使うのではなくパーツを集め直して新しいeval関数を定義することになる。

しかしEffect Handlerを使うとopen recursionも簡単(?)に実装できるようになるのか・・・?この点に関してはもうちょっと考えてみたい。

今回のコード

gist.github.com

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 handler2let 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になったくらい)。しかし実際に実行される流れはかなり違う。

  1. まず「ハンドラが存在しないExtension構文をすべて捕捉してエラーにするハンドラ」をかけた上でeval関数に項eが渡される
  2. eval関数で「自分自身と(eval3に含まれる)すべてのExtensionハンドラをかけるハンドラ」をかけた上でeval_effectする
  3. eval_effectでEvaluateエフェクトが発生し、eval内で定義された「すべてのハンドラをかけるハンドラ」に捕捉される
  4. 「すべてのハンドラをかけるハンドラ」がすべてのハンドラをかけた上でeval_baseに項eを渡す
  5. eval_baseでExtensionエフェクトが発生し、いずれかのExtensionハンドラに捕捉される(このテストケースの場合handler3にExtension (Gt(e1, e2))が捕捉される)。この時点でそのExtensionハンドラより内部のハンドラは抜けてきていてかかっていない
  6. 部分項を順次eval_effectに渡すとeval_effectでEvaluateエフェクトが発生し、残っていたすべてのExtensionハンドラ(ただし未定義構文を捕捉するcatch-all以外)を抜けて「すべてのハンドラをかけるハンドラ」に捕捉される(部分項がないIntやBoolなどの場合はそのままその値が結果となり、ステップ9に飛ぶ)
  7. 部分項e'に関して再帰的にステップ4から処理される。
  8. 必要な部分項が評価されたら、それらを組み合わせて項の評価結果とする
  9. 限定継続にその評価結果を渡す(部分項の場合はステップ6に戻る、全体の項の場合はそのままevalから返される)

といった処理になる。ややこしい。

一つの項だけに絞ると:

  1. ある項が評価されるときはまず必ずeval_effectでEvaluateエフェクトが発生する
  2. その結果、Extensionハンドラはすべて抜けてEvaluateハンドラに捕捉される
  3. Evaluateハンドラは自身を含むすべてのハンドラをかけ直した状態で項をeval_baseし、その結果Extensionエフェクトが発生する
  4. 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の解決を見ていく。

今回のコード

gist.github.com