LunarMLを含む多くのStandard MLコンパイラーはStandard ML自身で記述されています。すでに動くStandard ML処理系があればSMLで書かれたコンパイラーを動かせますが、Standard ML処理系のない新しいプラットフォームでStandard MLコンパイラーを動かしたい場合はどうすればいいでしょうか？
まあ現実的には「すでにStandard ML処理系が動く環境でStandard ML処理系を動かして、新しいプラットフォーム向けにコンパイル（クロスコンパイル）する」あるいは「ポータブルな中間言語向けに事前にコンパイルしておく」となるでしょう。例えば、Poly/MLは配布されるソースの中に、事前に用意されたバイトコードが含まれます。SML#はLLVM IRへコンパイルされたSML#を配布しています。
信頼の問題
この場合いずれにしても、Standard ML処理系が動く環境、特にStandard ML処理系のバイナリー（非テキスト形式という意味ではなく、コンパイル済み生成物という意味）が必要にあります。コンパイルされたバイナリーというのは人力での検証が難しく、果たしてコンパイル済みのSML処理系のバイナリーは信頼できるのでしょうか？信頼されないコンパイラーでコンパイルされたバイナリーは信頼できないので、コンパイル済みSML処理系のバイナリーが信頼できるためには、それをコンパイルしたSML処理系のバイナリー、その処理系をコンパイルしたSML処理系のバイナリー、それのさらに先祖が信頼できる必要があります。
別の言語で書かれたStandard ML処理系という案
こういう風に考えると、「別の低レベル言語で書かれたSML処理系」があると良いのではないかという気持ちになります。「別の低レベル言語」としては、C言語が無難な選択肢です。ガチなbootstrap界隈ではアセンブリー言語やForthが使われることもあるというのをどこかで見ました。まあ今回はそこまで考えません。
というわけで、「C言語で記述されたSML処理系」を作りたいなあという気分になっています。C言語ならおそらく「信頼できる」コンパイラーがありそうですし、新しいプラットフォームにも真っ先に移植されていそうです。
型推論をどうするか
C言語で記述されたSML処理系は主目的が「他の（SMLで記述された）SML処理系を動かすこと」なので、SMLのフル機能を実装する必要は必ずしもありません。具体的には、型推論を省けないか考えたいです。
他の言語、例えばHaskellは実行時の評価のために型推論が必要です。なぜなら、型クラスによるオーバーロードがあるからです。ですが、Standard MLには型クラスはありません。なので、型注釈を全て無視してもある程度実行はできます。留意が必要なのは以下の3つです：
- 等価性判定
=のオーバーロード：LunarMLではこれは型情報を使ってコンパイルしています。型クラスの辞書渡しと同じ感じです。ですが、この戦略は必ずしも必要ではなく、値にタグを持たせれば型情報なしでもコンパイル・実行できます。実際、いくつかのSML処理系では値のタグを使っているようです。 - 演算子のアドホックなオーバーロード：
+という関数はint * int -> intという型がつくかもしれませんし、real * real -> realという型がつくかもしれません。 - リテラルのアドホックなオーバーロード：
123みたいな定数はInt.intという型がつくかもしれませんし、Int8.intという型がつくかもしれません。
まず、等価性は値のタグを使えば良いでしょう。演算子のアドホックなオーバーロードも、入力の値のタグを使えばなんとかできそうです。
問題は、リテラルのアドホックなオーバーロードです。一つの戦略は、すべてデフォルトの型として扱うということです。123 を見たら全て int だと思い、0w123 を見たら全て word だと思うのです。デフォルトの int は多倍長整数とすれば、不必要に Overflow 例外が発生することもないでしょう。HaMLetの評価器はこの戦略を採用しているようです。
「すべてデフォルトの型として扱う」やり方には、動かしたいSMLコードが Int8.int のような型を参照していると困るという問題があります。128 * 128 : Int8.int が例外を投げなかったら、標準的な処理系での動作と型推論なしの処理系での動作が食い違うことになります。例外の有無だけでなく、例外を起こさない 0w128 * 0w2 = 0w0 のような式の評価結果も変わってしまいます。
この問題の対処法を考えます。
- 動かしたいコードを書き換えて、型注釈
128 : Int8.intの代わりにasInt8 128というような関数適用にしておく。asInt8は受け取った値にInt8というタグをつけて、以後の演算ではそれを尊重する。 - 動かしたいコードを書き換えて、整数型のサイズが
IntInf.intとLargeWord.wordさえあれば動くようにしておく。浮動小数点数や、WideChar系の型は使わない。 - 事前に他のStandard ML処理系を使って動かしたいソースコードに関する部分的な型情報を用意しておく。つまり、ソースコード中の各リテラルについて「
foo.smlの123行目にある456というリテラルはInt32.intという型である」というような情報を用意しておく。この情報はプログラムの動作を大きく変えるものではないため、「他のStandard ML処理系」が信頼できなくても構わないということにする。型推論を行わないミニマルな処理系は、この情報を使って実行する。 - 諦めてC言語で真面目に型推論を実装する。あるいは、「リテラルの型を決定するのに必要な最低限度の型推論」を実装する。
自分が書いたStandard ML処理系（LunarML）であれば「動かしたいコードを書き換えて」という選択肢が使えるでしょう。一方で、SML/NJやMLtonなどの他人の書いたSML処理系を動かしたい場合は、後ろ2つの選択肢が必要になりそうです。
LunarMLはどうするか
「C言語で書かれたSML処理系」の話を長々としましたが、LunarMLとしてはまずは自分自身をそれなりの速度で動作させられるようになるのが先決です。現状、LunarMLは自分自身をLuaやJavaScriptへコンパイルできますが、そうやってできたスクリプト版LunarMLは非常に低速で、普段使いはできません。できればネイティブコード、その前にSML向きのバイトコードへコンパイルしたいです。
それができたら、LunarMLの配布物の中に「C言語で書かれたVM」と「コンパイル済みのバイトコード」を含めて、C言語の動作環境さえあればLunarMLを動作させられるようにしたいです。信頼性の問題は、「MLton等のコンパイラーでコンパイルしたLunarMLで生成したバイトコード」と「（他のコンパイラーでコンパイルした）LunarMLで生成したLunarMLで生成したバイトコード」が一致すれば良しとします。また、そもそも「プレーンテキストで書かれたソースコードであっても、規模が大きいと人力で全て確認するのは難しいのではないか」という問題もあります。
そういえば、LunarMLでHaMLet以外のSML処理系（SML/NJやMLton）が動作するのかまだ試していません。LunarMLでSML/NJやMLtonが動くようになったら「LunarMLさえ動けば他のSML処理系も動く」状態になります。
そんなことを考えていたら、RustのコンパイラーをC言語で実装しようとする人の記事が（SNSに）流れてきました。すごい。