僕は先日、「コンパイル時Cコンパイラ」なるプログラムをつくって、公開した。
「コンパイル時Cコンパイラ」とは、コンパイルするとC言語プログラムのコンパイルが行われるというようなC++プログラムである。
C++のコンパイル中に C言語プログラムのコンパイルを行う、
— うどん (@kw_udon_) 2016年11月18日
"コンパイル時Cコンパイラ"をつくりました #ELVMhttps://t.co/kKiLU3rLFX
自分で書いておいてなんだが、「なんのこっちゃ」という感じではある。(ちゃんと記事中で説明する。)
実際、変なプログラムではあるのだが、とても嬉しいことに多くの人に面白がっていただき、予想だにしなかった大きな反響をいただいた。 Hacker Newsで1位になったり、LLVMの公式ブログで紹介されたり、果てはC++の作者であるBjarne Stroustrupにも言及されるに至った。
今回はその「コンパイル時Cコンパイラ」について書こうと思う。
まずはそもそも「コンパイル時Cコンパイラ」とは一体何なのかということを説明をする。 次にそれをどうやってつくったかについて、そして最後に「もうひとつの」コンパイル時Cコンパイラについて、書こうと思う。
お付き合いいただけたら、幸いである。
この記事はC++ Advent Calendar 2016の3日目の記事として書かれました。
2日目の記事はC++ ヘッダとソースでファイルを分ける 応用編 - Qiita でした。4日目の記事は VS2017の新機能 · GitHub です。
そもそも、コンパイル時Cコンパイラとは？
コンパイル時Cコンパイラと聞くと、「コンパイルする時を、"コンパイル時"というのだから、コンパイル時コンパイラって当たり前なのでは？」と思う人もいるかもしれない。
だが、そういうことではない。 コンパイル時Cコンパイラは、「コンパイル時計算として、C言語コンパイルを行う」C++プログラムである。 C++er向けに書くと、「C++14のconstexpr関数として実装されたCコンパイラ」のことである。
ということで、まず、コンパイル時計算についての説明からはじめる。
C++のコンパイル時計算
コンパイル時計算とは、ざっくりいってしまうと、実行時の状態に依存しない計算を、前もってコンパイルの際にやってしまうことである。 それによって、その部分は実行時には定数として扱うことができるのである。
例として、以下のC++プログラムを考える。これは、実行時に「0〜100の合計を計算し、それを出力する」普通のプログラムである。
#include<cstdio> int sum(int n) { int x = 0; for (int i = 0; i <= n; ++i) { x += i; } return x; } int main () { int x = sum(100); printf("%d\n", x); }
このプログラムをコンパイルし、実行すると、"5050" が出力される。
さて、このプログラムは入力に依存したり、乱数を使ったりしていない。
そのため、出力される変数xの値は、常に"5050"である。
よって、もし、int x = sum(100); の部分を、 int x = 5050; としても、プログラムを実行する側にとっては、何も問題ない。
むしろ、実行の際に、ループを回して計算する必要がないので、こっちの方が実行時間は短くて済むので嬉しい。
ただ、この"5050" という値を別途計算して、手でソースコードに埋め込むというのは、全くプログラマ的ではない。 では、どうするか。 ここで出てくるのが、コンパイル時計算である。
先ほどのプログラムに、次のように constexpr キーワードを追加する。
#include<cstdio> constexpr int sum(int n) { // constexprを追加 int x = 0; for (int i = 0; i <= n; ++i) { x += i; } return x; } int main () { constexpr int x = sum(100); // constexprを追加 printf("%d\n", x); }
この constexpr は、"constant expression"(定数式)の略であり、コンパイル時に値が決定する定数やコンパイル時に実行される関数につけるキーワードである。
(詳しくはリファレンス)
よって、このプログラムをコンパイルすると、sum(100) の計算がコンパイル中に 行われるようになる。
その結果、コンパイルが終わった時には、"5050" という値は既に求まっており、実行ファイルに定数 として埋め込まれている。
そして、その実行ファイルは定数"5050"を出力するだけのものである。
constexpr内でかける処理に関しては制約はあるし、そもそも入力に依存する計算はコンパイル時にはできないので、コンパイル時計算は万能ではないが、実行時のパフォーマンスの向上のための有効な手段の一つである。
コンパイル時Cコンパイラ
さて、「0〜100の和の計算」を例にコンパイル時計算を説明してきたが、和を計算するだけじゃ、コンパイル時計算の力を引き出しきれているとは言い切れない。 もっと複雑な計算だって、コンパイル時にできるはずである。
そう。たとえば、コンパイルだってできるかもしれない。
コンパイラだって、言ってしまえばただのプログラムである。 そのため、コンパイル時計算としてコンパイルができても何も不思議ではない。
というわけで、コンパイル時計算として Cプログラムのコンパイルを行うのが、「コンパイル時Cコンパイラ」である。
これは、8cc というCコンパイラの、C++の定数式への移植とみることもできる。
「0〜100の和」の例との対比で、挙動を説明をしてみる。 先ほどのコンパイル時に和を求めるプログラムをC++のコンパイラ(たとえばg++)を使ってコンパイルし、実行すると、次のようになる:
- コンパイル中に「0〜100の和の計算」が行われ、
- "5050"という値が定数として、実行ファイルに埋め込まれ、
- 実行時に、定数である5050が出力される
これに対し、コンパイル時コンパイラをg++でコンパイルすると次のようになる:
ちなみに、入力に関してだが、constexpr関数は入力をとれないので、文字列化したCプログラムを、プリプロセッサでソースコードに埋め込むということをやっている。
ちなみに"Hello World"のコンパイルは、3分くらいかかるもののちゃんとできる。 メモリ8GBのラップトップで動作を確認している。 g++ 6.2が入っていれば、簡単に試せるので、よかったら試してみて欲しい。
何の役に立つの？
もし万が一、「コンパイル時Cコンパイラ、なんか便利そう!」と思ってここまで読んでくださった方がいらっしゃったとしたら、本当に申し訳ない。 僕の文章力不足だ。コンパイル時Cコンパイラは基本的に役に立たない。 コンパイル時CコンパイラでCプログラムをコンパイルするには、GCCが必要になるが、手元にGCCがあるなら、直接GCCでコンパイルすればよいのである。
コンパイル時Cコンパイラは、言ってしまえば、ジョークプログラムなので、 「名前の響きが面白い」とか、「C++のコンパイル時計算はこんなことまでできるのか」とか、そういうことを感じてもらえればありがたい。
コンパイル時Cコンパイラのつくりかた
さて、コンパイル時Cコンパイラとは一体何かということを説明したところで、じゃあ、どうやって作ったのか、という話に移る。
ただ、つくったとは言ったが、僕はコンパイラを自分の手で実装したわけではない。 ELVMという機構を利用し、C言語で実装された8ccをconstexprへ翻訳したのである。 それについて、書く。 これ以降、若干テクニカルな話になる。
8ccとは？
8ccはrui314さん作のCで実装されたセルフホストされたCコンパイラである。 C11をサポートしているのに1万行程度とコンパクトで、しかもわかりやすい綺麗なコードで書かれていて、非常にクール。 今回は、この8ccをELVMでconstexprへ変換するということをした。
ELVMとは？
ELVMとは、EsoLang Virtual Machineの略で、C言語プログラムから他の言語への変換を行うためのコンパイラ基盤である。 これを使うと、C言語プログラムをBrainF*ckプログラムに変換したりできる。
詳しくは作者のid:shinichiro_hさんのスライドがわかりやすい。 構造を軽く説明するとELVMは、
からできている。
このELVMをつかうと、例えば、
「フロントエンドでCコンパイラをIRに変換し、バックエンドでIR→BrainF*ckの変換を行うことで、BrainF*ckで実装されたCコンパイラを得る」
というようなことができる。 現在、ELVMのバックエンドはEsoLang(難解言語)を中心に、20個以上のターゲット言語に対応している。(README参照) それによって、色々な人の手によって、世界に変な言語によるCコンパイラ達が誕生した。
僕もこの流れに乗って、ELVMを利用した。 つまり、僕は実際にやったことは、ELVMのconstexprバックエンドを実装ということになる。
ELVMのconstexprバックエンド
さて、ELVMのconstexprバックエンドであるが、僕ははC言語バックエンドをベースに改造することで実装した。
Cバックエンドはこんな感じの、ELVM IRの実行をシミュレートするようなCプログラムが出力する。
ELVMのCバックエンド・constexprバックエンドの出力例 · GitHub
レジスタとメモリに対応するグローバル変数を用意して、プログラムカウンタpcの値によって、対応する処理を実行するというようなプログラムである。
ELVM IRとの対応も取りやすいとおもう。
僕が作ったconstexprバックエンドもこれと似たようなプログラムを出力する。 C++14でconstexpr関数内での制限が緩和されたおかげで(参考)、プログラムの構造はほとんど同じである。 とはいえ、まだ制約はあり、主に次の3点について工夫が必要だった:
- 入出力
- グローバル変数
- 関数間の状態共有
順に説明する。
1. 入出力
C言語バックエンドでは、getcとputcに対応して、それぞれ getchar, putchar を吐くようになっていたが、残念ながらこれらの関数は実行時にしか使えないので、工夫が必要であった。
これに関しては、id:bolerosさんの コンパイル時BrainF*ckコンパイラを参考にした。
具体的には、入力はプリプロセス時に文字列として埋め込むようにした。
そして、getc のたびにカーソルを文字列の先頭から動かしていき、値を取得する。
一方、出力はバッファに溜め、実行時にそれを出力するという形をとった。
2. グローバル変数
Cのバックエンドが吐くプログラムでは、メモリやレジスタをグローバル変数で管理していた。 しかし、C++14のconstexprでは、副作用は関数内にとどめる必要があり、グローバル変数へのアクセスはできない。 では、どうしたか。単純に、グローバル変数ではなく、関数内で定義するようにした。
3. 関数間の状態共有
これは2.に関連する。 C言語バックエンドが生成したプログラムはグローバル変数を使って、関数間で状態の共有を行っていたが、2 でそれができなくなった。 複数の関数で変数の状態を共有するには、いちいち値をコピーして引数として渡さなければならない。 それは計算コストがかかるので嫌だ。 では、どうしたか。関数間で状態を共有しないですむように、全部の処理を一つの関数内で完結するようにした。 つまり、処理を全部巨大constexpr関数内でやる感じ。力技である。
大体こんな感じだったので、あまり技術的困難さは感じなかった。
そうしてできたconstexprバックエンドをつかって、8ccを変換してできたのが、8cc.hppである。
約150000行・2.8MBの巨大ファイルである。
eight_cc というconstexpr関数が本体なのだが、こいつはcaseの数が8300個以上の巨大switch文をもっているといった感じだ。
まぁ、人間が読むものではない。
constexpr-8ccを試すには、cloneしてきて、
$ g++-6 -D'EIGHT_CC_INPUT_FILE="./test/putchar.c.txt"' ./8cc.cpp
としてみればよい。
ファイル"./test/putchar.c.txt" の中身は、文字列化されたCプログラムである。これがプリプロセッサによって、ソースコードに埋め込まれる。
そして、それを入力とみなして、コンパイルが行われるのである。
ちなみに、これはg++6.2必須である。
Clangだと、constexprによるコンパイル時計算のステップ数に上限があり、それに引っかかってしまう。(GCCには上限がなさそうだが、未調査。)
また、g++ 5系で動かそうとすると、index_tuple のinstantiationの深さが上限を超えたというエラーで動かない。（5系と6系にどんな違いがあるのかは調査してないので、理由は不明）
こうして、ELVMのconstexprバックエンドができたわけであるが、これを使えば、色んな「コンパイル時〇〇」が簡単にできる。
「〇〇」をするプログラムをC言語で実装して、ELVMで変換かければ、あっという間に「コンパイル時〇〇」をするプログラムができるのである。 これはもう、なんでもコンパイル時にできてしまう時代の幕開けかもしれない。（これは冗談で、流石にそんなことはない）
余談: 反響について
冒頭にも書いたが、ありがたいことに、constexpr-8ccは色々な人に面白がっていただいた。 本当に嬉しかった。(嬉しさからエゴサしまくったのは恥ずかしいので内緒)
どうも、Hacker Newsで1位になったのがきっかけだったのかとおもう。 C++14でconstexprの制約を緩和してくださった方にも届いたようである。 また、ELVMはLLVMのパロディであるが、それが公式であるところのLLVMに言及されたのも面白かった。LLVM Weeklyという公式のブログ中にもコメントがある。
そして、その後、C++の作者であるBjarne Stroustrupにまで言及されるに至った。 偶然にもちょうどMeeting C++というカンファレンスが行われていたタイミングだったようだ。
btw, Bjarnes comment on the constexpr C++14 C compiler during #meetingcpp was, "its only a C compiler if it handles pointers and unions".
— Meeting C++ (@meetingcpp) 2016年11月20日
インターネットすごい。本当にびっくりした。
ちなみにこのコメント、はじめ読んだ時、"handles" の主語の it が何を指しているか掴めず、意味がわからなかったが、 pointerとunionが扱えないということから、この"it"は"constexpr"なのではないかと思われる。*3
ひとつ目のitはコンパイル時コンパイラだと思うので、訳してみると、
「もしconstexprでポインタと共用体が扱えるようになったら、コンパイル時コンパイラはただの(実行時)Cコンパイラになるだろう」
みたいな感じだろうか。 constexprの自由度が高まってきており、もう少しで、コンパイル時と実行時でできることに差異がなくなりそう、みたいな意味かと思う。
文中のconstexprでポインタが扱えないというのは、mallocのような動的なメモリ確保ができないことかとおもう。 また、共用体が扱えないというのは、次のようなコードの話だと思われる。
union Uni { float f; int i; }; constexpr int f() { Uni u = {1.0f}; // 初期化したのは'f'なので、 return u.i; // 'i'にはアクセスできない } int main() { constexpr int x = f(); // なので、コンパイルエラー return 0; }
ちなみに"handles" の主語の itを「コンパイル時コンパイラ」としても
「もしコンパイル時コンパイラがポインタと共用体を扱える(サポートしている)なら、単なるCコンパイラである」
となって意味は通るのだが、なぜわざわざ「ポインタと共用体」がでてきたのかということがわからなくなる。 8ccはもちろんポインタと共用体を使ったプログラムもコンパイルできる。 また、Cコンパイラにおける共用体のサポートは、構造体をサポートしていれば容易にできるはずである。 そのため構造体より使用頻度の低い(はず)の共用体をわざわざ名指しするのには違和感がある。
ただ、なんか勘違いをしてるかもしれないので、指摘・ツッコミがあればよろしくおねがいします。
「もうひとつの」コンパイル時Cコンパイラ
さて、ここで記事を終わりにしてもよかったのだが、せっかくなので、「もうひとつ」のコンパイル時Cコンパイラの話も書こうと思う。
C++のコンパイル時計算はconstexprの他に「もうひとつ」ある。
そう、テンプレートメタプログラミング(TMP) である。
というわけで テンプレートメタプログラミングによる コンパイル時Cコンパイラがこちらである。
だが、このコンパイラの実行、すなわちGCCでのコンパイルは絶対にやってはいけない!! GCCがメモリを喰らい尽くしてしまうからだ。
というわけで、カッコつけて「もうひとつの」なんて書いてしまったが、このTMP-8ccは、動かすことのできない、失敗作の 観賞用のコンパイル時Cコンパイラである。
constexpr版コンパイラができたので、こちらはお蔵入りにする予定だったが、せっかくなので(蛇足かもしれないが)その話も書くことにした。
経緯
時系列的にいうと、TMP版を作り始めたのはconstexpr版よりも前の話である。 まず、TwitterでELVMを知った時に思い出したのが @akabeさん作のEvil ML である。 Evil MLはMLのプログラムをC++テンプレートに変換するコンパイラである。 じゃあ、これみたいな感じで、ELVMのC++テンプレートバックエンドを書いたら面白いのではないかというように着想を得た。
ELVMのTMPバックエンド
テンプレートメタプログラミング(TMP)は、C++のテンプレートを純粋関数型言語とみなしてプログラミングを行うものである。 そのため、ELVMバックエンドを実装するにあたって問題になるのは、環境の破壊的変更をいかにシミュレートするかということである。 ここでいう環境とは、VMのレジスタ・メモリの状態・入出力バッファである。例えばメモリへの書き込みなどが破壊的変更にあたる。
この問題にはStore-passing Styleというテクニックを使えばよい。 これは状態(あるいは環境)を関数間で引数・返り値として、持ち回すというものである。
別に難しい話ではなく、
引数 → 返値 という副作用ありの関数のかわりに、
(引数、環境) → (返値、新しい環境) というような副作用なしの関数を書くというイメージである。
このテクニックは、関数型プログラミングで副作用を扱えない・扱いたくないときによくつかわれる。
というわけで、ELVMのTMPバックエンドをつくるにあたって、まず、ELVMの各命令に対応する処理をテンプレートで実装したライブラリ的なものをつくった。 それがこれである。 見てもらえばわかるが、movやstoreなど各命令に対応する処理がかかれている。 また、メモリを2分木として実装するなどしている。
そして、ELVMでのバックエンドが吐くプログラムはこれらの処理を呼ぶようにした。
そうして、できたTMPバックエンドはforkしてきたレポジトリで別ブランチとして公開している。
$ CPP_TEMPL=1 make cpp_templ とすると、いくつかテストが走る。(が、最後までは動かないので、適度なところでkillしてやる必要がある。)
Gistに出力例をおいておく。 ELVMの変換例: EIR, C++Template, C, constexprの比較 · GitHub
イメージがつきやすいように抜粋すると、
mov B, 77 store B, 300 load A, 300
というような命令は、
typedef mov_imm <r0, b, 77> r1; typedef store_imm<r1, m0, b, 300> m1; typedef load_imm <r1, m1, a, 300> r2;
というように変換される。
r0, r1はレジスタの状態に対応する型、m0,m1はメモリの状態に対応する型である。
一行目は、今のレジスタの状態r0 と レジスタ名 b、値77を引数として、mov_immという関数に渡すと、レジスタbの値が77に書き換えられた新しいレジスタの状態r1が得られるというような感じで読める。
ちなみにこの記事を書いている最中に、id:iroriさんによるELVMのUnlambdaバックエンドの記事が公開された。(前編、後編) Unlambdaは難解言語の一種で、純粋関数型言語である。そのため、僕のTMPバックエンドの実装方針と一部似ている部分がある。 しかし、Unlambdaのほうがずっと制約もきつく、より面白いことをやっているように思える。
ただ、このTMPバックエンド、できたはいいものの、生成されるコードはまともに動かない。 手でかかれたELVM IRから生成したコードはある程度動くが、Cから生成されたものになると全然だめである。
具体的にどれくらい動かないかというと、FizzBuzzで10まで表示させるプログラムの計算に約10分 かかり、メモリを82.5GB程度使う。たまたまAWSの無料クレジットをもっていたのでRAMが100GB以上のインスタンスを借りて、なんとか動かすことができたというレベルだ。
しかも、この使用するメモリの量は実行ステップ数が増えるにつれて、ガンガン増えていく。 (計測は十分ではないが、一応FizzBuzzで5までの場合は約1分半、使用メモリは16GB程度だったので、メモリ使用量増加のオーダーはステップ数の線形では済まないっぽい。)
注意してほしいのは、これはFizzBuzzプログラムのコンパイルではない。0, 1, 2, Fizz, ... と出力するだけである。
FizzBuzzの実行ステップ数とCプログラムのコンパイルの実行ステップ数は比べ物にならないはずなので、TMPバックエンドによるTMPコンパイル時Cコンパイラの実行は絶望的である。
TMP-8ccが動かない理由
さて、どうして、そんなにメモリを食うのだろうか。 Unlambdaの方が実装上の制約はきついのに、(1日以上かかるらしいが)動いているのだから、TMPの方も動いてもよいのではないか。
UnlambdaCコンパイラが動いて、TMP Cコンパイラが動かない原因は、端的にいうと処理系におけるメモリ解放の有無だと考えられる。
Unlambdaでは、新たな環境が作成されたら、古い環境はもう不要なので、インタプリタ上のGCによって解放される。
一方で、TMPでは不要になった古い環境も保持される。というのも、「環境」といっても実のところ、C++における型情報だからである。 C++コンパイラの気持ちになれば、判明した型情報を最後まで保持しておくのは、当然である。
これはつまり、TMPバックエンドが吐いたプログラムは、今までの環境の履歴を全てメモリ上に保持し続けながら計算が進んでいくということを意味する。 例えば、storeが行われるたびに、メモリの全コピーをすることになるが、そのとき、コピー前のメモリの状態も全てメモリ上に残るのである。 こんなの、現実のマシンでまともに動くわけがない。
TMP-8ccを動かすには、要らなくなった型情報をガンガン捨てていくTMP専用C++コンパイラをつくる必要がある気がする。(そんなことができるのかはよくわからず、適当書いている)
ちなみにTMPバックエンドで生成したプログラムがまともに動かないことに気づいた頃に、shinhさんがELVM公開直後にしていたこんなツイートを見つけた。
「TMPのアイディア自体は既出で、まともに動かないことまで予期されていたのか」と少し悔しくなった。ELVMで8ccをC++ templateに変換してC++くらいになるとコンパイルタイムにコンパイラが動くぜ？てネタをやろうかと思ったけど現実的な時間で動く気がしない。D compile-timeだと自明だろうしなあ
— shinichiro hamaji (@shinh) 2016年10月18日
ただ、個人的にはTMPは今回のためにはじめて触ったこともあり、やってみなければ無理だということもわからなかったので、やってよかったと思う。 それに、shinhさんはconstexprバックエンドまでは考えていなかったっぽい。 個人的には最終的にconstexprという良い着地点が見つかって、コンパイル時Cコンパイラを実現できたので、満足であった。
Related Work
最後に、関連する他プロジェクトについてまとめておく。
Cプログラムから、他言語への変換ができることは言われてみればそれはそうだが、実際に実装し、しかも現実に動くものをつくってしまうのはすごい。 また、バックエンドも書きやすいように設計されており、とてもありがたかった。
今回僕はコンパイラをつくったといっても、実質変換器を書いただけであったが、以前、Cコンパイラを実装したこともある。 8ccを知ったのはその頃だ。とてもわかりやすくかかれているので、「Cコンパイラって案外自分でもかけるかも」という気持ちにさせられた。 また当時、作者のruiさんの8ccを開発したときの日記も読んで、奮い立たされたのを覚えている。 そのようなこともあり、今回、ruiさんにも面白がってもらえたのは、個人的にかなり嬉しかった。
- ELVMで作られた他のコンパイラ達
昨日・今日で各アドベントカレンダーの記事として、ELVMの色々なバックエンドに関する記事が公開された。 バックエンド言語ごとの工夫があって、楽しい。
- Unlambda UnlambdaでVMを実装する（前編） - iroriの日記, UnlambdaでVMを実装する（後編） - iroriの日記
- Vim Script ELVM で C コンパイラをポーティングしてみよう（Vim script 編） - はやくプログラムになりたい
- TeX ELVMにTeXバックエンドを足した話 - hak7a3が書き残す何か
MLから、C++テンプレートへ変換するコンパイラ。TMP-8cc のセクションでも触れたとおり、ELVMのバックエンドとして、C++のテンプレートをやってみようという発想は、これに影響された。
C++14のconstexprで実装された、Brainf*ckコンパイラ。
僕のは世界初のconstexprで書かれたコンパイル時Cコンパイラのはずだが、単にconstexprで書かれたコンパイル時コンパイラ」としてなら、こっちが世界初だと思われる。
入力を#include で埋め込むといったアイディアなどはここからいただいた。
また、作者の中３女子さんはconstexprに関してライブラリや多くの資料を公開されており、それらも実装の際に参考にさせていただいた。
- 手書きのC++11 TMPによる"ちゃんと動く"コンパイル時Cコンパイラ (2018年追記)
本文中ではTMPによるコンパイル時Cコンパイラを動かすことを諦めたと書いたが，本記事公開から約1年後の2017年12月に現実のマシンで実行できるTMPによるコンパイル時Cコンパイラが登場した． それがltmpcである． これは自動生成ではなく，手で実装されており，TMPの色々なテクニックをつかって，メモリ消費量の問題に立ち向かっている． 本当に凄い． Qiitaにある解説も詳しい．
以上が、「コンパイル時Cコンパイラ」をつくった話である。 ELVMをいじって、コンパイル時Cコンパイラをつくるのはめちゃくちゃ楽しかった。 ELVM作者のshinhさんと、8cc作者のrui314さんには感謝したい。 みなさんも、ELVMで遊んでみてはいかがでしょうか？
ちなみに、shihさんは、今、TensorFlowバックエンドを実装しているようである。 意味がわからない。面白すぎる。
おわり
