source: http://cpp-next.com/archive/2012/10/using-strings-in-c-template-metaprograms/
メタプログラミング1が大好きになる理由のなかでも、プログラムに”小さな言語”を埋めこむことができる、というのは抗い難い魅力がある。たとえば、複素数のパーサーを再帰下降パーサーを手書きするよりは、こんなふうに書きたいと思うだろう。
auto parse_complex =
'(' >> double_ >> -(',' >> double_) >> ')'
| double_;
ほかにも、CDプレーヤーのステートマシンを手書きするかわりに、状態遷移表をこのように書きたいと思うはずだ。
auto player = Stopped + play [some_guard] / (some_action , start_playback) == Playing , Stopped + open_close/ open_drawer == Open , Stopped + stop == Stopped , Open + open_close / close_drawer == Empty , Empty + open_close / open_drawer == Open , Empty + cd_detected [good_disk_format] / store_cd_info == Stopped
これらBoost.SpiritとBoost.MetaStateMachineを使った二つの例は、どのようにパーサーやステートマシンを記述できるかを示している。 これらのライブラリに組み込まれているメタプログラムは、ユーザーが記述した高度に抽象化された宣言を解釈し、超効率的な実行コードを生成する。 これらの宣言を表現するための”小さな言語”はライブラリ・ドメインに特化しており(パーサーやステートマシン)、ホスト言語であるC++に埋め込まれている。このような言語は、 EDSL(Embedded Domain Specific Language) と呼びならわされる。
式テンプレート
上記二つのEDSLには、”式テンプレート(expression templates)”と言うテクニックが用いられている。 式テンプレートにおいては、人が普通考える即時計算のような流れではなく、演算子と関数をオーバーロードすることで、メタプログラムが最終的に要求されたコードを生成するために利用する、コンパイル時パースツリーの生成を達成している。 この “遅延評価” によって、ライブラリは式全体を考慮することができるので、式を即時評価する場合には不可能な最適化を行うことができる。
BoostにはProtoという式テンプレートライブラリを組み立てるためのライブラリがある、という点をみても、式テンプレートは汎用的で非常に効率的であると言えるだろう。 だが、厳しい制限もある。式がC++で有効な表現でなければならないという点だ。このような小さな言語の強力な利点としてよく上げられるのは、既に存在していて、広く知られており、その問題領域に属する人が受け入れやすいように進化した構文を提供できる点だろう。 このような進化はコンピュータで言語が処理されるよりもはるか前に起こっている場合もある(記譜法について考えてみよ)。よって、有効なC++の式として正確に解釈できるDSLというのはごく少ない。我々には近い構文を思いつくのが精々だ。非常に”コンピューターに近い”言語、たとえば正規表現でさえも、直接C++に与えることはできない。
auto all_caps = [A-Z]+; // SYNTAX ERROR
古き良き文字列ならどうか?
もちろんC++式の代わりに、DSLコードスニペットを表現するのに文字列を使う手もある。 実際、この方法は”従来の”ライブラリにもよく使われている。
auto all_caps = std::regex("[A-Z]+"); // OK
ただ、一つ問題がある。文字列の内容はランタイムにしか分からないので、この埋めこんだ言語はランタイムにしか解釈できず、翻訳した結果をコンパイル済みのコードに落とすことが不可能になることだ。”遅延評価”は実行時まで遅延されてしまう。
しかし、逆に言えば、コンパイル時に文字列をパースできれば、最適なパフォーマンスを得ることができるわけだ。これをやってのけるには、テンプレートメタプログラムに文字列を渡すことが必要不可欠だ。テンプレートメタプログラムはもちろん、この文字列を処理して、同時に、解釈可能なC++コードを生成しなければならない。こんな風に書けるのが理想だろう。
tmp_string<"Hello World!">
しかし、文字列リテラル”Hello World!”は内部リンケージを持つ文字配列なので、テンプレート実引数として渡すことはできない。
メタプログラムでの文字列
さて、テンプレートメタプログラムが解釈できる文字シーケンスをどう表現したらいいだろう?
MPLは、コンパイル時に個々の要素に対する操作や列挙を行う機能をもつ、テンプレートメタプログラム用のシーケンスを備えている。例えば、
boost::mpl::vector_c<
char, 'H','e','l','l','o',' ','W','o','r','l','d','!'
> s;
char const fifth_char // 'o'
= boost::mpl::at_c<s,4>::type::value; // like s[4]
いちどこのように表現できてしまえば、これを処理するのは簡単だ2。問題はどうやってここまで持ってくるかだ。もちろん、直接書き下してもいいが、とても書きにくいし読みにくい。MPLには複数の文字定数を受けつける特殊なラッパーテンプレートがある。
boost::mpl::string<'Hell','o Wo','rld!'>
ほんのちょっと短くなったが、さらに読みづらくなってしまった。また、文字の挿入や削除は非常にやっかいだ。というのは、4文字境界を破壊しないように、毎回手作業で調整しなければならないからだ。
ましな方法
必要なのは”Hello World!”のようなC++文字列リテラルをMPLシーケンスに自動変換する方法だ。そのために、MPLのpush_backメタ関数を使って一文字ずつ組み上げてみよう。こんな風に。
boost::mpl::push_back< boost::mpl::string<'Hell'>, boost::mpl::char_<'o'> >::type // approximately boost::mpl::string<'Hell','o'>
MPLシーケンスの要素はどんな型もとり得るので、mpl::char_ラッパーを使って’o’文字を型に落し込んでいる。上の式は”Hello”という文字列をmpl::char_sのコンパイル時シーケンスとして生成する。
この方法を使えば、文字列全体を一文字ずつ生成できる:
boost::mpl::push_back<
boost::mpl::push_back<
// ...
boost::mpl::push_back<
boost::mpl::string<>, // The empty string
boost::mpl::char_<'H'>
>::type,
// ...
boost::mpl::char_<'d'>
>::type,
boost::mpl::char_<'!'>
>::type
この型式は空文字列で始まり、一文字ずつ”Hello World!”という文字を加えていくのだが、もちろんこんなのを手作業で書きたくはないだろう。コンパイラが自動的にこれを生成するワザが欲しいと思うのが普通だ。そのために、突破口となる新しい言語機能が必要になる。
一般化された定数式
C++11では、”一般化された定数式”3 が標準化された。これは基本的に二つのことをやってのける。
- 文字列リテラルのようなものも、コンパイル時定数として使える
enum { o = "Hello"[4] }; // OK in C++11
- 実引数が全てコンパイル時定数なら、出力される結果もコンパイル時定数になるconstexpr関数の追加
constexpr unsigned factorial(unsigned x)
{
return x == 0 ? 1 : x * factorial(x-1);
}
int a[factorial(6)]; // OK in C++11
ぱっと見、この二つの機能があれば、もうコンパイル時に文字列リテラルを直接操作できるような気がする。 だがしかし、constexpr関数には、普通の関数としてもコンパイルされなければならない、という縛りがある。仮に実引数のうち一つでもコンパイル時定数でないなら、この関数は普通にランタイム動作することになり、コンパイル時定数ではなくなってしまう。その結果、関数内部、そしてその戻り値の型は、ふつうの実行時に利用される値として扱わねばならなくなってしまう。 これはC++メタプログラミングの要であるが、実行時の値は型に対してまったく影響をおよぼさない。
constexpr std::array<int,n> // ERROR: n is not a constant expression
f(unsigned n);
constexpr void g(unsigned m)
{
std::array<int, m> a; // ERROR: m is not a constant expression
}
制限をごまかすには
まだ全てがオジャンになったわけではない。constexpr関数でそう多くのことを達成できないが、前に示した通り、文字列リテラルも定数式だし、定数式である配列の添字演算子もまた定数式である。よって、”Hello World!”[ 0 ]は定数式なので、先の型シーケンスは以下のようにも構築できる。
boost::mpl::push_back<
boost::mpl::push_back<
// ...
boost::mpl::push_back<
boost::mpl::string<>,
boost::mpl::char_<"Hello World!"[0]>
>::type,
// ...
boost::mpl::char_<"Hello World!"[10]>
>::type,
boost::mpl::char_<"Hello World!"[11]>
>::type
上の例は、前のヴァージョンそっくりだが、個々の文字を記述するのではなく”Hello World!”という文字列から添字演算子で抽出している点が異なる。
明らかに、複雑さの上にややこしさを積んだようなもので、より悪くなっているようにしか見えない! だがちょっと待ってほしい。上の例は、マクロ実引数として文字列リテラルを取るプリプロセッサマクロに書き直せる。
#define _S(s) \
boost::mpl::push_back< \
boost::mpl::push_back< \
// ... \
boost::mpl::push_back< \
boost::mpl::string<>, \
boost::mpl::char_<s[0]> \
>::type, \
// ... \
boost::mpl::char_<s[10]> \
>::type, \
boost::mpl::char_<s[11]> \
>::type
こうすれば、以下のように”Hello World!”はテンプレート実引数として渡せるようになる。
f<_S("Hello World!")>
マクロを整える
マクロを短縮していないので、上記の例は4倍ほども長くなっているし、典型的なDRY違反を犯している。もうすこしこのコードをまともにするために、Boostのプリプロセッサメタプログラミングライブラリを使って、この繰り返しをなんとかしてみよう。
#define PRE(z, n, u) boost::mpl::push_back<
#define POST(z, n, u) , boost::mpl::char_<s[n]>>::type
#define _S(s) \
BOOST_PP_REPEAT(12, PRE, ~) \
boost::mpl::string<>, \
BOOST_PP_REPEAT(12, POST, ~)
BOOST_PP_REPEATがPRE、POSTを展開するとき、nマクロ実引数として、添字、すなわち展開するときのリスト中の位置を渡す。POSTはこの添字からs中の文字を示す添字を生成する。4
さて、constexprの使い時だ
12という数字はこの例の文字列の長さからもってきたが、これでは12文字より短い文字列に対応できない。例えば、_S(“foo”)は以下のように展開されるだろう。
boost::mpl::push_back<
// ...
boost::mpl::push_back<
boost::mpl::push_back<
boost::mpl::push_back<
boost::mpl::push_back<
boost::mpl::string<>,
boost::mpl::char_<"foo"[0]>
>::type,
boost::mpl::char_<"foo"[1]>
>::type,
boost::mpl::char_<"foo"[2]>
>::type,
boost::mpl::char_<"foo"[3]>
>::type,
// ...
boost::mpl::char_<"foo"[11]>
>::type
{‘f’, ‘o’, ‘o’, ‘\0’} はたった4要素しかないので、与えられる添字は配列の終端を9回も越していることになる。幸いにも、これらのことはコンパイル時に解決されるので、コンパイラはエラーを吐いてくれるだろう。安全なだけではなく、もっと汎用性を持たせられないものか。この問題をどうにかするには、配列の要素を取得する関数テンプレートを記述すればよい。そしてここでconstexprがやってくれる。
template <int N>
constexpr char at(char const(&s)[N], int i)
{
return i >= N ? '\0' : s[i];
}
char const(&s)[N]は N個の要素からなるconst charの配列への参照を意味し、これにより配列のサイズが推論できるので、終端よりむこうの要素を指すような添字が与えられたなら0を返すことができる。_Sマクロで使っている添字演算子をこれで置きかえてみよう:
#define PRE(z, n, u) boost::mpl::push_back<
#define POST(z, n, u) , boost::mpl::char_<at(s, n)>>::type
#define _S(s) \
BOOST_PP_REPEAT(12, PRE, ~) \
boost::mpl::string<>, \
BOOST_PP_REPEAT(12, POST, ~)
やっかいな0
上述の実装で_S(“foo”)をコンパイルできるようになったが、これはイマイチよろしくない結果を吐きだす。”foo”に対応するシーケンスを吐くのではなく、”foo\0\0\0\0\0\0\0\0\0”に対応するシーケンスを吐いてしまうのだ。_Sが文字列の長さについて感知しないので、ただ言われた数だけ文字列のうしろにヌル文字を追加してしまうからだ。この運命を変えるには、boost::mpl::push_backを、規定の長さに達したらシーケンスの拡張を止めるラッパーに置きかえればよいだろう。
template <class S, char C, bool EOS>
struct push_back_if_c :
boost::mpl::push_back<S, boost::mpl::char_<C>>
{};
template <class S, char C>
struct push_back_if_c<S, C, true> : S {};
このラッパーは元文字列と、文字数、さらに追加のboolean実引数を取る。このbooleanが真のとき、文字列の終端を越えたことを示す。このとき、単に前の結果を返すだけだ。でなければ、push_backに実引数を転送する。
この関数を使うことで、このマクロは12文字以下の文字列を正しく扱うことができるようになる。
#define PRE(z, n, u) push_back_if_c<
#define POST(z, n, u) , at(s, n), (n >= sizeof(s))>::type
#define _S(s) \
BOOST_PP_REPEAT(12, PRE, ~) \
boost::mpl::string<>, \
BOOST_PP_REPEAT(12, POST, ~)
制限を設定可能にする
12文字より文字列が長い場合はどうだろう?うむ、このマクロは破綻してしまう。しかし、ハードコーディングしている12を別のシンボルに置きかえれば、ユーザーが上限を設定できるようになる。
#ifndef STRING_MAX_LENGTH
#define STRING_MAX_LENGTH 32
#endif
#define PRE(z, n, u) push_back_if_c<
#define POST(z, n, u) , at(s, n), (n >= sizeof(s))>::type
#define _S(s) \
BOOST_PP_REPEAT(STRING_MAX_LENGTH, PRE, ~) \
boost::mpl::string<>, \
BOOST_PP_REPEAT(STRING_MAX_LENGTH, POST, ~)
このコードは_Sが扱える最大文字数を示すSTRING_MAX_LENGTHマクロを導入している。ユーザーが_Sの定義をインクルードする前に#define STRING_MAX_LENGTHがなければ、デフォルトとして12が与えられる。
もしpush_back_ifが_Sを使うたびにSTRING_MAX_LENGTH回利用されるとしたら、必要よりも高い制限を使わないのは理に叶っている。ただ注意しなければならないのは、未使用の文字それぞれについて、同じ組の実引数が繰りかえしpush_back_if_cに渡されるということだ。
push_back_if_c< // The final string, '\0', true >
すなわち、未使用の文字のぶんだけ、コンパイル時間は伸びてしまうが、テンプレート実体化の数は変わらない。
まとめ
プリプロセッサ、constexpr、テンプレートメタプログラミングを組みあわせることで、文字列リテラルをテンプレートメタプログラムで操作できる型に落としこむ方法を示した。このアーティクルで紹介した技法は、Metaparseライブラリという、コンパイル時文字列パーサー生成キットに組み込まれている。