タイトルどおり、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で追加されるバリアントはモジュール名が前置きされるのでそういった名前空間汚染は起きなさそう。

供養

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

今回のコード

gist.github.com

Arantium Maestum

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

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