2年ほど前からSML処理系を自作している。それがこの度、「動作するターゲットコード (Lua) を出力する」という重要なマイルストーンに到達したので記念に記事を書いておく。

この処理系については、2018年9月に開催された勉強会「ML Day #2」で進捗報告のLTをしたこともあった。（あれから2年も経ってまだこの段階かよ！）

• ML Day #2
  • 発表資料
• GitHub: minoki/DamepoML: A non-working implementation of Standard ML

動かす

1 + 2 をコンパイルするには次のように実行する。処理系としてはSML/NJを使っている（他の処理系で動くかは確認していないが、適当に御膳立てしてやれば動くのではないかと思う）。

$ git clone https://github.com/minoki/DamepoML.git
$ cd DamepoML
$ sml
Standard ML of New Jersey (64-bit) v110.98 [built: Tue Jul 21 22:13:05 2020]
- CM.make "sources.cm";
...
- val (a,b,c,d,e,f,g) = Driver.compile "1 + 2;";
...
- print(g);
local it_100 = table.unpack((function()
local exp_101 = (_PLUS_ATint_41)({[1] = 1, [2] = 2})
return (function()
if true then
return (function()
local it_100 = exp_101
return {[1] = it_100}
end)()
else
return (__raise_99)({})
end
end)()
end)())
val it = () : unit

Driver.compile の結果をタプルに代入したうちの g がLuaコードを含む文字列となっている。出力されたコードはLuaインタープリターを起動して実行するわけだが、現状、組み込み関数については事前に手動で定義しておく必要がある。

$ lua
Lua 5.3.5  Copyright (C) 1994-2018 Lua.org, PUC-Rio
> _PLUS_ATint_41 = function(t) return t[1] + t[2] end
> 

ここに、さっき出力されたコードをコピペする。ただし、結果を見る都合上、最初の local は省く。

> it_100 = table.unpack((function()
>> local exp_101 = (_PLUS_ATint_41)({[1] = 1, [2] = 2})
>> return (function()
>> if true then
>> return (function()
>> local it_100 = exp_101
>> return {[1] = it_100}
>> end)()
>> else
>> return (__raise_99)({})
>> end
>> end)()
>> end)())

無事にパースされた。あとは it_100 を出力すれば、演算結果である「3」が出力されるはずだ。

> print(it_100)
3

現状はできることはこのぐらいである（まだprint関数がないのでHello worldもできない）。見ての通り、出力されるコードは無駄が多いが、そういうのはこれから改良していくことになる。

処理系の目標

どうもこのブログでこのプロジェクトに触れるのは初な気がするので、目標とかの基本的なことから書いておこう。

このプロジェクトの目標は、ML Day #2でのスライドにも書いたが、次のような感じだ：

• Standard MLの処理系を作る。
• Lua（やJavaScript）など、スクリプト言語のコードを出力することを目指す。
  • GCやクロージャーを自前で実装しなくて良い。
  • TeXやPandocなどのLuaを採用している環境で、静的型やパターンマッチの恩恵を受けることができる。
• 将来的にはセルフホストを目指す。

流れ

現在の処理の流れは次のようになっている：

• 字句解析
• パース（この段階では演算子の優先順位は処理しない）
• パースの後処理（演算子の優先順位を処理する）
• AST変換（パターン中の識別子が変数かコンストラクターか判断する）
  • この変換の際に、構文木の要所要所に型（単一化で使う型変数）を埋め込むようにする。
• 型推論
  • ついでに、 val <pattern> = ... を変換して左辺が単純な変数 or タプルへのマッチとなるようにする。
• 型が曖昧だった部分にデフォルトの型（int など）を当てはめる
• equality typeの脱糖（比較関数を引数として受け渡すようにする）をしつつ、System Fライクな表現へ変換する
• パターンマッチの脱糖
• Luaコードの出力

この2年は型推論とそれ以降の部分を実装していた、ということになる。

後回しにした方が良かった機能

「機能は最小限でいいからとりあえず動くものを作る」というのは趣味プロジェクトのモチベーション維持の上で非常に重要である。この自作SML処理系では、SMLの実装を目標として最初から色々考慮してしまったせいで、いつまで経っても動作まで辿りつかない、という状態に陥ってしまった。

SMLは機能が豊富すぎた。「SMLの実装」というプロジェクトを仮に0からやり直すとすれば、もっと大胆に機能を削ったサブセットから出発するべきだっただろう。

具体的には、最初の動くコードを出力できるようになるまでは

• 識別子の演算子化や、演算子の優先順位の設定を省略する。
  • SMLでは演算子の優先順位と結合性をプログラマーが指定できる（この機能はHaskellにもある）。しかし、パースの簡略化を考えれば最初は「演算子の最初の文字で優先順位を決める」という（OCamlライクな）仕様で良いと思う。
  • SMLは、任意の（アルファベット始まり、または記号列から成る）識別子について「中置演算子か否か」を指定できる。パースの簡略化を考えるとこれは面倒なので、最初は「中置演算子か否か」は処理系にハードコードしておくので良いと思う。（一方Haskellは、アルファベット始まりの識別子を中置で使うには一律でバッククォートで囲むことになっているので、偉い）
• ユーザー定義のデータ型は省略する。Hello worldには必要ないので。
  • ユーザー定義のデータ型を実装するとしても、letや関数の内部で定義できるする必要はあるのかね？
• 変数束縛の左辺には単純な変数名（もしくは、せいぜいワイルドカード）しか書けないようにする。
  • val SOME foo = bar みたいなやつを書けなくしよう、というやつ。この辺は型推論の簡略化 vs 複雑化に繋がる。ターゲット言語にはパターンマッチがないことを考えると、コード生成も面倒になる。
• 演算子オーバーロードは後回しにする。
  • SMLには等号に関する型変数のあれこれと、算術演算子のアドホックな型付け規則がある。これらがあると、当然型推論が複雑になる。
  • 筆者は型理論的な興味から欲張って演算子オーバーロードを実装した。eqtypeはHaskellの型クラスの辞書渡しみたいな感じで実装した（辞書じゃないけど）。
• データ構築子か否かは構文的に決まっていた方が良い（Haskellは最初の文字で決まるようになっているので偉い）が、それをやるとSMLのサブセットじゃなくなりそうなので困るなあ。
• local宣言は面倒。
  • かといってlocal宣言を考慮するか否かでは一部の関数の設計が変わってきそう。
• モジュール周りの省略は誰でも考えるだろうし実際筆者もそうしている。

という感じにした方が良いと思う。ていうかML系言語実装初心者はSMLはやめとけ感がある。

まあ最初から何でもかんでも省略してしまうと、後でそれらを本実装することになった時に手戻りが発生しそうである。その辺の按配は実際にやってみないとわからなさそうだが…。

まとめ

俺たちの戦いはまだ始まったばかりだ！（2回目）