OCamlで存在型を試してみた （その２ーーファンクタ）

zehnpaard.hatenablog.com

の続き。

前回は第１級モジュールを非常に綺麗に存在型に対応させられることが示せた。

しかし第１級モジュールを使わずとも、OCamlだとモジュールのシグニチャ自体が存在型的だ。（ただし微妙だが重要な差異もある）

今回はファンクタを通してシグニチャを使うことと存在型の関連について。

ファンクタ

「同じインタフェースを提供するモジュールに対してパラメトリックなコードを書く」という必要がある場合、第１級モジュールを使う手もあるが、OCamlでのより一般的な言語機構は「モジュールを引数にモジュールを返す『関数的なもの』」であるファンクタである。

前回に続いてADDABLE_INTというシグニチャとそれに合致するnative intとペアノ数を使った実装の二つのモジュールを用意する：

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

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

module PeanoInt = 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

前回の記事にはなかった要素として、ゼロに対応する値zeroをシグニチャ・ストラクチャ両方に追加した。

これでt * intの掛け算を計算する関数をパラメトリックに定義できる：

module MakeMul (M : ADDABLE_INT) = struct
  let rec mul x n =
    if n = 0 then M.zero
    else if n = 1 then x
    else M.add x (mul x (n-1))
end

module MulInt = MakeMul(IntInt)
module MulPeano = MakeMul(PeanoInt)

utop # IntInt.to_int @@ MulInt.mul (IntInt.create 5) 6;;
- : int = 30

utop # PeanoInt.to_int @@ MulPeano.mul (PeanoInt.create 5) 6;;
- : int = 30

MakeMulファンクタはADDABLE_INTに合致するモジュールを受け取り、mul : t -> int -> t関数を持つモジュールを返す。 ファンクタの内部では渡されたモジュールがどんな実装になっているかはわからないので、インタフェースを通してのみ引数モジュールを使える。

というわけでファンクタの引数のシグニチャに抽象型（この例ではtype t）があれば、概ね存在型だと見做せる。

ただしTaPLで定義されている存在型で拡張されたシステムFの機能とは違うところもある：

1. ファンクタの中でも依然としてモジュールのままで値としてデータ構造に入れたりなどはできない
2. 引数となるモジュールごとに新しいモジュールが返されるので、ファンクタの外ではモジュールを統一的に使うことにはならない
3. ファンクタを使って作成したモジュールの関数から存在型のtype tがリークしてもいい

１に関しては「ファンクタ内に入る時点で引数のモジュールがpackとunpackを立て続けにされる」という見方もできる。なので途中経過であるpackされた値が出てこない（結果できることの自由度は下がる）。

２についてはMulInt.mul (IntInt.create 5) 6とMulPeano.mul (PeanoInt.create 5) 6と、結局別モジュールであることを明示しないといけないのがポイント。

３は重要なポイントで、TaPLに載っているシステムFの存在型拡張やOCamlの第１級モジュールを使うと、最終的な戻り値がtype tな関数は書けない。何らかの非多相的な確定した型（intとかstringとか）である必要がある。

それに対して例えばMulInt.mulが返すのはIntInt.t型だしMulPeano.mulが返すのはPeanoInt.t型である。ファンクタ内部では引数モジュールのtype tの実装に触れることはできないが、ファンクタの外に出てしまえば作成されたモジュールはしっかり引数モジュールのtype tにパラメータ化されている。

存在型で拡張されたシステムF、そして第１級モジュールに比べて、ファンクタはこの点に関してより自由度が高い・より表現力が強いとも言えるし、実装の隠蔽が弱いとも言える。

ファンクタの戻り値であるモジュールに対してもシグニチャを設定でき、そこで型を抽象化することもできる：

module MakeMul (M : ADDABLE_INT) : sig type t val mul : t -> int -> t end = struct
  type t = M.t
  let rec mul x n =
    if n = 0 then M.zero
    else if n = 1 then x
    else M.add x (mul x (n-1))
end

がこれをしてしまうと今度は引数モジュールのtype tと戻り値モジュールのtype tが一致しなくなってしまうので使い勝手が悪い。

utop # MulInt.mul (IntInt.create 5) 6;;
Line 1, characters 11-28:
Error: This expression has type int but an expression was expected of type
         MulInt.t

実装を隠蔽したいなら、ファンクタの方でシグニチャをいじるより、大元の引数モジュールのtype tを抽象型にしてしまった方がいい。

次回はそのモジュールとシグニチャと存在型の話。