C++テンプレートは計算完備

趣 考 ぷ

KEMURIをチューリング完全にするためにはどうしたらいいか、あるいはどうすればチューリング完全性を判定できるのか、ヒントを探していたら「C++テンプレートはチューリング完全だよー」という論文にたどり着いた。


Boost::MPL みたいなものが実現できるあたり、その可能性は感じていたけどやっぱりか！！但し、チューリング完全だと、いわゆる「チューリング機械の停止判定問題」があるわけで、C++はその問題を避けるために、言語仕様では最低17回の再帰までしか保証しないことにしている。なので、厳密にはチューリング完全ではないところ、これを無制限と仮定しているのがミソ。そして、テンプレートがチューリング完全ならば、（テンプレートを使った）C++プログラムはコンパイルできるかどうか判定する事が一般的にできなくなる*1。

昨年の夏のプロシンで、コンパイルが停止しないMLプログラムを見せてもらい、衝撃を覚えた。実は同じ衝撃を、C++でも味わえるのが嬉しい。

// コンパイルが停止しない
template <int N>
class recursion {
public:
    enum { val = recursion<N - 1>::val };
};

int main() 
{
    return recursion<10>::val;
}

で、ならば・・・と、C++テンプレートだけで Brainfuck のインタプリタ（インタプリテーションするのはコンパイル時）を作ろうと思ったけど、基本的に関数プログラミングになり手続きが記述できない。それだけなら、以前、BrainfuckインタプリタをSchemeで書いたときの要領でやればよいのだが、困った事にテンプレートでは分岐が直接記述できない。もちろんチューリング完全なので等価な手段はあるわけで、それが分岐パターンの数だけ部分特殊化されたテンプレートを定義する、というもの。このあたりは、Prologのそれによく似ている。非常に手間がかかる。なによりも、テンプレートの部分特殊化に対応したコンパイラが極稀なうえ、コンパイル時に実行するのでデバッグができん！！

というわけで、止めたわけではないが時間がかかりそう。

// コンパイルが停止する（再帰の基底条件を与えた）
template <int N>
class recursion {
public:
    enum { val = recursion<N - 1>::val };
};

template <>
class recursion<1> {
public:
  enum { val = 1 };
};

int main() 
{
    return recursion<10>::val;
}

*1:文法上のエラーは無いものとして