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

改善１

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エフェクトが発生するようになる。

改善２

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

改善３

ここで気づくのは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も含めて、どういう責務をどこに持たせたいとどのような形になるのか、という点についてもうちょっと考えてみたい。