C++11TMPによるコンパイル時コンパイラltmpcを支えるテンプレートメタプログラミングテクニック

C++のテンプレートメタプログラミングによるコンパイル時C言語コンパイラ、「ltmpc」を作っています。まだまだ実装すべきことはたくさんありますが、最低限動くようになってきました。
ltmpcのはなし

実は、以前にC11のフルセットをサポートするC言語のコンパイラがC++TMP上に実装されたことがありました。
コンパイル中にコンパイルする「コンパイル時Cコンパイラ」をつくった話
しかし、この自動生成法のアプローチでは、メモリ使用量が爆発する問題から、残念ながら現存するコンパイラで現実的なコンピュータ上で動かすことはできません。

テンプレートメタプログラミングで、C言語のコンパイラほど大きな「動く」プログラムが作られたことは今までになかったように思われます。今回は、いかにして「動く」TMPプログラミングを行っていくか、というおはなしをしたいと思います。

既存技術の紹介

constexprメタプログラマは、テンプレート再帰深度を抑えることに心血を注いできました。ltmpcでは、その成果をフルに活用しています。まずは、それらの既存のテクニックを紹介します。
constexpr idiomsというスライドが詳しいです。併せてご覧になることをおすすめします。

make_index_tuple

簡単に言うとIndexTupleイディオムを使う時に必要な、以下のような非型テンプレートパラメータパックに連続する整数がならんだものを構築する技法です。

template<index_t... Indices>
void f( index_tuple<Indices...> );

// [Indices = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}]でfを呼び出す
f( make_index_tuple<10>{} );

標準ライブラリの方法

C++14で導入されたstd::make_index_sequenceでは、実質的にはmake_index_sequence<10>がmake_index_sequence<9>を呼び出し、それがさらにmake_index_sequence<8>を呼び出し……という方法によりstd::index_sequence<0,1,2,3,4,5,6,7,8,9>を作り出します。

• この方法のテンプレート再帰深度はΘ(N)

メタプログラマの方法

index_tuple イディオムにおける index_range の効率的な実装 - ボレロ村上 - ENiyGmaA Code
メタプログラマは、std::make_index_sequence<10000>などとしてテンプレート再帰深度制限に引っかかることを嫌い、模索した結果、パック展開をうまく使うと再帰深度が対数オーダーで抑えられることに気づきました。[N = 5, Indices = {0, 1, 2, 3, 4}]の時にIndices..., (Indices+N)...と書くと0, 1, 2, 3, 4, 5, 6, 7, 8, 9と等価になることが分かります。このことを利用し、make_index_tuple<10>は引数が半分のmake_index_tuple<5>を呼び出し、さらにそれがmake_index_tuple<2>を呼び出し……といった方法を使ったものです。

• この方法のテンプレート再帰深度はΘ(log N)

C++17erの方法

Folding-expressionを用いてparameter pack長のindex_sequenceを構築する - ここは匣
index_tupleが必要な場合、たいていはmake_index_tuple<sizeof...(Ts)>のような、パラメータパックのサイズだけのindex_tupleが欲しいことが大半です。こういった場合、畳み込み式が手に入ったC++17メタプログラマは、畳み込み式を使ってテンプレート再帰深度をΟ(1)に抑えることに成功しました（畳み込み式はコンパイラマジックにより、テンプレート再帰深度がΟ(1)になります）。

• この方法のテンプレート再帰深度はΘ(1)

パラメータパックへのランダムアクセス

テンプレートパラメータパックは、普通には以下のように先頭にしかアクセスできませんが、

template<class T, class... Ts>
auto get_front( tuple<T, Ts...> ) -> T;

工夫すると構築時テンプレート再帰深度Θ(1)+index_tuple構築分、アクセス時テンプレート再帰深度Θ(1)のランダムアクセスが可能になります。
再帰深度を抑えたtuple的コンテナの構築 - ここは匣

template<std::size_t N, class T>
struct indexed_type {};

template<class, class...>
struct type_tuple_base;
template<index_t... Indices, class... Ts>
struct type_tuple_base<index_tuple<Indices...>, Ts...> : indexed_type<Indices, Ts>... {};

template<class... Ts>
struct type_tuple : type_tuple_base<make_index_tuple<sizeof...(Ts)>, Ts...> {
    template<std::size_t N, class T>
    static auto get_type_impl( indexed_type<N, T> ) -> T;
    template<std::size_t N>
    auto get_type() -> decltype( get_type_impl<N>(*this) );
};

この例のようにパック展開による多重継承を使い、それをget_typeの中に入れると暗黙のアップキャストによりオーバーロード解決がされることを利用するのです。
なおこのアップキャストは、ポインタや参照を介したものではなく、値のコピー時の基底クラスへの暗黙変換を利用しています。

型の辞書

「パラメータパックへのランダムアクセス」のインデックスは、必ずしも整数である必要はなく、型にすることも可能です。これを使うと、ある型から、それに対応付けられた別の型を表引きすることができます。

パラメータパックの後半取得

make_index_tupleと全く同様な手法により、型voidが任意個並んだvoid_tuple<void, void, void, ..., void>を作り出すmake_void_tupleを、テンプレート再帰深度Ο(log N)で書けます（「C++17erの方法」でも書けますが、後述の理由により「メタプログラマの方法」がよいです）。これを使うと、パラメータパックの後半を取得することが簡単にできます。

template<class... Ts>
struct type_tuple {
    template<class... Voids, class... Us>
    static auto tail_impl2( Voids*..., Us*... )
        -> type_tuple<Us...>;

    template<class... Voids>
    static auto tail_impl( void_tuple<Voids...> )
        -> decltype( tail_impl<Voids...>( static_cast<Ts*>(nullptr)... ) );

    using tail = decltype( tail_impl( make_void_tuple<(sizeof...(Ts)/2>{} ) );
};

パラメータパックをテンプレート引数に取り、さらにパラメータパックの推論も行うという非常に珍しいテクニックを使っています。clang3.9.1までは、この構文に対応していませんでしたが、clang4.0以降では使えるようになったようです。

分割統治によるテンプレート再帰深度抑制

例として、x, f(x), f(f(x)), ..., f(f(f(...f(x)...)))のように、関数を任意回適用した結果のリストを得ることを考えます。C++17の畳み込み式を使うとそれなりに簡単になりますが、それを使わないで書くことを考えましょう。ちょっと長くなります。

template<class...>
struct TypeTuple {};

template<class... Ts, class... Us>
auto merge( TypeTuple<Ts...>, TypeTuple<Us...> ) 
    -> TypeTuple<Ts..., Us...>;

template<template<class>class Func, std::size_t N, class Init>
struct Unfold {
    using HeadResult = typename Unfold<Func, N/2, Init>::Result;
    using HeadNext = typename Unfold<Func, N/2, Init>::Next;
    using TailResult = typename Unfold<Func, N-N/2, HeadNext>::Result;
    using Next = typename Unfold<Func, N-N/2, HeadNext>::Next;
    using Result = decltype( merge( HeadResult{}, TailResult{} ) );
};

template<template<class>class Func, class Init>
struct Unfold<Func, 1, Init> {
    using Next = Func<Init>;
    using Result = TypeTuple<Init>;
};

template<template<class>class Func, class Init>
struct Unfold<Func, 0, Init> {
    using Next = Init;
    using Result = TypeTuple<>;
};  

[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ

まずは前半半分を処理して作ったリストをResultとし、その最後の要素の次(途中結果)をNextとします。
そして、そのNextを後半部分への初期値として渡すことで、順次的な処理を実現します。
最後に、前半部分を処理して作ったリストHeadResultと後半部分を処理して作ったTailResultをマージすることにより、全体の結果とします。
この方法により、愚直な実装だとテンプレート再帰深度がΘ(N)になりかねないところを、Θ(log N)に抑えることができます。

テンプレート再帰深度Θ(1)のその先へ

constexprメタプログラマ達は、テンプレート再帰深度Θ(1)を達成したところで満足してしまったように思われます。たしかに、constexprメタプログラミングをするだけなら、テンプレートの再帰深度問題に引っかからなくなりさえすれば、もともとの目的のconstexprメタプログラミングに集中できます。しかし、大規模なTMPを行うにはこれではまだ不十分です。さらにその先を見ていきましょう。

make_index_tuple再考

先ほどmake_indext_tupleの実装方法を三つ紹介しました。さて、そのうちでどの方法が良いのでしょうか。一見、C++17erの方法がテンプレート再帰深度が小さくて、コンパイラにやさしそうに見えます。あなたがconstexprメタプログラマであれば、その見解は正しいかもしれません。しかし、あなたがTMPプログラマであるのなら、これが正しくないことに気づかないかぎり、大規模プログラムをTMPで書くことはできないでしょう。

実際に計測してみましょう。

メタプログラマの方法

「メタプログラマの方法」で実装されたindex_tupleはSprout C++ Librariesに存在するため、それを使いましょう。Wandboxでも簡単に使えます。

log_index_tuple_test.cpp

#include <iostream>
#include <sprout/index_tuple.hpp>

template<char...>
struct Text {};

template<char... Chars, sprout::index_t... Indices>
void print( Text<Chars...>, sprout::index_tuple<Indices...> ) {
    (std::cout << ... << Chars) << std::endl;
    (std::cout << ... << Indices) << std::endl;
}

int main() {
    Text<
#include "text.inc"
    '$'> text;

    print( text, sprout::make_index_tuple<SIZE>{} );
}

ただし、text.incの中身は、'S','P','R','Y','N',...とランダムで生成されたchar型テンプレート実引数がSIZE個入っているものです(printf("'%c',", rand()%27+'@')を繰り返したもの。最後に余分なコンマがつくためソースコード上で'$'と書いている)。

さてコンパイルしてみましょう（-O0をつけないと最適化しようとしてclangが落ちてしまうので注意！）。

$ clang++-4.0 -std=c++1z -O0 -I /path/to/Sprout/ log_index_tuple_test.cpp

実験環境: Ubuntu14.04, Intel core i7-3630QM @2.40GHz, 16GBRAM(DDR3, 1600MHz) のもとで動作させると、
SIZE=10000で、2.8秒、メモリ使用量166MB
SIZE=20000で、5.6秒、メモリ使用量284MB
SIZE=50000で、16.1秒、メモリ使用量627MB
SIZE=100000で、39.5秒、メモリ使用量1.22GB
という感じになりました。それなりにスケールした動作をしていますね。10万要素ものテンプレートがコンパイルできるのは驚きです。

C++17erの方法

「C++17erの方法」を実装してみました。たった14行です。畳み込み式は読みやすくなって良いですね。

cxx17_index_tuple.hpp

#include <cstdint>

template<std::size_t... Indices>
struct cxx17_index_tuple {};

tmeplate<std::size_t... Indices>
auto operator+( cxx17_index_tuple<Indices...>, char ) {
    return cxx17_index_tuple<Indices..., sizeof...(Indices)>{};
}

template<template<char...>class C, char... Chars>
auto make_index_tuple( C<Chars...> ) {
    return (cxx17_index_tuple<>{} + ... + Chars);
}

cxx17_index_tuple_test.cpp

#include <iostream>
#include "cxx17_index_tuple.hpp"

template<char...>
struct Text {};

template<char... Chars, std::size_t... Indices>
void print( Text<Chars...>, cxx17_index_tuple<Indices...> ) {
    (std::cout << ... << Chars) << std::endl;
    (std::cout << ... << Indices) << std::endl;
}

int main() {
    Text<
#include "text.inc"
    '$'> text;

    print( text, make_index_tuple( text ) );
}

さてコンパイルしてみましょう……

先ほどと同じ感じで動作させてみると、
SIZE=500で、0.9秒、メモリ使用量115MB
SIZE=1000で、2.9秒、メモリ使用量297MB
SIZE=2000で、5.9秒、メモリ使用量1.01GB
SIZE=5000で、31.2秒、メモリ使用量5.95GB
という感じになりました。これではとてもコンパイラが動きそうな気配はありません。

なぜC++17erの方法はスケールしないのか？

C++17erの方法はテンプレートの再帰深度こそΘ(1)になりますが、基本に立ち返ってみると、

template<std::size_t... Indices>
auto operator+( cxx17_index_tuple<Indices...>, char )

というテンプレートのインスタンス化はN回起こるということが分かります。そして、コンパイラはこのテンプレートがインスタンス化したことを覚えておくわけです。しかも、それはコンパイルが終了するまで忘れられることがありません。
[Indices={}]のインスタンス、[Indices={0}]のインスタンス、[Indices={0, 1}]のインスタンス、……[Indices={0, 1, 2, 3, 4, ..., 998}]のインスタンス、[Indices={0, 1, 2, 3, 4, ..., 999}]のインスタンス、そんなものを覚えておくためには、Θ(N^2)の空間が必要ということに気が付くでしょうか。

これこそがC++17erの方法（や標準ライブラリの方法）がスケールしない理由です。テンプレート再帰深度だけに目を奪われてはいけません。逆に、メタプログラマの方法はテンプレート再帰深度こそΘ(log N)ではありますが、必要な空間はΘ(N)ですむのです！

パラメータパックへのランダムアクセス

空間の節約

さあ、先ほど得られた知見を「パラメータパックへのランダムアクセス」に適用してみましょう。

template<class... Ts>
struct type_tuple {
    template<std::size_t M>
    auto get_type() -> ...;
};

これに対してget_type<0>とやるとどうなるでしょうか。
そう、[M = 0; Ts = {N個の型リスト}]のインスタンスが生成されます。つまり、一つ呼ぶだけでΘ(N)の領域を使ってしまいます。decltype(get_type<Indices>())...などと書くと、下手するとΘ(N^2)の領域を使ってしまうことにつながり、コンパイラにやさしくありません。

幸い、これには非常に単純な解決策があります。メンバ関数にしているから不要なTs情報がついてくるのであって、フリー関数にしてしまえばよいのです。そうすると一つ呼ぶにはΘ(1)の領域、全種類呼んでもΘ(N)の領域しか使わなくなります。

時間の節約

多重継承されたものからマッチする暗黙変換を選び出すという作業は、とても時間がかかります。明らかに、他の暗黙変換がマッチしないことを確かめるだけでΘ(N)の時間がかかります（注1）。つまり、線形探索をやっているようなものです（しかも他にマッチするものがないかも確認するので、偶然先頭にあった場合は速いとかいうわけではなく、常に線形時間かかります）。二分木型の継承を使うことで、これを二分探索にすることができます。

なお、ltmpcではこの手法は採用されていません。もしかするとこの方法を使うとより高速化するかもしれませんが、そもそもパラメータパックを半分ずつにするのは難しいです(後述)。

(注1): ただし、前方にある暗黙変換が採用される場合の方が、後方にある暗黙変換が採用される場合より定数倍速くなります。理由はコンパイラのコードを見ないとわかりませんが、一段の暗黙変換で採用できるオーバーロード関数の候補が現れたので、暗黙変換の暗黙変換等を考慮しなくてよくなったことが原因なのかもしれません。

分割統治によるテンプレート再帰深度抑制

先の「分割統治によるテンプレート再帰深度抑制」を見てみましょう。
mergeするとき、同じ大きさのもの同士をマージするテクニックを使っていますね。これは、ふつうのプログラミングをする時にも使える、時間計算量を低減させるテクニックとして頻出のアルゴリズムです。TMPでは一度使った空間は帰ってこないため空間計算量がΘ(N log N)になりますが、いずれにせよそれほど空間を浪費している感じはありません。

一方、畳み込み式の方の実装はどうでしょうか。大きいものに小さいものを順次マージになっていますね。これではmake_index_tupleの時同様、Θ(N^2)の空間を使ってしまいます。

このように、テンプレート再帰深度を対数に抑制することは、空間を節約することにもつながってきます。
一方、畳み込み式を使うのは、実は愚直な線形再帰と大して変わらない、コンパイラにやさしくない方法だということが分かったでしょうか。

まとめ

大規模TMPを行う時は、テンプレート再帰深度だけにとらわれず、テンプレートのインスタンスが消費するメモリ量を考えましょう。それこそが、本当にコンパイラにやさしいコードです。

ltmpcを実装するにあたって開発された技術

パラメータパックを半分ずつに分割する(flat_tuple)

順次処理が必要なコンパイラを実装するにあたって、「分割統治によるテンプレート再帰深度抑制」を使うことはほぼ必須であるといえるでしょう。ここで、コンパイラを実装するには、例に挙げたunfoldではあまり役立ちませんが、prefix scanと呼ばれる高階関数を実装すると都合がよいです。prefix scanとは、{0, 1, 2, 3, 4, 5, 6}から{0, 1, 3, 6, 10, 15, 21}を生成するような、畳み込みの途中結果のリストを作成する、型(T→U→T)→[U]→T→[T]を持つ高階関数です。これを使うと、ステートマシン(トランスデューサー)を実装することができます。[U]は入力列、[T]は{出力、ステートマシンの次状態}というタプルの列であると解釈すると、prefix scan高階関数により自然に実現できることがわかります。ここから出力列だけを取り出すときにはmap高階関数を使えばよく、これはTMP組み込みのパック展開を使えば自明に実装することができます。

さて、unfoldの例では入力はただ一つでしたが、prefix scanでは入力のパラメータパックを前半と後半に分割して渡す必要があります。ここで問題になるのは、「パラメータパックを半分ずつに分割する」ことが意外に難しいということです。「パラメータパックの後半取得」を使うと後ろ半分を取り出すことはできるのですが、同じ方法では前半分を取り出すことはできません（推論されるパラメータパックは引数の最後に存在しないといけないという制約があります）。
結局、「パラメータパックへのランダムアクセス」を複数回繰り返すことで、無理やりパラメータパックの前半を取得することにしました。しかし、この「パラメータパックへのランダムアクセス」は、前述したように一要素を取り出すだけでパラメータパックのサイズに比例する時間がかかります。つまり、前半部分を作り出すだけでΘ(N^2)の時間がかかってしまうことになります。
とはいえ、背に腹は代えられないので、時間がΘ(N^2)かかるとしても、空間使用量がΘ(N log N)な方法でパラメータパックを半分ずつにできる手法は有用です。
それにしてもパラメータパックを分割するだけでΘ(N^2)の時間がかかるのはなかなか厳しいものがあります。長さによらず高速に取得できる後半部分を長くとり、長くとると時間がかかる前半部分を短くとることで、空間使用量を若干犠牲にしつつ、定数倍の姑息な高速化が可能です。ltmpc内部ライブラリのlfl::flat_tupleでは、前半1:後半3に分割しています。なお、flat_tupleは私が勝手につけた名前です。

また、「パラメータパックへのランダムアクセス」の中のget_typeをフリー関数化して空間使用量を節約する、という最適化が可能であるということを前述しました。ここにはうっかりしやすい落とし穴が存在します。それは、名前修飾せずに呼び出すとADLが発動するということです。別にこれが発動したところでコンパイル自体は問題なく行われるのですが、呼び出し関数を決定するために探索する範囲が一気に広がるので、非常に低速になります。パラメータパックを再帰的に分割していくと、この関数は合計でΘ(N log N)回呼ばれるため、これが遅くなってしまうのは致命的です。ちゃんと名前修飾してあげましょう。

余談：禁断の魔術を使えば

そもそもパラメータパックの前の方にあるものは直に取り出すことができるのでした。禁断の魔術、Cプリプロセッサマクロを使えば、無理やり前から取り出すことで高速に前半部分のリストを作り出すことも可能です。また、boostのリピートマクロを使っているわけではないので、要素数の制限は事実上ありません。

#include <type_traits>
#include <boost/preprocessor/cat.hpp>

template<class... Ts>
struct Tuple{};

#define CLASSES1(c,t) c t
#define CLASSES2(c,t) CLASSES1(c,BOOST_PP_CAT(t,0)), CLASSES1(c,BOOST_PP_CAT(t,1))
#define CLASSES4(c,t) CLASSES2(c,BOOST_PP_CAT(t,0)), CLASSES2(c,BOOST_PP_CAT(t,1))
#define CLASSES8(c,t) CLASSES4(c,BOOST_PP_CAT(t,0)), CLASSES4(c,BOOST_PP_CAT(t,1))
#define CLASSES16(c,t) CLASSES8(c,BOOST_PP_CAT(t,0)), CLASSES8(c,BOOST_PP_CAT(t,1))
#define CLASSES32(c,t) CLASSES16(c,BOOST_PP_CAT(t,0)), CLASSES16(c,BOOST_PP_CAT(t,1))
#define CLASSES64(c,t) CLASSES32(c,BOOST_PP_CAT(t,0)), CLASSES32(c,BOOST_PP_CAT(t,1))
#define CLASSES128(c,t) CLASSES64(c,BOOST_PP_CAT(t,0)), CLASSES64(c,BOOST_PP_CAT(t,1))
#define CLASSES256(c,t) CLASSES128(c,BOOST_PP_CAT(t,0)), CLASSES128(c,BOOST_PP_CAT(t,1))
#define CLASSES512(c,t) CLASSES256(c,BOOST_PP_CAT(t,0)), CLASSES256(c,BOOST_PP_CAT(t,1))
#define CLASSES1024(c,t) CLASSES512(c,BOOST_PP_CAT(t,0)), CLASSES512(c,BOOST_PP_CAT(t,1))

#define HEAD_FUNCS(n) template<\
BOOST_PP_CAT(CLASSES,n)(class, T),\
class... Ts,\
typename std::enable_if<sizeof...(Ts) && sizeof...(Ts) <= n, std::nullptr_t>::type = nullptr\
>\
auto head()\
    -> Tuple<\
        BOOST_PP_CAT(CLASSES,n)(,T)\
    >;

HEAD_FUNCS(1)
HEAD_FUNCS(2)
HEAD_FUNCS(4)
HEAD_FUNCS(8)
HEAD_FUNCS(16)
HEAD_FUNCS(32)
HEAD_FUNCS(64)
HEAD_FUNCS(128)
HEAD_FUNCS(256)
HEAD_FUNCS(512)
HEAD_FUNCS(1024)

decltype( head<void, char, int, double>() );
// => Tuple<void, char>

いや、でもさすがにこれは何か違うでしょ…………。
というわけで、"TMPによるCコンパイラ"のltmpcには採用されていません。

関数を使ったTMP

従来のTMPプログラミングでは、structを定義し、typename Func<T>::typeなどと書くことで関数適用のようなものを実装していました。
ltmpcでは、より読みやすい形式として、関数を使う形式を主に採用しています。関数を使う形式のメリット・デメリットは次のようになります。
適材適所で構造体を使う形式とうまく使い分けていくと、TMPがより楽しくなるのではないでしょうか。

メリット

読みやすい

従来の形式では、関数をネストして適用したい場合、typename Func1<typename Func2<T>::type>::typeのように長く、読みづらい書き方をする必要がありました。関数を使う形式では、decltype( func1( func2( T{} ) ) )のように、普通のプログラミングと同様のわかりやすい書き方が可能になります（decltypeは一番外につけるだけでよいです）。

パターンマッチング分解が書きやすい

従来の形式では、パターンマッチング分解を行いたい場合、構造体の部分特殊化に頼らざるを得ませんでした。

template<class>
struct Func;
template<class A, class B, class C>
struct Func<Tuple<A, B, C>> {
    using type = ...;
};

関数を使う形式では、より直接的に以下のように書けます。

template<class A, class B, class C>
auto func( Tuple<A, B, C> )
    -> ...;

デバッグが容易

何かを間違えたとき、構造体を使う形式では「不完全型をインスタンス化しようとした」(gcc)、「未定義のテンプレートをインスタンス化しようとした」(clang)というエラーメッセージが出るだけですが、関数を使う形式の場合は「このオーバーロード関数とマッチしない理由は……」と教えてくれるので少しデバッグが楽です。

SFINAEによってオーバーロード解決の候補から外すことが容易

これは好みの問題な気もしますが、関数を使う形式の方は後から突然SFINAEしたくなった時に楽だと思います。

SFINAEによる暗なバックトラックが容易

template<class T>
auto f( T ) -> T;
template<class T>
auto f( S<T> ) -> decltype( g( T{} ) );

などとしたとき、f( S<int>{} )と書いた場合、基本的には下のオーバーロード関数が呼び出されますが、g( T{} )というオーバーロード関数の呼び出しに失敗した場合は、関数fの呼び出しにさかのぼって上のオーバーロード関数を呼び出してくれるという、SFINAEによる暗なバックトラックを利用することができます。
ただし、この機能があるため、本来バグっているところと違うところでエラーが発生する可能性があることがデバッグを困難にします。
構造体を使う形式の場合、こういったSFINAEを書くにはデフォルトテンプレートパラメータを使う必要があります。ただし、その方がバックトラックを意図していることが明白になる点は構造体を使う形式の方が優れています。

暗黙の型変換が発動する

これは、ソースコードの見た目の問題ではなく、本質的に高機能な部分です。
長くなるので章を分離して後述します。

デメリット

複数の型を返すことができない

明らかに関数は一つの型しか返せません。タプルに入れることで疑似的に複数の型を返すことはできますが、ネストした関数呼び出しのところでは分解が必要になります。
もちろん、複数の関数を定義するのもよいですが、お互いの結果を相互に参照するタイプの場合は記述が複雑になります。
構造体形式なら素直にたくさんの結果を記述することができます。

途中結果を保存することができない

構造体を使う形式の場合は、計算途中の結果をusing TempResult = ...;などとすることで、計算途中の結果をいったん"一時変数"に保存することができました。関数を使う形式ではこのようなことができません。テンプレートのインスタンスはメモ化されるため、複数回呼び出すことは大きなデメリットとはならないとはいえ、見た目もよくないですし、途中結果に名前を付けてコードをわかりやすくすることは重要です。

前方宣言ができない

相互再帰や自己再帰をしたい場合、前方宣言が必要になります。しかし、C++における関数の前方宣言とは、関数の中身（実行コード）が定義されていないものであって、まさに我々が"定義"しようとしている返り値の型は宣言しないといけません。このため、TMPで"前方宣言"をすることは不可能です。
構造体を使う形式の場合は、このことを気にする必要はありません。
また、ADLが行われるような関数にすれば、呼び出す関数の解決が保留されるため、この問題が解決されます。

特殊化が不可能

f<>()やf<true>()みたいな関数はSFINAEなしでは作れません。構造体を使う形式なら簡単に作れます。

未既定の挙動を踏むことがある

関数のオーバーロード解決をするとき、その解決に不必要なテンプレートの実体化は、してもしなくてもよい（未既定）(17.7.1)と書かれています。これではポータブルなコードを書くことは難しいです（ltmpcでは、これに気付くのが遅かったため多くの部分にこの問題が埋め込まれてしまっています。今後修正したいですね）。
そうでなくとも、関数を使う形式のTMPは世の中に広まっていないので、コンパイラのバグを踏み抜くことも発生するかもしれません。

暗黙変換を使いこなす

さて、ここまではいかにオーダー的にメモリ消費量を抑えたアルゴリズムを使ったライブラリを作るか、というはなしをしてきました。
ここからは、ユーザーコードのはなしになります。ユーザーコードで使うテクニックは、メモリ消費量よりも書きやすさに重きを置いているため、定数倍ではありますがメモリを無駄に消費します（派生を使っているため、本来必要ない基底クラスのテンプレートが無駄にインスタンス化されます）。

共通コードを暗黙変換の利用によりまとめる

ちょっと意図的ですが、以下のような演算を定義することを考えます。

+	A	B	C
A	A	B	C
B	B	B	C
C	C	C	C

この時、ふつうにコードを書くとoperator+の定義は9つ書く必要があります。
テンプレートを使えば、template<class T>auto oprator+( C, T ) -> Cなどと書いて共通化できますが、AやBに関しては、Cのテンプレートの優先順位をつけるのが難しい（SFINAEに頼るしかない）ので、結局冗長に書かざるを得ません。
ここで、以下のようにA, B, Cを派生を使って定義してみましょう。

struct C {};
struct B : C {};
struct A : B {};

A operator+( A, A );
B operator+( B, B );
C operator+( C, C );

たったこれだけで先ほどの演算を定義できました。今回のは例がうますぎるのですが、コンパイラを作るときなどでは、うまく構造を見抜くとこのような大幅な省力化ができることがあります。

情報を失わずに暗黙変換する

先程の例では、暗黙変換されてしまうと、確定したオーバーロードoprator+関数内で、もともと何が渡されたのかの情報を知ることはできません。
しかし、CRTP(Curiously Recursive Template Pattern)を使うと、全く情報を失わずに暗黙変換をすることができます。これは、実行時には不可能な芸当です。型上でやっているので、情報が失われるはずのアップキャストでも情報を保持することができるのです。

template<class T> struct CRTP_C {};
template<class T> struct CRTP_B : CRTP_C<T> {};
template<class T> struct CRTP_A : CRTP_B<T> {};

struct C : CRTP_C<C> {};
struct B : CRTP_B<B> {};
struct A : CRTP_A<A> {};

// T, Uにもともと呼び出したときの型が入る
template<class T, class U>
auto operator+( CRTP_A<T>, CRTP_A<U> ) -> A;
template<class T, class U>
auto operator+( CRTP_B<T>, CRTP_B<U> ) -> B;
template<class T, class U>
auto operator+( CRTP_C<T>, CRTP_C<U> ) -> C;

暗黙変換を使っていらない情報を捨てる

暗黙変換で情報が失われることを逆手にとって、いらない情報を捨てることだってできます。

完全に文脈自由文法のパースにしか適用できそうにないテクニックですが、一応。
以下のような典型的な文法を考えます。

S -> E
E -> E+T | T
T -> T*F | F
F -> (E) | Int 

これに0+0という入力が来たとき、以下の構文木が作られます。

  S
  |
  E 
 / \
E + T
|   |
T   F
|   |
F   Int
|
Int

この構文木の構築をテンプレートを使って書くと、以下のようになります。

template<char>
struct Op {};

template<class... Ts>
struct Expr {};

template<class... Ts>
struct Term : Expr<Term<Ts...>> {};

template<class... Ts>
struct Fuctor : Term<Fuctor<Ts...>> {};

template<int N>
struct Int : Fuctor<Int<N>> {};

template<class... Ts, class... Us>
auto make_plus( Expr<Ts...>, Term<Us...> )
    -> Expr<Expr<Ts...>, Op<'+'>, Term<Us...>>;

decltype( make_plus( Int<0>{}, Int<0>{} ) );
// => Expr<Expr<Term<Fuctor<Int<0>>>>,Op<'+'>,Term<Fuctor<Int<0>>>>

ところで、さきほどの構文木で一本道の部分は文脈自由文法的には意味があっても抽象構文木としては役に立たない部分です。この部分を捨てれば、スリムで取り回しやすいテンプレートが手に入りそうです。というわけで少し工夫して情報を捨てるバージョンが以下になります。

template<char>struct Op {};

template<class>
struct AST_Base {};

template<class... Ts>
struct Expr : AST_Base<Expr<Ts...>> {};
template<class T>
struct Expr<T> : AST_Base<T> {};

template<class... Ts>
struct Term : Expr<Term<Ts...>> {};
template<class T>
struct Term<T> : Expr<T> {};

template<class... Ts>
struct Fuctor : Term<Fuctor<Ts...>> {};
template<class T>
struct Fuctor<T> : Term<T> {};

template<int N>
struct Int : Fuctor<Int<N>> {};

template<class T, class U>
auto make_plus( AST_Base<T>, Expr<U> )
    -> Expr<T, Op<'+'>, U>;

decltype( make_plus( Int<0>{}, Int<0>{} ) );
// => Expr<Int<0>,Op<'+'>,Int<0>>

Term<T>のようにテンプレート引数が一つの場合、単に一本道な構文木の"道"でしかないので、Expr<Term<T>>と自分の情報を入れるのではなく、単にExpr<T>とすることで不要な情報が出力に残ることを防いでいます。make_plus関数では、Expr<Ts...>とExpr<T>の二種類×Term<Ts...>とTerm<T>の二種類、で合計四種類のオーバーロードを作るのが論理的に正しいですが、一段階優先順位が低いもの(TermはExpr、Exprは勝手に作ったAST_Base)のテンプレート引数が一つの形式で受け取るとその四種類すべてを一つの関数にまとめることができます。

CRTPにより擬似的な型クラスを実現する

ある型が条件Constraintを満たしている場合はこっちのオーバーロード関数、そうでないときはこっちのオーバーロード関数に振り分けたい、という状況は頻出です。通常そういう場合にはSFINAEで対応するのですが、CRTPと暗黙変換を使って振り分けることも可能です。
……と聞いて下のようなコードを書いてしまうのは多くの場合間違いです。

template<class>
struct Constraint {};

struct A {};
struct B : Constraint<B> {};

template<class T>
auto f( T ) -> char;
template<class T>
auto f( Constraint<T> ) -> int;


f( A{} ); // 上のオーバーロード関数が呼ばれる
f( B{} ); // 下のオーバーロード関数が呼ばれる……？

genericなTで受ける方が、暗黙変換を一回行うのよりも優先順位が高いため、上のようなコードではfに何を渡してもgenericなTで受ける方のオーバーロード解決になってしまいます。正しくは、以下のように書きます。

template<class>
struct Any {};
template<class T>
struct Constraint : Any<T> {};

struct A : Any<A> {};
struct B : Constraint<B> {};


template<class T>
auto f( Any<T> ) -> char;
template<class T>
auto f( Constraint<T> ) -> int;

f( A{} ); // 上のオーバーロード関数が呼ばれる！
f( B{} ); // 下のオーバーロード関数が呼ばれる！


template<class T>
auto g( Any<T> ) -> char;
template<class T>
auto g( AnotherConstraint<T> ) -> int;

g( A{} ); // どちらでも、上のオーバーロード関数が呼ばれる
g( B{} ); // こういうことをするためにConstraint<T>はAny<T>から派生させておくべき

このように、genericなTで受け取るのではなく、Any<T>で受け取ることでオーバーロードの優先順位を最低にすることができます。
また、Constraint<T>をAny<T>から派生させることは、記述量を減らすだけでなく、以下のようなパターンであいまい性をなくすために必要です。

template<class>
struct Any {};
template<class T>
struct Constraint : Any<T> {};
template<class T>
struct AnotherConstraint : Any<T> {};

struct A : Constraint<A> {};
struct B : AnotherConstraint<B> {};

// NG: f( A{}, B{} )があいまい
template<class T, class U>
auto f( T, AnotherConstraint<U> ) -> char;
template<class T, class U>
auto f( Constraint<T>, U ) -> int;

// OK: g( A{}, B{} )は上のオーバーロードを呼び出す
template<class T, class U>
auto g( T, AnotherConstraint<U> ) -> char;
template<class T, class U>
auto g( Constraint<T>, Any<U> ) -> int;

// OK: h( A{}, B{} )は下のオーバーロードを呼び出す
template<class T, class U>
auto h( Any<T>, AnotherConstraint<U> ) -> char;
template<class T, class U>
auto h( Constraint<T>, U ) -> int;

このように、genericなTで受けるとき、CRTPによる型クラスで受けるとき、Any<T>で受けるとき、の順番でオーバーロードの優先順位が低くなっていくため、型クラスが全順序になっている場合、ほとんどの望むオーバーロード優先順位をSFINAEに頼ることなく自然に記述することができます。

CRTPによる擬似的な型クラスの限界

template<class T>
struct Constraint {};

struct Base : Constraint<Base> {};
struct Derived : Base, Constraint<Derived> {};

template<class T>
auto f( Constraint<T> ) -> A;

f( Derived{} ); // [T = Derived]でfを呼び出す……？

派生クラスを作る場合、以上のコードはとても素直に見えます。しかし、この方法はうまくいきません。fのオーバーロード解決をする場合、以下の二パターンがあり、あいまいになってしまうからです。

• DerivedをBaseに暗黙変換した後、さらにConstraintに暗黙変換する。すると、[T = Base]でマッチする。
• DerivedをConstraintに暗黙変換する。すると、[T = Derived]でマッチする。

暗黙変換が少ない下のパターンでマッチしてほしいと考えてしまうわけですが、厳格なコンパイラは「両者は完全に別のパスの継承ルートになっているため、お互いの暗黙変換の優先順位は比較不可能。だからあいまい。」という結論を出すわけです。

このようなことが行いたい場合は、SFINAEをつかったtraits的な方法で何とかします。

テンプレートテンプレートパラメータを使って抽象化する

通常のC++プログラミングにおいては、テンプレートという機能は多相性を実現するために使われます。これは、抽象化によるコードを削減を行っていることに相当します。
では、テンプレートという機能をデータ構造を表すために使っているTMPではどのように多相性を実現し、抽象化すればよいでしょうか。ということで重要になってくるのがテンプレートテンプレートパラメータです。

template<class, class>
struct Plus {};
template<class, class>
struct Mult {};

template<template<class, class>class BinaryOp, class T, class U>
auto type_check( BinaryOp<T, U> )
    -> BinaryOp<decltype( type_check( T{} ) ), decltype( type_check( U{} ) )>;

上の例は適当すぎですが、Plus<T, U>に対するtype_check関数、Mult<T, U>に関するtype_check関数、……のように一つ一つ書かなくても、テンプレートテンプレートパラメータを使って抽象化すると一つにまとめられるということは伝わったかと思います。

おわりに

以上、ltmpcで使われている、他のTMPプログラミングにも役に立ちそうな技術を一通りまとめました。
TMPでつまづいた時には、ltmpcの開発中に出会ったTMP注意点10選も役に立つかもしれません。
階乗を計算するようなTMPでは物足りなく、もっと複雑なプログラムを書きたいなどのお役にたてれば幸いです。

それではよいテンプレートメタプログラミングライフを。