Beginning Template Meta-Programming: Introducing meta-functions

I intended this to be an article about “arbitrary binding” in template meta-programming, but I found that there was much I needed to introduce in order to do so and the article was becoming quite lengthy without actually providing much.  Thus I’ve decided to begin a series on template meta-programming that will introduce the topic and expand into more complex subjects, partial application being one of them.

Some history – expression templates

Meta-programming in C++ was pretty much a total accident.  The template system was defined without meta-programming in mind.  For many years in C++ development, and unfortunately still not as rare as it should be, developers were afraid of templates and in some cases avoided them entirely.  More than one team would have coding standards that dictated that no developer use templates.  The problem was that many compilers did not implement templates very well and in fact there are still issues with some of the more commonly used compilers.  If you chose to go down the road of becoming efficient at Template Meta-Programming (TMP) you are sure to run into a few compiler bugs.

Even so though, some brave souls embraced templates and came up with some very interesting constructs.  The STL is but one of the more fascinating examples.  Many of the ideas introduced there indicated that there was much potential for expressive power in templates.  One very early example of techniques that hinted at TMP though are expression templates.  If you search through the Internet for this term you’ll find a great many excellent articles and papers.  Expression templates are a powerful concept that can be used to reduce the amount of temporaries created during calculations of complex objects such as matrices.  The idea is that operators, such as addition, don’t actually perform addition at all but instead create an object that implements the functions that perform that task.  This is in some ways hinting at lazy evaluation except that (until C++11 changed the meaning of auto) nobody in their right mind wants to declare the type that would be necessary to store that lazy evaluator in a variable.  Instead, the act of assignment or access would perform all the calculations in the complete expression leaving out that which is unnecessary, encoding the evaluation of each cell into a single expression, and eliminating the need for temporary objects.  What follows is a very brief example (the rest of the operators are left as an exercise):

// represents a delayed addition operation.
// Represents a result but isn't itself one.
template < typename Right
         , typename Left >
struct matrix_addition
{
    matrix_addition( expr_matrix const& lh
                   , expr_matrix const& rh)
        : m1(lh)
        , m2(rh)
    {}

    int get_value(int x, int y) const
    {
        return m1.get_value(x,y) 
             + m2.get_value(x,y)
        ;
    }

    operator expr_matrix() const // perform the addition and return the result.
    {
        expr_matrix tmp;
        for (size_t i = 0; i < 3; ++i)
        {
            for (size_t j = 0; j < 3; ++j)
            {
                tmp.assign_value(i,j, get_value(i,j));
            }
        }
        return tmp;
    }

private:
    expr_matrix const& m1;
    expr_matrix const& m2;
};

// override '+' to return addition result representation.
template < typename Right 
         , typename Left >
matrix_addition<Right,Left> operator + (Right const& rh, Left const& lh)
{
    return matrix_addition<Right,Left>(rh,lh);
}

BOOST_AUTO_TEST_CASE(check_expr_approach)
{
    expr_matrix m1;
    expr_matrix m2;

    fill_test_matrices(m1,m2);

    // Creates a full result through implicit casting.
    expr_matrix result = m1 + m2;

    check_test_matrices(m1,m2,result);

    // The only additions performed here are on [0,0].  None of the others are performed.
    // A complete summation of the matrixes used is not done.
    BOOST_CHECK((m1 + m2).get_value(0,0) * 2 == (m1 + m2 + result).get_value(0,0));
}

Expression templates are an example of an embedded Domain Specific Language (DSL). They turn expressions involving the matched types and operator overloads into a set of recursively defined types that represent an abstract syntax tree.

Our first “pseudo” meta-function

One of the first examples of a metafunction generally introduced is the factorial function.  I’m going to call this a pseudo metafunction because it doesn’t match any defined protocol for creating a consistent language for template metaprogramming.  As with functional programming in general, this compile time factorial calculator is recursive in nature.  In something like Haskel or Scala you would use pattern matching on the argument to invoke a different calculation for the argument should it be general or should it be your base case.  In TMP you do this with template specialization:

template < size_t I > // general case
struct pre_tmp_fact
{
    // recursively invoke pre_tmp_fact
    // and multiply the result with the current value.
    enum { value = I * pre_tmp_fact<I-1>::value };
};

template < > // base case specialization
struct pre_tmp_fact<0>
{
    // 0! == 1
    enum { value = 1 };
};

BOOST_AUTO_TEST_CASE(first_example)
{
    BOOST_CHECK(pre_tmp_fact<5>::value == 5 * 4 * 3 * 2);
}

Defining a protocol

In C++ Template Metaprogramming, Abrahams and Gurtovoy define a protocol for implementing a consistent language for template metaprogramming in C++.  That protocol involves three basic definitions:

Meta-Function
A meta-function is a template that takes types as parameters and ‘returns’ a type in the form of an internal type typedef.
Value Meta-Function
Value meta-functions are metafunctions that represent values. They have all the characteristics of a meta-function and also an internal value member. They are “identity meta-functions” in that they return themselves as their type. If you create instances of them they are generally convertible to the underlying raw value type they represent, with the appropriate value of course.
Meta-Function Class
Since a meta-function is not a type it cannot be passed as a parameter to another meta-function. Therefor an additional concept, that of meta-function class, needs to be defined. It is a type that has an internal meta-function called apply.

Our first meta-function

With the above in mind, we can recreate our factorial metafunction using these concepts.  In this article I’ll implement very basic, minimally functional integer wrapper meta-functions.  In the future I will use the Template Metaprogramming Library (MPL), which is part of the boost library set.  It’s worth reviewing here, for instruction purposes, but it’s generally easy to use what other people have built and tested than reinventing the wheel.  This time though, we’ll reinvent the wheel, we just won’t add all the spokes and will not true it:


// integer value wrapper metafunction.
template < int I >
struct int_
{
    typedef int_<I> type;
    enum : int { value = I };
};

BOOST_AUTO_TEST_CASE(value_mf)
{
    // Has a value...
	BOOST_CHECK(int_<5>::value == 5);
	// Is an identity metafunction...
	BOOST_CHECK(int_<5>::type::value == 5);
	// This recursion is OK because the compiler won't instantiate until requested.
	// Can go on forever.
	BOOST_CHECK(int_<5>::type::type::value == 42);
}

// This is not how boost's MPL does it!

// Forward declaration of metafunction
template < typename T >
struct prev;

// Specialize for int_ wrappers.
template < int I >
struct prev<int_<I>>
{
    typedef int_<I-1> type;
    enum { value = int_<I-1>::value };
};

BOOST_AUTO_TEST_CASE(prev_int)
{
    BOOST_CHECK(prev<int_<5>>::value == 4);
}

// General case.
template < typename T >
struct tmp_fact
{
    typedef tmp_fact<T> type;
    enum { value = T::value * tmp_fact<typename prev<T>::type>::value };
};

// Specification for base case.
template < >
struct tmp_fact<int_<0>>
    : int_<1> // You can subclass the result sometimes, to be preferred.
{};

BOOST_AUTO_TEST_CASE(fact_check)
{
    BOOST_CHECK(tmp_fact<int_<5>>::value == 5 * 4 * 3 * 2);
}

Moving forward

If you are interested in continued study of template meta-programming in C++ then I suggest purchasing the book, C++ Template Metaprogramming.  I will also be continuing forward with some other instructional material in future blogs, including implementing named parameters and partial evaluation (arbitrary binding) in templates.  This has been but a rudimentary look at the very basics that will be needed by future blog entries.

I might suggest also playing with the above code and trying to improve it. There are a great many ways in which it can be. The factorial metafunction for example could use tail recursion and could even use subclassing all the way through. It is much easier to read and work on a metafunction that can be defined in terms of other metafunctions through simple inheritance, so unless you must do otherwise to leverage lazy evaluation (any time you can avoid explicitly refering to type within a metafunction you’re doing lazy evaluation) it should be preferred. Often this requires decomposition of more complex metafunctions into smaller, simpler ones. This is of course, like with your usual code, never a bad thing.

About these ads

4 Responses to “Beginning Template Meta-Programming: Introducing meta-functions”

  1. Hi,

    i really like your structured explanations and learned a lot.
    I was a first a little confused about the

    typedef int_ type;

    in your listing.

    I guess it is
    typedef int_ type;
    instead.

    Anyway, great introduction to meta programming. Found you via Google.

    Regards,
    Tobi

  2. Sorry. brackets didn’t work in my post. :-)
    I meant behind int_ there must be I-1 in template brackets.

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

Follow

Get every new post delivered to your Inbox.

Join 26 other followers

%d bloggers like this: