ltmpcのはなし

C++テンプレートメタプログラミングによるコンパイルC言語コンパイラ、「ltmpc」を作っています。 やっとコードが生成できるようになったので、今日はそのはなしを書こうと思います。

動くものが見たい!

GitHub - lpha-z/ltmpc: C++11TMP compile time C compiler

はじめに

世の中には、プログラムを書くこと自体が難しいような、難解言語と呼ばれるものがあります。難解言語は何かを効率化するためにはあまり役に立ちませんが、その魅力から意外と愛好者がいるようです。

難解言語は手で書くのが難しいため、自動生成しようとの試みがよく起きます。それを推し進めたものとして、去年、ELVMというコンパイラ基盤が出現しました。

ELVM Compiler Infrastructure について - 兼雑記

これは、いきなりC言語ソースから難解言語ソースを生成するのではなく、途中に中間層をはさみ、フロントエンド・バックエンド構成としたものです。バックエンドは、各難解言語ごとに作る必要がありますが、フロントエンドの出力はかなり小さい命令セットを持った仮想機械語になっているので、バックエンドを制作するときは、それらの機械語だけを難解言語に落とし込めればよいということになります。この方法により、C言語を難解言語に変換することがより簡単になりました。

そして、多くの人が自分の好きな難解言語バックエンドを追加していった結果、平易なC言語で書かれたC言語コンパイラ8ccを変換することにより、非常に多くの難解言語上でC言語コンパイラが動くようになったのでした。

Cコンパイラをスクラッチから開発してみた(日記) - Qiita

C言語コンパイラが動く難解言語のうちには、C++14constexprもあります。これも去年非常に話題になりました。

コンパイル中にコンパイルする「コンパイル時Cコンパイラ」をつくった話 - kw-udonの日記

C++にはテンプレートという機能もあります。テンプレートはコンパイル時に処理されるのですが、おそろしいことに、コンパイル時の型の計算のみでチューリング完全になっています。 これを使ってコンパイル時にいろいろと計算することをテンプレートメタプログラミング(TMP)と呼んでいます。もちろんTMPは実用的な計算をするための言語ではないので、難解言語と言ってもいいでしょう。さて、それではTMPでC言語コンパイラは動くのでしょうか?

残念ながら、ELVMのC++TMPバックエンドでは、C言語コンパイラを動かすことは叶いませんでした。これについては、上のブログで考察されているように、TMPにはメモリを開放する方法が一切なく、メモリ使用量が非常に大きくなってしまうことが原因です。

それでも、TMPでC言語コンパイルしたい

TMPは純粋関数型言語なので、C言語のような手続型のコードを変換するのはそれなりに大変です。ELVMのC++TMPバックエンドでは、Store-passing Styleを用いることでこの問題を解決しようとしていますが、この自動生成コードをコンパイルすると非常にメモリを消費します。これは、一変数だけ変更する時、他の部分は全く書き換わらないのにもかかわらず、全てコピーする必要があるからです。普通の関数型言語でよく使われるリスト(イミュータブルな単方向連結リスト)において、末尾の要素だけを変更したリストを作ることが高くつくことと似ています。しかし、普通の関数型言語においては時間的には高くつきますが、ガベージコレクション(GC)が働くため、空間的にはそれほど問題になりません。ところが、TMPではいったんテンプレートがインスタンス化されるとコンパイルが終了するまで残ってしまうため、空間的にも非常に高くつくことになります。

よくよく考えると、これらのコードはテンプレートメタプログラミングの機能を生かし切れていません。たとえば、TMPには組み込みでパック展開というものが存在します。パック展開で一気に処理をすることができれば、テンプレートのインスタンス化量が激減するため、メモリ使用量の問題を解決できるかもしれません。

パック展開は関数型言語のmap関数のようなことができます。部分特殊化を使えば、パターンマッチングをすることだってできます。そう、TMPには関数型言語的な気の利いた機能がたくさんあるのです。 C言語を変換するという作戦ではなく、最初から純粋関数型言語っぽく、C言語コンパイラを書けば、もしかしたら、TMPでもC言語コンパイラが作れるのではないでしょうか……?

ということを9月ごろに思ってから、ちまちまと作り続けて、

ついに動きました!

ようやく今朝コンパイルができるようになりました!

なんとか、アドベントカレンダーに間に合いましたね……。

ltmpcの中身の紹介

本当はこれも書きたかったんですが、今日はとても疲れてしまったので、明日以降に書きましょう。

なんか内容がとても少ない記事になってしまった。プログラマはコードで語る、ということにしておきましょう。