はりぼて自作OCamlコンパイラAQamlでセルフホストしてみた

（4年前） Hacking, 読み物 0 艮 鮟鱇

おじさん1なにしたの

はりぼて自作OCamlコンパイラを書いてセルフホストを達成しました2。コミットログによると、11月から開発を始めて3およそ2ヶ月くらいかかったようです。レポジトリはこちら4：

https://github.com/ushitora-anqou/aqaml

文字列・リスト・タプル・レコード・バリアント・参照などの基本的なデータ構造5と、 if・for・パターンマッチ・let・相互再帰関数・クロージャなどの基本的な制御構造6が実装されています。

セルフホストに必要な機能のみを実装したので、もちろんOCamlの全てを実装したわけではありません。例えばGC7・カリー化8・クラスなどのOCamlの重要な機能が無い他、型推論9もありません。 GCが無いのでセルフコンパイルに数百MBのメモリを要しますが、まぁそれはそれです。

OCamlってなに

一言では説明できないのでググってください。

きっかけ

うちの学部の名物教授・准教授がおすすめしていた MOOCのOCaml講座を受講し始めたのがきっかけ。それまでOCamlはSATySFiの実装言語という認識しかありませんでした。言うまでもなく大学生は単位の奴隷10なので、 0.01でもGPAを上げるためなら寸暇を惜しみません11。

始めてみると、今まで私が触れてきた言語とは異なるパラダイム・文法を持っていて、その仕組みが気になりました。ということで、コースを半分ほど終えたところで勝手にコースアウトしてOCamlコンパイラをOCamlで書き始めました。これが楽しくなってどんどん書いているうちに、いつのまにかOCaml学習コースは未履修のまま期日を迎えていました。残念。

実装

AQamlを作成するにあたって次のような方針をとりました12：

  • 必要になるまで作らない。
  • インクリメンタルに作る。
  • 入力は正しいと仮定する。
  • テストでバグ混入を防ぐ。
  • パーサは全て自前で書く。
  • スタックマシンでの実装。
  • 出力の最適化は行わない。

これらの方針に基づいて作ると、ソースコード中に大量のTODOが入ったり、出力アセンブリの効率が悪かったり、拡張性が無かったり、OCamlの基本的で重要な機能が無かったりすることになりますが、セルフホストという大きな目標の前では些細な問題です13。とにかく、簡単にセルフホストすることを目標にして、できるだけ最短経路を通るようにしました。もちろんはじめて行うことですし、aqcc14のときと異なり相談できる相手も居ないため、「自分が最短経路だと思う方向」に進んでいくわけですが15、意外とどうにかなります。

aqccのときと同様に、最初は「入力として整数値を受け取って、その整数値を戻り値とするようなアセンブリを出力するコンパイラ」から始めました。その後四則演算を作ったりなんだかんだしていると、壁にぶつかりました。

クロージャはつらいよ

OCamlなどの言語では関数の中で関数を定義することができます。この場合、外側で定義された変数を内側の関数で使うことができるため、変数の生存期間をよしなに判断してやる必要があります。 OCamlの場合、内側で定義された関数と、その部分で使用されているけれども外部で定義されている変数をひっくるめて「クロージャ」というものを作ります。こうすることによって関数そのものを引数として別の関数にわたしたり、あるいは関数そのものを関数の戻り値とすることができたりします16。

さてOCamlコンパイラを書くからには、このクロージャを実装しなければなりません。面倒そうに見えますが、アイデアは単純です。すなわち、外部で定義された変数を関数本体と一緒にひっくるめてクロージャを作成しておき、そのクロージャを呼び出す際には、そのひっくるめておいたクロージャを紐解いて、外部で定義された変数の情報も一緒に関数にわたしてやればよいのです。基本的にはこれで構わないのです――基本的には。

ところで世の中には再帰関数と言って、関数の中で自分自身を呼び出すような関数が存在します。こいつがクロージャになった場合を考えてみましょう。まずこの関数を外から呼び出すときには、先述のような手順で外部定義の変数情報が与えて呼び出します。次にこの関数を再帰呼び出しする際には、外部から与えられた変数情報をもとに予め自分自身のクロージャを作成しておき、これを呼び出すことになります。面倒そうですね。

ところで世の中には相互再帰関数と言って、複数の関数がぐるぐると再帰的に呼び合う関数が存在します17。こいつがクロージャになる場合、この関数が外から呼ばれた時に与えられた外部定義の変数情報をもとに、関連する全ての相互再帰関数のクロージャを作成しておき、これを呼び出すことになります。ますます面倒そうですね。

ところでOCamlでは先述のように関数を返す関数を作成することがクロージャの存在により可能ですから、関数を返す関数の戻り値にさらに引数を与えることができます。OCamlにおいて関数適用は左結合ですからこの括弧は省略できます。何を言っているのかといえばつまり

f a b c d e

というような、関数fに引数a,b,c,d,eを与えるような関数呼び出しは、もちろん関数fは5引数関数であるかもしれませんが、ひょっとするとfは3引数関数を返すような2引数関数である（すなわち「(f a b) c d e」）かもしれませんし、あるいは1引数関数を返すような2引数関数を返すような2引数関数（すなわち「((f a b) c d) e」）かもしれないのです。そこでクロージャを呼び出す際には、それぞれに応じた呼び出しを行う必要があります。恐ろしく面倒そうですね。

ところで、そもそも「関数fをクロージャとして扱う必要がある」すなわち「関数fは外部で定義された変数を内部で使用している」ことを、どのように知ることができるのでしょうか。対象の関数が再帰関数である場合、「関数が外部で定義された変数を使用している」という情報を、再帰呼び出しをする際に使用します。従って関数内部を解析する際にはこの情報が必要です。しかしその情報は関数を解析するまで分かりません。まるで鶏と卵です18。 AQamlでは、最初に関数を解析する際にはひとまず「その関数は外部で定義された変数を内部で使用していない」と仮定して解析を行います。もし途中で外部で定義された変数を使用している箇所があれば、一番最初に戻り、今度は「その関数は外部で定義された変数を内部で使用している」として解析します19。なんとも面倒ですね。

一事が万事この調子で、クロージャを正しく動かすのにはかなり手間取りました。時間があれば、また何かの機会にまとめたいと思います20。

第二世代バグが起こらない

さてaqccを作成したときには「第二世代バグ」というものを踏み抜き、このバグを潰すのに心底苦労しました21。すなわち「gccでコンパイルしたaqcc」にはバグが見つからないけれども、「gccでコンパイルしたaqccでコンパイルしたaqcc」がなぜかバグるというものです。

AQamlでもこのバグ取りに時間を費やすだろうと思っていたのですが、意外とスムーズに動いたので驚きました。理由はよく分かりませんが、OCamlの強い型推論機構のおかげだったりするのかもしれません22。

今後の展望

他にもいろいろと書きたいことがあった気がするのですが、思い出せないのでとりあえずここまで。また思い出したら個別に記事にしたいと思います23。

AQamlの今後の方向としては次のような機能を追加していきたいなと思っています：

  • カリー化
  • 完全なモジュール
  • レジスタ割り当て
  • GC
  • 型推論

――思ってはいるのですが、そろそろ言語処理系に飽きてきた感じがないでもないので、もしかしたら全く別のことに手を出すかもしれません。あと最近肩こりと偏頭痛がひどくて24、パソコンばっかり触っている生活を見直す時期に来ているのかなと思ったりしています。

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

できる！ OCamlコンパイラ作成資料

AQamlを作成した際に参考にした資料一覧です。OCamlコンパイラを作りたい方におすすめです。

  1. 大学生以上は、女性を除いてみなおじさん。↩
  2. つまり自分自身をコンパイルできるOCamlコンパイラを作ったということ。↩
  3. GitHubのAQamlレポジトリで initial commit は11月12日となっています。意外とはやくセルフホストまで行き着きました。↩
  4. WordPressってどうやったらGitHubリンク埋め込めるんだろうか。 Twitterカードっぽく出せると良いんだけど、やり方が分からん。↩
  5. 「基本的な」データ構造ということは「応用的な」データ構造もあるのかと言われると、それはよくわからない。ちょうど、「京大の数学の問題は基本的だ」というステートメントに近いかもしれない。↩
  6. 関数が「基本的な」制御構造かと言われるとかなり疑問ですが、ほかに押し込むべき場所もなかったので、言葉の綾ということで。↩
  7. ガベージコレクション、またの名を「ゴミ集め」。不要になったメモリ空間を勝手に開放する機構のこと。 C言語を知っている人は、malloc(3)したメモリ領域を勝手にfree(3)してくれる機構、というのが一番分かりやすいかと。 Javaを知っている人は、ほら、なんかnewすると勝手に領域確保するけど、それいつ開放されてると思う？みたいな話です。↩
  8. ところで京大前の「ラジュ」というカレー屋がおいしいのでおすすめ。↩
  9. これはちょっと驚く人も居たり居なかったりするんじゃないだろうか。型推論というのは、プログラマがコード中に型を書かなくても、コンパイラの方でよしなに型を予測してくれるという機構で、OCamlに似た言語（MLと呼ばれる）でよく目にする。言ってみればMLを特徴づける言語機能の1つと言ってもいいものなんだけれど、実はAQamlには搭載されていない。これが意味することはつまり、コードの型が分からなくても（一部例外を除いて）OCamlはアセンブリに変換できるということなのです。↩
  10. 嘘です。むしろ単位が大学生の奴隷ではあるまいか。↩
  11. 嘘です。↩
  12. ほとんどセキュキャンCコンパイラ開発ゼミのときの方針の横流し。横流しは恥だが役に立つ。恥でもない。↩
  13. セルフホストしてから作ればいいし。↩
  14. 私がセキュキャン全国大会で作成したCコンパイラ。レポジトリはこちら。↩
  15. これを勾配降下法と言います。嘘です。↩
  16. 偉そうに書いていますが、本当にこれがクロージャを特徴付けているかは自信がありません。おしえてエロい人。↩
  17. 例えば「nが偶数であるとは(n-1)が奇数であることであり、nが奇数であるとは(n-1)が偶数であることである。ただし0は偶数とする」のような関数のことを相互再帰関数といいます。↩
  18. 「鶏が先か、卵が先か」という問題。↩
  19. この手法はMinCamlからパクりました。↩
  20. それまで待てない！という人はぜひAQamlのコードリーディングをおすすめします。そしてバグを見つけてPull requestを投げてほしい。↩
  21. 苦労した挙げ句、結局hsjoihsさんに見つけてもらった。↩
  22. しないかもしれません。↩
  23. やっぱりaqccの時みたいに日記をつけておくべきだったかなぁ。あれ前日どんな開発をしていたかも思い出せるので、開発中も便利なんですよね。↩
  24. こないだ偏頭痛で嘔吐したので病院に行ったら、肩こり治療に鍼を進められました。西洋医学の先生から鍼という言葉が出てくるのは新鮮でした。↩
  25. タイトルはフランス語で「文法規則」だそうです。 OCamlはフランスで開発された部分が多い（らしい）のでフランス語の資料が多い――気がしなくもないです。↩