Arantium Maestum

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

OCamlで存在型を試してみた (その3ーーモジュール)

シリーズ前々回前回に続いて存在型を探っていく。

今回はパラメトリックな機構はまったく使わないただのモジュールと存在型について。

第1級モジュールやファンクタによる抽象化機能と存在型について書いてきたが、型としての「存在型」はどちらの場合でもモジュールシグニチャだった。

つまり例えば:

module type ADDABLE_INT = sig
  type t
  val zero : t
  val create : int -> t
  val to_int : t -> int
  val add : t -> t -> t
end

これが「あるt型が存在し、そのt型があてはまる以下の値が定義されている」という存在型になり、この存在型をインタフェースとして第1級モジュールやファンクタはパラメトリックな挙動を可能にしている。

しかしOCamlでモジュールシグニチャを使うためには第1級モジュールやファンクタのような強力な機能を使うまでもなく、ただのモジュールでも普通に使えるし実際使う:

module IntInt : ADDABLE_INT = struct
  type t = int
  let zero = 0
  let create x = x
  let to_int x = x
  let add = (+)
end

module PeanoInt : ADDABLE_INT = struct
  type t =
  | Zero
  | Succ of t

  let zero = Zero

  let rec create n =
    if n = 0 then Zero
    else Succ (create (n-1))

  let rec to_int = function
  | Zero -> 0
  | Succ x -> 1 + (to_int x)

  let rec add x = function
  | Zero -> x
  | Succ y -> add (Succ x) y
end

IntIntPeanoIntstruct ... endで定義されている実装に対し、抽象型を持つシグニチャADDABLE_INT型としてモジュール名を束縛されている。

これでTaPLでいうところの「抽象的データ型としての存在型」的なことはできている。つまり内部実装は全然違うモジュールの型を隠蔽することで、統一されたインタフェースを通してのみデータを操作できるようになっている。

ただし、同一のインタフェースであるからといって異なるモジュールを同じデータ構造に入れたり動的に入れ替えて使ったりなどはできない。

これまでの三記事をまとめると

モジュール

シグニチャで隠蔽することで抽象型を作成し、抽象的データ型のように内部実装は触れずインタフェースを通してのみ操作できるデータを提供できる。その場合隠蔽された抽象型と、提供されたインタフェースが「存在型」的となる。動的な入れ替えを含めた「同一インタフェースを持つモジュールを統一的に扱う」といった処理はファンクタ・第1級モジュールを使わないとできない。

ファンクタ

ファンクタ内部では、引数モジュールをシグニチャのインタフェースを通してのみ操作できる、という制約によって同じコードで「同一のインタフェースを持つ(≒特定の存在型に属するモジュール?)モジュールなら何でも扱える」パラメトリック性を持つ。ただし完全に静的な挙動でファンクタを特定のモジュールに適用して新しいモジュールを作成する必要があり、動的な入れ替えなどはできない。その分、t型のデータを返す(t型がファンクタ外部にリークする)ような関数も書くことができる。

第1級モジュール

「存在型で拡張されたシステムF」の挙動と合致させることができる(ただし第1級モジュールでは抽象型がないシグニチャを使うこともでき、その場合は存在型にはならない)。pack/unpackに個別に相当する構文let m = (module M : T)let module M = (val m)が存在し、モジュールをそのままデータとして扱える。例えばリストなどのデータ構造に異なるモジュールをデータ化したものを入れたり、引数を「特定のシグニチャに合致するデータ化されたモジュール」とすることで関数を「モジュールにパラメトリック」にすることができる。(ただし「モジュールにパラメトリック」な関数はt型を返すことはできない。これも「存在型で拡張されたシステムF」と同じ挙動だ)

というわけで

  • 完全に存在型に合致した挙動が欲しいなら第1級モジュール
  • 実装を隠蔽した抽象的データ型が欲しいだけならモジュール、
  • モジュール選択は静的に解決されるが「存在型」的なインタフェースにパラメトリックなコードを書きたいならファンクタ

という使い分けになるかと思う。実際のOCamlプログラミングで第1級モジュールが必要となるのは稀な印象だ。

ちなみに存在型をそのままエンコードするだけが目的ならモジュール機構に頼る必要はなく、GADTでもできる。

次回はその話。