self-hosting可能なmincamlコンパイラという夢(とその進捗)
この記事は、
adventar.org
の5日目の記事として書かれました。昨日はmoratorium08さんの
moraprogramming.hateblo.jp
でした。コンパイラの穴をついたexploit、今後こういうジャンルも増えるんでしょうか。期待ですね。
本題
8月にセキュリティキャンプに参加しました。
そこで、C言語セルフホスティングトラックの人たちと話す機会があったのですが、
「大学の授業でmincamlのコンパイラを書いたんですよ」というと
「そのコンパイラはセルフホストできるんですか？？？」(この辺は実際の発言と差があるかもしれない)
と言われたので、そんならいっちょやったるか、という気持ちで趣味の実装を進めているので、その紹介をします。
実装はここ
github.com
で現在進行形で進めています。
mincamlとは
OCamlの教育的subsetみたいなものです。
作者による解説は 速攻MinCamlコンパイラ概説 とか
github.com とかですね。
僕はCPU実験でコンパイラ係だったので、その際にmincamlコンパイラ
github.com
を書きました。今回のものは、それにさらに手を加えていったものです。
mincamlの基本的な能力は、
- データ型はint, float, 関数, タプル, 配列 のみ
- 型推論は単相型のみ
- プログラム全体は1つの値で、1ファイルに記述する
ヴァリアント型とパターンマッチ
コンパイラ内部では、プログラムを抽象構文木の状態で持ち回して処理していくので、構文木を扱うためのヴァリアント型の導入が必要になります。この拡張により、
type hoge = | A of int | B of int * int let rec f x = | match x with | A(t) -> t | B(s,t) -> s + t
みたいなのが書けるようになりました。また、多相ヴァリアントも実装しました。*1これにより、list型やoption型のデータが扱えるようになりました。
内部的には、タグを表現するintの値とデータの組で表現しています。たとえば ["a";"b"] は @Cons("a",@Cons("b",@Nil)) としているので、
(1,("a",(1,("b",(0,())))) みたいなかんじで持っています。 この変換を型推論時(K正規化へ変換する際)に行います。
https://github.com/satos---jp/mincaml_self_hosting/blob/23f6b59ffd7f5748f6c0149d5b903ec09e0735c2/src/compiler/type_checker.ml#L417-L438
パターンマッチは、与えられたデータのタグをみてパターンに合致していればそちらに分岐するようなif文の連鎖、に変換するようにしました。
https://github.com/satos---jp/mincaml_self_hosting/blob/23f6b59ffd7f5748f6c0149d5b903ec09e0735c2/src/compiler/type_checker.ml#L439-L484
この変換も型推論時に同時に行っています。
型推論時には、変数の型環境以外に、型そのものについての環境やタグに対応するについての環境を追加することになります。また、型定義にも、intやfunctionやtuple以外に、variantについての型が入るようになります。
https://github.com/satos---jp/mincaml_self_hosting/blob/23f6b59ffd7f5748f6c0149d5b903ec09e0735c2/src/compiler/type.ml#L18
あと、レキサやパーサがこれらをパースできるように拡張しました。*2
https://github.com/satos---jp/mincaml_self_hosting/blob/master/src/compiler/parser.mly#L124-L204
これらの変換はK正規化移行には影響しないので、K正規化以降のソースコードには手を加えることなくヴァリアント型とパターンマッチを導入することが(多分)できました。
Openによるファイル分割
コンパイラを複数ファイルに分割して書いていたので、ファイル同士のOpenができるようする必要があります。*3
hoge.ml 内で
let rec f x = x + 1
として、hoge.mli内で
val f : int -> int
とすると、別のファイル内で
open Hoge let y = f 3
とできるようになります。
モジュールシステムの再現は大変なので、とりあえすOpenができるようにしました。
また、ファイルごとの分割コンパイルもできるようにしました。上のhoge.mlのみをコンパイルすると、Hoge@fをシンボルとして公開しているようなオブジェクトファイルにコンパイルされます。
この拡張により、 List.map などの標準ライブラリ関数を(僕が実装すれば)使えるようになりました。
https://github.com/satos---jp/mincaml_self_hosting/tree/master/lib/ml
内のファイルで様々に実装しています。
内部的には、.mliがパースできるようにパーサを拡張して、シグネチャを表現するデータ型を追加しました。
また、emit時に、各ファイルの中身を順番に実行していくようなstubを追加したり、ファイル同士の依存関係を解析したりするのを追加しました。
いちおう、シグネチャの型と実際の型が合致しているか確認するのを
https://github.com/satos---jp/mincaml_self_hosting/blob/master/src/compiler/type.ml#L188-L228
で実装しましたが、なんだかバグっているのでこのへんの修正がTODOですね。*4
あと、.mlから.mliを出力するような機能*5も追加したのですが、これもいろいろ壊れている感じです。
String型、Ref型
コンパイラ内部でばりばりに使うので必要になります。
let s = "Hello " ^ "World" in let str = ref "" in str := s; print_string (!str)
みたいなのが動くようになりました。
内部的にはどちらも特殊定数ですね。型推論時とemit時にintやfloatと同様に定数として書き出せばいいだけです。あとデータに触るためのアセンブラを実装
https://github.com/satos---jp/mincaml_self_hosting/blob/master/lib/asm/string.s
https://github.com/satos---jp/mincaml_self_hosting/blob/master/lib/asm/pervasive.s#L406-L423
すればよいです。
let多相
ないとList操作などが非常に辛くなるやつです。大規模プログラムを書くには必需。たとえば
List.memの内部実装は
let rec mem a v = match v with | x :: xs -> if x = a then true else mem a xs | [] -> false
なわけですが、これが多相でないと地獄をみます。
型推論機の型多相的拡張は、3年夏学期の関数論理型実験でやったので、そのコードをだいたい流用すればよいです。*7
変更点はそこだけかというとそうではなく。例えば上のList.memの例にもあるように、任意の型による比較演算が発生するので、バイナリ上に型情報のデータを載せる必要が出てきます。僕は32bitデータの上3bitを削ってそこに型データを載せることにしました。内部実装の概要は
https://github.com/satos---jp/mincaml_self_hosting/blob/master/src/compiler/emit_zatsu_x86.ml#L19-L48
みたいな感じです。*8
*9
yacc,lexの実装
コンパイラは構文解析をするので実装する必要があります。*10
https://github.com/satos---jp/mincaml_self_hosting/blob/master/src/lex/lexer.mll
こういうのや
https://github.com/satos---jp/mincaml_self_hosting/blob/master/src/lex/parser.mly
こういうのがコンパイルできるようになりました。
それぞれ実装は
https://github.com/satos---jp/mincaml_self_hosting/tree/master/src/lex
https://github.com/satos---jp/mincaml_self_hosting/tree/master/src/yacc
です。lexやyaccの理論は3年夏学期の授業で習うので、いわばその実践ですね。
lexは、OCaml内部実装とは違い、各正規表現ごとにNFAに変換したあと、lex時に同時に回して、longestでfirstなものを返すようにしました。(OCaml内部ではNFAをDFAにしたあと、DFAの同時積をとってひとつのでかいDFAにしているようで、たとえば rule main = parse | "aa"* { 1 } | "aaa"* { 2 } | "aaaaa"* { 3 } | "aaaaaaa"* { 4 } | "aaaaaaaaaaa"* { 5 } | "aaaaaaaaaaaaa"* { 6 } とかをocamllexするとコンパイル！に1分くらいかかります。)
yaccは、授業でやったように、LALRオートマトンを作ってそれに従ってパースします。まだ%left,%right,%nonassocなどのprecedenceについては未実装でコンパイラのパーサには必要なので、そのあたりはTODOです。
ガベージコレクション
巨大なプログラムを連続して動かすには必要になってきます。実装の本質は
github.com
このコードです。
今回はCopying GCを実装しました。メモリ確保時にヒープを使い果たしているならGCが走ります。今回、ヒープ以外で生きている可能のあるデータは必ずスタックもしくはファイルごとの初期化部分のみに載っているので、そこを走査すれば十分です。できればこのへんもmincamlで書きたかったんですが、高級言語の悲しい性として低レイヤー部分には触れないのでCでの実装になっています。((mincamlでCコンパイラを書けばセルフホスティングに近づくのでTODOですね(ほんまか)))
これらの実装による現在の進捗
以上の拡張を施すことにより、自作コンパイラでlexer自身
https://github.com/satos---jp/mincaml_self_hosting/tree/master/src/lex
が"だいたい"コンパイルできるようになりました！！やったね！！
コンパイルの様子は、
https://github.com/satos---jp/mincaml_self_hosting/tree/master/lexer_compile_test
ここでcompile.shを叩いてもらうと確認できます。
実は若干いろいろ残っていて、ArrayやSysは実装していないのでmainに若干のパッチがかかるとか、.mli生成がバグっていてlexer.mliは手動修正しないといけないとかあるのですが、
それでもまぁコンパイラとしてはだいぶ実用的になったのではないでしょうか。
今後の展望
- yaccのprecedence
- 例外機構
を実装する必要があります。
また、その他にも細々としたものをさまざま実装しなければならないでしょう。self-hostingに成功したあかつきには、またブログで成果を報告したいと思います。
明日は、_uenokuさんの「LLVMとcpu実験」です。今年のコンパイラフルスクラッチ勢として強いコンパイラの記事を書いてくれるのでしょう。楽しみですね。
*1:多相ヴァリアント型定義のパースは未実装で、コンパイラ内部で定義したものしかまだ使えないですが...
*2:これらを加える際に発生したconflictを未だに解消できてない...
*3:一つの巨大ファイルに結合してしまう手もあったが肥大したファイルで全部やっていくのは開発が辛い
*4:多分部分型関係にあればよさそうなのだけれどちゃんとよく分かっていない
*5:lexerに必要になってくる
*6:一応format型を実装してみたりはしたんですが、文字列がstringかformatかを判別するタイミングがよくわからない感じです。なんか型推論機を改造しなきゃならんのでしょうか、だれか教えて強いひと...
*7:実はパターンマッチ時にもいろいろlet多相的なことが起こるのでそのままとはいかない。多分今もいろいろバグっているはず。
*8:正確には、上2~4bitを削っています(上1bitには整数型の符号があるので)。あと、浮動小数点の場合は、演算前に4bitシフトするようにする https://github.com/satos---jp/mincaml_self_hosting/blob/master/src/compiler/emit_zatsu_x86.ml#L255-L272 ことで、指数部を削らずに制度の下3bitを犠牲にしています。正直このあたりは闇。
*9:あと、Refを実装したことと合わせるとexploitableになってしまうのでvalue restrictionを実装する必要があるんですがまだ面倒なのでやってません。TODOです。
