Don't do this at home. I am professional.
絶対にマネをしてはいけません。
コンパイルタイムプログラミング - 主題のない日記
昨晩、これと同じことがC++で出来るかどうか質問を受けた。5という数字が与えられたときに、0,1,2,2,3,3,3,4,4,4,4,5,5,5,5,5という数列をコンパイル時に生成できるかという問題である。
その時は、プリプロセッサー以外に、どうにもうまい実装方法が思いつかなかった。問題は、再帰を止める方法だ。しかし、今朝、改めて問題を考えると、頑張ればなんとかなるのではないかとも思った。
まず、プリプロセッサーによる実装を考えよう。これは、BOOST.Preprocessorを使えば、簡単に実装できる。簡単というのは、C++のプロにとって簡単という意味である。言うまでもなく、プリプロセッサーは邪道であり、中でもBoost.Preprocessorは禁断の秘術である。D&Eの第18章を暗唱できるようになるまで、プリプロセッサーを書いてはならない。今回は、メタプログラミングの可能性を示すために、あえて、この極悪非道の魔術を使うことにする。
#include <boost/preprocessor/enum.hpp>
#include <boost/preprocessor/enum_shifted.hpp>
#include <boost/preprocessor/arithmetic.hpp>
#define HITO_PRINT_PP( z, n, data ) data
#define HITO_DUP_HELPER_PP( z, n, data ) \
BOOST_PP_ENUM_ ## z( n, HITO_PRINT_PP, n )
#define HITO_DUP_PP( COUNT ) \
0, BOOST_PP_ENUM_SHIFTED( BOOST_PP_ADD(COUNT, 1), HITO_DUP_HELPER_PP, ~ )
int main()
{
constexpr int a[] = { HITO_DUP_PP(5) } ;
for( auto value : a )
{ std::cout << value << "," ; }
}
このメタプログラムは、コンマで区切られた目的の数列を生成してくれる。
問題は二つある。まず第一に、これはプリプロセッサーである。第二に、BOOST_PP_LIMIT_REPEATまでしか数列を生成できない。BOOST_PP_LIMIT_REPEATの値は、現在のところ、256である。
では、これを本当のC++0xの言語機能で実装しよう。まず、前提知識として、配列を返す関数を書くことはできない。これは、C++の制限である。そこで、配列をメンバーに持つリテラル型を使うことにする。std::arrayは、ちょうどこの条件をみたしている。
どうやって配列を初期化するのか。それには、Variadic Templatesを用いる。以下のようにpack expansionをしてやればいいのだ。
template < typename ... Types >
std::array< int, sizeof...(Types) > f( Types ... args )
{
return std::array< int, sizeof...(Types) >{ args... } ;
}
つまり、この関数をconstexprにして、再帰で実引数を加えていき、目的の数列を生成した上で、std::arrayを返せばいいのだ。問題は、再帰を止める条件である。C++0xでは、関数も特殊化できるようになった。しかし、部分的特殊化はできない。そのため、クラスを使うしかない。
また、std::arrayのサイズは、最初のインスタンス化の際に決定して置かなければならない。つまり、数列の数の個数を、あらかじめ与えてやらなければならない。幸いにして、この非常に難しい数学上の難問は、300年以上前に、当時小学生のガウス君が、宿題を真面目にやるのがめんどくさかったという理由によって、見事に解決してくれている。
// summation from n=0 to i of n
constexpr std::size_t summation( std::size_t i )
{
return 1 + i * (i + 1) / 2 ;
}
// for compile time selection
template < bool, bool >
struct selector ;
// list construction completed.
template < bool b >
struct selector< true, b >
{
template < std::size_t COUNT , int I, int J, typename ... Types >
constexpr static std::array<int, summation( COUNT )> invoke( Types ... args )
{
return std::array<int, summation( COUNT )>{ args... } ;
}
} ;
// add number I, I times.
template < >
struct selector< false, true >
{
template < std::size_t COUNT , int I, int J, typename ... Types >
constexpr static std::array< int, summation( COUNT ) > invoke( Types ... args )
{
return selector< (COUNT < I), I != J + 1 >:: template invoke< COUNT, I, J + 1 >( args..., I ) ;
}
} ;
// carry over to the next number.
template < >
struct selector< false, false >
{
template < std::size_t COUNT , int I, int J, typename ... Types >
constexpr static std::array< int, summation( COUNT ) > invoke( Types ... args )
{
return selector< (COUNT < I + 1), true >:: template invoke< COUNT, I + 1, 0 >( args... ) ;
}
} ;
// User Interface
template < std::size_t COUNT >
constexpr std::array< int, summation( COUNT ) > dup( void )
{
return selector< (COUNT < 1), true >:: template invoke< COUNT, 1, 0 >( 0 ) ;
}
int main()
{
constexpr auto a = dup<5>() ;
for( auto value : a )
{ std::cout << value << "," ; }
}
selectorクラスを三つに特殊化し、それぞれで別のことをしているのには、理由がある。というのも、単にひとつの関数に条件演算子を使って書いたのでは、インスタンス化を止めることができないからである。つまり、どの処理をするか判定した後まで、インスタンス化を遅らせる必要があるのだ。そのために特殊化が必要になる。
さて、ここで非常に悲しい事実が判明した。このC++0xの機能をあますところなく使った美しいコードは、なんと、最新のgcc 4.6では、dup<18>までしかインスタンス化できないのである。片や、プリプロセッサーはHITO_DUP_PP(256)まで、問題なくコンパイルできるというのに。なんと、プリプロセッサーに負けてしまったのだ。
ちなみに、これは私の経験上、もっとも難しかったテンプレートメタプログラムである。このコードを書くのに二時間半も費やしてしまった。このコードのデバッグは、非常に困難であった。何しろこのコードで、再帰的インスタンス化を止められなければ、gccが一切のエラーメッセージを出さずにクラッシュしてしまうのだから。
追記:MPLを使ったところ、非常に分かりやすくなった。
#include <boost/mpl/if.hpp>
#include <boost/mpl/eval_if.hpp>
// summation from n=0 to i of n
constexpr std::size_t summation( std::size_t i )
{
return 1 + i * (i + 1) / 2 ;
}
// we've done it. return the result.
struct construct_initializer_list
{
typedef construct_initializer_list type ;
template < std::size_t COUNT , int I, int J, typename ... Types >
constexpr static std::array<int, summation( COUNT )> invoke( Types ... args )
{
return std::array<int, summation( COUNT )>{ args... } ;
}
} ;
struct carry_over ; // forward declaration
// add a initilizaer of number I, I times.
struct add_initializer
{
template < std::size_t COUNT , int I, int J, typename ... Types >
constexpr static std::array< int, summation( COUNT ) > invoke( Types ... args )
{
return boost::mpl::eval_if_c< ( COUNT < I ),
/* if true then*/ construct_initializer_list,
/* else */ boost::mpl::if_c< ( I != J + 1),
/* if true then*/ add_initializer,
/* else*/ carry_over > >::type:: template invoke< COUNT, I, J + 1>( args..., I ) ;
}
} ;
// carry over to the next number
struct carry_over
{
template < std::size_t COUNT , int I, int J, typename ... Types >
constexpr static std::array< int, summation( COUNT ) > invoke( Types ... args )
{
return boost::mpl::if_c< ( COUNT < I + 1 ),
/* if true then*/ construct_initializer_list,
/* else */ add_initializer >::type:: template invoke< COUNT, I + 1, 0 >( args... ) ;
}
} ;
// User Interface
template < std::size_t COUNT >
constexpr std::array< int, summation( COUNT ) > dup( void )
{
return boost::mpl::if_c< ( COUNT < 1 ),
/* if true then*/ construct_initializer_list,
/* else */ add_initializer >::type:: template invoke< COUNT, 1, 0 >( 0 ) ;
}
int main()
{
constexpr auto a = dup<5>() ;
for( auto value : a )
{ std::cout << value << "," ; }
}