自作 OCaml コンパイラでセルフホストした

概要

ここ最近作っていた OCaml1コンパイラmlml2でセルフホストを達成しました。ﾔｯﾀｰ

mlml には以下に代表されるような、OCaml の基本的な機能が実装されています。

  • 再帰関数
  • ヴァリアント、レコード
  • パターンマッチ
  • カリー化
  • モジュール

また、多少の標準ライブラリも実装されています。

mlml の特徴

ほぼフルスクラッチ

今回 LLVM やパーサジェネレータに頼らないコンパイラづくりを体験するのが目的の一部だったので、結果的にフルスクラッチらしきこと3になりました。OCaml の標準ライブラリ以外の外部ライブラリを使用しておらず、字句解析器・構文解析器は手書きです。

OCaml で書かれている

セルフホストしたのでそれはそうなんですが、OCaml で書かれています。

また、言語処理系を書く場合ランタイムライブラリは C 言語で用意してリンクする場合が多いと思いますが、今回は謎に意地を張ってしまい全て OCaml 内で完結させました。これがよかったのかはよくわからないんですが、文字列などのデータ構造を扱うのにコード生成部と共通のコードを使えるので保守性が上がった(気がします)。

x86_64 のアセンブリを吐く

GAS4に流すことを想定している、x86_64 で glibc の環境向けのアセンブリを吐きます。

今まで LLVM IR を出力するコンパイラしか作ったことがなかったので、x86 もやってみようと今回チャレンジしてみました。

dune の真似をするバンドラーがくっついている

mlml ではduneをビルドシステムとして使っています。そのため気軽にソースを複数のファイル・ディレクトリに分割して開発できました。

しかしセルフホストするときに自分自身が複数のファイルに分割されていると、それらをまとめる部分も作らなければいけません。 ということで、mlml には dune の動作をシミュレートするバンドラーがくっついています。内部ではファイル間の依存関係を解決する部分まで書く羽目になりました。これはかなり沼で5、セルフホストをやるうえでは設計ミスだったなと思っています。カッコつけずに少ないファイルで作ればよかった。

作り始めたきっかけ

なんとなく OCaml を書けるようになろうと思ったので、公式のチュートリアルをやりました。4 月の初め頃のことです。

それが一通り終わったのでコンパイラを作ることにしました。

コンパイラならなんでも良かったんですが、@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 でアンケートをとったら以下のようになりました。

「自分自身をコンパイルできる」派が優勢のようです。僕は「第一世代と第二世代の出力が一致する」派です。真相はいかに

感想

前方参照がないことのキツさ12やヴァリアント・レコードの実装の簡単さ13といったことを身をもって感じられたのが一番の収穫だと思っています。

OCaml への理解は深まったかというとそうでもなくて、オブジェクト指向や GADT、ファンクタなどに触れていない。これは残念です。(セルフホストがしたかったのでしょうがないが)

あとは地味に再帰をガリガリ書く関数型プログラミングをやるのは今回が初だったりするので、慣れることができてよかったなと思っています再帰にかなり苦手意識があったので…

今後の展望

TaPL を読み進めたり Software Foundations を進めたりしたいのでしばらくは mlml から離れるつもりです。しかし、例外の実装には興味があるのでいずれ mlml に追加したいなと思っています。

次回に続く

読んでいただきありがとうございました。

次は役に立つことを書くぞ！！　(技術的な詳細を書いていこうと思います)

追記: 実装の詳細について書きました。

  1. とある関数型プログラミング言語 https://ocaml.org/↩︎

  2. 開始当初は“モルモル”と読むつもりだったが実際そう読んだことはない↩︎

  3. ビビリなので自信がない 「フルスクラッチ」ってなんだ？↩︎

  4. というか面倒なので gcc に流すわけだが↩︎

  5. しかも Sys.readdir を実装しなきゃいけない！↩︎

  6. ゴールデンウィーク中に終わらせるつもりだったんですが全然終わらなかった(それはそう) ↩︎

  7. expressiとかでやってた↩︎

  8. 型付けできない項は invalid である、Curry-style typing とも↩︎

  9. 例えばフォーマット文字列と通常の文字列を使われ方によって切り替えることができないので、Printf.printf "Hello" は実行時エラーになります↩︎

  10. テストケースを第一世代に流すスクリプトをいずれ書くかもしれない↩︎

  11. docker が必要です↩︎

  12. let rec … and … が本当につらい 特にコンパイラを書く人にとって…↩︎

  13. やってみると大抵のものはタプルだった↩︎