関数型言語としてのC++ Template MetaProgramming入門

C++ではtemplateを使ってコンパイル時に計算を行うことができる。 今回は、関数型言語としての視点からC++テンプレートメタプログラミング(C++-TMP)の簡単な紹介をやってみたい。

注:私はHaskelllispの経験がホンの少しだけあるが、どちらも使いこなせるようになっているわけではない。のでこの記事には関数型への誤解が含まれる恐れがあることを注意していただきたい。

C++TMPでは型、もしくはコンパイル時定数が値に相当する。つまり、C++TMPにおいて値の型は、型もしくはコンパイル時定数(の型)ということになる。値の型が型とかめっちゃ面白いな

例えば我々は以下のようにして型を値として用いることができる。

struct v1{};
struct v2{};
struct v3{};
...
template<typename T1, typename T2>
struct add;
template<>
struct add<v1, v2> {typedef v3 type;};

空の構造体に名前をつけてやり、それに対する必要な演算を定義してやれば、立派な値だ。数値の計算にこの手法を用いるのは馬鹿げているが、コンパイル時に型を条件に合わせて自動生成する、というような状況ではこのやり方が役に立つ。

または、コンパイル時定数を使う。

constexpr static int five = 5;
template<int x> struct identity
{
    constexpr static int value = x;
};

本来現実世界でC++TMPが有用なのは数値演算でなく、型をいじりまわす場合だ。コンパイル時にメモ化やテーブル作成がしたければconstexprの方が書きやすさ・読みやすさ・ポータビリティ共に良い選択になるだろう。ただ、型を値とする計算も(inttypenameに、演算子template structになるくらいで)基本的に変わらないことと、例示と説明が楽になるという二つの理由から、以下ではコンパイル時定数を値として使って説明をしていく。

ちなみに、コンパイル時定数は、integral_constantを使うことで型へキャストできる(この言い方はもはや冗談めいているが、はっきり言うとこの記事全体が冗談である)。

#include <type_traits>
typedef typename integral_constant<int, 5> five;

関数

C++TMPでは、関数は構造体で、その引数はtemplate引数である。そして本体はその構造体に紐づけられた定数あるいは型定義だ。 例えば、二つの数(コンパイル時定数)を加算する関数は、

template<int x, int y>
struct add{constexpr static int value = x + y;};

となるだろう。宣言が超絶複雑な言語なのだと思えばいい。この関数は、

constexpr static int v = add<1, 2>::value; // 3

のようにして適用する。

関数の評価は、内部の型定義や定数を取り出す操作に対応することになる。これが少し面白い状況を作り出していて、一つの関数が複数の方法で評価され得るのだ。そのためには、単に複数の(互いに異なっていても良い)型定義や定数を持つtemplate構造体を作ればいい。例えば

template<int x, int y>
struct compute
{
    constexpr static int add = x + y;
    constexpr static int sub = x - y;
    constexpr static int mul = x * y;
    constexpr static int div = x / y;
};

constexpr int a = compute<4, 2>::add;
constexpr int s = compute<4, 2>::sub;

別の用途のものを転用しているからこそ出現する面白さだ。ただ、以降ではわかりやすさのために標準ライブラリに従って、型が返り値の場合はtypeを、定数が返り値の場合はvalueを使うことにする。

分岐

if式

以下のようなクラスを作ることで、if式が作れる。ここで必要になる通常のC++の知識は、templateの部分特殊化のみである。

template<bool Cond, typename Then, typename Else>
struct if_;

template<typename Then, typename Else>
struct if_<true, Then, Else>
{
    typedef Then type;
};

template<typename Then, typename Else>
struct if_<false, Then, Else>
{
    typedef Else type;
};

この式はtypedef if_<...>::type tによって評価され、その結果がtに入ることになる。この場合、引数をtypenameとして受けてtypedefで評価されているので、返り値の型は型である。 逆に、返り値の型をコンパイル時定数のintなどにしたいなら、別にif_intなどのようなものを作るか(ここではオーバーロードはないので)、intstd::integral_constantによって型へキャストするとよい。

struct happy{};
struct sad{};
typedef typename if_<is_good::value, happy, sad>::type answer;

第一引数がtrueに評価されれば、answerはhappyになっているだろう。falseなら、sadになる。

switch

同様のことをすれば、switch式も作れる。最も単純には、

template<std::size_t N, typename T1, typename T2, typename T3>
struct switch_;
template<typename T1, typename T2, typename T3>
struct switch_<0, T1, T2, T3> {typedef T1 type;};
template<typename T1, typename T2, typename T3>
struct switch_<1, T1, T2, T3> {typedef T2 type;};
template<typename T1, typename T2, typename T3>
struct switch_<2, T1, T2, T3> {typedef T3 type;};

のようにできるだろう。ただし任意の長さへの対応がこれでは厳しいので、C++98ならBoost.Preprocessorを、C++11ならvariadic templateを使おう。 C++11なら、タプルとそのインターフェースを使って楽をすることができる。

template<std::size_t N, typename ... Ts>
struct switch_
{
    typedef typename std::tuple_element<N, std::tuple<Ts...>>::type type;
};

パターンマッチ

そもそも、部分特殊化とはパターンマッチだ。

template<int x>
struct is_2or3or5{constexpr static bool value = false;};
template<>
struct is_2or3or5<2>{constexpr static bool value = true;};
template<>
struct is_2or3or5<3>{constexpr static bool value = true;};
template<>
struct is_2or3or5<5>{constexpr static bool value = true;};

これは、引数が2,3,5のどれかの時だけtrueになる。

もう少し意味のある例として、以下のようなことができる。

template<int x, int y>
struct power
{
    constexpr static int value = x * power<x, y-1>::value;
};

template<int x>
struct power<x, 1>
{
    constexpr static int value = x;
};

template<int x>
struct power<x, 0>
{
    constexpr static int value = 1;
};

再帰

再帰だ。これはもう素直に、構造体定義の中で自分自身を使えば良い。さっきすでに出て来た気がするが見なかったことにしてほしい。

template<int x>
struct factorial
{
    constexpr static int value = x * factorial<x - 1>::value;
};

template<>
struct factorial<0>
{
    constexpr static int value = 1;
};

同様のHaskellコードは以下のようになるだろうか。

factorial :: Int -> Int
factorial 0 = 1
factorial x = x * factorial (x-1)

パターンマッチの順番が関係なくなっているのは注意すべきかもしれない。 C++だと、あとでより特殊化された定義が見つかればコンパイラはそちらを用いる。

高階関数

関数を引数として受け取る関数と言うのは、C++TMPでは「templateクラスを受け取るtemplateクラス」だ。受け取る関数の引数が固定になってしまうのが難点だが。

受け取った関数を第二引数に適用するだけの関数は以下のように書ける。

template<template<int>class F, int x>
struct apply{constexpr static int value = F<x>::value;};

ならmapが書けるはずだ。準備としてちょっとしたリストとその操作のための関数を作る。リストの部分はおなじみのcarcdrconsを作っているだけなので(対象がリストではないが)読み飛ばして構わない。

template<int ... x>
struct pack{};

template<typename T>
struct car;
template<int x, int ...xs>
struct car<pack<x, xs...>>
{
    constexpr static int value = x;
};

template<typename T>
struct cdr;
template<int x, int ...xs>
struct cdr<pack<x, xs...>>
{
    typedef pack<xs...> type;
};

template<int x, typename T>
struct cons;
template<int x, int ... xs>
struct cons<x, pack<xs...>>
{
    typedef pack<x, xs...> type;
};

エッジケースとかの処理は何一つしていないが大目に見てほしい。 とりあえず準備ができたので、このpackに対するインターフェースが実装されている型に対してのmapを作ることができる。

template<template<int>class F, typename T>
struct map
{
    typedef typename cons<
            F<car<T>::value>::value,
            typename map<F, typename cdr<T>::type>::type
        >::type type;
};

template<template<int>class F, int x>
struct map<F, pack<x>>
{
    typedef pack<F<x>::value> type;
};

要素が1つになった場合に止めるようにしないと、無のcarとかcdrを取ろうとしてお亡くなりになる。

関数を返す関数は、templateクラスを中で定義しているtemplateクラスになる。例えば、C++11のtemplate using aliasを使って以下のようにする

template<typename T>
struct X
{
    template<typename U>
    using Y = std::pair<T, U>;
};

typedef typename X<int>::template Y<double> pair_int_double;

か、まあ同じことだがrebindをする

template<typename T>
struct X
{
    template<typename U>
    struct Y {typedef std::pair<T, U> type;};
};

typedef typename X<int>::template Y<double>::type pair_int_double;

ことで返せなくはない。ちなみに、私がここでrebindと呼んだテクニックはSTLのコンテナが中でallocatorに対して行なっている。例えばlistはそれぞれのノードが値の他に前後のノードへのポインタを持っているので、一度に確保すべき量がallocator<T>が持っている一要素分のサイズより大きく、allocator<node<T>>のようにしないといけない。だが、ユーザーから渡されるのはallocator<T>であるので、内部で戦略のみ引き継いだ別の型のためのallocatorを作れなければならない。このために、allocatorrebindなる構造体を内部で持っている。

アロケータもふわっとした知識のまま来てしまっているし、カスタムアロケータを一度書くと言うようなことをするべきかもしれない。

部分適用

C++11のusing aliasによって部分適用が簡単に書けるようになった。

template<int x, int y>
struct add{constexpr static int value = x + y;};

template<int x>
using increment = add<x, 1>;

C++98でも、新たなラッパー構造体を定義することで部分適用が可能になる。

template<int x>
struct increment
{
    const static int value = add<x, 1>::value;
};

終わり

いかがだっただろうか。C++TMPも別に恐るるに足らない、要するに少し力の弱いだけの関数型言語なのだと言うことがわかってもらえたと思う。 私はこう言う「今までずっとしてきた見方をちょっと変えると、全く違うと思っていた別のものと同じものだとわかる」というのが結構好きだ。 そうやって対応付けをした結果非常に奇妙だったり非直感的だったりする対応関係ができたら特に面白い。 その面白さがこの奇妙すぎる題材から伝われば幸いである。