そもそも、コンパイル時Cコンパイラとは?コンパイル時Cコンパイラと聞くと、「コンパイルする時を、"コンパイル時"というのだから、コンパイル時コンパイラって当たり前なのでは?」と思う人もいるかもしれない。コンパイル時Cコンパイラは、「コンパイル時計算として、C言語コンパイルを行う」C++プログラムである。C++er向けに書くと、「C++14のconstexpr関数として実装されたCコンパイラ」のことである。いうことで、まず、コンパイル時計算についての説明からはじめる。C++のコンパイル時計算コンパイル時計算とは、ざっくりいってしまうと、実行時の状態に依存しない計算を、前もってコンパイルの際にやってしまうことである。それによって、その部分は実行時には定数として扱うことができるのである。例として、以下のC++プログラムを考える。これは、実行時に「0〜100の合計を計算し、それを出力する」普通のプログラムである。このプログラムは入力に依存したり、乱数を使ったりしていない。そのため、出力される変数xの値は、常に"5050"である。しても、プログラムを実行する側にとっては、何も問題ない。実行の際に、ループを回して計算する必要がないので、こっちの方が実行時間は短くて済むので嬉しい。いう値を別途計算して、手でソースコードに埋め込むというのは、全くプログラマ的ではない。ここで出てくるのが、コンパイル時計算である。キーワードを追加する。expression"(定数式)の略であり、コンパイル時に値が決定する定数やコンパイル時に実行される関数につけるキーワードである。して埋め込まれている。その実行ファイルは定数"5050"を出力するだけのものである。これがC++におけるコンパイル時計算*1の例である。constexpr内でかける処理に関しては制約はあるし、そもそも入力に依存する計算はコンパイル時にはできないので、コンパイル時計算は万能ではないが、実行時のパフォーマンスの向上のための有効な手段の一つである。コンパイル時Cコンパイラさて、「0〜100の和の計算」を例にコンパイル時計算を説明してきたが、和を計算するだけじゃ、コンパイル時計算の力を引き出しきれているとは言い切れない。複雑な計算だって、コンパイル時にできるはずである。コンパイルだってできるかもしれない。コンパイラだって、言ってしまえばただのプログラムである。そのため、コンパイル時計算としてコンパイルができても何も不思議ではない。Cプログラムのコンパイルを行うのが、「コンパイル時Cコンパイラ」である。いうCコンパイラの、C++の定数式への移植とみることもできる。「0〜100の和」の例との対比で、挙動を説明をしてみる。実行時に、定数であるコンパイル結果が出力されるちなみに、入力に関してだが、constexpr関数は入力をとれないので、文字列化したCプログラムを、プリプロセッサでソースコードに埋め込むということをやっている。これが、コンパイル時Cコンパイラである。World"のコンパイルは、3分くらいかかるもののちゃんとできる。メモリ8GBのラップトップで動作を確認している。6.2が入っていれば、簡単に試せるので、よかったら試してみて欲しい。何の役に立つの?もし万が一、「コンパイル時Cコンパイラ、なんか便利そう!」と思ってここまで読んでくださった方がいらっしゃったとしたら、本当に申し訳ない。コンパイル時Cコンパイラは基本的に役に立たない。コンパイル時CコンパイラでCプログラムをコンパイルするには、GCCが必要になるが、手元にGCCがあるなら、直接GCCでコンパイルすればよいのである。「名前の響きが面白い」とか、「C++のコンパイル時計算はこんなことまでできるのか」とか、そういうことを感じてもらえればありがたい。コンパイル時Cコンパイラのつくりかたさて、コンパイル時Cコンパイラとは一体何かということを説明したところで、じゃあ、どうやって作ったのか、という話に移る。つくったとは言ったが、僕はコンパイラを自分の手で実装したわけではない。ELVMという機構を利用し、C言語で実装された8ccをconstexprへ翻訳したのである。これ以降、若干テクニカルな話になる。8ccとは?8ccはrui314さん作のCで実装されたセルフホストされたCコンパイラである。C11をサポートしているのに1万行程度とコンパクトで、しかもわかりやすい綺麗なコードで書かれていて、非常にクール。今回は、この8ccをELVMでconstexprへ変換するということをした。Machineの略で、C言語プログラムから他の言語への変換を行うためのコンパイラ基盤である。これを使うと、C言語プログラムをBrainF*ckプログラムに変換したりできる。詳しくは作者のid:shinichiro_hさんのスライドがわかりやすい。IRを別の言語へ翻訳するバックエンドからできている。「フロントエンドでCコンパイラをIRに変換し、バックエンドでIR→BrainF*ckの変換を行うことで、BrainF*ckで実装されたCコンパイラを得る」というようなことができる。現在、ELVMのバックエンドはEsoLang(難解言語)を中心に、20個以上のターゲット言語に対応している。それによって、色々な人の手によって、世界に変な言語によるCコンパイラ達が誕生した。Cコンパイラ僕もこの流れに乗って、ELVMを利用した。僕は実際にやったことは、ELVMのconstexprバックエンドを実装ということになる。ELVMのconstexprバックエンドさて、ELVMのconstexprバックエンドであるが、僕ははC言語バックエンドをベースに改造することで実装した。IRの実行をシミュレートするようなCプログラムが出力する。GitHubレジスタとメモリに対応するグローバル変数を用意して、プログラムカウンタpcの値によって、対応する処理を実行するというようなプログラムである。IRとの対応も取りやすいとおもう。僕が作ったconstexprバックエンドもこれと似たようなプログラムを出力する。C++14でconstexpr関数内での制限が緩和されたおかげで(参考)、プログラムの構造はほとんど同じである。吐くようになっていたが、残念ながらこれらの関数は実行時にしか使えないので、工夫が必要であった。コンパイル時BrainF*ckコンパイラを参考にした。具体的には、入力はプリプロセス時に文字列として埋め込むようにした。たびにカーソルを文字列の先頭から動かしていき、値を取得する。出力はバッファに溜め、実行時にそれを出力するという形をとった。グローバル変数Cのバックエンドが吐くプログラムでは、メモリやレジスタをグローバル変数で管理していた。C++14のconstexprでは、副作用は関数内にとどめる必要があり、グローバル変数へのアクセスはできない。単純に、グローバル変数ではなく、関数内で定義するようにした。関数間の状態共有これは2.に関連する。それができなくなった。複数の関数で変数の状態を共有するには、いちいち値をコピーして引数として渡さなければならない。それは計算コストがかかるので嫌だ。関数間で状態を共有しないですむように、全部の処理を一つの関数内で完結するようにした。処理を全部巨大constexpr関数内でやる感じ。大体こんな感じだったので、あまり技術的困難さは感じなかった。してできたconstexprバックエンドをつかって、8ccを変換してできたのが、8cc.hppである。約150000行・2.8MBの巨大ファイルである。いうconstexpr関数が本体なのだが、こいつはcaseの数が8300個以上の巨大switch文をもっているといった感じだ。人間が読むものではない。./8cc.cppとしてみればよい。中身は、文字列化されたCプログラムである。これがプリプロセッサによって、ソースコードに埋め込まれる。それを入力とみなして、コンパイルが行われるのである。ちなみに、これはg++6.2必須である。Clangだと、constexprによるコンパイル時計算のステップ数に上限があり、それに引っかかってしまう。(GCCには上限がなさそうだが、未調査。instantiationの深さが上限を超えたというエラーで動かない。(5系と6系にどんな違いがあるのかは調査してないので、理由は不明)こうして、ELVMのconstexprバックエンドができたわけであるが、これを使えば、色んな「コンパイル時〇〇」が簡単にできる。「〇〇」をするプログラムをC言語で実装して、ELVMで変換かければ、あっという間に「コンパイル時〇〇」をするプログラムができるのである。これはもう、なんでもコンパイル時にできてしまう時代の幕開けかもしれない。反響について冒頭にも書いたが、ありがたいことに、constexpr-8ccは色々な人に面白がっていただいた。Newsで1位になったのがきっかけだったのかとおもう。C++14でconstexprの制約を緩和してくださった方にも届いたようである。ELVMはLLVMのパロディであるが、それが公式であるところのLLVMに言及されたのも面白かった。Weeklyという公式のブログ中にもコメントがある。Stroustrupにまで言及されるに至った。C++というカンファレンスが行われていたタイミングだったようだ。2016年11月20日インターネットすごい。pointerとunionが扱えないということから、この"it"は"constexpr"なのではないかと思われる。「もしconstexprでポインタと共用体が扱えるようになったら、コンパイル時コンパイラはただの(実行時)Cコンパイラになるだろう」みたいな感じだろうか。constexprの自由度が高まってきており、もう少しで、コンパイル時と実行時でできることに差異がなくなりそう、みたいな意味かと思う。文中のconstexprでポインタが扱えないというのは、mallocのような動的なメモリ確保ができないことかとおもう。共用体が扱えないというのは、次のようなコードの話だと思われる。itを「コンパイル時コンパイラ」としても「もしコンパイル時コンパイラがポインタと共用体を扱える(サポートしている)なら、単なるCコンパイラである」となって意味は通るのだが、なぜわざわざ「ポインタと共用体」がでてきたのかということがわからなくなる。8ccはもちろんポインタと共用体を使ったプログラムもコンパイルできる。Cコンパイラにおける共用体のサポートは、構造体をサポートしていれば容易にできるはずである。そのため構造体より使用頻度の低い(はず)の共用体をわざわざ名指しするのには違和感がある。なんか勘違いをしてるかもしれないので、指摘・ツッコミがあればよろしくおねがいします。「もうひとつの」コンパイル時Cコンパイラさて、ここで記事を終わりにしてもよかったのだが、せっかくなので、「もうひとつ」のコンパイル時Cコンパイラの話も書こうと思う。C++のコンパイル時計算はconstexprの他に「もうひとつ」ある。コンパイル時Cコンパイラがこちらである。GCCがメモリを喰らい尽くしてしまうからだ。観賞用のコンパイル時Cコンパイラである。constexpr版コンパイラができたので、こちらはお蔵入りにする予定だったが、せっかくなので(蛇足かもしれないが)その話も書くことにした。時系列的にいうと、TMP版を作り始めたのはconstexpr版よりも前の話である。MLはMLのプログラムをC++テンプレートに変換するコンパイラである。これみたいな感じで、ELVMのC++テンプレートバックエンドを書いたら面白いのではないかというように着想を得た。ELVMのTMPバックエンドテンプレートメタプログラミング(TMP)は、C++のテンプレートを純粋関数型言語とみなしてプログラミングを行うものである。そのため、ELVMバックエンドを実装するにあたって問題になるのは、環境の破壊的変更をいかにシミュレートするかということである。ここでいう環境とは、VMのレジスタ・メモリの状態・入出力バッファである。メモリへの書き込みなどが破壊的変更にあたる。Styleというテクニックを使えばよい。これは状態(あるいは環境)を関数間で引数・返り値として、持ち回すというものである。いうような副作用なしの関数を書くというイメージである。このテクニックは、関数型プログラミングで副作用を扱えない・扱いたくないときによくつかわれる。いうわけで、ELVMのTMPバックエンドをつくるにあたって、まず、ELVMの各命令に対応する処理をテンプレートで実装したライブラリ的なものをつくった。見てもらえばわかるが、movやstoreなど各命令に対応する処理がかかれている。メモリを2分木として実装するなどしている。ELVMでのバックエンドが吐くプログラムはこれらの処理を呼ぶようにした。して、できたTMPバックエンドはforkしてきたレポジトリで別ブランチとして公開している。すると、いくつかテストが走る。(が、最後までは動かないので、適度なところでkillしてやる必要がある。)Gistに出力例をおいておく。r2;というように変換される。r1はレジスタの状態に対応する型、m0,m1はメモリの状態に対応する型である。b、値77を引数として、mov_immという関数に渡すと、レジスタbの値が77に書き換えられた新しいレジスタの状態r1が得られるというような感じで読める。ちなみにこの記事を書いている最中に、id:iroriさんによるELVMのUnlambdaバックエンドの記事が公開された。Unlambdaは難解言語の一種で、純粋関数型言語である。そのため、僕のTMPバックエンドの実装方針と一部似ている部分がある。Unlambdaのほうがずっと制約もきつく、より面白いことをやっているように思える。このTMPバックエンド、できたはいいものの、生成されるコードはまともに動かない。IRから生成したコードはある程度動くが、Cから生成されたものになると全然だめである。かかり、メモリを82.5GB程度使う。AWSの無料クレジットをもっていたのでRAMが100GB以上のインスタンスを借りて、なんとか動かすことができたというレベルだ。この使用するメモリの量は実行ステップ数が増えるにつれて、ガンガン増えていく。(計測は十分ではないが、一応FizzBuzzで5までの場合は約1分半、使用メモリは16GB程度だったので、メモリ使用量増加のオーダーはステップ数の線形では済まないっぽい。)注意してほしいのは、これはFizzBuzzプログラムのコンパイルではない。FizzBuzzの実行ステップ数とCプログラムのコンパイルの実行ステップ数は比べ物にならないはずなので、TMPバックエンドによるTMPコンパイル時Cコンパイラの実行は絶望的である。TMP-8ccが動かない理由さて、どうして、そんなにメモリを食うのだろうか。Unlambdaの方が実装上の制約はきついのに、(1日以上かかるらしいが)動いているのだから、TMPの方も動いてもよいのではないか。Cコンパイラが動かない原因は、端的にいうと処理系におけるメモリ解放の有無だと考えられる。Unlambdaでは、新たな環境が作成されたら、古い環境はもう不要なので、インタプリタ上のGCによって解放される。一方で、TMPでは不要になった古い環境も保持される。いうのも、「環境」といっても実のところ、C++における型情報だからである。C++コンパイラの気持ちになれば、判明した型情報を最後まで保持しておくのは、当然である。これはつまり、TMPバックエンドが吐いたプログラムは、今までの環境の履歴を全てメモリ上に保持し続けながら計算が進んでいくということを意味する。storeが行われるたびに、メモリの全コピーをすることになるが、そのとき、コピー前のメモリの状態も全てメモリ上に残るのである。こんなの、現実のマシンでまともに動くわけがない。TMP-8ccを動かすには、要らなくなった型情報をガンガン捨てていくTMP専用C++コンパイラをつくる必要がある気がする。(そんなことができるのかはよくわからず、適当書いている)ちなみにTMPバックエンドで生成したプログラムがまともに動かないことに気づいた頃に、shinhさんがELVM公開直後にしていたこんなツイートを見つけた。templateに変換してC++くらいになるとコンパイルタイムにコンパイラが動くぜ?てネタをやろうかと思ったけど現実的な時間で動く気がしない。「TMPのアイディア自体は既出で、まともに動かないことまで予期されていたのか」と少し悔しくなった。個人的にはTMPは今回のためにはじめて触ったこともあり、やってみなければ無理だということもわからなかったので、やってよかったと思う。それに、shinhさんはconstexprバックエンドまでは考えていなかったっぽい。個人的には最終的にconstexprという良い着地点が見つかって、コンパイル時Cコンパイラを実現できたので、満足であった。Work最後に、関連する他プロジェクトについてまとめておく。ELVMCプログラムから、他言語への変換ができることは言われてみればそれはそうだが、実際に実装し、しかも現実に動くものをつくってしまうのはすごい。バックエンドも書きやすいように設計されており、とてもありがたかった。8cc今回僕はコンパイラをつくったといっても、実質変換器を書いただけであったが、以前、Cコンパイラを実装したこともある。8ccを知ったのはその頃だ。わかりやすくかかれているので、「Cコンパイラって案外自分でもかけるかも」という気持ちにさせられた。当時、作者のruiさんの8ccを開発したときの日記も読んで、奮い立たされたのを覚えている。そのようなこともあり、今回、ruiさんにも面白がってもらえたのは、個人的にかなり嬉しかった。昨日・今日で各アドベントカレンダーの記事として、ELVMの色々なバックエンドに関する記事が公開された。バックエンド言語ごとの工夫があって、楽しい。MLMLから、C++テンプレートへ変換するコンパイラ。セクションでも触れたとおり、ELVMのバックエンドとして、C++のテンプレートをやってみようという発想は、これに影響された。コンパイル時Brainf*ckコンパイラC++14のconstexprで実装された、Brainf*ckコンパイラ。僕のは世界初のconstexprで書かれたコンパイル時Cコンパイラのはずだが、単にconstexprで書かれたコンパイル時コンパイラ」としてなら、こっちが世界初だと思われる。埋め込むといったアイディアなどはここからいただいた。作者の中3女子さんはconstexprに関してライブラリや多くの資料を公開されており、それらも実装の際に参考にさせていただいた。Qiita以上が、「コンパイル時Cコンパイラ」をつくった話である。ELVMをいじって、コンパイル時Cコンパイラをつくるのはめちゃくちゃ楽しかった。ELVM作者のshinhさんと、8cc作者のrui314さんには感謝したい。みなさんも、ELVMで遊んでみてはいかがでしょうか?ちなみに、shihさんは、今、TensorFlowバックエンドを実装しているようである。