小さなメタプログラミングライブラリ

(以下の理解しにくいメタプログラミング。気弱な人向けではありません。)

最近の C++ 標準化委員会のアーバナシャンペーン会議で、Bill Seymour は彼の論文 N4115:Searching for Types in Parameter Packs を発表しました。その名前が示すように、パラメーターパック内の型を検索するためのライブラリ機能について説明しています。とりわけ。 packer というテンプレートが提案されていますパラメーターパックを保持するには:

// A class template that just holds a parameter pack:
template <class... T> struct packer { };

あなたの多くはおそらくすでにそのような施設に精通しているでしょうが、別の名前で:

// A class template that is just a list of types:
template <class... T> struct typelist { };

N4115 に関する議論で、C++ には標準の typelist が必要であることが明らかになりましたテンプレートとそれらを操作するためのいくつかのユーティリティ。しかし、具体的にはどのようなユーティリティでしょうか?

野生のメタプログラミング

C++ でのメタプログラミングに関して言えば、先行技術が不足することはありません。 Andrei Alexandrescu は、彼の Loki ライブラリで流行を開始しました。 Boost は、Boost.MPL、Boost.Fusion、および (現在開発中の) Hana で活動を開始しました。これらのライブラリはすべて機能が豊富で、独自の哲学、特に STL のコンテナー、反復子、およびアルゴリズムからインスピレーションを得た Boost.MPL を備えた精巧なものです。

STL の設計を MPL が勝手に模倣していることを疑うようになったのはつい最近のことです。 STL の抽象化は、実際のコンピューターハードウェア上で実際のデータ構造を処理する実際のアルゴリズムから凝縮されました。しかし、メタプログラムはハードウェア上では実行されません。それらはコンパイラで実行されます。メタプログラムのアルゴリズムとデータ構造は、固有の問題領域と実行環境に合わせて調整する必要があります。その演習を行った場合、どの抽象化が失敗するかを誰が言うことができますか?コンパイル時のイテレータ?それともまったく別の何か?

ダムタイプリスト

いくつかのメタプログラミング機能を標準化するとしたら、それらはどのように見えるべきでしょうか?興味深い質問です。 N4115 は 1 つのことを正しく理解しています。パラメーターパックは、選択されたコンパイル時のデータ構造です。 C++11 以降、C++ には言語サポートがありますタイプのリスト用。他のものと一緒に仕事をするのはばかげているでしょう。 IMO、標準のメタプログラミング機能が何もしなかった場合しかし、パラメーターパック — ばかげた型リスト — を操作すると、問題空間の 95% をカバーできます。

しかし、パラメーターパック自体は、言語の第一級市民ではありません。たとえば、パラメータパックを展開せずに関数に渡すことはできません。パラメータパックを可変長 typelist でラップするテンプレートは簡単です。

したがって、N4115 が示唆するように、これは賢明な出発点です:

// A class template that just a list of types:
template <class... T> struct typelist { };

ただし、これはかなり不吉なスタートです。明らかにもっと必要です。しかし、何？それに答えるには、実際のメタプログラミングの例を見る必要があります。具体的な例を挙げれば、この質問は一体何なのかという質問に答えることができます。良いとにかく？例として、標準ライブラリ自体に目を向ける必要はありません。

Tuple_cat

Stephan T. Lavavej は tuple_cat に注目しました。標準ライブラリの関数、N tuple を取る関数 s を接着して 1 つにします。簡単に思えますが、効率的にコーディングするのは難しく、メタプログラミング機能の優れた動機付けの例であることが判明しました。それをコーディングして、いくつかのタイプリストアルゴリズムを仮定して、仕事を簡単にしましょう。 (ここで説明するコードはすべて、GitHub の range-v3 ライブラリにあります。)

まず、最終的な解決策を提示して、私たちが何を目指しているかを理解してもらいます。願わくば、この投稿を最後までたどり着く頃には、これが何らかの意味を持っていることを願っています.

namespace detail
{
    template<typename Ret, typename...Is, typename ...Ks,
        typename Tuples>
    Ret tuple_cat_(typelist<Is...>, typelist<Ks...>,
        Tuples tpls)
    {
        return Ret{std::get<Ks::value>(
            std::get<Is::value>(tpls))...};
    }
}

template<typename...Tuples,
    typename Res =
        typelist_apply_t<
            meta_quote<std::tuple>,
            typelist_cat_t<typelist<as_typelist_t<Tuples>...> > > >
Res tuple_cat(Tuples &&... tpls)
{
    static constexpr std::size_t N = sizeof...(Tuples);
    // E.g. [0,0,0,2,2,2,3,3]
    using inner =
        typelist_cat_t<
            typelist_transform_t<
                typelist<as_typelist_t<Tuples>...>,
                typelist_transform_t<
                    as_typelist_t<make_index_sequence<N> >,
                    meta_quote<meta_always> >,
                meta_quote<typelist_transform_t> > >;
    // E.g. [0,1,2,0,1,2,0,1]
    using outer =
        typelist_cat_t<
            typelist_transform_t<
                typelist<as_typelist_t<Tuples>...>,
                meta_compose<
                    meta_quote<as_typelist_t>,
                    meta_quote_i<std::size_t, make_index_sequence>,
                    meta_quote<typelist_size_t> > > >;
    return detail::tuple_cat_<Res>(
        inner{},
        outer{},
        std::forward_as_tuple(std::forward<Tuples>(tpls)...));
}

わずか 43 行のコードです。 stdlib++ での実装は 3 倍長く、理解するのは簡単ではありません (IMHO)、および 効率が悪い。このようなものには真の価値があります。本当に。

最初に戻り値の型を見てみましょう:

// What return type???
template< typename ...Tuples >
???? tuple_cat( Tuples &&... tpls );

タプルは、型 and のリストと考えることができます値のリスト。戻り値の型を計算するには、型のリストのみが必要です。したがって、タプルをタイプリストに変換するテンプレートが役立ちます。 as_typelist としましょう .タプルを取り、明白なことを行います。 (別の可能性として、タプルをタイプリストとして使用できるようにすることもできますが、今はこれで行きましょう。)

すべてのタプルをタイプリストに変換すると、タイプリストのリストになります。次に、それらを連結します。ああ！そのためのアルゴリズムが必要です。 typelist_cat としましょう tuple_cat に敬意を表して . ^{_{(関数型プログラマー:typelist_cat は List Monad に参加しています。シーッ!! 渡してください。)}} これまでの内容は次のとおりです。

// Concatenate a typelist of typelists
template< typename ...Tuples >
typelist_cat_t<
    typelist< as_typelist_t< Tuples >... >
>
tuple_cat( Tuples &&... tpls );

ここでは、some_trait_t<X> という C++14 の規則に従っています。 typename some_trait<X>::type のテンプレートエイリアスです .

上記の署名はまだ正しくありません — tuple_cat tuple を返す必要があります、 typelist ではありません .タイプリストをタプルに戻す方法が必要です。タイプリストを可変個引数テンプレートに拡張する操作は便利であることが判明したので、そのためのアルゴリズムを作成しましょう。それは何と呼ばれるべきですか？タイプリストをテンプレートに展開することは、タプルを関数呼び出しに展開することによく似ています。 apply と呼ばれる Library Fundamentals TS には、そのためのタプルアルゴリズムがあります。 .それでは、メタ関数 typelist_apply を呼び出しましょう .実装は短く興味深いので、ここで紹介します:

template<template<typename...> class C, typename List>
struct typelist_apply;

template<template<typename...> class C, typename...List>
struct typelist_apply<C, typelist<List...>>
{
    using type = C<List...>;
};

最初のパラメーターは、めったに見られないテンプレートテンプレートパラメーターです。完了する前にこのインターフェースを微調整しますが、今のところはこれで十分です。

tuple_cat の署名を記述できるようになりましたとして:

template<typename...Tuples>
typelist_apply_t<
    std::tuple,
    typelist_cat_t<typelist<as_typelist_t<Tuples>...> > >
tuple_cat(Tuples &&... tpls);

悪くはありません。すでに 3 つのタイプリストアルゴリズムを発見しています。

Tuple_cat の実装

tuple_cat を実装する時が来ました、そしてここで物事が奇妙になります。最初のタプルを剥がして再帰呼び出しの末尾に展開することで実装できます。引数リスト内のすべてのタプルを再帰すると、すべてのタプル要素が関数の引数に分解されます。そこから、それらを最終的なタプルにまとめれば完了です。

これは多くのパラメーターの受け渡しです。

Stephan T. Lavavej は私にもっと良い方法を教えてくれました:すべてのタプルを取り、それらを std::forward_as_tuple で tuple-of-tuples にまとめます。 .タプルはランダムアクセスであるため、タプルのタプルは要素のギザギザの 2 次元配列のようなものです。 (i,j) でこの 2 次元配列にインデックスを付けることができます座標、そして (i,j) の正しいリストがある場合ペアを作成すると、各要素を順番に取得し、結果のタプルを 1 回で構築できます。すべての爆発は必要ありません。

これをより具体的にするために、次の tuple_cat への呼び出しをイメージします。 :

std::tuple<int, short, long> t1;
std::tuple<> t2;
std::tuple<float, double, long double> t3;
std::tuple<void*, char*> t4;

auto res = tuple_cat(t1,t2,t3,t4);

結果を次のタイプのモンスタータプルにしたい:

std::tuple<int, short, long, float, double,
           long double, void*, char*>

tuple_cat へのこの呼び出し次の (i,j) のリストに対応します座標:

[(0,0),(0,1),(0,2),(2,0),(2,1),(2,2),(3,0),(3,1)]

以下は tuple_cat_ です i を取るヘルパー関数さん、j 、およびタプルのタプル、および結果のタプルを構築します:

template<typename Ret, typename...Is, typename ...Js,
    typename Tuples>
Ret tuple_cat_(typelist<Is...>, typelist<Js...>,
    Tuples tpls)
{
    return Ret{std::get<Js::value>(
        std::get<Is::value>(tpls))...};
}

ここでは、Is と Js std::integral_constant のインスタンスです . Is シーケンス [0,0,0,2,2,2,3,3] および Js を含む [0,1,2,0,1,2,0,1] が含まれています。

まあまあですが、Is を計算する方法と Js ?カンザスはさようならだから、しっかり待っててね。

高次メタプログラミング、テイク 1

最初に Js のシーケンスを考えてみましょうそれは少し簡単だからです。私たちの仕事は、型リスト [[int,short,long],[],[float,double,long double],[void*,char*]] のリストを整数のリスト [0,1,2, 0,1,2,0,1]。 4 つの段階でそれを行うことができます:

<オール>

typelist のリストを typelist sizes のリストに変換します :[3,0,3,2],

std::make_index_sequence を使用して、それをインデックスシーケンス [[0,1,2],[],[0,1,2],[0,1]] のリストに変換します、

std::index_sequence を変換します std::integral_constant のタイプリストに as_typelist の、

typelist_cat を使用して最終的なリストにフラット化します .

ここまでで、4 番目のタイプリストアルゴリズムを発見したことは明らかです:typelist_transform . std::transform のように、 typelist_transform シーケンスと関数を取り、各要素が関数によって変換された新しいシーケンスを返します。 ^{_{(関数型プログラマー:List Functor の fmap です)}} .考えられる実装の 1 つを次に示します。

template<typename List, template<class> class Fun>
struct typelist_transform;

template<typename ...List, template<class> class Fun>
struct typelist_transform<typelist<List...>, Fun>
{
    using type = typelist<Fun<List>...>;
};

簡単です。

メタ関数構成

上記では、typelist_transform で 3 つの連続したパスを提案しました . 3 つのメタ関数を 1 つにまとめれば、これをすべて 1 つのパスで実行できます。メタ関数合成は非常に重要なユーティリティのようで、型リスト操作に固有のものではありません。これまで、メタ関数を他のメタ関数に渡すためにテンプレートテンプレートパラメータを使用してきました。その世界では、メタ関数の構成はどのように見えますか?以下は meta_compose と呼ばれる高階メタ関数です。他の 2 つのメタ関数を構成します:

template<template<class> class F0,
         template<class> class F1>
struct meta_compose
{
    template<class T>
    using apply = F0<F1<T>>;
};

2 つのメタ関数を合成すると、新しいメタ関数が発生する必要があります。ネストされたテンプレートエイリアス apply を定義することにより、テンプレートを「返す」イディオムを使用する必要があります。

簡単そうに見えますが、実際にはすぐに扱いにくくなります。 3 つのメタ関数を構成する場合、コードは次のようになります:

meta_compose<F0, meta_compose<F1, F2>::template apply>
    ::template apply

きもい。さらに悪いことに、それはあまり一般的ではありません。 std::make_index_sequence を構成したい、そしてそのメタ関数は型を取らない;整数を取ります。 meta_compose に渡すことはできません .バックアップしましょう。

高次メタプログラミング、テイク 2

meta_compose<X,Y>::template apply を渡す代わりに、 typelist_transform のような高階関数に、 meta_compose<X,Y> を通過しました typelist_transform にしますネストされた apply を呼び出します ?さて、typelist_transform のような高階関数テンプレートテンプレートパラメータの代わりに通常の型を使用します。 typelist_transform 次のようになります:

template<typename ...List, typename Fun>
struct typelist_transform<typelist<List...>, Fun>
{
    using type =
        typelist<typename Fun::template apply<List>...>;
};

これは typelist_transform の実装を複雑にします、しかし、インターフェースをより扱いやすくします。メタ関数のように動作するクラス型の概念は、Boost.MPL に由来し、メタ関数クラス と呼ばれます。 .

ネストされたメタ関数を一連の引数に適用する小さなヘルパーを使用して、メタ関数クラスを扱いやすくすることができます。

template<typename F, typename...As>
using meta_apply = typename F::template apply<As...>;

meta_apply で、 typelist_transform を書き換えることができますとして:

template<typename ...List, typename Fun>
struct typelist_transform<typelist<List...>, Fun>
{
    using type = typelist<meta_apply<Fun, List>...>;
};

それはまったく悪いことではありません。これで meta_compose を変更できますメタ関数クラスでも操作する:

template<typename F1, typename F2>
struct meta_compose
{
    template<class T>
    using apply = meta_apply<F1, meta_apply<F2, T>>;
};

もう少し手を加えると、任意の数のメタファンクションクラスを受け入れて、それらすべてを構成することさえできます。楽しいエクササイズです。試してみてください。

最後に、メタ関数クラスができたので、typelist_apply を変更する必要があります。テンプレートテンプレートパラメータの代わりにメタ関数クラスを取得するには:

template<typename C, typename...List>
struct typelist_apply<C, typelist<List...> >
{
    using type = meta_apply<C, List...>;
};

メタ関数からメタ関数クラスへ

評価しようとしている 4 つのステップを思い出してください。

<オール>

typelist のリストを typelist sizes のリストに変換します :[3,0,3,2],

std::make_index_sequence を使用して、それをインデックスシーケンス [[0,1,2],[],[0,1,2],[0,1]] のリストに変換します、

std::index_sequence を変換します std::integral_constant のタイプリストに s with as_typelist 、

typelist_cat を使用して最終的なリストにフラット化します .

ステップ (1) でタイプリストのサイズを取得するため、typelist_size という別のタイプリストアルゴリズムが必要です。型 typelist のサイズをフェッチします:

template<typename...List>
struct typelist_size<typelist<List...> >
  : std::integral_constant<std::size_t, sizeof...(List)>
{};

これを meta_compose に渡したいと思います、しかし typelist_size はテンプレートで、meta_compose メタ関数クラスが必要です。ラッパーを書くことができます:

struct typelist_size_wrapper
{
    template<typename List>
    using apply = typelist_size<List>;
};

これらのラッパーを書くのはすぐに退屈になります。しかし、そうする必要はありません。以下は、退屈な古いメタ関数をメタ関数クラスに変換するための簡単なユーティリティです:

template<template<class...> class F>
struct meta_quote
{
    template<typename...Ts>
    using apply = F<Ts...>;
};

名前 quote Boost.MPL を介して LISP から取得されます。 meta_quote で typelist_size を回すことができますテンプレートを meta_quote<typelist_size> で Metafunction クラスに .これで meta_compose に渡すことができますまたは typelist_transform .

私たちのステップでは、3 つのメタ関数を構成する必要があります。次のようになります:

meta_compose<
    meta_quote<as_typelist_t>,            // Step 3
    meta_quote<std::make_index_sequence>, // Step 2
    meta_quote<typelist_size_t> >         // Step 1

すでに述べたように、std::make_index_sequence 型ではなく整数を取るため、meta_quote に渡すことはできません .これは残念です。 meta_quote の亜種で問題を回避できますこれらの種類のテンプレートを処理します。 meta_quote_i としましょう :

template<typename Int, template<Int...> class F>
struct meta_quote_i
{
    template<typename...Ts>
    using apply = F<Ts::value...>;
};

meta_quote_i で、次のように 3 つの関数を構成できます:

meta_compose<
    meta_quote<as_typelist_t>,              // Step 3
    meta_quote_i<std::size_t,
                 std::make_index_sequence>, // Step 2
    meta_quote<typelist_size_t> >           // Step 1

これで、構成された関数を typelist_transform に渡すことができます :

typelist_transform_t<
    typelist<as_typelist_t<Tuples>...>,
    meta_compose<
        meta_quote<as_typelist_t>,
        meta_quote_i<std::size_t, make_index_sequence>,
        meta_quote<typelist_size_t> > > >;

出来上がり！タプルのリストをリストのリスト [[0,1,2],[],[0,1,2],[1,2]] に変えました。最終結果を得るために、typelist_cat を使用してこれを 1 つのリストに滑らかにします :

// E.g. [0,1,2,0,1,2,0,1]
typelist_cat_t<
    typelist_transform_t<
        typelist<as_typelist_t<Tuples>...>,
        meta_compose<
            meta_quote<as_typelist_t>,
            meta_quote_i<std::size_t, make_index_sequence>,
            meta_quote<typelist_size_t> > > >;

結果は K です tuple_cat_ に渡すインデックスヘルパー。上から繰り返しますが、I インデックスは以下で計算されます:

// E.g. [0,0,0,2,2,2,3,3]
typelist_cat_t<
    typelist_transform_t<
        typelist<as_typelist_t<Tuples>...>,
        typelist_transform_t<
            as_typelist_t<make_index_sequence<N> >,
            meta_quote<meta_always> >,
        meta_quote<typelist_transform_t> > >;

手順を踏むことはしませんが、次の 2 つの点に注意してください:(7) 行目では、meta_always という奇妙な型を使用しています。 (後述)、(8) 行目で typelist_transform を渡します。 typelist_transform の別の呼び出しへの関数引数として .構成可能性について話してください!

meta_always とは ?簡単に言うと、これは常に同じ型に評価されるメタ関数クラスです。その実装はこれ以上簡単ではありません:

template<typename T>
struct meta_always
{
    template<typename...>
    using apply = T;
};

上記のコードが機能する理由を理解するのは皆さんにお任せします。

まとめ

私は、標準化に適したタイプのリストを操作するための最小限の有用なプリミティブのセットを見つけようと試みました。結果に満足しています。私が見つけたのは、 typelist に加えてテンプレートには、tuple_cat の実装に必要なアルゴリズムのような小さなセットのアルゴリズムが必要です :

typelist_apply
typelist_size
typelist_transform
typelist_cat
as_typelist

他のいくつかのタイプリストアルゴリズムは、他のメタプログラミングタスクで使用されます:

make_typelist (カウントとタイプから)
typelist_push_front
typelist_push_back
typelist_element (タイプリストへの索引付け)
typelist_find と typelist_find_if
typelist_foldl (別名、累積) および typelist_foldr
など

さらに、typelist_transform のような高次のメタ関数のために、と typelist_find_if メタ関数クラス (メタ関数として使用できる通常のクラス型) の概念を理解しておくと役に立ちます。メタ関数クラスを作成および操作するためのユーティリティの小さなセットは、タイプリストアルゴリズムを使用できるようにするために不可欠です:

meta_apply
meta_quote
meta_quote_i
meta_compose
meta_always

その他の問題については、メタ関数クラスを部分的に適用 (別名バインド) する機能が非常に便利です:

meta_bind_front
meta_bind_back

それだけです。私の意見では、これらのユーティリティはすべてのメタプログラムの 95% のニーズを満たします。それらはシンプルで直交しており、強力な方法で構成されています。 typelist に制限したためデータ構造、非常に Boost.MPL よりも簡単です。ここでは反復子は必要ありません。反復子はかなりステートフルで反復的な抽象化であり、メタプログラミングは純粋に機能的であるため、これは理にかなっています。

最後に…

以下は、あなたの麺をくすぐるもう 1 つのメタ関数です。 transform の N-way バリアントです :タイプリストとメタ関数クラスのリストを取り、それらすべてをマッピングして新しいタイプリストを構築します。これが標準に含まれるほど重要または有用であることを示唆しているわけではありません。これらのプリミティブ操作がより豊富な機能を構築するためにいかにうまく構成されているかを示すために、私はそれを示しているだけです.

// ([[a,b,c],[x,y,z]], F) -> [F(a,x),F(b,y),F(c,z)]
template<typename ListOfLists, typename Fun>
struct typelist_transform_nary :
  typelist_transform<
    typelist_foldl_t<
      ListOfLists,
      make_typelist<
        typelist_front_t<ListOfLists>::size(),
        Fun>,
      meta_bind_back<
        meta_quote<typelist_transform_t>,
        meta_quote<meta_bind_front> > >,
    meta_quote<meta_apply> >
{};

お楽しみください!

更新: この tkamin のコメントは、上記の typelist_transform_nary が zipWith だけです関数型プログラミングの世界のアルゴリズム。最新のコードで名前を変更し、 typelist_zip を提供しました typelist_zip_with にディスパッチするメタ関数 meta_quote<typelist> で関数の引数として。とてもいいですね!