自作SML処理系で 1 + 2 がコンパイルできた の続き。
ここ最近、自作SML処理系の作業を進めている。具体的には
print : string -> unitを実装したので Hello world! ができるようになった。- これまではSML/NJのREPL上で自作コンパイラーを動かしていたのに対し、MLtonでコンパイルすることにより単体のコマンドとして動くようになった。
fun宣言に対応した。- 字句解析器でソース位置（行番号とカラム番号）を管理するようにして、構文エラーの際にソース位置を表示するようになった。ASTの対応はまだ。
特に、単体のコマンドとして動くようになったことで結構コンパイラーとしての体裁が向上したと思う。
https://github.com/minoki/DamepoML
動くようになったコード
フィボナッチ数（指数時間）：
val rec fib = fn n => if n = 0 orelse n = 1 then 1 else fib (n - 1) + fib (n - 2); val rec loop = fn i => if i >= 10 then () else ( print (Int_toString (fib i) ^ "\n"); loop (i + 1) ); loop 0;
フィボナッチ数（線形時間）：
fun fib n = fibLoop 0 1 n
and fibLoop a b 0 = a
| fibLoop a b n = fibLoop b (a + b) (n - 1);
fun loop i = if i >= 50 then
()
else
( print ("fib[" ^ Int_toString i ^ "]=" ^ Int_toString (fib i) ^ "\n");
loop (i + 1)
);
loop 0;
FizzBuzz:
fun ! (ref x) = x;
val counter = ref 1;
while !counter <= 100 do
let val i = !counter
val s = case (i mod 3 = 0, i mod 5 = 0) of
(true, true) => "FizzBuzz"
| (true, false) => "Fizz"
| (false, true) => "Buzz"
| _ => Int_toString i
in print (s ^ "\n");
counter := i + 1
end;
リストの連結・反転・文字列化：
fun op @ ([], ys) = ys | (x :: xs) @ ys = x :: (xs @ ys); fun rev nil = nil | rev (x :: xs) = rev xs @ [x]; fun id x = x; fun list_toString showElem = let fun go [] = "" | go (x :: xs) = "," ^ showElem x ^ go xs in fn [] => "[]" | (x :: xs) => "[" ^ showElem x ^ go xs ^ "]" end; val strlist_toString = list_toString id; print (strlist_toString [] ^ "\n"); print (strlist_toString ["foo"] ^ "\n"); print (strlist_toString ["foo","bar"] ^ "\n"); print (strlist_toString ["foo","bar","baz"] ^ "\n"); val intlist_toString = list_toString Int_toString; print (intlist_toString [] ^ "\n"); print (intlist_toString [0] ^ "\n"); print (intlist_toString [1,2] ^ "\n"); print (intlist_toString ([1,2] @ [3,4,5]) ^ "\n"); print (intlist_toString (rev [2,3,5,7,11,13,17]) ^ "\n");
100以下の素数の列挙（試し割り）：
fun isPrime n = n >= 2 andalso let fun go i = if i * i > n then
true
else if n mod i = 0 then
false
else
go (i + 1)
in go 2
end;
fun primesBelow n = let fun go i = if i > n then
[]
else if isPrime i then
i :: go (i + 1)
else
go (i + 1)
in go 2
end;
val primesBelow100 = primesBelow 100;
fun list_toString showElem = let fun go [] = ""
| go (x :: xs) = "," ^ showElem x ^ go xs
in fn [] => "[]"
| (x :: xs) => "[" ^ showElem x ^ go xs ^ "]"
end;
print (list_toString Int_toString primesBelow100 ^ "\n");
SML/NJからMLtonへ
最初はSML/NJで単体の実行ファイルを出力したいと思ったが、
を読むと「ヒープイメージをファイルとして書き出す」とか書いてあって「？？？」となった。SML/NJは単体の実行ファイルの出力には向いていないのかもしれない……。
SMLの処理系はSML/NJの他にも色々ある。大域的な単一化を行い効率の良いバイナリを吐くMLton、リージョン推論でGCなしのメモリ管理を実現するMLKit、東北大で開発されていて色々拡張機能を盛り込んでいるSML#などだ。
というかこの3つを代替として検討したのだが、
- MLtonはコンパイルが遅そう（偏見）
- MLKit付属のML-Yaccではバグによりsyntax.grmがコンパイルできなかった（報告済み）
- SML#ではSML/NJのような「複数の入力ファイルを単純に連結（逐次実行）する」タイプのファイル分割はサポートされていなさそう（.smiファイルを新たに書く必要がある）
という感触で、結果としてMLtonを採用することにした。
そういうわけで「コマンドライン引数で与えられたファイルを読み取ってコンパイルして.luaファイルとして書き出す」部分をチャチャッと書いて、スタンドアロンで動作するコンパイラーができた。
組み込み関数をどうやって実装するか
Hello world!を書けるようにする上で一番重要なのは print 関数を用意することだ。この組み込み関数を追加する上で行ったのは大きく次の二つ
- コンパイルの際に使う初期環境に
print : string -> unitを追加する。 - 出力ファイルを吐く際に、組み込み関数の実装（
local function _print(x) io.write(x) endみたいな感じ）を先頭にくっつける。
である。
ただ、組み込み関数が少数なら良いが、関数が増えてくると色々煩雑になる。現状の実装では、「初期の環境」に変数を追加するのに4箇所くらいコードを追加する必要がある。実行時に使われる（Luaによる）実装の部分も含めると5箇所となる。
できれば、言語のコアに依存しない組み込み関数はメンテナンスしやすい形で実装できるようにしたい。
方針としては、SMLに適当なプリミティブやFFI用の構文を追加してSMLで組み込み関数を定義できるようにするやり方、組み込み関数を収録した定義ファイルを書いてそれを元にコンパイラーのコードの一部を生成するやり方、などが考えられる。
fun宣言の実装は楽しくない
SMLでは任意の識別子を中置演算子として使うことができる。例えば
A B C
というコードの前に infix B という宣言があればこれは B という関数に (A, C) という引数を与える関数呼び出しだし、そういうのがなければ A という関数を B という引数で呼び出してその結果にさらに C を与えて呼び出す関数呼び出しだ。
なので、パーサーの実装がかなり面倒になる。典型的には、ML-Yaccで生成するパーサーでは中置演算子は考慮せずにフラットな列として読み込んで、その後のフェーズで改めて中置演算子を考慮して構文木を作り直すことになる。
fun 宣言にも同じことが言える。
fun A B C = ();
という定義の前に infix B があればこれは二項演算子 B の定義とみなされ、そうでない場合は関数 A の定義とみなされる。
別の例を見てみよう。
fun (A B C) D E = ();
という宣言は、
BとDのいずれも中置でない場合はエラーBが中置、Dが非中置の場合はBという関数の定義（val rec B = fn (A, C) => fn D => fn E => ();みたいな感じ）Bが非中置、Dが中置の場合はエラーBとDが両方中置の場合は、Dという関数の定義で、Bは中置のデータ構築子（val rec D = fn (op B (A, C), E) => ();）
という感じになる。
スクリプト言語をターゲットとすること
このプロジェクトは、LuaやJavaScript等のスクリプト言語のコードを出力することを目標としている。
これは実装の簡易化（GCやクロージャーを実装しなくて良い）という面もあるが、諸事情によりスクリプト言語しか使えない環境に静的型やパターンマッチ等のML系言語の恩恵をもたらすという目的が大きい。
「スクリプト言語しか使えない環境」というのは、アプリケーションに組み込まれた実行環境とかそういうのだ。そういう用途で使われるスクリプト言語としては、
- Lua
- JavaScript
- Scheme（GNU GuileやGIMPなど）
- Emacs Lisp
などがある。当面の目標はLuaとJavaScriptだ。
こういう、「他のスクリプト言語（複数種類）にコンパイルできる」タイプの処理系としてはHaxeがある。Haxeは昔触った感じではターゲット言語の違いを隠蔽しきれていなくて辛かったので、自作処理系ではその辺頑張りたい。
ところで、アプリケーション組み込みの実行環境としては今後WebAssemblyが流行ることが予想される。しかし、現行の実装戦略ではターゲット言語のGCやクロージャーを当てにしているので、簡単にWebAssemblyに対応することは出来なさそうである。
スクリプト言語の欠点、ネイティブコードへの憧憬
スクリプト言語をターゲットとすることにはメリットも大きいが、デメリットもある。処理系のバージョンや組み込み先の環境に大きく左右されることだ。
例えばLuaは、Lua 5.2からLua 5.3で整数型周りがガッツリ変化した。処理系としてはLuaJITという変種もある。さらに、ファイルシステム操作やPOSIX関数の呼び出しには外部のモジュールを頼る必要がある。
JavaScript (ECMAScript) は、WebやNode等の実行環境では比較的モダンな文法が使えることが期待できるが、アプリケーションに組み込まれるようなミニマルな実行環境ではES5やES3止まりの可能性もある。
なので、出力すべきコードは「ターゲット言語」だけでは決まらず、「ターゲットとなる実行環境」を想定する必要がある。TypeScriptの --lib オプションみたいなものが必要だろう。
数値型、Unicode文字列、OSのAPIなど色々考えていくと、「つべこべ言わず低レベルなレイヤーを直接触らせてくれ」という気持ちになったりならなかったりする。
なので、スクリプト言語出力が一段落したら次はネイティブコード出力を……と言いたいところだが、ネイティブコードを出力できるSML処理系はすでに色々あるのでなんだかなあという気がする。
処理系の名前
処理系の名前は今の所 “DamepoML” で進めているが、今更ながらこの名前はちょっとどうかなあという気がするのでそのうちしれっと変えるかもしれない。
SMLの言語拡張
SMLの処理系はそれぞれ独自の言語拡張を実装していることがある。Vectorリテラル #[1, 2, 3] だとか、高階モジュールだとか、多相レコードだとか、FFIだとか。
自作SML処理系の当面のターゲットとしているLuaとJavaScriptはどちらもハッシュテーブルを普段使いするスタイルで、SMLのレコードをハッシュテーブルとしてコンパイルすれば多相レコードのコード生成は素直に出来そうな気がする。
ただ、安易に多相レコードを実装してしまうと、将来Scheme等他の言語をターゲットにする際に非自明なコード生成が必要になりそうで、よく考えて決めないといけない。
次の目標
簡単なプログラムは動くようになったので、もっと複雑なプログラムを動かせるようにしたい。具体的には
- ユーザー定義のデータ型
- 組み込み関数の追加
- エラーメッセージの改善
- 現状のASTはソースの位置情報を持っていないので意味解析のエラーの際に適切なエラー位置を表示できない。
- モジュール
あたり。
引き続き頑張っていきたい。
ピンバック: 自作SML処理系進捗：Hello Lua! | 雑記帳
ピンバック: LunarMLの進捗2021 | 雑記帳
ピンバック: 2021年振り返りと来年に向けて | 雑記帳