セルフホスティングCコンパイラを作るのが流行っていたので、それに感化されて F# サブセット言語のコンパイラでセルフホスティングをやってみました。
コードネームは ミローネ言語 です。
リポジトリ: vain0x/milone-lang
開発期間: 2018/08/31 ～ 2019/10/04 (うち5か月ほど休止期間)
開発言語: F#
F# にはオブジェクト指向の言語機能と関数型の言語機能の両方が乗っていて、普段なら適当に使い分けてプログラミングします。
しかしセルフホストするためには、
使用する言語機能 ＝ 実装する言語機能
となるわけで、あまりたくさんの言語機能を使えません。
今回はコンパイラを書くのに向いているであろう 関数型の言語機能 (リストや再帰関数など) を使うことにしました。
また、実装量を減らすために イミュータブル縛り でやってみました。つまり、
- 変数への再代入は禁止
- オブジェクトの破壊的変更は禁止
ということで、すべての変数とオブジェクトがイミュータブルです。副作用はファイルの読み書きに限定しました。
対象言語: C言語
ネイティブコードを吐くコンパイラを作るのは大変なので、代わりに C言語のソースコードを生成してCコンパイラに渡す という方針にしました。
それはコンパイラなのか？ という感じもありますが、プログラムをネイティブコードに限らず 低レベルな言語に変換するソフトウェアはすべてコンパイラ なのでセーフ。
C言語を対象にすることはたくさんメリットがあって、
- よくできたCコンパイラ(GCC)の最適化の恩恵にあずかれる
- 関数型言語に必須の末尾再帰最適化をやらなくて済みました
- 静的検査でテストできる
- コンパイラをバグらせても、出力したコードの不正な部分をGCCが見つけてくれることがあります
- よいサブゴールになる
- 比較的単純なC言語ですら難しいのに F# のネイティブコンパイラを作りだしても絶対に挫折します
コンパイラ型の処理系を作るのは初めてなので相応の難度の挑戦です。
セルフホスティング
ここでいうセルフホスティング (self-hosting) は、作成したコンパイラがコンパイラ自身のソースコードをコンパイルできる ということです。
[ミローネ言語コンパイラのソースコード(ミローネ言語)]
| | F# コンパイラでコンパイル
| v
| [ミローネ言語コンパイラ(.NET)] でコンパイル
v
[ミローネ言語コンパイラのソースコード(C言語)]
| GCC
v
[ミローネ言語コンパイラ(ネイティブ)]
F# (のサブセットであるミローネ言語) で書いたソースコードを F# コンパイラでコンパイルし、ミローネ言語コンパイラ (第1世代) を作ります。第1世代コンパイラは .NET Core ランタイム上で動作します。
次に第1世代コンパイラにコンパイラ自身のソースコードを渡して、コンパイルします。すると、C言語のソースコードが生成されます。これを GCC でコンパイルすると、ミローネ言語コンパイラ (第2世代) が出てきます。第2世代は第1世代と違って、ランタイムなしで動作します。
第2世代コンパイラのバイナリがあるおかげで、ミローネ言語は F# のツールに依存することなく動作する ようになりました。「ミローネ言語で書かれたコンパイラのおかげで、ミローネ言語をコンパイルできるようになった」という状況が自己言及的で面白いですね。
また、上記の工程をもう一度繰り返して、第2世代コンパイラで元のソースコードをコンパイルするとどうなるでしょうか？ 実は、第2世代コンパイラの元となったC言語のソースコードと全く同一のソースコードが出力されます！ つまり、動作環境が異なっていても 第1世代と第2世代は同じ動作をする わけです。
変換過程
作業量を減らす話ばかりしていて一体何を実装したんだという感じなので、ある関数がどのようにミローネ言語 (F#) からC言語に変換されるかをざっと見てみます。
リストの各要素に関数を適用して別のリストを作る関数 listMap を例にとります。
let listMap f xs =
let rec go acc xs =
match xs with
| [] ->
listRev acc
| x :: xs ->
go (f x :: acc) xs
go [] xs
名前解決
ソースファイルを字句解析や構文解析やモジュールバンドラーにかけて中間表現 (木構造) を作るところまでは飛ばして、まず 名前解決 をやります。上のコードには xs という名前 (何らかのリストを表すよくある名前) の変数がよく見ると3つあって、区別しておかないと変換しづらいです。
ここでは変数に番号をつけて、すべての変数や関数が異なる識別子を持つようにします。
// 名前解決後
let listMap f xs1 = // ← xs1 は listMap のローカル変数 (1個目)
let rec go acc xs2 = // ← xs2 は go のローカル変数 (2個目)
match xs2 with
| [] ->
listRev acc
| x :: xs3 -> // ← xs3 は xs2 の尾部 (3個目)
go (f x :: acc) xs3
go [] xs1
型推論
F# では型は書かなくてもよいですが、C言語では変数と関数の型ぐらいは明記しないといけません。型推論 により、式の型を自動で補います。例えば f は f x という関数呼び出しを受けているので、関数の型 'x -> 'y を持つはずです。
また、xs2 は、
match xs2 with
| [] -> // 略
| x :: xs3 -> // 略
のように空のリスト ([]) か否かで場合分けされているので、リスト型 ('x list) のはずです。
受け取るリストの要素の型 'x と、出力するリストの要素の型 'y が何かは、この時点では分かりません。これは自動的に 多相関数 になります。変数と関数に型の注釈をつけると以下のような感じです。
let listMap (f: 'x -> 'y) (xs1: 'y list): 'y list =
let rec go (acc: 'y list) (xs2: 'x list): 'y list =
match xs2 with
| [] ->
listRev acc
| (x: 'x) :: (xs3: 'x list) ->
go (f x :: acc) xs3
go [] xs1
クロージャ変換
C言語の関数と違って、F# の関数は外側のローカル変数を使用できます。例えば listMap の内側にある go 関数は、外側の関数の引数 f を使えています。
これは、外部の変数を内側の関数に引数として渡す ことにして解決します。(MinCaml とは異なる挙動なので、これをクロージャ変換と呼んでいいのかは分かりません。)
let listMap (f: 'x -> 'y) (xs1: 'y list): 'y list =
// ↓ f を受け取る引数を増やす
let rec go (f: 'x -> 'y) (acc: 'y list) (xs2: 'x list): 'y list =
match xs2 with
| [] ->
listRev acc
| (x: 'x) :: (xs3: 'x list) ->
go f (f x :: acc) xs3 // ← f を渡す
go f [] xs1 // ← f を渡す
もう go が listMap の内側にある必要はないので、外側に移動できます。
let rec go (f: 'x -> 'y) (acc: 'y list) (xs2: 'x list): 'y list =
match xs2 with
| [] ->
listRev acc
| (x: 'x) :: (xs3: 'x list) ->
go f (f x :: acc) xs3
let listMap (f: 'x -> 'y) (xs1: 'y list): 'y list =
go f [] xs1
単相化
ここに listMap を呼んでいるコードがあるとします。
let strings = listMap string [1; 2; 3]
//=> ["1"; "2"; "3"]
この位置の listMap では、受け取るリストの要素の型は 'x = int、出力するリストの要素の型は 'y = string だと型推論で分かっています。そこで、型変数に具体的な型を代入して関数のコピーを作ります。これが 単相化 です。
// 'x = int
// 'y = string
let rec goOfIntString (f: int -> string) (acc: string list) (xs2: int list): string list =
match xs2 with
| [] ->
listRev acc
| (x: int) :: (xs3: int list) ->
goOfIntString f (f x :: acc) xs3
let listMapOfIntString (f: int -> string) (xs1: int list): string list =
goOfIntString f [] xs1
let strings = listMapOfIntString string [1; 2; 3]
//=> ["1"; "2"; "3"]
パターンマッチの展開
最後の砦はパターンマッチです。これは機械的に条件分岐と代入に分解できます。
空のリストは NULL ポインタで表されるので、ポインタが NULL か否かで分岐します。NULL でない方のケースでは、中身 (先頭と尾部) を安全に取り出せます。
struct StringList* go_2(struct IntStringFun1 f_, struct StringList* acc_1, struct IntList* xs_1) {
struct StringList* match_1; /* match 式の結果を入れる一時変数 */
if ((!((!(xs_1))))) goto next_5; /* 判定: リストが空でなければジャンプ */
/* [] のケース */
struct StringList* call_2 = /* listRev acc */;
match_1 = call_2;
goto end_match_4;
/* x :: xs2 のケース */
next_5:;
if ((!(xs_1))) goto next_6;
/* 代入: 空でないリストの先頭と尾部を取り出す */
int x_ = xs_1->head;
struct IntList* xs_2 = xs_1->tail;
match_1 = /* go f (f x :: acc) xs3 */;
goto end_match_4;
next_6:;
exit(1);
end_match_4:;
return match_1;
}
そういうわけでC言語になりました。段階的にギャップが埋まっていく様子がまさにコンパイルです。
まとめ
開発中は本当にこれ完成するのか？ という不安感でいっぱいでしたが、なんとかなって安心しました。振り返ってみると めっちゃ楽しかった です。
さて、いったん完成としましたが、
- C言語からアセンブリ等へのコンパイルを追加して、GCC を経由せずにネイティブコードを吐く
- オブジェクト指向の言語機能も導入して、F# 用のコードをコンパイル可能にする
などなど遊べることはたくさんあります。楽しみですね。
みなさんもお好きな言語をCにコンパイルしてみてください！