テンプレートメタプログラミングでアッカーマン関数を実装してみよう
まったくちがう。節約の問題ではない。
テンプレートメタプログラムの視点からはvtblは『邪魔』なことがある。
実行時のスピードのパフォーマンスの話ではなくて、存在そのものが邪魔になる。
vtblがない方がいいのではなくて『存在してはならない』パターンもある。Java的考えでは実行時のポリモーフィズムで解決するもののうちのある種のものを
C++ではコンパイル時にテンプレートで解決させる(という考え方がある)。
この辺は(あえて悪い言葉を使うと)Java脳のひとには理解できない。
なるほど。テンプレートメタプログラミングですか。テンプレートメタプログラミング的な所は全然たしなんでいなくて、アッカーマン関数をテンプレートメタプログラミング的に計算させてしてコンパイル終わらないね、みたいなのを試したくらいです。実際のところ仮想関数による実行時の多態とテンプレートメタプログラミングは相容れないですね(多分。生半可な知識で言ってます)。
virtualがデフォルトではないC++ではこういうこともできるというのは美点であると思います。でもこの辺の世界は
「継承するつもりのあるクラスでは基本的にvirtualデストラクタを用意せよ。そうしないのならば、自分が何をしようとしているか把握した上でせよ。」
>自分が何をしようとしているのか把握した上
な世界だと、私は思いますけどね。
てなやりとりがありました。テンプレートメタプログラミングというのは聞いたことがない人もいるかもしれません。C++の中でもかなりハードコアな領域だと個人的には思います。僕はさわりくらいしか知りません。テンプレート展開によって計算を行うという前衛的なプログラミング手法で、再帰的なテンプレート展開によるループと、テンプレート引数のマッチによる条件分岐ができるので、チューリングコンプリートであることが証明できるシロモノのようです。そして、テンプレート展開はコンパイル時に行われるので、計算をコンパイル時にやらせることができます。従って逆に、コンパイル時に決定できない情報がある場合はテンプレートメタプログラミング的に計算することはできません。
コンパイル時に計算(テンプレート展開)が行われるということは、計算量が極めて多い計算をさせるとコンパイルに時間がかかることになります。計算量が極めて多い計算といえばアッカーマン関数、ということで、アッカーマン関数をテンプレートメタプログラミング的に実装して、コンパイル時に計算が行われている様子を確認してみましょう!
#include<iostream> using namespace std; template<unsigned int m, unsigned int n> struct Ack { enum { value = Ack<m-1, Ack<m, n-1>::value>::value }; }; template<unsigned int m> struct Ack<m, 0> { enum { value = Ack<m-1, 1>::value }; }; template<unsigned int n> struct Ack<0, n> { enum { value = n+1 }; }; int main(){ cout << Ack<3, 1>::value << endl; //g++ 4.1.2 では再帰的なテンプレート展開の深さがデフォルトでは500に制限されているので、 //-ftemplate-depth-N オプションを付けてNに大きい数を指定しないとコンパイルが失敗する //cout << Ack<4, 1>::value << endl; return 0; }
のような定義をそのまま書いてるだけのように見えますが、ちゃんと計算できます。すばらしいですね!
そして、Ack<4, 1>のような膨大な計算をしようとすると、テンプレート展開の深さの制限にひっかかってコンパイルできなくなりますので、(g++ならば)-ftemplate-depth-100000 とかつけてコンパイルしてみましょう。手元のcoLinuxでやろうとしたらちっともコンパイルが終わらないので途中であきらめました(これは別にTMPの欠陥ではありません。Ack(4, 1)なんて普通に実装してもかなり時間がかかります)。
だんだんコンパイルが遅くなっていく様子が見たければ、m=3辺りでnを1,2,3,...と増加させると遅くなっていくのが分かります。一方で、計算は全てコンパイル中に行われているので、コンパイルにどれだけ時間がかかろうがコンパイルが終わってさえしまえばプログラムの実行は一瞬です。
正直、僕のような凡人にはこれがどのように応用できるか例が思いつかないですが、BoostにはMPLというTMPのためのライブラリがあったりするので、これを見れば有用な使い方が分かるかもしれません。