最近テンプレートメタプログラミング (Template meta programming, TMP) から離れているなぁと思ったので、また書いてみました。
Quine(クワイン)とは、自分のソースコードを出力するプログラムのことです。
ソースコードは以下に公開してあります。C++11の機能のみを使った、伝統的なスタイルのTMPで書かれています。 なお、ソースコードはすべて手で打ち込んだものであり、自動生成した部分は一切ありません。
GitHub - lpha-z/TMP-Quine: A quine written in C++ template meta programming
TMPでQuineを書くとなると結構なコード量になるかと思っていたのですが、実際には十分に短いプログラムになりました*1。 プログラムサイズ自体が小さいため、以前に作ったTMPによるC言語コンパイラ ltmpc の時に開発した、メモリ消費量を抑えるテクニックなしでも、現実的な時間・メモリ使用量でコンパイルが可能です。 clang++-4.0を用いた場合、9秒・1.3GBでコンパイルできました。
Quineの仕組み
自分のソースコードを出力するプログラムを素直に作ろうとすると、文字列として自分自身のソースコードを埋め込むことになります。 つまり、C言語の場合、以下のようになります。
#include <stdio.h> int main() { puts("#include <stdio.h>\nint main() { puts(\"...\");}"); }
しかし、このようにしてしまうと、循環参照的になっているため、...
の部分を書くことが不可能であることに気づきます。
よって、このようなナイーブな方法ではうまくいきません。
典型的なQuineの作り方
典型的には、Quineは以下のような構成になっています。
- ライブラリ部分
- データ領域
- 出力部分
この場合、重要なのは「ソースコードを文字列化したものを読み込んで、それを解釈し、その文字列表現を計算する」部分です。
ソースコードを文字列化したデータを読み込んでも、その文字列表現は得られません。
例えば、C言語の文字列は"ABC"
みたいになっていますが、これを読み込んでもABC
というデータが得られるだけで、"
のデータは得られません。
しかし、「ソースコードを文字列化したもの」を規則正しく作っておくことにより、ABC
から"ABC"
を「計算により」復元することができます。
C言語の例の場合、「規則正しく」の部分がわかりづらいかもしれません。
これは、"A""BC"
などと文字列化してはいけないということを示しています。
このようにしてしまうと、"
を余分に出力しないとQuineになりませんが、その場所がどこかを示すデータが別途必要になってしまい、問題がややこしくなります。
あるいは、AABC
を"A\101BC"
などと気まぐれに文字列化してしまうと、場所によってどう計算すべきかが変わってしまい、問題がややこしくなります。
TMPでのQuineの実現
出力方法
TMPには出力機能がないため、純粋なTMPだけでQuineを達成することは不可能です。
今回は、Quine
という型変数が、String<(ソースコードの一文字一文字をchar...に入れたもの)>
となるようにしました。
それだけだと本当にQuineが完成したかの確認が困難なため、以下の実行時コードがついています。
#include <cstdio> #include <initializer_list> template<class> struct Printer; template<template<char...>class Container, char... Chars> struct Printer<Container<Chars...>> { Printer() { using Swallow = std::initializer_list<int>; Swallow swallow { putchar(Chars)... }; } }; Printer<Quine> printer; int main() {}
Swallow
は、initializer_list
を使ってパラメータパックを展開するときのイディオムです。
関数の引数でパラメータパックを展開すると、その実行順は保証されませんが、initializer_list
の中であれば前から順番に実行されることが保証されます。
ソースコードの文字列化方法
ソースコードを文字列化するためには、素直に文字リテラルを用いました。なお、文字リテラルの間には必ず,
が入っています(規則的に書かれています)。
文字リテラルを用いたのは、ソースコードを手書きするにはそのほうがやりやすかったためです。 しかし、エスケープが不可避なため、ソースコードが長くなってしまいます。
ソースコードを自動生成する前提ならもっと短くなる方法があります。 例えば文字リテラルではなく、その文字コードを直打ちするという方法です。この場合、エスケープは不要です。 十進数で書くと2桁のものと3桁のものができてしまって不便なため、八進数で書き、leading zerosを使って桁数をそろえるとよさそうです。
ソースコードを文字列化したものを読み込んで、それを解釈し、その文字列表現を計算する方法
BuildSource
構造体テンプレートがその計算をする部分です。
ソースコードの文字データの先頭は、, 'C'
の形になっていないため、別途生成しています。
そのため、先頭の一文字を落としてEncodeChar
構造体テンプレートに渡しています。
EncodeChar
構造体テンプレートは、C
というデータから, 'C'
という文字列表現を計算する部分です。エスケープが必要な場合、特殊化されたテンプレートが選ばれ、必要な\
を出力します。
これを各文字について行い、文字列表現を計算します。その際に行われる結合は「大きいものに小さいものをマージ」戦略によっているため、メモリ使用量・コンパイル時間がソースコードサイズに対して二乗のオーダーとなってしまっています。