OCamlでも（オブジェクト使わずに）Open Recursionしたい！・・・したい？

タイトルからも察していただいた方も多いと思うが、実用的な話はしません。あくまで「open recursionってなんだっけ」「こんな感じの開かれた再帰をOCamlで書いてみよう」という趣旨です。

Open Recursionってなんだ？

ソフトウェアデザイン誌の2021年3月号がOOP特集だったようで、「至高のオブジェクト指向」「究極の関数型」的な話題がツイッターに渦巻いていたのを観測した。

と同時に「OOPで本当にやりやすくなるのってOpen Recursionくらいじゃないか？」という話もちらほらと出ていて、そもそもOpen Recursionってなんだっけ？と調べてみた。

stackoverflow.com

しかしあまり回答に納得がいかない。

Open recursion. Another handy feature offered by most languages with objects and classes is the ability for one method body to invoke another method of the same object via a special variable called self or, in some languages, this. The special behavior of self is that it is late-bound, allowing a method defined in one class to invoke another method that is defined later, in some subclass of the first.

とのことだが・・・　あるオブジェクトのメソッドから同じオブジェクトのメソッドを呼び出せる？どこが再帰なんだ？そもそも上記の文はOpen Recursionの定義なのかOOPでどうやってOpen Recursionが実現されているかの解説なのかもよくわからない。

と思ってTaPLを開いてみた。

開いてみたらp227に上記とまったく同一の文章が出てきた・・・　出典TaPLだったのか・・・

ただ、さすがにこれだけでは終わらず、１０ページ弱を使ってopen recursionの定義と実装について書いてあった。

よく読むと「名前空間が再帰的」、つまりどのメソッドの定義中にも他のすべてのメソッドが見える、というのがポイントのようだ。そしてlate bindingにより、例えばX.fの定義のなかでX.gが使われているとして、X.gが実際にどういう実装になっているかが問題になるのは実行時になるので、X.gは後から（例えばサブクラスの中で）定義できる。

「後々拡張できる開かれた形で名前空間が再帰的」ということだろう。

まあ非常に微妙な例だけどPythonでいえばこんな感じ：

class A:
  def f(self, n):
    print(n)
    if n > 0: self.g(n-1)

class B(A):
  def g(self, n):
    print(n)
    if n > 0: self.f(n-2)

selfという変数にメソッドなどが格納されているから、selfを渡されているメソッドすべてに名前空間が見えていて、そしてselfへのアクセスは実行時なのでAで定義されているfがBで定義されているgを呼び出すようになっていても問題ない。（C++だったらvirtual使う必要が出てくるけど）

OCamlでopen recursionめいたものができるか？

で、本題であるOCamlで（オブジェクトを使わずに）似たようなことができるかという話。ちなみに実用性は皆無。（二度目）

ここでいうOpen Recursionとは「同時にコンパイルされなくてもいいような形で相互再帰的な関数が定義できる」こととする。

OCamlだと相互再帰するのにlet rec f = ... and g = ...のように、明示的に相互再帰であると示してやる必要がある：

let rec f n = print_int n; if n > 0 then g (n-1) else ()
and g n = print_int n; if n > 0 then f (n-2) else ()

これを分割して、「継承」ぽい感じで別々のモジュールで定義して使うことはできるだろうか。

失敗例

module Module2 = struct include Module1 ... endでModule1の内容をModule2から使えるように出来るので、includeはまあだいたいクラスベースOOPにおける実装の継承に対応すると考えて良さそうだ。

includeを利用して、まずはダメな例：

module A = struct
  let g _ = ()
  let f n = print_int n; if n > 0 then g (n-1) else ()
end

module B = struct
  include A
  let g n = print_int n; if n > 0 then f (n-2) else ()
end

これでB.g 10などと試してみると108と出力して止まってしまう。B.gがA.fを呼び、A.fがA.gを呼んで終了、という流れだ。A.fから見えるgがBモジュールによる変更に開かれていない。（C++で親クラスのメソッドをvirtualにしないと似たような事になる）

refを使った実装

TaPLの実装解説でも出てくるが、こういう分割相互再帰を書くためにはfixとthunkを使うかrefを使うか、という選択肢が存在する。今回は楽なのでrefでやってみる：

module A = struct
  let f = ref (fun n -> failwith "")
  let g = ref (fun n -> failwith "")
  let () = f := (fun n -> print_int n; if n > 0 then !g (n-1) else ())
end

module B = struct
  include A
  let () = g := (fun n -> print_int n; if n > 0 then !f (n-2) else ())
end

エラーがどの型としても型チェックされることを利用して、まずはref (fun n -> failwith "")で可変な変数としてメソッドを初期化。あとはその変数をderefして使う実装を別々に定義しても大丈夫になる。

これで!(B.g) 10とすれば10875421-1と出力されてオッケー。

refを隠蔽

fやgの呼び出し時に!と明示的に書くのが実装が透けすぎていやだ、という場合は：

module A = struct
  let f_ = ref (fun n -> failwith "")
  let g_ = ref (fun n -> failwith "")
  let f n = !f_ n
  let g n = !g_ n
  let () = f_ := (fun n -> print_int n; if n > 0 then g (n-1) else ())
end

module B = struct
  include A
  let () = g_ := (fun n -> print_int n; if n > 0 then f (n-2) else ())
end

で隠蔽してもよし。これでrefはf_やg_という変数になり、実際に呼び出す関数fやgはそれらを包んで隠蔽するものになる。Bモジュールのシグナチャからf_やg_を消せばなお良い。

ファンクタでrefを守る

ここまでの実装だとAを二つの別のモジュールBとCが継承しようとすると変な事になる（同じAのrefを使いまわしているのでBの関数定義がCのものに上書きされてしまう）、のでファンクタを使うのもいいかもしれない：

module A (_ : sig end) = struct
  let f_ = ref (fun n -> failwith "")
  let g_ = ref (fun n -> failwith "")
  let f n = !f_ n
  let g n = !g_ n
  let () = f_ := (fun n -> print_int n; if n > 0 then g (n-1) else ())
end

module B = struct
  include A(struct end)
  let () = g_ := (fun n -> print_int n; if n > 0 then f (n-2) else ())
end

module C = struct
  include A(struct end)
  let () = g_ := (fun n -> print_int n; if n > 0 then f (n-3) else ())
end

Aをファンクタにして、BとCの中で空のモジュールを引数として渡してA(struct end)でまったく新しいモジュールを作成している。これによってBとCはまったく別のf_とg_というrefを持つ事になるので実装が上書きされない。

そもそもOpen Recursionしたいのか

私は個人的にOpen Recursionを縦横無尽に利用して問題解決したことはないが、まあユースケースとしてはコンパイラでAST処理するコードを自由に拡張できるようにしたいとか、複雑なネスト可能なUIの処理を拡張可能なように書きたいとか、とにかく扱うデータ・システム自体が再帰的な構造になっている上で、元のソースに触ることなく拡張する必要がある、という状況だと役に立つのではないだろうか。

再帰的構造というのは気をつけて探せば案外どこにでも転がっているものなので、上記のようなニーズは特にライブラリコードだったら結構ありえるのではないか。

そういうケースに遭遇した場合は、いちいちref作ったり隠蔽したりファンクタで管理したりするのも大変なので、OCamlだったら素直にオブジェクト機構を使おうと思う。