テンプレートメタプログラミングと呼ばれるテクニックがC++のコードに意識的に用いられ始めたのは1995年頃にまで遡るらしい(C++ による科学計算のためのライブラリBlitz++を作ったT. Veldhuizenの記事)。Alexander StepanovがテンプレートをANSI/ISOのC++委員会に提案したのがそれを遡ること2年前、1993年である。科学計算の分野で最も高速に動作するプログラムを構成するにはC言語ではなくFortranが最適であるという周知の事実に対し、C++言語でテンプレートを積極的に用いて、Fortranによる場合と同水準のパフォーマンスと、より見通しの利くオブジェクト指向を採用したプログラム構造とを両立させようという試みのもとに、このテクニックは開発されてきた。広く一般の認知を受けたのは、2001年のAndrei Alexandrescuによる著作Modern C++ Designによってである。以来、Modern C++ Designで解説されたジェネリックプログラミングとテンプレートメタプログラミングのテクニックを収めたライブラリLoki、Boostライブラリに収められているテンプレートメタプログラミングのためのフレームワークMPLを通じて、その利用は徐々に広がりつつある。
ところが一方で、このテンプレートメタプログラミングなるものが根底は非常に単純であるにもかかわらず、テンプレートについての解説すら省いてあることもあるC++の入門書などでは全く扱われていない。テンプレートメタプログラミングやジェネリックプログラミングが現れるのは、C++プログラミングに関する書籍の分類ではいわゆる上級の部類とされる書籍である。
私はその結びつきには全く必然性がないと考える。むしろ、C言語の解説でリンクリストがポインタを使用した基本的なツールとして与えら れるように、テンプレートメタプログラミングもテンプレートを利用した簡便でプラグマティックなツールとして紹介されてよいはずである。ひょっとしたら、テンプレートの項が継承の項より先に出てくるというラディカルな構成の教科書があっても良いかもしれない。オブジェ クト指向とジェネリックプログラミングは直交している。もっとも、テンプレートメタプログラミングは、C++テンプレートの使用から得られる直接の効果であるコードやパターンの再利用(オブジェクト指向でのクラス再利用ではない)とは若干位相を異にし、プログラム自体のパフォーマンスや最適化を追及するためのテクニックでもあるので、単にプログラミング上の生産性を上げるという目的からは逸れた、二次的なトピックとされる可能性があるのも致し方ないところ ではある。また、C++言語の解説書というのは、往々にしてC言語の熟練者を対象にしており、あまりにも異なるパラダイムのプログラミングは解説書レベルでは導入しにくいという見方もあるだろう。しかし、テンプレートをインテリジェントなマクロとして見れば、C言語の熟練者が扱いに困るとは思えない。
ここでは、C++におけるテンプレートメタプログラミングの、一般のオブジェクト指向プログラミングとは異質であるイディオムを、単な るおおまかなパターンの解説に留まらず基礎から列挙することによって、具体的かつ機械的にこのテクニックを習得することを目指す。オブジェクト指向は(直接には)関係ないので、C++言語の一応は知っているがオブジェクト指向は深く知らないという状態でも本文の理解には全く差し支えない。
C++という言語はある部分で低水準性を引きずっているため、より新しいオブジェクト指向言語(たとえばRuby)がしばしば活用されるような、具象を離れて抽象的なデザインを行う局面で用いるには泥臭すぎるとの評もあろう。しかし一方で、底辺により近いツールキットとして繰り返し用いられるべき真に再利用性の高い部品を構築するには、細部にわたって緻密な機械寄りの視点と実装が必要となるに違いない。C++があくまで開かれた言語であ るのと同様に、C++におけるジェネリックプログラミングとテンプレートメタプログラミングは、そうした細部への着目と、大胆な抽象性とを併せ持った(Multi-Paradigm)、希有かつ野心的な分野であり作法である。
まずは、テンプレートメタプログラミングの定義から始めよう。これは、言葉の文字通りの解釈で足りる。つまり、テンプレートを使って、プロ グラムを生産するプログラム(メタプログラム)を作る、という作業を指す。ではそのメタプログラムはいつどこで実行するのかといえば、C++テンプレートについてはコンパイル時にC++コンパイラ上で実行するということになる。
つぎに、テンプレートメタプログラミングで何が出来るのか、何を行えばよいのかという点が問題となる。単刀直入に言えば、「テンプレートメタプログラミングで出来ること/すべきこと」とは、「C++コンパイラが出来ること/すべきこと」に他ならない。そこで、C++コンパイラがC++で書かれたコードに対しコンパイル時にCPUの種類に関係なく出来ることを列挙してみることにする。「テンプレートの展開」はC++を扱う以上当然行われる。その上で、いわゆるコンパイラによる最適化の観点からは、定数の畳み込み、定数伝播、ループ展開といった関連トピックが出てくる。C++での一般的なテンプレートの使用はパターン再利用によるコード記述量減少という効果を持つ一方で、 テンプレートメタプログラミングにおけるテンプレートは主に最適化を目的としているため、コンパイラの果たす/果たすべき機能のエミュレーションをいかに コード上で行うかという視点が有効なのは当然である。ただしアセンブリ命令を明示的に指定するような類の手作業での最適化と異なるのは、テンプレート設計 のみを行い、ソースコード生成(テンプレートのインスタンス化)の作業はコンパイラに委託する点である。
以下では「定数の畳み込み」「テンプレートの展開」「ループの展開」について扱う。
C++の主要な単位であるclassの中で定数を定義する方法は、2種類有る。ひとつはenumを用いる方法、もうひとつはstatic const変数を使用する方法である。
ここでenumについて、この定数valueはC::valueのようにスコープ演算子を用いてクラスからアクセス可能になる。つまり インスタンスを生成せずにこのクラスCは用いられる。インスタンスを生成すれば'.'(ドット)演算子によってもアクセス可能だが実益はない。const 変数については、同様にクラスからアクセスするためと、コンストラクタで初期化できるただのconst変数では意味がないので、staticが必要である。ちなみにジェネリックプログラミングやテンプレートメタプログラミングに登場するクラスは複数ポリシーのバインダや定数の器としての役割しかないヘルパクラスである場合が多い。つまり、テンプレートパラメータに使用できる型である点を除けば、namespaceの果たす機能と大差ない。
従って、主に実行時のオブジェクトの振る舞いや外部との関係をイメージするために意味を持つ、関数やデータメンバのカプセル化のための アクセス制限機構は、ここでは大した意味を持たない。テンプレートメタプログラミングで用いられるクラスはデータメンバもほとんど持たないのが一般的であり、それゆえに実行時の生成オーバーヘッドを気にすることなくこれらのクラス(小規模なクラスなのでstructが使用される場合が多い)をツールとして用いることが出来る。ただしconst変数を即値に展開しないコンパイラが存在する可能性を考慮する と、enumを使用する方が若干の気休めにはなるかもしれない。
さて定数で重要なのは、式の右辺はコンパイルの時点で計算されるということである。コンパイルの時点で決定しない物はenumの右辺に指定できないので至極当然ではある。
定数式の中で三項演算子(? : )が用いられているのが奇異に映るかも知れない。しかし、条件として提示されている1 + 1 == 2という式はコンパイル時に判定でき、従って、valueには1が代入される。このことの含意は、条件式をコンパイル時に決定できる要素のみで組み立てれば、Cプリプロセッサマクロを用いなくてもコンパイル時に制御構文めいた構造が利用できるということである。
こうして、定数式の右辺に計算式を記入するだけで、コンパイラのための立派な計算プログラムが成立してしまう。例えば
これで、コンパイラを走らせる度にではあるものの、実行時にCPU資源を全く消費することなく計算結果を得られる。現実的とはいえない例だが、テンプレートメタプログラミングとは結局のところこれ以上でも以下でもない。テンプレートすら未だに導入していないこの例の段階で断定するのは些か早計に見えても、テンプレートメタプログラミングの可能性と限界は実はここに顕著である。詳細は後に譲り、定数で構成された世界にもう一つの道具であるテンプレートを導入して状況がどう変化するか見てみよう。
テンプレートの導入によって、右辺に変数が導入され、方程式が表現できるようになった。ジェネリックプログラミングにおいてテンプレートクラスはparameterized typeと呼ばれ、その引数として型を取り、新しい型を生成するという、型オブジェクトを扱う関数のような存在である。この型は、classではなく整数のようなプリミティブ型をパラメータに指定した場合、具体的な数値となる。従ってパラメータがコンパイル時に決定されているならば
のようにパラメータとして具体的な数値を与えて計算結果を得ることが出来る。これは、定数のみを使用していること、実行時に計算が行われていないことを除けば、
このような関数を実行しているのと結果は変わらない。記法については丸括弧が山括弧に変わっただけである。返り値 はクラスの定数(value)にアクセスして得る。この、テンプレートの山括弧を、関数呼び出しの丸括弧と同一視できるようになれば、テンプレートメタプログラミングに対する感覚的な素地は整ったと見て差し支えない。丸括弧で表記された関数ポインタ を介して関数が実行され制御が移ってゆくのが一般のC++プログラムコードを実行した場合の動的な評価である。これに対し、「テンプレートの展開」 がもたらすのは、コンパイラ上でのメタプログラムの評価という静的実行である。
次に「ループの展開」について見ていこう。ループをテンプレートで表現するには、動的実行のC++プログラムにおける、forによる繰り返し構文がアナロジーとして参考になる。for構文の丸括弧の中では、繰り返しに用いる条件の初期化/増分/終了条件を指定する。その繰り返しという営為の中の振る舞いを各々抽出すると、初期化/関数/終了という3つの段階が抽出できる。これはある法則を持つ数列の一部分を取り出して表す場合と同様である。ただし、前回の関数の実行結果をループの次のラウンドで使用するために、この関数の毎回の実行結果をコンテクスト情報として累積的に保存する変数(accumulator)が必要となる場合もある。
コンテクスト情報が保存されていれば、このループの各ラウンドを表す関数は定義時点でコンテクストを持たない単なる 関数定義ではなく、ループのコンテクストに拘束されコンテクスト情報と合成されたものとなる。これはいわゆる関数閉包 (closure)であり、たとえばRuby言語のイテレータ/ブロックも単なるループされる再入可能な関数ではなく同様の性格を持つ。 こうして得られたループの各要素をC++テンプレートを用いて表す場合、初期化は「テンプレートの部分的特殊化」という テクニックを用いて表し、ループされる関数閉包はテンプレートそのものを用いて表す。終了はすなわち最終的評価であるので、具体的なパラメータを与えてのコード上でのテンプレートのインスタンス化がそれに該当する。
ただし、単純にループさせる一区切りの関数としてのC++テンプレートを具体的な数値を与えてインスタンス化しただけでは、ループの最終ラウンドが実行されるだけである。そこで用いられるのが、再帰のテクニックだ。すなわち、インスタ ンス化するテンプレートの中に、前回ラウンドのテンプレートのインスタンスを含ませればよい。これにより、ループの最終ラウンド(n回目)のインスタンス化によってn-1回目のラウンドがインスタンス化/実行され、さらにn-2回目が...という調子で遡りながらループの各ラウンドがインスタンス化/実行されていく。ただし、ループの実行ラウンド数が負になることはありえないので、一番最初のラウンドまで戻ったときに遡及を停止しなければならない。これ は、先に初期化について述べたように、1回目のラウンドをテンプレートの部分的特殊化を用いて特殊化することによって解決される。
この再帰を用いたループ展開は、Lisp言語において、末尾再帰(tail-recursion)と呼ばれる再帰構造をループへ変換する作業の、ちょうど逆である。再帰よりはループの方がスタックを消費しない分パフォーマンスが上がりスタックオーバーフローの危険も無いというので手作業で末尾再帰構造をループに書き直すことがある。SchemeというLisp言語の方言では、処理系が末尾再帰を単なるジャンプへ変換するのでこの作業は要らず、全て再帰を用いて書いても問題ない。Lispでの末尾再帰のループ変換については、Lispテクニックの解説書などを参照して頂きたい。
さてここでループに至る前に、より単純な、再帰やaccumulator無しで書ける単純な数列の表現と、テンプレートの部分的特殊化とを使う例として、実際に役に立ちそうなユーティリティクラスを作成してみることにする。複数の相互に排他的ではないフラグを表現するときに、ビットが立っているか否かで判定できるビットフラグを用いると空間効率の点で有利である。MS Windows環境では、たとえばWinGDI.hには
このようなフラグの定義が載っている。こうしたフラグに各ビットの立った数値を割り振ったものを、使うのはともかく自分で一々定義するのは煩わしいし、新しい要素を末尾ではなく中央に挿入したいときなど並べ直しも面倒である。各要素は立っているビットを順に1ビットずつ単に左シフトしたものにすぎない。そのような時に以下が使用できる。
これを使用するときは、以下のようにenumと併せて使用する。
これでenumの中にフラグの名称シンボルを列挙するだけで、対応するビットの立った値を手作業で割り付けることなくビットフラグが利用できるようになった。ただし、たとえば32ビットの領域をベクタの保持に選んだ場合、32個までしかビットフラグは利用できないので、enumに誤って32個より多くシンボルを入れた場合に正しくフラグが作れない。これが気になる場合は、LokiのSTATIC_CHECKやBoostのstatic_assertを用いて、範囲外のフラグを使用していないかコンパイル時にコンパイラにチェックさせればよい。
次に、ループ展開について検討する。ループ展開は、コンパイラによる最適化の段階では、CPUサイクルを多く消費する可能性のある条件判定をできるだけ削除することによりオーバーヘッドを取り除くという作業である。テンプレートメタプログラミングでも同様に、各ラウンドの命令がループ回 数分並んでいるだけという状態の最終的なマシン語コードを生成することを目標として、テンプレートのインスタンス化の段階でループ展開を行う。
例として、符号理論で登場する、オーダーが256のガロアフィールド(GF256)での演算のための指数テーブルを、テンプレートを使ってコンパイル時に生成してみよう。テンプレートを用いずダイナミックに求める場合の計算式は以下のようになる。これを、コンパイル時に配列GEXPに指数表が格納されるようなテンプレートメタプログラムに変換することにする。
まず、先に検討したループ展開の各要素について見ていく。得るべき値はGEXPなのでこれを中心に、どのようにすればGEXPの各要素に望む値を入れることが出来るか考えていけばよい。まず初期化について、明らかにGEXP[0] = 1であり、しかもループがi == 1から始まっていることから逆に考えれば、i == 0のラウンドが特殊化されていると見ることが出来る。従って、まずはこれをテンプレートの部分的特殊化を用いて表現すればよい。つぎに、ループの各ラウンドの内容となる関数閉包について、見るからにごちゃごちゃしているのでどう分析したものか迷うかもしれない。ただ、ラウンドの最後の部分を見ると、最終的に必要な値はGEXPの各要素の値であり、そこに代入される値は、配列pの各要素を各項とする多項式の計算結果である。また、GEXP[256]からGEXP[510]は、各ラウンドのiの値をnとするとGEXP[n - 255]で表せる(ちなみにGEXP[511]は演算には不要なので0でよい)。
ここで多項式の各項pについて見ると、例えば最初のp[0] = p[8]ならば現在のラウンドのp[0]に一つ前のラウンドのp[8]を代入している。つまり、上で挙げたような再帰によってラウンドを遡及しながら最終ラウンドの値までを順に求めていく必要がある。ただし問題なのは、多項式の各項はそれぞれ他の項と個別に異なった関係を結んでいるという点である。そこで、多項式の各項pをそれぞれ別の容器に保持し、各項の関係をテンプレートで表現することによって、全体像を表現することにする。各項の配列pの初期化は、例によってテンプレートの部分的特殊化で表現できる。
以上の方針で変換したものが次のリストである。
これによって、プログラムの実行の最初に初期化関数を実行して得られたデータを以後シングルトンとして管理する等の作業から解放される。
ただし問題点もある。一見して気になるのが、最下部のGEXPの表である。ここには、511(+1)個分のEのインスタンスが入る。面倒な作業なのでPerlなどのスクリプトで生成してソースコードにペーストするしかない。 プログラム内で表の中のどの数を使用するかがあらかじめ決定できるわけではないので、静的な世界と動的な世界の橋渡しとして、このような表が必要になるのは致し方ない。
また、もっと深刻な問題は、このプログラムのコンパイルにかかる時間である。実はこれが一番最初に書いたテンプレートメタプログラミン グの限界を画する重要な問題に他ならない。コンパイラのテンプレートに対する最適化具合にもよるが、上記のようなテンプレートを展開しコンパイルするには相当なリソースが必要となって しまうのである。そこで、残念ながら、私ならば上記のプログラムを使わずに、昔ながらの定数テーブルをプログラムの中にペーストする方を選んでしまうだろう。付け加えると、本来的には、テンプレートメタプログラムのインスタンスは定数テーブルと同一の機械語コードを生成しなければならないはずだが、実際にそうなるかはコンパイラ次第なので、テンプレートメタプログラムの作成、ビルド、実行の各段階にかかるコストの見積に失敗すると痛い目に遭う。このトピッ クについてはDavid Abrahamsらによる考察に詳しいのでそちらを参照して頂きたい。
最後に、同じGF256の、逆対数を求めるテーブルをテンプレートメタプログラムに変換し、静的な制御構造について学習する。動的に表を作るには、以下のプログラムを実行する。
一見して指数表の場合と異なるのは、if...elseブロックによる条件分岐がある点ぐらいか。単純にGAL[i] に値を代入しているだけなので、上で三項演算子(?:)を使用したのと同様にvalueに値を入れる構造を作れば十分である。ここでは、別の方法によるテンプレートメタプログラム化を試してみることにする。
StaticIfクラステンプレートが、コンパイル時に評価されるifの表現である(ちなみに、BoostのMPLに ほとんど同じものが一式揃っている)。テンプレートパラメータbool Condが真か偽かにより、Returnクラステンプレートの元のテンプレートか部分的特殊化バージョンのどちらかがインスタンス化され、それによってな し崩し的にtype_nameがテンプレートパラメータTrueReturnかFalseReturnのどちらかを表すようにtypedefされる。ここではtypedefによって型そのものがあたかも値であるかのように保持され、操作されている。言い換えれば、typedefされたエイリアス型は、型を保持するスロットであり、上記で使用してきた enumが定数に対するそれであるのと同様にはたらく。そのようにして結果的に得られた型については、これもenumの場合と同様に、 StaticIf<...>::result_typeのようにスコープ演算子を用いてアクセスする。
テンプレート内でのtypedefの使用や型の操作については、例えばSTLアロケータでのrebindは、型とテンプレート型を伝播させていくのに便利な手段として使用される(詳しくはRobert Schmidtによるコラムを参照されたい)。また、Lokiに おけるtypelistは、非常に強力な型操作のためのツールである(ただし、テンプレートメタプログラミングというよりはジェネリックプログラミングの範疇に属する)。typelistは、今のところマクロで実現されているとはいえ、極めて利用価値が高く、将来のC++標準へ言語機能として組み込まれることが望ましい機能の1つである。
さらに、例に登場させてはいないものの、sizeof演算子は型と定数という2つの要素を関連付け組み合わせるのに有用なツールである。sizeofは静的に適用でき、その結果はenumなどの定数に保持できる。つまり、テンプレートメタプログラミングの文脈では、型を定数に変換する ツールであると考えればよい。ただし、型によってサイズが異なるとは限らないので、サイズと型を一対一に対応させたり相互変換ができたりするわけではな く、限定的な利用形態に留まる。
以上、テンプレートメタプログラミングについて基本を一通り見てきた。単なるシンタックスシュガーを超えてC++テンプレートには非常に大きな可能性があること、現在のC++の最重要機能はテンプレートであることを意識して頂ければ幸いである。
参考文献:
[1] The Blitz++ Library
[2] Todd Veldhuizen, Template Metaprograms
[3] Andrei Alexandrescu, Modern C++ Design: Generic Programming and Design Patterns Applied (C++ in Depth Series)
, Addison Wesley 2001 (邦訳
)
[4] Loki: A C++ library of designs, containing flexible implementations of common design patterns and idioms
[5] The Boost C++ Library
[6] The Boost MPL Library
[7] James O. Coplien, Multi-Paradigm Design for C++
, Addison Wesley 1999 (邦訳
)
[8] Paul Graham, On Lisp, Prentice Hall, 1993 (webで全文閲覧可能)
[9] static_assert in The Boost C++ Library
[10] David Abrahams and Carlos Pinto Coelho, Effects of Metaprogramming Style on Compilation Time
[11] Robert Schmidt, Deep C++: Typedef Templates, Microsoft Corporation Aug. 2000
ところが一方で、このテンプレートメタプログラミングなるものが根底は非常に単純であるにもかかわらず、テンプレートについての解説すら省いてあることもあるC++の入門書などでは全く扱われていない。テンプレートメタプログラミングやジェネリックプログラミングが現れるのは、C++プログラミングに関する書籍の分類ではいわゆる上級の部類とされる書籍である。
私はその結びつきには全く必然性がないと考える。むしろ、C言語の解説でリンクリストがポインタを使用した基本的なツールとして与えら れるように、テンプレートメタプログラミングもテンプレートを利用した簡便でプラグマティックなツールとして紹介されてよいはずである。ひょっとしたら、テンプレートの項が継承の項より先に出てくるというラディカルな構成の教科書があっても良いかもしれない。オブジェ クト指向とジェネリックプログラミングは直交している。もっとも、テンプレートメタプログラミングは、C++テンプレートの使用から得られる直接の効果であるコードやパターンの再利用(オブジェクト指向でのクラス再利用ではない)とは若干位相を異にし、プログラム自体のパフォーマンスや最適化を追及するためのテクニックでもあるので、単にプログラミング上の生産性を上げるという目的からは逸れた、二次的なトピックとされる可能性があるのも致し方ないところ ではある。また、C++言語の解説書というのは、往々にしてC言語の熟練者を対象にしており、あまりにも異なるパラダイムのプログラミングは解説書レベルでは導入しにくいという見方もあるだろう。しかし、テンプレートをインテリジェントなマクロとして見れば、C言語の熟練者が扱いに困るとは思えない。
ここでは、C++におけるテンプレートメタプログラミングの、一般のオブジェクト指向プログラミングとは異質であるイディオムを、単な るおおまかなパターンの解説に留まらず基礎から列挙することによって、具体的かつ機械的にこのテクニックを習得することを目指す。オブジェクト指向は(直接には)関係ないので、C++言語の一応は知っているがオブジェクト指向は深く知らないという状態でも本文の理解には全く差し支えない。
C++という言語はある部分で低水準性を引きずっているため、より新しいオブジェクト指向言語(たとえばRuby)がしばしば活用されるような、具象を離れて抽象的なデザインを行う局面で用いるには泥臭すぎるとの評もあろう。しかし一方で、底辺により近いツールキットとして繰り返し用いられるべき真に再利用性の高い部品を構築するには、細部にわたって緻密な機械寄りの視点と実装が必要となるに違いない。C++があくまで開かれた言語であ るのと同様に、C++におけるジェネリックプログラミングとテンプレートメタプログラミングは、そうした細部への着目と、大胆な抽象性とを併せ持った(Multi-Paradigm)、希有かつ野心的な分野であり作法である。
まずは、テンプレートメタプログラミングの定義から始めよう。これは、言葉の文字通りの解釈で足りる。つまり、テンプレートを使って、プロ グラムを生産するプログラム(メタプログラム)を作る、という作業を指す。ではそのメタプログラムはいつどこで実行するのかといえば、C++テンプレートについてはコンパイル時にC++コンパイラ上で実行するということになる。
つぎに、テンプレートメタプログラミングで何が出来るのか、何を行えばよいのかという点が問題となる。単刀直入に言えば、「テンプレートメタプログラミングで出来ること/すべきこと」とは、「C++コンパイラが出来ること/すべきこと」に他ならない。そこで、C++コンパイラがC++で書かれたコードに対しコンパイル時にCPUの種類に関係なく出来ることを列挙してみることにする。「テンプレートの展開」はC++を扱う以上当然行われる。その上で、いわゆるコンパイラによる最適化の観点からは、定数の畳み込み、定数伝播、ループ展開といった関連トピックが出てくる。C++での一般的なテンプレートの使用はパターン再利用によるコード記述量減少という効果を持つ一方で、 テンプレートメタプログラミングにおけるテンプレートは主に最適化を目的としているため、コンパイラの果たす/果たすべき機能のエミュレーションをいかに コード上で行うかという視点が有効なのは当然である。ただしアセンブリ命令を明示的に指定するような類の手作業での最適化と異なるのは、テンプレート設計 のみを行い、ソースコード生成(テンプレートのインスタンス化)の作業はコンパイラに委託する点である。
以下では「定数の畳み込み」「テンプレートの展開」「ループの展開」について扱う。
C++の主要な単位であるclassの中で定数を定義する方法は、2種類有る。ひとつはenumを用いる方法、もうひとつはstatic const変数を使用する方法である。
struct C
{
enum {value = 1};
};
struct CC
{
static const value = 1;
};
ここでenumについて、この定数valueはC::valueのようにスコープ演算子を用いてクラスからアクセス可能になる。つまり インスタンスを生成せずにこのクラスCは用いられる。インスタンスを生成すれば'.'(ドット)演算子によってもアクセス可能だが実益はない。const 変数については、同様にクラスからアクセスするためと、コンストラクタで初期化できるただのconst変数では意味がないので、staticが必要である。ちなみにジェネリックプログラミングやテンプレートメタプログラミングに登場するクラスは複数ポリシーのバインダや定数の器としての役割しかないヘルパクラスである場合が多い。つまり、テンプレートパラメータに使用できる型である点を除けば、namespaceの果たす機能と大差ない。
従って、主に実行時のオブジェクトの振る舞いや外部との関係をイメージするために意味を持つ、関数やデータメンバのカプセル化のための アクセス制限機構は、ここでは大した意味を持たない。テンプレートメタプログラミングで用いられるクラスはデータメンバもほとんど持たないのが一般的であり、それゆえに実行時の生成オーバーヘッドを気にすることなくこれらのクラス(小規模なクラスなのでstructが使用される場合が多い)をツールとして用いることが出来る。ただしconst変数を即値に展開しないコンパイラが存在する可能性を考慮する と、enumを使用する方が若干の気休めにはなるかもしれない。
さて定数で重要なのは、式の右辺はコンパイルの時点で計算されるということである。コンパイルの時点で決定しない物はenumの右辺に指定できないので至極当然ではある。
struct C
{
enum {value = 1 + 1 == 2 ? 1 : 0};
};
定数式の中で三項演算子(? : )が用いられているのが奇異に映るかも知れない。しかし、条件として提示されている1 + 1 == 2という式はコンパイル時に判定でき、従って、valueには1が代入される。このことの含意は、条件式をコンパイル時に決定できる要素のみで組み立てれば、Cプリプロセッサマクロを用いなくてもコンパイル時に制御構文めいた構造が利用できるということである。
こうして、定数式の右辺に計算式を記入するだけで、コンパイラのための立派な計算プログラムが成立してしまう。例えば
#include <iostream>
struct C
{
enum {value = 24181 - 42917 * 242 % 2325 - 1245};
};
int main()
{
std::cout << C::value << std::endl;
return 0;
}
これで、コンパイラを走らせる度にではあるものの、実行時にCPU資源を全く消費することなく計算結果を得られる。現実的とはいえない例だが、テンプレートメタプログラミングとは結局のところこれ以上でも以下でもない。テンプレートすら未だに導入していないこの例の段階で断定するのは些か早計に見えても、テンプレートメタプログラミングの可能性と限界は実はここに顕著である。詳細は後に譲り、定数で構成された世界にもう一つの道具であるテンプレートを導入して状況がどう変化するか見てみよう。
template <int x>
struct Square
{
enum {value = x * x};
};
テンプレートの導入によって、右辺に変数が導入され、方程式が表現できるようになった。ジェネリックプログラミングにおいてテンプレートクラスはparameterized typeと呼ばれ、その引数として型を取り、新しい型を生成するという、型オブジェクトを扱う関数のような存在である。この型は、classではなく整数のようなプリミティブ型をパラメータに指定した場合、具体的な数値となる。従ってパラメータがコンパイル時に決定されているならば
#include <iostream>
int main()
{
std::cout << Square<16>::value << std::endl;
return 0;
}
のようにパラメータとして具体的な数値を与えて計算結果を得ることが出来る。これは、定数のみを使用していること、実行時に計算が行われていないことを除けば、
int square(const int x)
{
return x * x;
}
このような関数を実行しているのと結果は変わらない。記法については丸括弧が山括弧に変わっただけである。返り値 はクラスの定数(value)にアクセスして得る。この、テンプレートの山括弧を、関数呼び出しの丸括弧と同一視できるようになれば、テンプレートメタプログラミングに対する感覚的な素地は整ったと見て差し支えない。丸括弧で表記された関数ポインタ を介して関数が実行され制御が移ってゆくのが一般のC++プログラムコードを実行した場合の動的な評価である。これに対し、「テンプレートの展開」 がもたらすのは、コンパイラ上でのメタプログラムの評価という静的実行である。
次に「ループの展開」について見ていこう。ループをテンプレートで表現するには、動的実行のC++プログラムにおける、forによる繰り返し構文がアナロジーとして参考になる。for構文の丸括弧の中では、繰り返しに用いる条件の初期化/増分/終了条件を指定する。その繰り返しという営為の中の振る舞いを各々抽出すると、初期化/関数/終了という3つの段階が抽出できる。これはある法則を持つ数列の一部分を取り出して表す場合と同様である。ただし、前回の関数の実行結果をループの次のラウンドで使用するために、この関数の毎回の実行結果をコンテクスト情報として累積的に保存する変数(accumulator)が必要となる場合もある。
コンテクスト情報が保存されていれば、このループの各ラウンドを表す関数は定義時点でコンテクストを持たない単なる 関数定義ではなく、ループのコンテクストに拘束されコンテクスト情報と合成されたものとなる。これはいわゆる関数閉包 (closure)であり、たとえばRuby言語のイテレータ/ブロックも単なるループされる再入可能な関数ではなく同様の性格を持つ。 こうして得られたループの各要素をC++テンプレートを用いて表す場合、初期化は「テンプレートの部分的特殊化」という テクニックを用いて表し、ループされる関数閉包はテンプレートそのものを用いて表す。終了はすなわち最終的評価であるので、具体的なパラメータを与えてのコード上でのテンプレートのインスタンス化がそれに該当する。
ただし、単純にループさせる一区切りの関数としてのC++テンプレートを具体的な数値を与えてインスタンス化しただけでは、ループの最終ラウンドが実行されるだけである。そこで用いられるのが、再帰のテクニックだ。すなわち、インスタ ンス化するテンプレートの中に、前回ラウンドのテンプレートのインスタンスを含ませればよい。これにより、ループの最終ラウンド(n回目)のインスタンス化によってn-1回目のラウンドがインスタンス化/実行され、さらにn-2回目が...という調子で遡りながらループの各ラウンドがインスタンス化/実行されていく。ただし、ループの実行ラウンド数が負になることはありえないので、一番最初のラウンドまで戻ったときに遡及を停止しなければならない。これ は、先に初期化について述べたように、1回目のラウンドをテンプレートの部分的特殊化を用いて特殊化することによって解決される。
この再帰を用いたループ展開は、Lisp言語において、末尾再帰(tail-recursion)と呼ばれる再帰構造をループへ変換する作業の、ちょうど逆である。再帰よりはループの方がスタックを消費しない分パフォーマンスが上がりスタックオーバーフローの危険も無いというので手作業で末尾再帰構造をループに書き直すことがある。SchemeというLisp言語の方言では、処理系が末尾再帰を単なるジャンプへ変換するのでこの作業は要らず、全て再帰を用いて書いても問題ない。Lispでの末尾再帰のループ変換については、Lispテクニックの解説書などを参照して頂きたい。
さてここでループに至る前に、より単純な、再帰やaccumulator無しで書ける単純な数列の表現と、テンプレートの部分的特殊化とを使う例として、実際に役に立ちそうなユーティリティクラスを作成してみることにする。複数の相互に排他的ではないフラグを表現するときに、ビットが立っているか否かで判定できるビットフラグを用いると空間効率の点で有利である。MS Windows環境では、たとえばWinGDI.hには
/* PIXELFORMATDESCRIPTOR flags */
#define PFD_DOUBLEBUFFER 0x00000001
#define PFD_STEREO 0x00000002
#define PFD_DRAW_TO_WINDOW 0x00000004
#define PFD_DRAW_TO_BITMAP 0x00000008
#define PFD_SUPPORT_GDI 0x00000010
#define PFD_SUPPORT_OPENGL 0x00000020
#define PFD_GENERIC_FORMAT 0x00000040
#define PFD_NEED_PALETTE 0x00000080
#define PFD_NEED_SYSTEM_PALETTE 0x00000100
#define PFD_SWAP_EXCHANGE 0x00000200
#define PFD_SWAP_COPY 0x00000400
#define PFD_SWAP_LAYER_BUFFERS 0x00000800
#define PFD_GENERIC_ACCELERATED 0x00001000
#define PFD_SUPPORT_DIRECTDRAW 0x00002000
このようなフラグの定義が載っている。こうしたフラグに各ビットの立った数値を割り振ったものを、使うのはともかく自分で一々定義するのは煩わしいし、新しい要素を末尾ではなく中央に挿入したいときなど並べ直しも面倒である。各要素は立っているビットを順に1ビットずつ単に左シフトしたものにすぎない。そのような時に以下が使用できる。
/* BitFlagVector.h */
#ifndef CALC_BITFLAGVECTOR_H
#define CALC_BITFLAGVECTOR_H
// 先に部分的特殊化を行うためのテンプレートクラスの前方宣言
// テンプレートクラス本体の定義の後で特殊化する場合は不要
template <int n> struct BitFlag;
// 具体的なパラメータ(0)によるテンプレートの部分的特殊化。
// テンプレートパラメータが0の場合のみBitFlagについて
// このテンプレートが適用される
template <> struct BitFlag<0>
{
enum {value = 0};
};
// ビットフラグの値を表すテンプレート。
// 1ビットを左シフトしていくことにより右から何番目(1-base)の
// ビットが立っているかを表す
template <int n>
struct BitFlag
{
enum {value = 1 << (n - 1)};
};
// ビットフラッグのベクタを保持するテンプレート。
// 保持のために使用する型(POD)をテンプレートパラメータとして取る
template <typename T>
struct BitFlagVector
{
volatile T data_;
BitFlagVector()
: data_(0)
{}
// i番目のビットを立てる
template <int i>
void on()
{
data_ |= BitFlag<i>::value;
}
// i番目のビットを下ろす
template <int i>
void off()
{
data_ &= ~ BitFlag<i>::value;
}
// i番目のビットが立っているかどうか
template <int i>
bool is() const
{
return data_ & BitFlag<i>::value;
}
// ベクタの初期化
void reset()
{
data_ = 0;
}
};
// DWORD(32ビット)を保存できるベクタ
typedef BitFlagVector<DWORD> BitFlagVector32;
#endif CALC_BITFLAGVECTOR_H
これを使用するときは、以下のようにenumと併せて使用する。
class C
{
public:
enum PFD
{ // 明示的な初期化のないenumは0から始まり1ずつ増える整数となる
NONE, // = 0
DOUBLEBUFFER,
STEREO,
DRAW_TO_WINDOW,
DRAW_TO_BITMAP,
SUPPORT_GDI,
SUPPORT_OPENGL,
GENERIC_FORMAT,
NEED_PALETTE
};
bool method()
{
flag_.on<PFD::STEREO>();
flag_.off<PFD::SUPPORT_GDI>();
return flag_.is<PFD::SUPPORT_OPENGL>();
}
private:
BitFlagVector32 flag_;
};
これでenumの中にフラグの名称シンボルを列挙するだけで、対応するビットの立った値を手作業で割り付けることなくビットフラグが利用できるようになった。ただし、たとえば32ビットの領域をベクタの保持に選んだ場合、32個までしかビットフラグは利用できないので、enumに誤って32個より多くシンボルを入れた場合に正しくフラグが作れない。これが気になる場合は、LokiのSTATIC_CHECKやBoostのstatic_assertを用いて、範囲外のフラグを使用していないかコンパイル時にコンパイラにチェックさせればよい。
次に、ループ展開について検討する。ループ展開は、コンパイラによる最適化の段階では、CPUサイクルを多く消費する可能性のある条件判定をできるだけ削除することによりオーバーヘッドを取り除くという作業である。テンプレートメタプログラミングでも同様に、各ラウンドの命令がループ回 数分並んでいるだけという状態の最終的なマシン語コードを生成することを目標として、テンプレートのインスタンス化の段階でループ展開を行う。
例として、符号理論で登場する、オーダーが256のガロアフィールド(GF256)での演算のための指数テーブルを、テンプレートを使ってコンパイル時に生成してみよう。テンプレートを用いずダイナミックに求める場合の計算式は以下のようになる。これを、コンパイル時に配列GEXPに指数表が格納されるようなテンプレートメタプログラムに変換することにする。
int GEXP[512]; // 指数を格納するテーブル
int p[9] = {0, 1, 0, 0, 0, 0, 0, 0, 0};
GEXP[0] = 1;
GEXP[255] = GEXP[0];
for (int i = 1; i < 256; ++i)
{
p[0] = p[8];
p[8] = p[7];
p[7] = p[6];
p[6] = p[5];
p[5] = p[4] ^ p[0];
p[4] = p[3] ^ p[0];
p[3] = p[2] ^ p[0];
p[2] = p[1];
p[1] = p[0];
GEXP[i] = p[1] + p[2] * 2 + p[3] * 4 + p[4] * 8
+ p[5] * 16 + p[6] * 32 + p[7] * 64
+ p[8] * 128;
GEXP[i + 255] = GEXP[i];
}
まず、先に検討したループ展開の各要素について見ていく。得るべき値はGEXPなのでこれを中心に、どのようにすればGEXPの各要素に望む値を入れることが出来るか考えていけばよい。まず初期化について、明らかにGEXP[0] = 1であり、しかもループがi == 1から始まっていることから逆に考えれば、i == 0のラウンドが特殊化されていると見ることが出来る。従って、まずはこれをテンプレートの部分的特殊化を用いて表現すればよい。つぎに、ループの各ラウンドの内容となる関数閉包について、見るからにごちゃごちゃしているのでどう分析したものか迷うかもしれない。ただ、ラウンドの最後の部分を見ると、最終的に必要な値はGEXPの各要素の値であり、そこに代入される値は、配列pの各要素を各項とする多項式の計算結果である。また、GEXP[256]からGEXP[510]は、各ラウンドのiの値をnとするとGEXP[n - 255]で表せる(ちなみにGEXP[511]は演算には不要なので0でよい)。
ここで多項式の各項pについて見ると、例えば最初のp[0] = p[8]ならば現在のラウンドのp[0]に一つ前のラウンドのp[8]を代入している。つまり、上で挙げたような再帰によってラウンドを遡及しながら最終ラウンドの値までを順に求めていく必要がある。ただし問題なのは、多項式の各項はそれぞれ他の項と個別に異なった関係を結んでいるという点である。そこで、多項式の各項pをそれぞれ別の容器に保持し、各項の関係をテンプレートで表現することによって、全体像を表現することにする。各項の配列pの初期化は、例によってテンプレートの部分的特殊化で表現できる。
以上の方針で変換したものが次のリストである。
namespace GF256
{
// 多項式の各項をテンプレートで再帰的に表現する
template <int i>
struct P
{
enum {
p0 = P<i - 1>::p8,
p1 = p0,
p2 = P<i - 1>::p1,
p3 = P<i - 1>::p2 ^ p0,
p4 = P<i - 1>::p3 ^ p0,
p5 = P<i - 1>::p4 ^ p0,
p6 = P<i - 1>::p5,
p7 = P<i - 1>::p6,
p8 = P<i - 1>::p7,
};
};
// テンプレートの部分的特殊化による各項の初期化
template <>
struct P<0>
{
enum {
p0 = 0,
p1 = 1,
p2 = 0,
p3 = 0,
p4 = 0,
p5 = 0,
p6 = 0,
p7 = 0,
p8 = 0
};
};
// 各指数のテンプレートによる表現。
// コンパイラによっては再帰が複雑すぎるというコンパイラエラーが起きる
// 場合があるのでi < 256の条件別に2つのテンプレートに分割してもよい
template <int i>
struct E
{
enum {value = i < 256 ?
(P<i>::p1 + P<i>::p2 * 2 + P<i>::p3 * 4
+ P<i>::p4 * 8 + P<i>::p5 * 16
+ P<i>::p6 * 32 + P<i>::p7 * 64
+ P<i>::p8 * 128)
: E<i - 255>::value
};
};
template <>
struct E<0>
{
enum {value = 1};
};
// GEXP[255] = GEXP[0]の特殊化による表現
template <>
struct E<255>
{
enum {value = E<0>::value};
};
// 各指数をインスタンス化し、定数のテーブルを初期化する
const int GEXP[512] = {
E<0>::value, E<1>::value, E<2>::value, E<3>::value,
E<4>::value, E<5>::value, E<6>::value, E<7>::value,
/* 中略*/
E<504>::value, E<505>::value, E<506>::value,
E<507>::value, E<508>::value, E<509>::value,
E<510>::value,
0
};
};
これによって、プログラムの実行の最初に初期化関数を実行して得られたデータを以後シングルトンとして管理する等の作業から解放される。
ただし問題点もある。一見して気になるのが、最下部のGEXPの表である。ここには、511(+1)個分のEのインスタンスが入る。面倒な作業なのでPerlなどのスクリプトで生成してソースコードにペーストするしかない。 プログラム内で表の中のどの数を使用するかがあらかじめ決定できるわけではないので、静的な世界と動的な世界の橋渡しとして、このような表が必要になるのは致し方ない。
また、もっと深刻な問題は、このプログラムのコンパイルにかかる時間である。実はこれが一番最初に書いたテンプレートメタプログラミン グの限界を画する重要な問題に他ならない。コンパイラのテンプレートに対する最適化具合にもよるが、上記のようなテンプレートを展開しコンパイルするには相当なリソースが必要となって しまうのである。そこで、残念ながら、私ならば上記のプログラムを使わずに、昔ながらの定数テーブルをプログラムの中にペーストする方を選んでしまうだろう。付け加えると、本来的には、テンプレートメタプログラムのインスタンスは定数テーブルと同一の機械語コードを生成しなければならないはずだが、実際にそうなるかはコンパイラ次第なので、テンプレートメタプログラムの作成、ビルド、実行の各段階にかかるコストの見積に失敗すると痛い目に遭う。このトピッ クについてはDavid Abrahamsらによる考察に詳しいのでそちらを参照して頂きたい。
最後に、同じGF256の、逆対数を求めるテーブルをテンプレートメタプログラムに変換し、静的な制御構造について学習する。動的に表を作るには、以下のプログラムを実行する。
int GAL[256]; // 逆対数を保持するテーブル
GAL[0] = 1;
int p = 1;
for (int i = 1; i < 256; i++)
{
if (((p << 1) < (1 << 9))
&& ((p << 1) & (1 << 8)))
GAL[i] = (p << 1)
^ ((1 << 8) | (1 << 4)
| (1 << 3) | (1 << 2) | 1);
else
GAL[i] = p << 1;
}
一見して指数表の場合と異なるのは、if...elseブロックによる条件分岐がある点ぐらいか。単純にGAL[i] に値を代入しているだけなので、上で三項演算子(?:)を使用したのと同様にvalueに値を入れる構造を作れば十分である。ここでは、別の方法によるテンプレートメタプログラム化を試してみることにする。
template<
bool Cond,
typename TrueReturn,
typename FalseReturn
>
struct StaticIf
{
template<bool C>
struct Return
{
typedef TrueReturn R;
};
template<>
struct Return<false>
{
typedef FalseReturn R;
};
typedef typename Return<Cond>::R result_type;
};
namespace GF256
{
template <int i>
struct T
{
enum {
value = (i << 1) ^ ((1 << 8)
| (1 << 4) | (1 << 3)
| (1 << 2) | 1)
};
};
template <int i>
struct F
{
enum {value = i << 1};
};
template <int i>
struct AL
{
enum {value = StaticIf<
((AL<i - 1>::value << 1)
< (1 << 9))
&& ((AL<i - 1>::value << 1)
& (1 << 8)),
T<AL<i - 1>::value - 1>,
F<AL<i - 1>::value - 1>
>::result_type::value};
};
template <>
struct AL<0>
{
enum {value = 1};
};
const int GAL[256] = {
AL<0>::value, AL<1>::value, AL<2>::value,
/* 中略 */
AL<253>::value, AL<254>::value, AL<255>::value
};
};
StaticIfクラステンプレートが、コンパイル時に評価されるifの表現である(ちなみに、BoostのMPLに ほとんど同じものが一式揃っている)。テンプレートパラメータbool Condが真か偽かにより、Returnクラステンプレートの元のテンプレートか部分的特殊化バージョンのどちらかがインスタンス化され、それによってな し崩し的にtype_nameがテンプレートパラメータTrueReturnかFalseReturnのどちらかを表すようにtypedefされる。ここではtypedefによって型そのものがあたかも値であるかのように保持され、操作されている。言い換えれば、typedefされたエイリアス型は、型を保持するスロットであり、上記で使用してきた enumが定数に対するそれであるのと同様にはたらく。そのようにして結果的に得られた型については、これもenumの場合と同様に、 StaticIf<...>::result_typeのようにスコープ演算子を用いてアクセスする。
テンプレート内でのtypedefの使用や型の操作については、例えばSTLアロケータでのrebindは、型とテンプレート型を伝播させていくのに便利な手段として使用される(詳しくはRobert Schmidtによるコラムを参照されたい)。また、Lokiに おけるtypelistは、非常に強力な型操作のためのツールである(ただし、テンプレートメタプログラミングというよりはジェネリックプログラミングの範疇に属する)。typelistは、今のところマクロで実現されているとはいえ、極めて利用価値が高く、将来のC++標準へ言語機能として組み込まれることが望ましい機能の1つである。
さらに、例に登場させてはいないものの、sizeof演算子は型と定数という2つの要素を関連付け組み合わせるのに有用なツールである。sizeofは静的に適用でき、その結果はenumなどの定数に保持できる。つまり、テンプレートメタプログラミングの文脈では、型を定数に変換する ツールであると考えればよい。ただし、型によってサイズが異なるとは限らないので、サイズと型を一対一に対応させたり相互変換ができたりするわけではな く、限定的な利用形態に留まる。
以上、テンプレートメタプログラミングについて基本を一通り見てきた。単なるシンタックスシュガーを超えてC++テンプレートには非常に大きな可能性があること、現在のC++の最重要機能はテンプレートであることを意識して頂ければ幸いである。
参考文献:
[1] The Blitz++ Library
[2] Todd Veldhuizen, Template Metaprograms
[3] Andrei Alexandrescu, Modern C++ Design: Generic Programming and Design Patterns Applied (C++ in Depth Series)
, Addison Wesley 2001 (邦訳)[4] Loki: A C++ library of designs, containing flexible implementations of common design patterns and idioms
[5] The Boost C++ Library
[6] The Boost MPL Library
[7] James O. Coplien, Multi-Paradigm Design for C++
, Addison Wesley 1999 (邦訳)[8] Paul Graham, On Lisp, Prentice Hall, 1993 (webで全文閲覧可能)
[9] static_assert in The Boost C++ Library
[10] David Abrahams and Carlos Pinto Coelho, Effects of Metaprogramming Style on Compilation Time
[11] Robert Schmidt, Deep C++: Typedef Templates, Microsoft Corporation Aug. 2000
コメント
コメントを投稿