Freestyling on patterns, idioms and semantics…

Icon

vivid hallucinations for bloodthirsty digital vampires

Variadic Metafunctions

An interesting use of variadic template arguments [VTA] comes used with metaprogramming: it results in a metafunction that takes a variable number of arguments.

For those who have never heard about metafuncions I would suggest to read a couple of books,  C++ Modern Design Pattern and the more specific C++ Template Metaprogramming. To make the long story short,  a metafunction is a function that runs at compile time. The technique was discovered by Erwin Unruh  years ago when he created a C++ program that, though not compiling, was able to generate the sequence of prime numbers in form of  compiler error messages.

Today metaprogramming has become a very refined technique widely exploited in a number of C++ template libraries, boost to mention one. A didactic example of a numeric metafunction is the factorial:

template <int N>
struct factorial
{
    enum { value = N * factorial::value };
};

template <>
struct factorial<0>
{
    enum { value = 1 };
};

An important achievement of the last years, presented by Alexandrescu in Modern Design Pattern, is the type list, that is a recursive agglomerate of types that resembles to a list of types. The type list enables implementations of different classes, tuple and variant to mention a few.

A possible implementation of a type list is the following one:

struct null {}; // typelist terminator

template <typename H, typename T>
struct typelist {};

typedef typelist< int, typelist< char, typelist< short, null> > > list_type; // list of int, char and short

…where the null type is a placeholder that identifies the end of the list. The list itself (list_type) is just a type. Therefore, to operate on it a set of metafunctions is required.

For instance, the following metafunction can be used to calculate the length of such a type list:

    // length<Tp>::value
    //

    template <typename Tp> struct length;
    template <>
    struct length<null>
    {
        enum { value = 0 };
    };

    template <typename T,typename U>
    struct length< typelist<T,U> >
    {
        enum { value = 1 + length<U>::value };
    };

By means of templates and recursion it is possible to implement a complete set of meta-functions, like adding a type to the head, to the tail and so forth.

However, VTA allows to express the type-list in a better way and in this essay I present a possible novel implementation along with some variadic companion metafunctions.

That said, a new definition of a typelist could be the following one:

    template <typename ...Ti>
    struct type_list {};

It follows that the declaration of a type-list looks like this:

    type_list<int, char, double>

which is very compact declaration in comparison to those enabled by means of C++03, that in the best case use some preprocessing macros to hide the boilerplate declaration.

This new list requires variadic metafunctions to perform operations on it. For instance, the metafunction that calculates the length of such a list is the following one:

    // length<>::value
    //
    template <typename Tl> struct length;

    template <typename T, typename ...Ti>
    struct length<typelist<T, Ti...>>
    {
        enum { value = 1 + length<typelist<Ti...>>::value };
    };

    template <typename T>
    struct length<typelist<T>>
    {
        enum { value = 1 };
    };

    template <>
    struct length<typelist<>>
    {
        enum { value = 0 };
    };

A better non-recursive implementation is based on the sizeof…() operator that, when applied to a parameter pack, returns the number of the elements.

    template <typename Tl> struct length;
    template <typename ...Ti>
    struct length<typelist<Ti...>>
    {
        enum { value = sizeof...(Ti) };
    };

It’s worth noting that by means of  VTA the implementation of meta-functions like insert and append result much simple:

    // append<>::type
    //
    template <typename Tl, typename Tp> struct append;
    template <typename Tp, typename ...Ti>
    struct append<typelist<Ti...>, Tp>
    {
        typedef typelist<Ti...,Tp> type;
    };

    // insert<>::type
    //
    template <typename Tl, typename Tp> struct insert;
    template <typename Tp, typename ...Ti>
    struct insert<typelist<Ti...>, Tp>
    {
        typedef typelist<Tp, Ti...> type;
    };

The other companion functions that a typelist should be implementing are not provided herein. I leave the reader with the pleasure to implement them as a brain teaser. All in all, an important part of coding is the fun.

Enjoy the C++0x, always!

Advertisements

Filed under: C++11, programming

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: