自作OCamlコンパイラでセルフホストした
概要
ここ最近作っていたOCaml*1コンパイラmlml*2でセルフホストを達成しました。ﾔｯﾀｰ
mlmlには以下に代表されるような、OCamlの基本的な機能が実装されています。
- 再帰関数
- ヴァリアント、レコード
- パターンマッチ
- カリー化
- モジュール
mlmlの特徴
ほぼフルスクラッチ
今回LLVMやパーサジェネレータに頼らないコンパイラづくりを体験するのが目的の一部だったので、結果的にフルスクラッチらしきこと*3になりました。OCamlの標準ライブラリ以外の外部ライブラリを使用しておらず、字句解析器・構文解析器は手書きです。
OCamlで書かれている
セルフホストしたのでそれはそうなんですが、OCamlで書かれています。
また、言語処理系を書く場合ランタイムライブラリはC言語で用意してリンクする場合が多いと思いますが、今回は謎に意地を張ってしまい全てOCaml内で完結させました。これがよかったのかはよくわからないんですが、文字列などのデータ構造を扱うのにコード生成部と共通のコードを使えるので保守性が上がった(気がします)。
x86_64のアセンブリを吐く
GAS*4に流すことを想定している、x86_64 glibcの環境向けのアセンブリを吐きます。
今までLLVM IRを出力するコンパイラしか作ったことがなかったので、x86もやってみようと今回チャレンジしてみました。
duneの真似をするバンドラーがくっついている
mlmlではduneをビルドシステムとして使っています。そのため気軽にソースを複数のファイル・ディレクトリに分割して開発できました。
しかしセルフホストするときに自分自身が複数のファイルに分割されていると、それらをまとめる部分も作らなければいけません。 ということで、mlmlにはduneの動作をシミュレートするバンドラーがくっついています。内部ではファイル間の依存関係を解決する部分まで書く羽目になりました。これはかなり沼で*5、セルフホストをやる上では設計ミスだったなと思っています。カッコつけずに少ないファイルで作ればよかった。
作り始めたきっかけ
なんとなくOCamlを書けるようになろうと思ったので、公式のチュートリアルをやりました。4月の初め頃のことです。
それが一通り終わったのでコンパイラを作ることにしました。
今ですが、OCamlの練習として(?)パーサジェネレータとLLVMを使わない縛りでコンパイラを書いている
— 歯車 (@coord_e) 2019年4月4日
やっと簡単なコード生成ができるようになった (x86に不慣れすぎる...) pic.twitter.com/O7KdJaYPja
コンパイラならなんでも良かったんですが、@ushitora_anqouさんの記事"はりぼて自作OCamlコンパイラAQamlでセルフホストしてみた | カオスの坩堝"を読んでセルフホストは楽しそうだなー思い、OCamlコンパイラを作ることに決めました。
その後はハッシュタグ#mlml_compilerに進捗を投稿しつつ制作を続け、開始からだいたい50日でセルフホストに至りました。二ヶ月ですね*6
実装の方針
完璧なOCamlコンパイラを作ろうとしたらいつまでたっても終わらないので、制作を始めるときにいくつか制限を決めました。
出力コードの効率は気にしない
x86_64を直接扱うコンパイラを書くのは初めてなので、まずは効率を気にせず確実に動くコードを吐かせることを優先してコードを書いていくことにしました。
型システムは作らない
これなんですが、作り始めた当時「型システムは実行時エラーを静的に検出するためのものなのに僕は型情報に依存したコード生成をやっている*7！型がなくてもコード生成ができるべきだ」という考えがあったことに起因します。(あとで知ったんですがこの考えは正しいわけではなく、OCaml含む大抵の言語は型情報が項に内因的に含まれています*8。よってコード生成で型情報を利用するのは当然のことです)
結果、型なしでOCamlを実装することになりました。意外にも大体の機能が型推論なしで実装できたんですが、使い勝手が悪かったり一部妥協があったりします。*9
テストイメージ内以外での動作は考えない
出力の可搬性を重視したいならLLVM IRを吐けばいい話なので、"動く環境が存在する"ことを重視することにしました。開発用のDockerイメージを用意し、その内部でテストなどを走らせました。
Dockerコンテナ内でワークフローを回せるようになっているので、macOSやWindowsでも開発が行えるようになっています(きっと)
内部構成
技術的な詳細は別記事にまとめたので、ここでは処理の流れを描いた図を示すだけに留めます。
クロージャ変換やα変換、ヴァリアント/レコード/パターンマッチを実装する体験ができたのは良かったです。作る前はどうやってやるのか見当もつかなかったので...
セルフホストについて
mlmlでは
ことを検証し、セルフホストできたという結論に達しました。*10
セルフホスト用スクリプトを書いたので、誰でも試すことができます。cloneしたディレクトリで以下のコマンドを実行します*11(完了まで一日ぐらいかかります)
./dev/exec.sh ./dev/self_host.sh
ちなみに"セルフホスト"の定義についてTwitterでアンケートをとったら以下のようになりました。
"セルフホスト"
— 歯車 (@coord_e) 2019年5月20日
「自分自身をコンパイルできる」派が優勢のようです。僕は「第一世代と第二世代の出力が一致する」派です。真相はいかに
感想
前方参照がないことのキツさ*12やヴァリアント・レコードの実装の簡単さ*13といったことを身をもって感じられたのが一番の収穫だと思っています。
OCamlへの理解は深まったかというとそうでもなくて、オブジェクト指向やGADT、ファンクタなどに触れていない。これは残念です。(セルフホストがしたかったのでしょうがないが)
あとは地味に再帰をガリガリ書く関数型プログラミングをやるのは今回が初だったりするので、慣れることができてよかったなと思っています 再帰にかなり苦手意識があったので...
今後の展望
TaPLを読み進めたりSoftware Foundationsを進めたりしたいのでしばらくはmlmlから離れるつもりです。しかし、例外の実装には興味があるのでいずれmlmlに追加したいなと思っています。
次回に続く
読んでいただきありがとうございました。
次は役に立つことを書くぞ！！ (技術的な詳細を書いていこうと思います)
追記: 実装の詳細について書きました。
*1:とある関数型プログラミング言語 http://ocaml.org/
*2:開始当初は"モルモル"と読むつもりだったが実際そう読んだことはない
*3:ビビリなので自信がない 「フルスクラッチ」ってなんだ？
*5:しかもSys.readdirを実装しなきゃいけない!!
*6: ゴールデンウィーク中に終わらせるつもりだったんですが全然終わらなかった(それはそう)
*8:型付けできない項はinvalidである、Curry-style typingとも
*9:例えばフォーマット文字列と通常の文字列を使われ方によって切り替えることができないので、Printf.printf "Hello"は実行時エラーになります
*10:テストケースを第一世代に流すスクリプトをいずれ書くかもしれない
*11:dockerが必要です
*12:let rec ... and ...が本当につらい 特にコンパイラを書く人にとって...
*13:やってみると大抵のものはタプルだった
