日本ソフトウェア科学会第 31 回大会 (2014 年度) 講演論文集

分割できながら等価：型レベル・エイリアス
Jacques Garrigue

OCaml のモジュールシステムは強力だが、名前空間の形成に使うと様々な問題点がある。まず、入れ子モジュールで階層化しようとすると、ファイル分割ができなくなるという問題。また、それを諦めて同じモジュールを複数の名前空間にコピーすると、一部の等価性が失われたり、型情報が異常に大きくなったりする。OCaml 4.02 に導入された型レベル・エイリアスはモジュールへのリンクを型情報に記録することでそれらの問題の解決に貢献している。

存関係が回避され、最適な分割コンパイルが可能に

1 背景なっている。コンパイル単元とそのインターフェース

ML のモジュールシステムが強力で、少なくとも理の組を不透明なシグネチャーを備えたモジュールとし論的には言語に名前空間のための特別な機構などをて捉えることができるので、この仕組みを言語の意味加えなくても、ライブラリーが柔軟に構成できるはず論の中で解釈することもできる。どの時点でどのファである。入れ子モジュールが階層化を可能にし、ファイルを再コンパイルするかはユーザ（あるいはビルドンクターが柔軟なリンク機能を提供している。

システム）に任されているが、コンパイルされたファ

しかし、これが言語の内側で正しくても、モジュールシステムのみでライブラリーの全ての問題が扱える

イルの中に依存する単元のシグネチャーのハッシュ値を含むことで一貫性が保証される。

訳ではない。処理系が解決しなければならない問題と残念ながら、この単純さには欠点がある。ファイルして、モジュール名をどうライブラリーファイルに結システム上にコンパイル単元を探すときは名前しかびつくか、そしてどうやって再コンパイルが少ない形考慮されないので、入れ子のないモジュール空間がでで分割コンパイルをサポートできるかが上げられる。

きてしまう。特に、あるモジュールの中に同名のサブ

OCaml [6] が採用したアプローチは至って単純であモジュールを二つ以上定義できないのと同様に、一つる。ローカルに束縛されていないモジュール名がファのプログラムの中に同名のコンパイル単元を二つ以イルシステム上に同名のファイルとして検索される。

上組み込むことができない。複数のライブラリーを利ファイルの配置を自由にするために、ライブラリーパ用するプログラムに取って、大きな枷になる。

スというフォルダーのリストが使われている。そうObjective Caml 3.05 以降、複数のコンパイル単元

いった外部モジュールはコンパイル単元 (compilationを集約単元 (packed unit) のサブモジュールとしてまunit) と呼ばれる。各コンパイル単元に対して、中味とめることで、この問題を回避できるようになった。のシグネチャーだけを含んだインターフェースファイ

しかし、この方法では、集約単元が元のコンパイルルを用意することで、コンパイル単元同士の直接な依単元に置き換わる形になり、全てのサブモジュールのコードが含まれる。一つのサブモジュールを使うた

Type-level module aliases: independent and equal†1Jacques Garrigue, 名古屋大学多元数理科学研究科, Graduate School of Mathematics, Nagoya University.
†1 この論文は [4] の日本語訳に基づいている。

めに、集約単元全体をプログラムに組み込まなければならず、プログラムが大きくなる。この意味では、集約単元は分割コンパイルに逆行していると言える。

ただし、分割できないのはコンパイルではなく、集約module StringSet1 = Set.Make(String)

後の単元である。

module StringSet2 = Set.Make(String)Standard ML の実装の SML/NJ では、全く異なる方法が選ばれた。コンパイルの実行およびライブ

module S = String
module StringSet3 = Set.Make(S)

ラリーの名前空間はコンパイル・マネジャー [2] [1] とOCaml のファンクターは適用型なので、ファンクターいうツールに任されている。コンパイル・マネジャーの結果の中に現れる個性を持った (nominal な) 型のは専用の構文で書かれた特殊なファイルによって、モ等価性はファンクターの引数の等価性によって決まる。

ジュール名とライブラリー内の実装のマッピングやコ

具体的には、ここで StringSet1 と StringSet2 で同ンパイルされたライブラリーのファイルシステム上のじ引数 String が適用されるので、 StringSet1.t と位置を知る。この情報によって、再コンパイルを最適StringSet2.t は等しくなる。しかし、StringSet3 で化できるだけでなく、モジュール名をライブラリー内は引数が S なので、StringSet1.t と StringSet3.tに隠蔽することで名前の衝突も避けられる。後からが等しくならない。従来の OCaml では S と String

外に見える名前を変えることも可能である。この豊が等しいを型レベルの情報として残すことができなかな表現力のお陰で、コンパイル・マネジャーはファかった。

イルシステムに基づいた方法の諸問題を回避できる。
しかし、そのために ML の意味論に含まれない新し型レベル・エイリアスがあると、モジュール定義

module S = String のシグネチャーはい言語が導入されている。
この二つの方法を見ると疑問を抱かざるを得ない。

ML のモジュールシステムの表現力が非常に高いと言われているのに、なぜ実際のプログラムの名前空間の問題を解決するために別の機構を必要とするのか。
型レベル・エイリアスはシグネチャーの中にモジュー

module S = String
あるいは、単集合カインドを意識した記法で、

module S : (module String)になり、S と String が型レベルでも等価になり、StringSet1.t と StringSet3.t が等しくなる。

ルのエイリアスを宣言できるようにするモジュールシ

それを可能にするために、型の等価性は型定義のステムの小さな拡張である。それを使うと、分割コン展開だけでなく、型レベル・エイリアスを考慮したパイルを失わない形で名前空間は自由にモジュールをモジュール・パスの正規化も使う、より強い方法に変使って構成できる。適用的ファンクターの等価性を強わる。

化するという別のメリットもある。型レベル・エイリ
アスは OCaml 4.02 以降のバージョンで使える。

2 等価性のためのエイリアス

3 分割のためのエイリアス
この強化された等価性は役に立つものの、それをフルに活用するために再帰モジュールを含む型システム

型レベル・エイリアスは分割コンパイルと全く違うの大規模な変更が必要なので、OCaml への導入が見方面から現れた概念である。元々、中田と Garrigue送られて来た。しかし、エイリアスにはもう一つのメの Traviata [8] において、再帰モジュールの型推論をリットがある。型によって与えられた情報はコードに可能にするための機構として導入された。後から、こは要らないということに着目し、コンパイルされたの機構が OCaml 流の適用型ファンクターの等価性のコードの一部が削られる。それをすると、依存関係が問題をいくつか解決できることが確認された [3]。次少なくなり、分割コンパイルが強化される。この応用の例では、Set.Make を要素の比較関数をもらい、集を主な目的とすれば、型システムの小さな変更でも十合を表す抽象データ型 t とそれを扱うための関数を分対応できる。

返すファンクターとする。

次のコードをコンパイル単元 Mylib の中味とする。

module A = MylibAがエイリアス先の中味に依存しないので、MylibA とmodule B = MylibB

MylibB の中で open Mylib と書いてもいい。これにA と B のエイリアスはシグネチャーに現れるので、Mylib のコンパイルした実装は MylibA と MylibB を参照しなくても良い。すなわち、Mylib 自身は MylibA

よって依存関係に巡回が生じない。
まとめると、以下のレシピーを使えば集約単元をエイリアスを使った分割可能な構造に変えられる。と MylibB に依存しない。結果的には、Mylib.A を1. 各単元の名前をライブラリー名を含む長いもの使って、Mylib.B を使わないようなプログラムはMylibA のみを組み込めばいい†2 。集約単元が分割で2. 全てのコンパイル単元に対して短い名前を与えきない問題がこれで回避できる。さらに、ここでは、るインターフェイス用のコンパイル単元を作る。

Mylib のコンパイルされた実装が空なので、こちらも3. このコンパイル単元を他の全ての単元で open組み込まれない。に変える。

する。

シグネチャー間の依存関係を減らすこともでき

4. 見せたい単元のエイリアスだけを含めたエキスる。Mylib のシグネチャーの型をチェックするとき、ポート用のインターフェイス単元も作る。(隠すMylibA と MylibB のシグネチャーを参照する必要はものがなければ、(2) と同じもので良い)ない。結果的には、Mylib のコンパイルされたシグネ集約単元の作り方に近づけるために、OCaml 4.02 でチャーは MylibA と MylibB と完全に独立している。

はコンパイラが新しい -open オプションを受け付け後者が変わったときに Mylib を改めてチェックする必るようになった。それを使えば、(3) が不要になる。

要がなく、Mylib を先にコンパイルすることさえ可能

インターフェイス用のコンパイル単元は通常のコである。ライブラリーを階層化するときにこの特徴がンパイル単元である。マッピングを与える以上のこと役に立つ。

をしても良い。例えば、エキスポートされたインターフェイスに入れ子のサブモジュールを使い、より深い4 名前空間への応用階層化を行う。または、同じエイリアスを何度も使

上記の説明から、既にモジュール名の衝突を避けるい、複数のビューを与えることもできる。型レベル・方法が分かる。ライブラリーを作るときに各コンパエイリアスは単なる論理的なポインターでしかない

イル単元の名前にそのライブラリー固有の名前を含ので、コストが生じない。

めておけばいい。利用をスムーズにするために、上以前から、Jane Street 社が開発している汎用ライの Mylib のように、各コンパイル単元の略称を与えブラリー Core/Async [5] ではモジュールによる名前るコンパイル単元を用意すればいい。そうすると、利空間の構成法が使われて来た。元々、集約単元で名用するソースの先頭に open Mylib という一行を加前の衝突を防ぎ、階層化で機能を整理していた。しえるだけで、各モジュールが短い名前で参照できるよ
うになる†3 。

かし、この方法では多くのコンパイル単元のシグネ

これで、利用側の問題が解決される。しかし、定義ため、リンクされたプログラムが大きくなる上、コン中のライブラリーの中でも、他の単元を短い名前で参パイル時間も問題になるほど長くなっていた。コード

照したい。ありがたいことに、Mylib のシグネチャーを全く変えずに、OCaml 4.02 に切り替えるだけで、チャーと実行コードが一つの集約単元にまとめられる

各ライブラリーのシグネチャーのサイズの合計を 1/3†2 厳密には、依存関係をなくすと MylibB が副作用を含んだ場合にプログラムの動作が変わる。そのせいで、依存関係をなくす機能は -no-alias-deps オプションを指定したときにのみ有効である。
†3 Standard ML と異なり、OCaml では open がモジ
ュールの中味をローカルな環境に加えるだけで、定義中のモジュールのシグネチャーには加えない。に減らすことができ、その分コンパイル時間も早くなる。さらに、上に書いたような手法がコードベース全体に適用された。そうすると、リンクされたプログラ
ムの大きさは合計で半分になった [7] [9]。（短いプログラムでは 1/10 の場合もあった)た、実験とデバッグに協力してくれた Jane Street 社

5 制限と今後の課題の社員達に感謝する。

型レベル・エイリアスの導入は型と実行コードの両方にまたがるため、かなり大きな拡張である。それを参 考 文 献最低限の規模に抑えるために、OCaml 4.02 における

[1] Blume, M.: CM: The SML/NJ Compilationand Library Manager, Lucent Technologies, BellLabs, May 2002. http://www.smlnj.org/doc/CM/new.pdf.
[2] Blume, M. and Appel, A. W.: Hierarchical modularity, ACM Transactions on Programming Languages and Systems, Vol. 21, No. 4(1999), pp. 813–847.
[3] Garrigue, J. and Nakata, K.: Path resolution forrecursive nested modules, Higher-Order and Symbolic Computation, Vol. 24(2012), pp. 207–237.
[4] Garrigue, J. and White, L.: Type-level module
aliases: independent and equal, ACM SIGPLAN
ML Family Workshop, September 2014.
[5] Jane Street: Open Source software. http://janestreet.github.io/.
[6] Leroy, X., Doligez, D., Frisch, A., Garrigue, J.,Rémy, D., and Vouillon, J.: The OCaml system release 4.01, Documentation and user’s manual, Projet Gallium, INRIA, September 2013.
[7] Minsky, Y.: Better namespaces through module aliases, May 2014. https://blogs.janestreet.
com/better-namespaces-through-module-aliases/.
[8] Nakata, K. and Garrigue, J.: Recursive modules for programming, Proc. International Conference on Functional Programming, Portland, Oregon, 2006.
[9] Shinwell, M. and Chapman, N.: Personal communication, May 2014.

型レベル・エイリアスの実装は型レベルに反影されるモジュール・エイリアスに多くの制限を加えている。
具体的には、以下のモジュール式へのエイリアスは型レベルに反影されない。

• モジュールパス以外の式 (ストラクチャーおよびファンクター)• ファンクターの適用を含むパス• 不透明な型注釈• ファンクターの引数として導入されたモジュー
ル変数を頭とするパス• 定義中の再帰モジュールを頭とするパス
一つ目の制限は本質的である。それを許せば言語全体をシグネチャーの中に書くことになる。しかし、他の制限は型検証アルゴリズムの強化で解除できるはずである。それを行えば、この機能はよりエレガントなものになるだろう。

謝辞
分割コンパイルへの応用について、ケンブリッジ大学の Leo White に多くのアイデアをいただいた。ま