初めて再帰モジュールが必要になった話

入力ストリームの実装から独立したパーサーを定義したい。 そこでまずは入力ストリームのデータ型を定義する。

module type INSTREAM = sig
  type instream
  (* 本当はinstreamに対する色々な操作を含むつもり *)
end

実際の入力元はチャネルだったりメモリ上の文字列だったりする。

module ChanIns = struct
  type instream = in_channel
end

module StringIns = struct
  type instream = string
end

パーサーのシグニチャと実装はこんな感じになる。

module type PARSE = sig
  type instream
  type result
  val parse : instream -> result
end

module Parse(I: INSTREAM): PARSE with type instream = I.instream
  = struct
  type instream = I.instream
  type result = unit
  let parse ins = ()
end

module StringParse = Parse(StringIns)
module ChanParse = Parse(ChanIns)

ここでparse関数の中で、 「ストリームから読み込んだデータをいったん文字列にしてparse関数自身でパースする」 という処理がしたい。 文字列が変数sだとして、その内部のparse関数の呼び出しはどのように書けばよいか。

単にlet rec parse ins = ...としてparse (s : string)では駄目そうだ。 parseの型はinstream -> resultなのだがinstreamはI.instreamであって、 stringであるとは限らない。

じゃあ StringParse.parse (s : string) では？というとこれもだめだ。 Parseの実装の中ではまだStringParseは定義されていない。 もちろんStringParseはParseに依存するのでParseより前に移動するわけにもいかない。

ということは…あ、再帰か。 ということで初めて実際に再帰モジュールというものが必要になる場面に出くわしたのだった。

結論から書くと、次のように書くことでコンパイルが通るようになる。

module Parse(I: INSTREAM)(S: PARSE with type instream = StringIns.instream)
  : PARSE with type instream = I.instream
  = struct
  type instream = I.instream
  type result = unit
  let parse ins = (ignore (S.parse ""); ())
end

module rec StringParse : PARSE with type instream = StringIns.instream =
        Parse(StringIns)(StringParse)
module ChanParse = Parse(ChanIns)(StringParse)

ファンクターは新しい引数Sをとる。 Sのモジュール型から、S.instreamはStringIns.instreamであるという想定がおけるので、 問題のparseの呼び出しはこのSに定義されたparseを呼ぶことでよくなる。

S.parseは結果的にはStringParse.parseを呼んでいることにしたい、 つまりS = StringParseであるということにしたいので、 ファンクターを適用するときに第2引数をStringParseにする必要がある。

これはChanParseのときは簡単な話で、普通に適用すればよい。 しかしStringParseを作るときは自分自身を使って自分自身を作るということになる。 これは再帰だ。ということでrecが付く。 再帰モジュール定義の場合はStringParseのモジュール型を明示する必要があるようだ。

後書き

実際にはSMLを書いていてこの問題に遭遇したのでこのように解決することはできませんでしたが、 そういえばOCamlには再帰モジュールって有ったと思い出して問題を翻訳しました。