Alice MLのモジュールシステム

Alice MLとは、Standard MLをベースにした言語であり、平行性や制約プログラミングなどをサポートしているのが特徴です。今回はAlice MLのモジュールシステムを取り上げます。

なお、この文書でStandard ML 97と言うときは、The Definition of Standard ML (Revised) [1]で定義された言語を指します。

対象読者: ML系言語に慣れていると読みやすいと思います。

MLモジュール速習ガイド

MLのモジュールシステムの基本要素はストラクチャ、ファンクタ、シグネチャの3つです。その内ストラクチャとファンクタをまとめてモジュールと呼びます。シグネチャはモジュールの型です。

局所的なモジュール定義

Standard ML 97とは違って、Alice MLではlet式内でモジュールやシグネチャを定義することができます:

fun f x =
let
  structure M = struct
    val v = 1
  end
in
  M.v + x
end

これは、ファンクタ適用や、後述するパッケージの利用に役立ちます。

高階ファンクタ

MLのモジュールシステムの文脈では、ファンクタ (functor)といえばモジュール上の関数のことです。ファンクタを引数に取ったり、結果として返すようなファンクタを高階ファンクタ (higher-order functor)と呼びます。一方、ストラクチャを引数に取り、ストラクチャを返すファンクタを1階ファンクタ (first-order functor)と呼びます。Standard ML 97では1階ファンクタのみがサポートされていますが、Alice MLでは、さらに高階ファンクタもサポートされています。次のコードでは、ファンクタFは「シグネチャS -> Tを持つファンクタを受け取り、シグネチャS -> Tを持つファンクタを返す」ファンクタです。

signature S = sig
  type t
end

signature T = sig
  type u
end

functor F (X : S -> T) (Y : S) = X Y

シグネチャの束縛

Standard ML 97において、シグネチャの定義はトップレベルでしか許されていませんでしたが、Alice MLではストラクチャ内やシグネチャ内でも可能です。

structure M : sig
  signature S = sig
    type t
  end
end = struct
  signature S = sig
    type t
  end
end

signature T = M.S

最後の行は「ストラクチャ内で定義されたシグネチャには、M.Sのようにアクセスできる」ことを示しています。(ちなみに、Moscow MLでもストラクチャ内でのシグネチャ定義が可能ですが、ストラクチャ内のシグネチャへアクセスする手段が一切無いせいで非常に不便です。)

抽象シグネチャ

Alice MLでは抽象シグネチャがサポートされています。これにより、多相的なファンクタを定義できるようになります。次のコードでは、多相的な恒等ファンクタIdを定義しています。

functor Id (X : sig
  signature S
  structure M : S
end) : X.S = X.M

抽象シグネチャの存在は、Alice MLの型検査がOCamlと同様の理由で、決定不能であることを示します。OCamlの型検査器を実際に無限ループに突入させるコードを書いたRossberg本人が、Alice MLのモジュールシステムの設計を担当していたと見られるので、意図的に抽象シグネチャを導入しているのだと思います:

We do not consider this a problem in practice, since already the simplest program to make the type checker loop is highly artificial

遅延評価、非同期性

Alice MLでは、コア言語レベルで遅延評価と平行性をサポートしていますが、モジュールにも同様の機能があります。遅延評価は、モジュールの前にlazyキーワードを前置することで実現できます。

structure M = lazy struct
  val () = print "lazy"
  val x = 4
end

このモジュールを実行しても、何も出力されません。次のように、モジュールの中身が必要になったときに始めて"lazy"という文字列が出力されます:

val _ = M.x + 1

一方、非同期処理は、spawnキーワードによって行なわれます。次のコードはおそらく"spawn"という文字列を出力するでしょう。

structure M = spawn struct
  val () = OS.Process.sleep (Time.fromSeconds (LargeInt.fromInt 1))
  val () = print "wn"
end

val () = print "spa"

First-class packaged modules

Alice MLというのは、Standard MLをベースにしているので、基本的には静的型付き言語です。しかし、動的検査の利点も活用したい、という訳でパッケージという仕組みが入っています。パッケージはpackageという抽象的な型を持つ値であり、何らかのモジュールを包んでいます。パッケージからモジュールを取り出すには、明示的なunpackによって行なわれます。このとき、動的検査が発生します。もしパッケージが内包するモジュールのシグネチャが、期待するシグネチャにマッチしない場合、動的にエラーが検出されます。このようにパッケージは、モジュールを1級の値に変換してコア言語で操作することと、動的検査を実現します。

パッケージを作るには、pack M : Sという形の式を使います。この式はモジュールMをパッケージに変換します。MがシグネチャSにマッチすることは、静的に検査されます。

structure M = struct
  type t = int

  val z = 0
  fun f x = x
end

signature S = sig
  type t

  val z : t
  val f : t -> int
end

fun f x =
let
  structure N = unpack x : S
in
  N.f N.z
end

val _ : int = f (pack M : S)

unpack x : Sという形の式は、パッケージxから、Sをシグネチャとして持つモジュールを取り出します。xが内包するモジュールのシグネチャがSにマッチすることは動的に検査され、もしマッチしない場合は、実行時例外が発生します。もしマッチした場合は、unpack x : Sを「シグネチャSを持つモジュール」として扱うことができます。

unpackに対して付けるシグネチャ注釈は、unpack結果のモジュールに対して知ることのできる唯一の情報です。したがって先程のコードの、unpackを利用する関数を次のように変更すると、型検査を通過しなくなります。

fun f x =
let
  structure N = unpack x : S
in
  N.f M.z
end

M.zM.t型、すなわちint型を持ちます。一方、N.fN.t -> int型を持ちます。N.t型がint型と等しいという情報は、S内に表現されていないので、この関数適用を型付けることはできません。次のように、シグネチャ注釈をより具体的なものにすることで解決します。

fun f x =
let
  structure N = unpack x : S where type t = int
in
  N.f M.z
end

また、unpackでの動的検査はPackage.Mismatchという例外を発生させ得るので、通常の例外処理が行なえます:

fun f x =
let
  structure N = unpack x : S
in
  N.f N.z
end handle Package.Mismatch _ => 10

静的検査されるfirst-class packaged moduleとの差異

明示的にコア言語の1級の値に変換されたモジュールをfirst-class packaged moduleと呼びます。First-class packaged moduleを最初に実装した言語はMoscow MLであり、unpackは静的に検査されます。OCamlのfirst-class packaged moduleもMoscow MLと基本的に同じなので、静的に検査されます。

Moscow MLやOCamlと比べて、Alice MLでは全てのモジュールを1つのpackage型を持つパッケージに変換できます。Alice MLにおいて、次のような全く異なるシグネチャを持つ2つのモジュールを、パッケージに変換して1つのリストに入れることができます。これは、どのパッケージもpackageという唯一の型を与えられるからです。

[ pack struct val a = 1       end
     : sig    val a : int     end
, pack struct type b = string end
     : sig    type b          end
]

一方、Moscow MLやOCamlではそのようなことはできません。異なるシグネチャを持つモジュールからは、異なる型を持つパッケージが得られるからです。そのようにしないと、静的に型検査をすることができません。Moscow MLにおいて、次のコードは先程のリストの第1要素と第2要素がどのような型を持つかを示しています。

val p1 : [sig val a : int end] =
  [structure struct val a = 1 end as sig val a : int end]

val p2 : [sig type b end] =
  [structure struct type b = string end as sig type b end]

Moscow MLにおける[structure M as S]はAlice MLにおけるpack (M :> S) : Sに対応します。一方、[S]はシグネチャSのモジュールから得られるパッケージが持つ型を表します。ここで、p1p2は異なる型を持つので、Alice MLのように1つのリストに入れることができないのです。

また、静的検査されるパッケージは、部分型を適用できないので不便です。たとえば、fMONOIDシグネチャを持つパッケージを受け取る関数とし、p_stringSTRINGシグネチャを持つパッケージとします。STRINGMONOIDの部分シグネチャ、つまりより具体的なシグネチャとします。Moscow MLではfp_stringに適用するために、一度unpackしてまたpackし直さないといけません(ここで、Moscow MLのstructure M as S = xはAlice MLのstructure M = unpack x : S に対応します):

let
  structure M as STRING = p_string
in
  f [structure M as MONOID where type t = string]
end

一方、Alice MLでは単にf p_stringとすればよいので便利です。

参考文献

  1. Robin Milner, Mads Tofte, Robert Harper and David MacQueen. The Definition of Standard ML (Revised). MIT Press, 1997.