最近テンプレートメタプログラミング (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は以下のような構成になっています。

ライブラリ部分
データ領域
1. ライブラリ部分のソースコードを文字列化したもの
2. 出力部分のソースコードを文字列化したもの
出力部分
1. 「ライブラリ部分のソースコードを文字列化したもの」を読み込んで、そのまま出力
2. 「ライブラリ部分のソースコードを文字列化したもの」を読み込んで、それを解釈し、その文字列表現を計算し、それを出力
3. 「出力部分のソースコードを文字列化したもの」を読み込んで、それを解釈し、その文字列表現を計算し、それを出力
4. 「出力部分のソースコードを文字列化したもの」を読み込んで、そのまま出力

この場合、重要なのは「ソースコードを文字列化したものを読み込んで、それを解釈し、その文字列表現を計算する」部分です。

ソースコードを文字列化したデータを読み込んでも、その文字列表現は得られません。例えば、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'という文字列表現を計算する部分です。エスケープが必要な場合、特殊化されたテンプレートが選ばれ、必要な\を出力します。

これを各文字について行い、文字列表現を計算します。その際に行われる結合は「大きいものに小さいものをマージ」戦略によっているため、メモリ使用量・コンパイル時間がソースコードサイズに対して二乗のオーダーとなってしまっています。

*1:ただし、Concatenateと書いていたらぎりぎりで再帰深度1024の壁を越えてしまったので、Catに直しました……。

よーる

テンプレートメタプログラミングでQuineを書いた