C++0xによるコンパイル時の配列生成

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 << "," ; }
}