Arantium Maestum

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

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

OCaml

前回の記事をツイートしたら@dico_lequeさんからこういう話を教えていただいた：

（このブログの半分は@dico_lequeさんからのご指摘でできています・・・）

blag.bcc32.com

この記事ではrefを使うことなく、OCamlのファンクタと再帰モジュールを使ってOpen Recursionを実装している。

かなりちゃんとした実装で、単に再帰を分割するのではなく、モジュールをクラス、M.t型をインスタンス、としっかりオブジェクト指向にも対応するような形になっている。

その分実装がちょっと複雑なので、自分の理解するためにも簡略化して追ってみたい。

というわけで前回と同じ非常に単純な再帰関数をわけるのにこの手法を使ってみる。

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 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.fはAモジュールで定義されたfをinclude Aで追加している。なのでfの定義で呼び出されているgはB.fではなくA.fになってしまう。

全体図

考え方としてはSelfという引数をとるファンクタを作り、module rec X = F(X)でそのSelfが自分自身であるようなモジュールを作成する。

module type MT = sig
  val f : int -> unit
  val g : int -> unit
end

module A_ (Self : MT) : MT = struct
  let f n = print_int n; if n > 0 then Self.g (n-1) else ()
  let g n = ()
end
module rec A : MT = A_(A)

module B_ (Self : MT) : MT = struct
  include A_(Self)
  let g n = print_int n; if n > 0 then Self.f (n-2) else ()
end
module rec B : MT = B_(B)

意外と失敗例に比べて記述量が激増しているわけではない。（モジュール内で型を定義していて、モジュール間でその型の整合性を取ろうとすると色々と型制約を書く必要が増えてごちゃごちゃしてくる）

個別に詳細を追っていく。

モジュールのシグニチャ

まずは最終的に作成したいモジュールのシグニチャ（型）を定義する：

module type MT = sig
  val f : int -> unit
  val g : int -> unit
end

このMT（Module Typeの意）というシグニチャはファンクタの引数と再帰的モジュールの型を指定する為に必要になる。（ファンクタの戻り値は型で指定する必要はないのだが、書いておいた方がわかりやすい）

ベースクラス

ベースクラスにあたるAモジュールを定義するのに、ファンクタと再帰的モジュールを使う：

module A_ (Self : MT) : MT = struct
  let f n = print_int n; if n > 0 then Self.g (n-1) else ()
  let g n = ()
end
module rec A : MT = A_(A)

まずはMT型のモジュールを受け取りMT型のモジュールを返すファンクタA_を定義している。A_内で定義されている関数が「再帰的に」同じモジュールで定義されている関数を呼び出したい時は、Self.f、Self.gのように引数として受け取ったMT型のモジュールの関数を代わりに使う。

その上でmodule rec A : MT = A_(A)で「自分自身がSelfなMT型モジュール」をA_を使って定義する。

子クラス

子クラスにあたるBモジュールも形はほとんど同じ：

module B_ (Self : MT) : MT = struct
  include A_(Self)
  let g n = print_int n; if n > 0 then Self.f (n-2) else ()
end
module rec B : MT = B_(B)

唯一違うのはB_ファンクタのなかで、fを定義する代わりにinclude A_(Self)していること。なのでここでincludeされるモジュールの中の定義で使われるSelfはB_ファンクタの引数のSelfとなる。

includeの時点ではfもgもA_で定義されたものなのだが、そのすぐ後にgを定義し直している。

そして再帰的モジュール定義でB_を使って作成するモジュールBをB_に渡す。これでB_の中のSelfはB、そしてinclude A_(Self)の部分のおかげでA_の中のSelfもBとなる。なのでA_のなかで定義されているfがSelf.gとしてB.gを使えるようになる。

使ってみる

A.f 10;; 
(* 10 が出力され結果はunit *)

B.f 10;;
(* 109764310 が出力され結果はunit *)

成功。refによる破壊的変更に頼ることなく再帰的関数を二つのモジュールに分割できた。

追記：

@dico_lequeさんが多相バリアントを使ったopen recursionの解説を書かれていた：

qiita.com

多相バリアントを使う＆最終的に作成するevalを（再帰的に）引数として渡すことにすれば、「バリアントのパターンごとの関数を個別に定義する」という分割が可能。なるほど・・・