メタプログラミングで遊ぶ

目次

• 総称プログラミングとメタプログラミング
• 予備知識
  • 整数定数メンバ
  • constexpr関数
  • メタ関数
  • 再帰実体化ループ
  • 条件判断メタ関数とループ
• コンパイル時出力
  • 意図的なコンパイルエラー
  • Code::Blocks上の出力
• 素数列の生成
  • void*変数への変換
  • 部分特殊化
  • std::enable_if
  • if constexpr
  • boost::mplライブラリ
  • C++標準ライブラリ
• プリプロセッサによるメタプログラミング

C++テンプレートによるメタプログラミングで遊んでみる。

メタプログラミングはプログラミング技法の一種で、一般に「プログラムを記述するプログラム」を書くことを指す。本サイトはこれを用語に加える事を躊躇する。

• Metaprogramming
• メタプログラミング

本サイトは以下の項目で意識的にメタプログラミングした。

• テキストエディタのファイル入出力クラスの追加(1)で扱う文字コードを型リストで定義し、その選択メニュー項目の生成を自動化した。
• pimplイディオムで異なる実装手段を型リストに保持し、テストコードの実行を一括した。
• テンプレートを考察するのソースコード(明示的実体化メタプログラミング)でテンプレート明示的実体化を型リストで自動化した。

サイト作成者レベルが積極的にメタプログラミングする機会は少ないが、テンプレートの利用自体をメタプログラミングとする見方もできる。本記事は実用性を無視してコンパイル時に素数列を生成するメタプログラミングで遊ぶ。

総称プログラミングとメタプログラミング

テンプレートはSTLに代表される総称プログラミングを実現する構文として発明された(Bjarne Straustrup, Parameterized Types for C++, Computing Systems, Vol.2 No.1, Winter 1989, p.56)。

• Parameterized Types for C++

テンプレートがメタプログラミングを実現する事はその後に発見されたとされている(David Vandevoorde et al., C++ Templates, Boston, Addison-Wesley, 2003, p.301,p.318)。その原論文(Erwin Unruh, Prime number computation, ANSI X3J16-94-0075/ISO WG-462, 1994)はJTC1/SC22/WG21サイトに見つからないが、デモンストレーション(Unruhデモ)のオリジナルコードは執筆者ウェブサイト(ドイツ語)で確認できる。Unruhデモはコンパイル時に素数列を生成した。

• Primzahlen

テンプレートは総称プログラミングとメタプログラミングを実現する。前者はプログラミングパラダイムの一つであり、後者はプログラミングの自動コーディング機構であり、それぞれ異なるカテゴリに属する。C++で両者の関係は曖昧で、総称プログラミングがメタプログラミングを利用すると解釈するのが最も妥当であり、この解釈を拡大すればテンプレート利用は全てメタプログラミングと言える。std::unique<int>をメタプログラミングと呼ぶのは大袈裟だが、少なくともあなたの代わりにintポインタのdeleteをコーディングしてくれる。

• Generic programming vs. Metaprogramming

予備知識

テンプレートによるメタプログラミングはコンパイル時のクラス/関数テンプレートの暗黙的実体化を利用して"実行"するが、これを通常のコンパイルされたプログラムの"実行"と明確に区別する必要がある。引き続き"実行"は通常のプログラム実行のみを参照するものとして、メタプログラミングのそれは"コンパイル"、"コンパイル実体化"、"テンプレート暗黙的特殊化"など文脈に適当な方法で表現する。C++11以降、規格はメタプログラミングを想定してテンプレート構文改良とライブラリ追加を行ってきた。これらはC++23も継続し、メタプログラミングの最適コーディングはC++バージョンに依存して今なお安定しない。

規格定義以外の用語は教科書(David Abrahams et al., C++ Template Metaprogramming, Boston, Addison-Wesly, 2005, pp.57-59)に準拠する。boostメタプログラミング(boost::mpl)ライブラリはチュートリアルに教科書の第3章を抜粋して用語定義を確認できる。

整数定数メンバ

メタプログラミングで利用するクラステンプレートは整数定数メンバをコンパイル時に"評価"する。整数定数は整数型のテンプレート実引数とする事ができる。

最初の規格書であるARM(Margaret A. Ellis et al., The Annotated C++ Reference Manual, Reading, Addison-Wesley, 1990; Reading, Addison-Wesley, 1997)で整数定数メンバは(スコープなし)メンバ列挙型のみであったが(ARM, p.181)、C++98はstatic constメンバの利用を可能とし、C++11はstatic constexprメンバを導入した(JTC1/SC22/WG21 N3242 9.4.2/p3、N4659 12.2.3.2/p3)。static constメンバは整数定数式(N4659 8.20)で初期化する場合でのみ整数定数となる。static constexprメンバは整数定数式でのみ初期化できる。つまり両者は整数定数メンバである限り等価と見なせる。

C++11/C++14ではクラススコープ宣言でstatic const/constexprの整数定数メンバを初期化できる/しなければならないが、それらは定義ではない。そのid式(id-expression)(8.1.4.1/p1)は左辺値式で、プログラム実行がそのアドレスを必要(odr-used)(6.2/p3)とすれば、ODRに従いプログラムを通してただ一つの定義をクラススコープ外に持たなければならない。逆に言えば、static const/constexprメンバ変数をコンパイル時整数定数としてのみ使用するなら定義は必要ない。なおスコープなし列挙型はクラススコープで定義されid式は純右辺値式なので、この議論と全く関係しない。

• constexpr vs. static const: Which one to prefer?

C++17ではstatic constにinline修飾子を追加できるようにして(12.2.3.2/p3、D1)、static constexprは暗黙にinlineとした。クラススコープ定義のinlineメンバ関数がそうであるように、static inline const/constexprによる整数定数メンバはクラススコープで定義かつ初期化して、クラススコープ外の定義はodr-usedでも不可/不要となった。なおinlineを持たないstatic constはC++11/C++14から変わらない。

• What's the difference between static constexpr and static inline variables in C++17?

サンプルコードはC++17以降でコンパイルできる。

#include <iostream>
 
int identity(int i) {return i;}
constexpr constexpr_identity(int i) {return i;}
 
struct integer_constants
{
    enum {a=constexpr_identity(0)};                     // Can't call non-constexpr function
    static const int b1=constexpr_identity(1);          // Ditto
    static const int b2=constexpr_identity(2);          // Ditto
    static const int b3;
    static inline const int b4=constexpr_identity(4);   // Ditto
    static constexpr int c=constexpr_identity(5);       // Ditto
};
const int integer_constants::b2;                // Makes b2 have an address
const int integer_constants::b3=identity(3);    // Can call non-constexpr function here,
                                                // that makes b3 not a constant expression
void func(const int& i) {}
template<int i> void func_template() {}
 
int main()
{
    func(integer_constants::a);                 // A prvalue converted to const int&
    //func(integer_constants::b1);              // A lvalue without an address, link error
    func(integer_constants::b2);
    func(integer_constants::b3);
    func(integer_constants::b4);
    func(integer_constants::c);
 
    func_template<integer_constants::a>();
    func_template<integer_constants::b1>();
    func_template<integer_constants::b2>();
    //func_template<integer_constants::b3>();   // Not a constant expression, compile error
    func_template<integer_constants::b4>();
    func_template<integer_constants::c>();
 
    return 0;
}

整数定数式は制約される。整数定数、組み込み演算子、整数定数式の制約に従うconstexpr関数から構成されると単純に理解して問題なかったが、この機会に規格を眺めればサイト作成者の理解能力を優に超える事を知る。コンパイル時の整数定数を、その存在を想定しない構文の全てに矛盾せず規格化するのは想像以上に難解で、今なお途上にあるようだ。

• Constant expressions

constexpr関数

コンパイル時の整数定数式が利用する関数は必ずconstexpr関数(N4659 10.1.5/p2)だが、constexpr関数の全てが整数定数式で利用できるわけではない。

constexpr関数はC++11ではreturn単一文に制約された(N3242 7.1.5/p3)。C++14以降に複合文に緩和されたが、その度合いはバージョンに依存する(N3797 7.1.5/p3、N4659 10.1.5/p3、N4849 9.2.5/p3、N4950 9.2.6/p3)。なお非リテラル型(N4659 6.9/p10)とは整数定数式に利用できない型で、例えば自明でないデストラクタ(non-trivial destructor)を持つクラスである。

		C++14	C++17	C++20	C++23
非リテラル型戻り値		不可	不可	不可	可
非リテラル型仮引数		不可	不可	不可	可
本体内	asm文	不可	不可	可	可
	goto文	不可	不可	不可	可
	gotoラベル	不可	不可	不可	可
	tryブロック	不可	不可	可	可
	非リテラル型変数	不可	不可	不可	可
	static変数	不可	不可	不可	可
	非初期化変数	不可	不可	可	可

整数定数式の制約に従うconstexpr関数だけが整数定数式に利用できる。C++20以前は(診断不要ながら)制約に従う実引数が存在しなければならないが(N4659 10.1.5/p5)、C++23はその必要は無い(N4950 9.2.6/p4)。つまりC++20以前は実引数に依存して整数定数式に利用できないconstexpr関数を許容し、C++23は全く利用できないconstexpr関数を許容する。mingw-w64は以下のtry_in_bodyとno_initialized_in_bodyをC++20/C++23の整数定数式で利用してもエラーとしないが、それが正しいかどうかを判断するには約300行に達する規格(N4950 7.7)を理解しなければならない。

struct non_literal_type {~non_literal_type() {};};
constexpr non_literal_type non_literal_type_interface(non_literal_type x) {return x;}   // C++23
constexpr void asm_in_body() {asm("");}                                                 // C++20
constexpr void goto_in_body() {goto Label;Label:;}                                      // C++23
constexpr void try_in_body() {try {} catch (...) {}}                                    // C++20
constexpr void non_literal_type_in_body() {non_literal_type x;}                         // C++23
constexpr void static_in_body() {static int i=0;}                                       // C++23
constexpr void no_initialized_in_body() {int i;}                                        // C++20

下記サンプルはC++14以降でコンパイルできる。func(true)は制約に従うがfunc(false)は従わず、つまりfunc(true)だけが整数定数式に利用できる。

constexpr int constexp_func() {return 0;}
int non_constexpr_func() {return 0;}
constexpr int func(bool flag)
{
    if (flag) {return constexp_func();}
    else {return non_constexpr_func();}
}
 
template<int i> void test() {}
 
int main()
{
    test<func(true)>();     // OK
//  test<func(false)>();    // Error
    return 0;
}

メタ関数

メタ関数(metafunction)はコンパイル時に型、あるいは整数定数を返すクラステンプレートとする。呼び出し側はテンプレート実引数を与えてtypeメンバあるいはvalueメンバで戻り値を得る。型特性ライブラリはC++標準<type_traits>(N4659 23.15)あるいはboost(Boost.TypeTraits)共に型判定や型改変を目的とするメタ関数を供給する。boost::mplライブラリはメタ関数を操作する高次のメタ関数を供給する。メタ関数に限らずメタプログラミングで利用するクラステンプレート特殊化は、そのインスタンス構築を想定しない場合が多い。メタ関数によるメタプログラミングは関数プログラミングに属する。

• Metafunction
• Tutorial: Metafunctions and Higher-Order Metaprogramming
• is c++ Template Metaprogramming a form of functional programming

template<...> struct MetaFunctionReturningType
{
    using type=...;                 // テンプレート仮引数から型を"評価"して返す、C++11以降
    //typedef ... type;             // 全てのC++バージョン
}
template<...> struct MetaFunctionReturningInt
{
    static constexpr int value=...; // テンプレート仮引数から整数定数を"評価"して返す、C++11以降
    //enum {value=...};             // 全てのC++バージョン
}

メタ関数が他のメタ関数を"コール"するにはtype/valueメンバ定義で"コール"する方法の他に、そのメタ関数を継承する方法がある(metafunction forwarding)。最上位のtypename ... ::type/valueが不要となって見た目が良い。

template<typename T> struct add_const_and_pointer
    {using type=typename std::add_pointer<typename std::add_const<T>::type>::type;};
template<typename T> struct add_pointer_and_const
    :std::add_const<typename std::add_pointer<T>::type> {};

再帰実体化ループ

"ループ"はクラス/関数テンプレートの再帰実体化で行い、必ず明示的特殊化で終端する。

#include <iostream>
 
// クラステンプレートによる再帰評価/再帰実体化
template<int i> struct recursive_class {static constexpr int value=recursive_class<i-1>::value+i;};
template<> struct recursive_class<1> {static constexpr int value=1;};   // 終端
 
// 関数テンプレートによる再帰評価/再帰実体化
template<int i> int recursive_func() {return recursive_func<i-1>()+i;}
template<> int recursive_func<1>() {return 1;}                          // 終端
 
int main()
{
    std::cout<<recursive_class<10>::value<<std::endl;
    std::cout<<recursive_func<10>()<<std::endl;
    return 0;
}

実体化の終端がコンパイル時の"評価"として不要の場合があるが、それでも再帰実体化の終端として省略できない。以下に極端な例を示すが、このように"評価"と実体化で終端が異なるコーディングは避けるべきだろう。

// 再帰評価しないが再帰実体化する関数テンプレート
template<int i> int never_recursive_func() {return i;never_recursive_func<i-1>();}
template<> int never_recursive_func<1>() {return 1;}                    // 終端

関数テンプレートには明示的特殊化以外にも以下の方法がある。関数テンプレートは部分特殊化できないため、再帰実体化ループがint i以外のテンプレート仮引数を持つ場合はこれらの方法によるか、クラステンプレート化する。

std::enable_ifはいわゆるSFINAE(Substitution Failure Is Not An Error、置き換え失敗はエラーではない)(N4659 17.8.2/p8、17.8.3/p1)で、requiresはC++20が導入したテンプレートの制約(N4849 9.3/p4、13.1/p9、13.5.2、12.4.2)である。詳細に立ち入らないがどちらもi==1あるいはi!=1でオーバーロード関数テンプレートを選択し、選択されなかった側は実体化しない。if constexprは条件式に整数定数式のみを許すif文で、条件成立しない分岐は実体化しない(N4659 9.4.1/p2)。つまりいずれの方法も無限の再帰実体化をもたらす側を実体化しない。

// std::enable_if (C++11)
template<int i> typename std::enable_if<i==1,int>::type recursive_func_enableif() {return 1;}
template<int i> typename std::enable_if<i!=1,int>::type recursive_func_enableif() {return recursive_func_enableif<i-1>()+i;}
 
// if constexpr (C++17)
template<int i> int recursive_func_ifconstexpr()
{
    if constexpr (i==1) {return 1;}
    else {return recursive_func_ifconstexpr<i-1>()+i;}
}
 
// requires (C++20)
template<int i> requires (i==1) int recursive_func_requires() {return 1;}
template<int i> requires (i!=1) int recursive_func_requires() {return recursive_func_requires<i-1>()+i;}

条件判断メタ関数とループ

ライブラリはstd::conditionalやboost::mpl::ifといった条件判断メタ関数を用意する。条件判断は高次メタ関数(higher-order metafunction)として低次メタ関数を選択できる。これと再帰実体化ループを組み合わせてループ終了条件を定義できるが、それでもやはり終端を必要とする場合がある。

以下サンプルのconditionally_recursiveメタ関数は1以上の整数iをテンプレート仮引数に受けて、1からiの総和を保持するint_クラステンプレート特殊化をtypeメンバに返す。i==1の終端が無ければconditionally_recursive<0>::typeを実体化して無限の再帰実体化をもたらす。高次/低次のメタ関数が混在するとネストする::typeが可読性を損なうため、本サンプルは条件判断を自らコーディングして戻りを::type_mfとした。ライブラリ利用ではその様な事は望めず常に苦労の種となる。

#include <iostream>
 
template<int i> struct int_ {static constexpr int value=i;};            // 整数値を保持するクラステンプレート
template<typename T> struct identity_ {using type=T;};                  // Tに受けるint_をそのまま返す低次メタ関数
template<typename T,int i> struct inc_ {using type=int_<T::value+i>;};  // Tに受けるint_をi増加して返す低次メタ関数
 
// 高次メタ関数となる条件判断メタ関数で、int_を返す低次メタ関数の特殊化を選択する
// 低次メタ関数::typeとの混同を避けるため::type_mfで返す
template<bool,typename,typename> struct if_;
template<typename T,typename F> struct if_<true,T,F> {using type_mf=T;};
template<typename T,typename F> struct if_<false,T,F> {using type_mf=F;};
 
// 条件判断を伴う再帰評価/再帰実体化、if_内のidentity_<int_<1>>は冗長、終端が無ければ(a)の再帰実体化は<1>::typeで止まらない
// (a) <i> → <i-1> → <i-1>::type → <i-2> → <i-2>::type → ... → <1> → <1>::type (→ <0> → <0>::type ...)
// (b) <i>::type
template<int i> struct conditionally_recursive
    :if_<i==1,identity_<int_<1>>,inc_<typename conditionally_recursive<i-1>::type,i>>::type_mf
    {};
template<> struct conditionally_recursive<1>:identity_<int_<1>> {}; // 終端
// 結局、条件判断は不要で以下で良い
//template<int i> struct conditionally_recursive:inc_<typename conditionally_recursive<i-1>::type,i> {};
//template<> struct conditionally_recursive<1>:identity_<int_<1>> {};
 
int main()
{
    std::cout<<conditionally_recursive<10>::type::value<<std::endl;
    return 0;
}

実体化は(a)conditionally_recursive<10>と(b)conditionally_recursive<10>::typeの2ステップとなる。問題は(a)で<i>が<i-1>::typeを実体化してしまうからで、これを(b)の<i>type側で遅延評価(lazy evaluation)すれば終端は不要になる。conditionally_recursive_with_lazy_evalメタ関数は::typeを省いてinc__メタ関数を"コール"し、inc__はT::typeでinc_メタ関数を"コール"する。終端は無くとも<1>で<0>::typeは実体化しない。

...
 
template<typename T,int i> struct inc__:inc_<typename T::type,i> {};  // inc_を遅延評価するメタ関数
// 条件判断を伴う再帰評価/再帰実体化、遅延評価、終端不要
// (a) <i> → <i-1> → <i-2> → ... → <1>
// (b) <i>::type → <i-1>::type → <i-2>::type → ... → <1>::type
template<int i> struct conditionally_recursive_with_lazy_eval
    :if_<i==1,identity_<int_<1>>,inc__<conditionally_recursive_with_lazy_eval<i-1>,i>>::type_mf
    {};
 
int main()
{
    std::cout<<conditionally_recursive_with_lazy_eval<10>::type::value<<std::endl;
    return 0;
}

コンパイル時出力

コンパイル時にテンプレート実体化の結果を逐次出力する手段は用意されていない。Unruhデモはこれを意図的なコンパイルエラーの発生で行い、本記事サンプルコードもライブラリ利用を除いて従う。ライブラリ利用なら逐次結果を"配列"化する手段があるのでコンパイル時生成の"配列"を実行時に出力できる。

意図的なコンパイルエラー

Unruhデモとサンプルコードのコンパイル時出力を説明する。素数判定して出力するクラステンプレートはテンプレート仮引数pに整数値を受け、pが素数の場合にint値をvoid*型へ変換してエラーを発生させる。mingw-w64は実体化したテンプレート実引数、すなわちpの値と共にエラーメッセージを出力する。最初のエラーでコンパイルがストップしないようフラグ-fpermissiveは必須で、必要に応じて-Wno-unused-variable、-Wno-unused-but-set-variable、-fdiagnostics-plain-output、-ftemplate-backtrace-limit=1などで余計なメッセージを抑止する。50までの素数列を降順出力した場合を例示するが、"In instantiation ... [with int p = ... ]':"が素数の出力行となっている。

main_CPP98_PointerConversion.cpp: In instantiation of 'void prime_print() [with int p = 47]':
main_CPP98_PointerConversion.cpp:12:21:   recursively required from 'void prime_print() [with int p = 49]'
main_CPP98_PointerConversion.cpp:12:21:   required from 'void prime_print() [with int p = 50]'
main_CPP98_PointerConversion.cpp:18:20:   required from here
main_CPP98_PointerConversion.cpp:11:13: warning: invalid conversion from 'int' to 'void*' [-fpermissive]
main_CPP98_PointerConversion.cpp: In instantiation of 'void prime_print() [with int p = 43]':
    ...
main_CPP98_PointerConversion.cpp: In instantiation of 'void prime_print() [with int p = 41]':
    ...

出力は不要な情報を多く含むのでコマンドプロンプトならMSYS2ツールsedで整形できる。バッチファイルを例示する。

@setlocal
@set PATH=C:\msys64\mingw32\bin;C:\msys64\usr\bin;%PATH%
@rem -stdに使用するC++バージョンを設定する
@g++ -std=c++98 -fpermissive -fsyntax-only -c main_CPP98_PointerConversion.cpp 2>&1 ^
| sed -E -n s/".* In instantiation .* \[with int p = ([0-9]*).*"/"\1"/p

Code::Blocks上の出力

サンプルコードをCode::Blocksプロジェクト化して[Build|Build and run]を行えば[Logs & others]ウィンドウ[Build log]ページあるいは[Build messages]ページで同様の出力をログとして確認できる。ただしログ出力行数は[Settings|Compiler]メニュー項目で開く[Compiler settings]ダイアログの[Global compiler settings]ページ[Build options|Max nr. of errors to log (0=unlimited)]で制限されている。ログ出力のエラー判定を出力文字列のパターン判定で行っているようで"recursively required from ..."を含む行をエラー出力行と誤判定して文字色赤で出力し、ビルド成功でもエラー発生と誤認して続くプログラム実行をキャンセルする。そのままソースコード変更なしで再度[Build|Build and run]すればビルドをスキップしてプログラムを正常実行する。なおライブラリ利用を除くサンプルコードはプログラム実行に意味は無く、コンパイル確認は[Build|build]、[Build|rebuild]、[Build|Compile current file]のいずれかでも良い。

覚え書き

Code::Blocksのログ出力の種別判定パターンはC:\Program Files\CodeBlocks\share\CodeBlocks\options_common_re.xmlの定義に従うと思われる。ソースコードからの確認はしていない。

素数列の生成

Unruhデモは2以上の整数pについて、整数iをi=p-1からi=2まで1ずつ減じて最後までp%i!=0を維持する場合に素数と判定する。これをコンパイル時メタプログラミングでなく実行時プログラミングすれば以下となる。is_prime関数が2以上のpを与えて素数判定し、prime_print関数が1以上のpを与えてp以下の素数列を降順で出力する。メタプログラミングはこれらをメタ関数、クラステンプレート、constexpr関数など様々な方法で実装するが、特にprime_printの素数判定による処理切り替えが問題となる。

main_CPP98_NoMetaprogramming.cpp

#include <iostream>
 
bool is_prime(int p,int i) {return i==1||((p%i)&&is_prime(p,i-1));}
bool is_prime(int p) {return is_prime(p,p-1);}
 
void prime_print(int p)
{
    for (;p!=1;--p) {if (is_prime(p)) {std::cout<<p<<std::endl;}}
}
 
int main()
{
    prime_print(50);
    return 0;
}

void*変数への変換

is_primeはメタ関数で再帰実装し、終端はi==1だがテンプレート仮引数pが残り部分特殊化となる。prime_printは関数テンプレートで再帰実装して終端はp==1で明示的特殊化する。素数判定による処理切り替えはis_primeの戻り値(value)をintキャストしてvoid*型へ変換し、value!=0の場合にコンパイルエラーが発生して出力する。これが可能なのはC++03以前で、C++11以降はvalue==0もコンパイルエラーとなって処理の切り替えができない。

• C++03以前は式が値を返す場合は右辺値式で、void*変数は0に限り整数型の右辺値式から変換される。
• C++11以降は式が値を返す場合は右辺値式で純右辺値式あるいは期限切れ値式(N4659 6.10)だが、リテラル(5.13.2)ではない。void*変数は0リテラルあるいはstd::nullptr_t型の純右辺値式(通常はnullptrリテラル(5.13.7))からヌル値に変換される(7.11/p1)。

サンプルコードは全てのC++バージョンでコンパイルできるがC++03以前でのみ素数列をコンパイル時出力する。これはUnruhデモも同様であった。

main_CPP98_PointerConversion.cpp

// Works only with -std=c++98/gnu++98, which -std=c++03/gnu++03 is the same as.
 
template <int p,int i=p-1> struct is_prime
{
    enum {value=(p%i)&&is_prime<p,i-1>::value};
};
template<int p> struct is_prime<p,1> {enum {value=1};};
 
template<int p> void prime_print()
{
    void* d=(int)is_prime<p>::value;
    prime_print<p-1>();
}
template<> void prime_print<1>() {}
 
int main()
{
    prime_print<50>();
    return 0;
}

部分特殊化

素数判定による処理切り替えをprime_print_oneクラステンプレート部分特殊化に変更して、全てのC++バージョンで素数列をコンパイル時出力できるようにする。

main_CPP98_PartialSpecialization.cpp

// Works with all C++ versions.
 
template <int p,int i=p-1> struct is_prime
{
    enum {value=(p%i)&&is_prime<p,i-1>::value};
};
template<int p> struct is_prime<p,1> {enum {value=1};};
 
template<int p,bool prime=is_prime<p>::value> struct prime_print_one;
template<int p> struct prime_print_one<p,true> {static void exec() {void* d=p;}};
template<int p> struct prime_print_one<p,false> {static void exec() {}};
 
template<int p> void prime_print()
{
    prime_print_one<p>::exec();
    prime_print<p-1>();
}
template<> void prime_print<1>() {}
 
int main()
{
    prime_print<50>();
    return 0;
}

std::enable_if

is_primeをconstexpr関数で実装して終端を不要とする。素数判定による処理切り替えをprime_print_one関数テンプレートのstd::enable_ifすなわちSFINAEによる。constexprとenable_ifはC++11で追加されて、サンプルコードはC++11以降でコンパイルできて素数列を出力する。

main_CPP11_EnableIf.cpp

// Works with -std=c++11/gnu++11 and later.
 
#include <type_traits>
 
constexpr bool is_prime(int p,int i) {return i==1||((p%i)&&is_prime(p,i-1));}
constexpr bool is_prime(int p) {return is_prime(p,p-1);}
 
template<int p> typename std::enable_if<is_prime(p)>::type prime_print_one() {void* d=p;}
template<int p> typename std::enable_if<!is_prime(p)>::type prime_print_one() {}
 
template<int p> void prime_print()
{
    prime_print_one<p>();
    prime_print<p-1>();
}
template<> void prime_print<1>() {}
 
int main()
{
    prime_print<50>();
    return 0;
}

if constexpr

prime_print関数テンプレートの素数判定による処理切り替えと終端をif constexprで行う。if constexprはC++17で追加されて、サンプルコードはC++17以降でコンパイルできて素数列を出力する。

main_CPP17_IfConstexpr.cpp

// Works with -std=c++17/gnu++17 and later.
 
constexpr bool is_prime(int p,int i) {return i==1||((p%i)&&is_prime(p,i-1));}
constexpr bool is_prime(int p) {return is_prime(p,p-1);}
 
template<int p> void prime_print()
{
    if constexpr (p!=1)
    {
        if constexpr (is_prime(p)) {void* d=p;}
        prime_print<p-1>();
    }
}
 
int main()
{
    prime_print<50>();
    return 0;
}

boost::mplライブラリ

boost::mplライブラリはboostの供給するメタプログラミングライブラリである。STLをモデルとするメタプログラミングをC++03以前に可能としたが、constexprや仮引数パックといった構文の登場でやや時代遅れとなった。とは言えクライアントの意図をソースコードで表現できる能力は今でも魅力的だと思う。

• THE BOOST MPL LIBRARY

is_primeメタ関数はboost::mplライブラリで書き換える。ライブラリは整数定数を表すint_クラステンプレートとint_を"配列"として記憶するlist_cクラステンプレートを用意する。prime_numbersクラステンプレートはtypeメンバをlist_cとしてコンパイル時に逐次生成する素数列を記憶する。prime_print関数テンプレートはライブラリのfor_each関数テンプレートを用いてprime_numbersの記憶する素数列をプログラム実行時に出力する。

prime_numbersは条件判断を伴う再帰で生成し、特に内側の条件判断を遅延評価とするためライブラリのeval_if_c/eval_ifクラステンプレートで条件判断する。テンプレート実引数として供する型はtypeメンバを持たなければならず、メタ関数でない"定数"はライブラリのidentityクラステンプレートで囲まなければならないが、list_cは自らを返すtypeメンバを持ちその必要は無い。それでもidentityで囲んだ方が意図は明確だったかもしれない。push_front_cクラステンプレートはprime_numbersに素数を追加するが、これをprime_numbers定義内に展開するとprime_numbers<p-1>::typeが遅延評価されずp==1で実体化して無限の再帰実体化をもたらす。

サンプルコードは全てのC++バージョンでコンパイルできる。素数列はコンパイルされたプログラムの実行で表示する。

main_CPP98_BoostMpl.cpp

// Works with all C++ versions.
 
#include <iostream>
#include <boost/mpl/logical.hpp>
#include <boost/mpl/equal_to.hpp>
#include <boost/mpl/list_c.hpp>
#include <boost/mpl/push_front.hpp>
#include <boost/mpl/for_each.hpp>
 
template<int p,int i=p-1> struct is_prime
    :boost::mpl::or_
        <boost::mpl::equal_to<boost::mpl::int_<i>,boost::mpl::int_<1> >
        ,boost::mpl::and_<boost::mpl::bool_<p%i>,is_prime<p,i-1> > >
    {};
 
template<typename P,int p> struct push_front_c
    :boost::mpl::push_front<typename P::type,boost::mpl::int_<p> >
    {};
template<int p> struct prime_numbers
    :boost::mpl::eval_if_c<p==1
        ,boost::mpl::list_c<int>
        ,boost::mpl::eval_if<is_prime<p>,push_front_c<prime_numbers<p-1>,p>,prime_numbers<p-1> > >
    {};
 
struct prime_print_one
{
    template<typename T> void operator()(T) {std::cout<<T::value<<std::endl;}
};
template<int p> void prime_print()
{
    boost::mpl::for_each<typename prime_numbers<p>::type>(prime_print_one());
}
 
int main()
{
    prime_print<50>();
    return 0;
}

C++標準ライブラリ

C++標準ライブラリはC++11で<type_traits>を追加してメタプログラミングに備えた(N3242 20.9、N4659 23.15)が、boost::mplのような高次操作は充実せず自分でコーディングする。テンプレート仮引数パック(N4695 17.5.3/p1)はコンパイル時生成した型リストとして扱えて、その展開(p4)を型リストへの実行時アクセスとして使えるが、boost::mplほどの表現力を伴わない。なおサンプルコードはstd::integer_sequenceクラステンプレート(23.3)を用いて素数列をコンパイル時に記憶するが、実態は仮引数パックである事に変わりない。

boost::mplライブラリのサンプルコード(main_CPP98_BoostMpl.cpp)に準じてコーディングする。is_primeメタ関数は<type_traits>で書き換える。整数値のイコール判定をstd::is_sameクラステンプレートで行うためstd::integral_constantクラステンプレート(23.15.3)を用いる。boost::mplのeval_if/eval_if_cは自分でコーディングする。prime_membersクラステンプレートはtypeメンバをinteger_sequence<int>としてコンパイル時に逐次生成する素数列を"配列"として記憶する。素数の追加はpush_front_cクラステンプレートが行い、仮引数パック展開と再構成を用いる。push_front_cはmain_CPP98_BoostMpl.cppと同じくprime_numbers定義内に展開できない。prime_print関数テンプレートは仮引数パック展開でprime_numbersの記憶する素数列をプログラム実行時に出力する。

integer_sequenceはC++14で、integral_constantはC++17で追加された。サンプルコードはC++17以降でコンパイルできる。素数列はコンパイルされたプログラムの実行で表示する。

main_CPP17_StdMpl.cpp

// Works with -std=c++17/gnu++17 and later
 
#include <iostream>
#include <type_traits>
 
template<int p,int i=p-1> struct is_prime
    :std::disjunction
        <std::is_same<std::integral_constant<int,i>,std::integral_constant<int,1>>
        ,std::conjunction<std::bool_constant<p%i>,is_prime<p,i-1>>>
    {};
 
template<bool B,typename T,typename F> struct eval_if_c:std::conditional<B,T,F>::type {};
template<typename B,typename T,typename F> struct eval_if:eval_if_c<B::value,T,F> {};
template<typename P,auto p> struct push_front_c:push_front_c<typename P::type,p> {};
template<typename T,T p,T... pp> struct push_front_c<std::integer_sequence<T,pp...>,p>
{
    using type=std::integer_sequence<T,p,pp...>;
};
template<int p> struct prime_numbers
    :eval_if_c<p==1
        ,std::common_type<std::integer_sequence<int>>
        ,eval_if<is_prime<p>,push_front_c<prime_numbers<p-1>,p>,prime_numbers<p-1>>>
    {};
 
template<typename T> void sequence_print(std::integer_sequence<T>) {}
template<typename T,T... II> void sequence_print(std::integer_sequence<T,II...>)
{
    for (const auto& r:{II...}) {std::cout<<r<<std::endl;}
}
template<int p> void prime_print()
{
    sequence_print(typename prime_numbers<p>::type{});
}
 
int main()
{
    prime_print<50>();
    return 0;
}

プリプロセッサによるメタプログラミング

boostプリプロセッサライブラリはboost::mplの補完が主目的であるが単独でメタプログラミングすることもできる。

• The Boost Library Preprocessor Subset for C/C++

これを用いて素数列を出力してみた。解読困難なコードでプリプロセス速度も驚くほど遅いが、少なくともプリプロセッサでメタプログラミングできる事は証明できる。素数列は#pragma messageでコンパイル(プリプロセス)時に出力する。

main_CPP98_BoostPreprocessor.cpp

// Works with all C++ versions.
 
#include <boost/preprocessor/array/push_back.hpp>
#include <boost/preprocessor/array/to_tuple.hpp>
#include <boost/preprocessor/arithmetic/mod.hpp>
#include <boost/preprocessor/stringize.hpp>
 
// IS_PRIME(p) returns 1 if p is a prime number, 0 otherwise.
// Recursive state of BOOST_PP_WHILE is (flag0,flag1,p,i).
// flag0==1             -> p is a prime number
// flag0==0 && flag1==0 -> p is not a prime number
// flag0==0 && flag1==1 -> requires next recursion
#define IS_PRIME(p) \
    BOOST_PP_TUPLE_ELEM(4,0,BOOST_PP_WHILE(IS_PRIME_PRED,IS_PRIME_OP,(0,1,p,BOOST_PP_DEC(p))))
#define IS_PRIME_PRED(d,state) \
    BOOST_PP_AND \
        (BOOST_PP_NOT(BOOST_PP_TUPLE_ELEM(4,0,state)) \
        ,BOOST_PP_BOOL(BOOST_PP_TUPLE_ELEM(4,1,state)))
#define IS_PRIME_OP(d,state) \
    (BOOST_PP_EQUAL(BOOST_PP_TUPLE_ELEM(4,3,state),1) \
    ,BOOST_PP_MOD(BOOST_PP_TUPLE_ELEM(4,2,state),BOOST_PP_TUPLE_ELEM(4,3,state)) \
    ,BOOST_PP_TUPLE_ELEM(4,2,state) \
    ,BOOST_PP_DEC(BOOST_PP_TUPLE_ELEM(4,3,state)))
 
// PRIME_NUMBERS(p) returns a tuple of prime numbers up to p.
// Recursive state of BOOST_PP_WHILE is (p,array).
// Prime numbers are held by an array which will be converted to a tuple.
#define PRIME_NUMBERS(p) \
    BOOST_PP_ARRAY_TO_TUPLE \
        (BOOST_PP_TUPLE_ELEM(2,1,BOOST_PP_WHILE(PRIME_NUMBERS_PRED,PRIME_NUMBERS_OP,(p,(0)))))
#define PRIME_NUMBERS_PRED(d,state) \
    BOOST_PP_NOT_EQUAL(BOOST_PP_TUPLE_ELEM(2,0,state),1)
#define PRIME_NUMBERS_OP(d,state) \
    (BOOST_PP_DEC(BOOST_PP_TUPLE_ELEM(2,0,state)) \
    ,BOOST_PP_IF(IS_PRIME(BOOST_PP_TUPLE_ELEM(2,0,state)) \
        ,BOOST_PP_ARRAY_PUSH_BACK(BOOST_PP_TUPLE_ELEM(2,1,state),BOOST_PP_TUPLE_ELEM(2,0,state)) \
        ,BOOST_PP_TUPLE_ELEM(2,1,state)))
 
#pragma message BOOST_PP_STRINGIZE(PRIME_NUMBERS(50))
 
int main()
{
    return 0;
}