LunarML進捗：functorの実装

コメントを残す

LunarMLの進捗と妄想 の続き。「SML ’97の言語機能を一通り実装する」という重要なマイルストーンを達成したので報告する。

目次

signatureの実装

まず、前回未実装だったopaque constraintを実装した。

中間言語のレベルではopaque constraintは存在型のpack/unpackとして実装される。

structure A = struct
  type t = int
  type u = string
  val x : t
  val y : u
end :> sig
  type t
  eqtype u
  val x = 42
  val y = "foo"
end

という風なSMLのコードは疑似コードで書けば

unpack (type t, tmp0) = let val x = 42
                            val y = "foo"
                            val S = { x = x, y = y }
                            val S = pack (type string, (op = : string * string -> bool, S)) : ∃u. (u * u -> bool) * { x : int, y : u }
                        in pack (type int, S) : ∃t. ∃u. (u * u -> bool) * { x : t, y : u }
                        end
unpack (type u, tmp1) = tmp0
val (eq_u, A) = tmp1

という風に展開される。LunarMLでは等価性比較を明示的に値として受け渡すようにコンパイルするので、equality typeを持つsignatureの場合は型だけではなく比較演算もpack/unpackされる。

標準ライブラリーのTextIOのinstream/outstreamでもopaque constraintを使うようにしてみた（以前はvalue constructorを隠したdatatypeとして実装していた）が、不要コード削除（dead code elimination）が十分ではないためinstream/outstreamを使わない場合でも出力コード中に関連するコードが残ってしまう。最適化の一環として型に対するインライン化のようなことを行い、unpack/packをなるべく除去する必要があると思われる。

functorの実装

opaque constraintを実装するついでにabstypeやstructureのsharing等の細々したderived formも実装したので、SML ’97の言語機能のうち残すところはfunctorのみとなった。そして、この数日間でfunctorの実装を行なった。

functorが返すstructureでは、functorの引数に与えた型を参照できる。functorのコンパイル後は、functorの引数の型については全称量化が行われる。例えば、

functor Foo (type t
             eqtype u
             val x : t
             val y : u
            ) = struct
  ...
end

なら

val Foo : ∀t. ∀u. (u * u -> bool) -> { x : t, y : u } -> { ... }
  = fn (type t) => fn (type u) => fn eq_u => fn { x : t, y : u } => ...

という風な中間言語にコンパイルされる。

opaque constraintが実装済みならfunctorの実装くらい2〜3日でできる、と言いたいところだったが、実際にやってみると実装済みの部分のリファクタリングやバグ修正も必要になり、結局4日くらいかかってしまった。

今後やること

SML ’97の言語機能は大体カバーしたといはいえ、まだ実用的なコンパイラーには程遠い。

複数ファイルのコンパイル：ML Basis System

Standard MLの仕様では分割コンパイルというものをきちんと規定していない。複数のSMLファイルをまとめてコンパイルするというのは処理系依存な行為になる。

例えばSML/NJやMLtonは複数のSMLファイルを連結してコンパイルする方法を提供し、SML#は.smiファイル（インターフェイスファイル）を使うことにより真の分割コンパイルを提供している。

このうちMLton（およびML Kit）が採用しているのがML Basis Systemというものである。こいつは単にファイルを連結するだけではなく、infix statusやsignature/functorを含めた環境に対するアクセス制御ができる。つまり「ライブラリーの中でだけ使うsignatureやfunctorを定義する」というようなことができる。もっぱら「標準ライブラリーの実装の内部で使う諸々を隠蔽できる機能」と言っても差し支えないかもしれない。

LunarMLでもML Basis Systemを採用しようと考えている。LunarMLは中間オブジェクトファイルを作らずに一気に出力ファイル（Lua）を書き出す設計のため、SML#のような分割コンパイルを採用する意義は薄いと判断した。

気になるのが条件コンパイルである。LunarMLでは今後Lua 5.3以外にも色々なターゲットを提供する予定である。その際に条件コンパイルができると嬉しい。MLtonのML Basis Systemではpath mapという仕組みによって読み込むファイルを変えることができる。MLtonの場合はTARGET_ARCHやTARGET_OSという変数によって条件コンパイルっぽいことができる。

LunarMLの場合はTARGET_LANGみたいな変数を導入することになるのか、あるいは独自にMLBを拡張して（標準ライブラリーの実装だけで使うことを想定した）条件コンパイルの仕組みを作るか……。そこはまだわからない。

標準ライブラリーの充実

Standard MLの標準ライブラリーは Standard ML Basis Library で色々規定されており、LunarMLが現段階で実装しているのはそのほんの一部である。実用的なプログラムを書けるようにするためにはもっと拡充していかなければならない。

しかしLunarMLの標準ライブラリーを収めたmlbasis.smlはすでに1300行を超え、ファイル分割したくなっている。なので、本格的な拡充はML Basis Systemを実装した後になるだろう。

パターンマッチの改良

現状のLunarMLではパターンマッチの網羅性検査や冗長性検査を行なっていない。また、コンパイル方法は「ifの羅列」で、あまり効率を意識したものではない。

パターンマッチについては最近κeen氏が

という本を公開したので、それを参考に改良を図りたい。

ただ、LunarMLではSuccessor MLの機能も取り込んでいきたいと考えており、そのためにはor patternやパターンガード等を実装することになる。これらの拡張機能の実装は自分で考えるか、論文を漁るかすることになるだろう。

また、ターゲット言語にgotoがあるかどうかでコンパイル方法も変わってくるだろう。最近のLuaにはgotoがあるが、JavaScriptにはない。なのでgotoに頼らないコード生成の方法も考えておく必要がある。

おまけ：パターンの網羅性とidentifier status

LunarMLではパターンの網羅性検査を行なっていないと書いたが、実は一箇所だけパターンの網羅性検査を行なっている部分がある。val宣言だ。

Successor MLでは、val宣言でgeneralizationが起こるのは左辺が網羅的な時に限る、としている。LunarMLでもこれに従うので、型検査の際に網羅性検査が必要となる。

網羅性検査とはいえ、対象となるパターンは単一なので、出現するコンストラクターがその型の唯一のものであることを確認すれば良い。ではどうやって「値コンストラクターがその型の唯一のものである」ことを確認するか。

これまでのLunarMLでは、環境の中に型名（TyName）に対する値コンストラクターの一覧（ValEnv）を持たせていた。しかし、本来TyNameが持つ属性というのは型引数の個数（arity）とequalityだけで、TyNameに値コンストラクターの一覧を持たせるのは構造として歪だった（一方でTyConの方には元々ValEnvが紐づいている）。

今回のリファクタリングでは、「値コンストラクターがその型の唯一のものであるか」を型ではなく識別子の方に持たせることにした。識別子には元々identifier statusという属性（value identifier / value constructor / exception constructor）が紐づいているが、このidentifier statusを表す型の定義を

datatype IdStatus = ValueVariable
                  | ValueConstructor
                  | ExceptionConstructor

から

datatype IdStatus = ValueVariable
                  | ValueConstructor of bool (* is it the sole constructor? *)
                  | ExceptionConstructor

に変え、value constructorが唯一のものであるか表せるようにした。なおexception constructorに対するマッチは唯一のものにはなり得ないのでいじる必要はない。

余談だが、SMLでは矛盾したsignatureを書くことができる。例えば次だ：

signature S = sig
  datatype t = T
  datatype u = U
  sharing type t = u
  val x : t
end

このSというsignatureのtという型については値コンストラクターについて相反する二つの規定があるため、いかなるstructureもマッチしない。しかし、functorを使うと矛盾した型についてパターンマッチをコード上で試みることができる：

functor F (S : S) = struct
  val _ = case S.x of
              T => "T"
            | U => "U"
end

コンパイラーはこのfunctorをどうコンパイルするべきか。試したうち、いくつかのコンパイラーではパターンマッチがredundant扱いされた（SML/NJ, HaMLet, Poly/ML）。MLtonは警告を出さなかった。SML#はそもそも矛盾したsignatureについてエラーを出した。

まあこのfunctorは決して呼ばれることはないし深く考える必要はないのだが、コンパイラー作成者として頭の片隅に入れておきたい。

このエントリーをはてなブックマークに追加

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です