Strike up a friendship with Template Metaprogramming

Posted: October 26, 2011 in Programming Recipes
Tags: ,

A template is a way to generate code. C++ supports generic programming through the template mechanism, which allows defining parameterized classes and functions, over a set of types, functions or constants. Templates together with other C++ features constitute a Turing-complete (e.g. a queue automata), compile-time sublanguage of C++.

For example:

template <typename One, typename Two>
struct Pair
{
 One first;
 Two second;
};

Providing arguments to a template, instantiates (at compile-time) the template with those arguments:

Pair<float,int> myNumericalPair;
 // One = float
 // Two = int

This produces something like this:

struct Pair
{
 float first;
 int second;
};

Remember that template classes (and functions) are not generated if not used, then the following code is correct (but clearly immoral!):


template <typename T>
struct MyTemplateClass {
	void functionThatWorksWithInt() {
		cout << "Just a ping on cout!" << endl;
	}

	void functionThatDoesNotWorkWithInt() {
		member.function(); // int does not have "nested functions"!
	}

	T member;
};
//...
MyTemplateClass<int> mtc; // ok
mtc.functionThatWorksWithInt(); // ok

In the code above, the function functionThatDoesNotWorkWithInt is never called by mct so the code is correct! This is a caveat, be careful. I’m going to face with this problem at the end of this post.

Another important feature is template specialization: given a template with one or more parameters we can provide special versions of the template where some of the parameters are fixed. There are two types of specializations: full (when all the arguments are specialized) and partial (when arguments have particular structure):

/* Primary template */
template<typename T>  class Set
{
    // e.g. Use a binary tree
};

/* Full specialization */
template <> class Set<char>
{
    // e.g. Use a bit vector
};

/* Partial specialzation */
template <typename T>  class Set<T*>
{
    // e.g Use a hash table
};

When we have more than one parameter, we can specialize a subset of the types:

/* general version */
template<typename T, typename U> class A { ... };

/* specialization on T */
template<typename U> class A<int,U> { ... };

/* specialization on both */
template<> class A<int,int> { ... };

A<double, double> a;  // uses general version
A<int, double> b;     // uses first specialization
A<int, int> a;        // uses second specialization

Partial specialization does not apply to functions:

template <typename T, typename U>  T fun(U obj) {...}

// the following is illegal
template <typename U>  void fun<void, U>(U obj) {...}

// the following is legal (overloading)
template <typename T> T fun(Window obj) {...}

The parameters of a template can be constant numbers (they are known at compile-time) instead of types (and we can also specialize on certain numbers):

template<unsigned n>
struct Num {
     static const unsigned num = n;
};

Num<5> x;
Num<8> y;

cout << x.num << endl; // prints 5
cout << y.num << endl; // prints 8

We have all the key concepts to talk about Metaprogramming: a metaprogram is a program that produces or manipulates constructs of a target language. Specifically, a template metaprogram is a C++ program that uses templates to generate customized C++ code at compile-time.

Why would I ever want to do this? You rebut.

TMP has a great numbers of benefits. The most obvious reason  to rely on a metaprogram is that by dong as much work as possible before the resulting program starts, we get faster (but sometims “bigger”) programs. A subtler but perhaps more important argument for using a metaprogram is that the result of the computation can interact more deeply with the target language. For example, the brace-enclosed actions in a YACC grammar can contain arbitrary C/C++ code to be executed as part of the generated parser. That’s only possbile because the actions are processed during grammar compilation and passed on to the target C/C++ compiler.

Instead of doing computation at runtime or compile time, we could just do it by hand. A good metaprogram can outstrip this by enabling a more expressive and reusable code, narrowing human errors and improving the code maintenance process.

Ok, I can believe you, but when is metaprogramming appropriate? In their excellent book, Abrahams  and Gurtovoy – C++ Template Metaprogramming: Concepts, Tools and Techniques from Boost and Beyond – say that if any three of the following conditions apply then a metaprogrammed solution can be appropriate:

  • You want the code to be expressed in terms of the abstractions of the problem domain.
  • You would otherwise have to write a great deal of boilerplate implementation code.
  • You need to choose component implementations based on the properties of their type parameters.
  • You want to take advantage of valuable properties of generic programming in C++ such as static type checking and behavioral customization, without loss of efficiency.
  • You want to do it all within the C++ language, without an external tool or custom source code generator.

Stop talking, let’s write some code! I’ll show you a simple metaprogram. Note that the code generation engine embedded in the C++ compiler can actually make some calculation by using recursion – to learn TMP, the functional metaprogrammer in you should pipe up!

Here is how to compute the factorial:

template<int n>
struct Fact {
    enum { value = n * Fact::value };
};

template <>
struct Fact {
    enum { value = 1 };
};

cout << Fact<5>::value << endl;

The key trick is to combine specialization with integral parameters. The specialization “stops” the recursion (the base case).

TMP is a programming world (I said, C++ TMP is a programming language, just like C++) then there exist several techniques and usages.

If you want to deeply learn TMP, I suggest you to read a handful of books:

  • C++ Template Metaprogramming: Concepts, Tools and Techniques from Boost and Beyond – it employs boost metaprogramming library (MPL) – a very good and widespread library.
  • Modern C++ Design: Generic Programming and Design Patterns Applied (by Andrei Alexandrescu) – it employs Loki (TMP library written by Alexandrescu). This book is a must-have.
  • C++ Templates: The Complete Guide (by Vandevoorde and Josuttis) – a very good book, it provides complete and accurate information on using templates.

Let’s write other metaprograms!

Sometimes you need to detect if two generic types A and B are in a relationship of convertibility, say A is convertible to B. We know that sizeof() is a compile-time mechanism of C/C++ to compute the size of a type (since it is done at compile-time, its argument is not actually executed at run-time, but it is only evaluated). For example, if the argument contains a function call, it only checks its (return) type:

int myIntFunction();
sizeof(myIntFunction()); // equivalent to sizeof(int)

We can define two types of different sizes:

typedef char OneByte;
class TwoBytes { char dummy[2]; };

Now take a breath and read:

template<typename T, typename U>
class Conversion {
     typedef char OneByte;
     class TwoBytes { char dummy[2]; };
     static OneByte Test(U);
     static TwoBytes Test(...);
     static T MakeT();
public:
     enum { exists = sizeof(Test(MakeT())) == sizeof(OneByte) };
};

What’s happened?

Keep calm.

We have two template parameters: T and U. There is a simple MakeT() function which type is T. We have also two functions Test(): the first takes one of the template arguments (U) and the other everything (…).

Intuitively, if we invoke MakeT() when T = U then the type of MakeT() is U. At this point, we get the “sizeof” Test(U) (because we just have a Test(U) function) and this returns OneByte. Then the left-hand side is equal to the right-hand side of the last expression, so the enum exists is 1 (aka true).

The key point is to understand if the compiler can automatically convert T to U. If so, it will use Test(U), otherwise Test(…)Test(U) and Test(…) have different types with different sizes, then the final equality expresses if the conversion takes place.

On the wake of the factorial example, here it is another recursive metaprogram. The idea is to compute the sum of the squares of the first n natural numbers. Let’s start with the metafunction (class-template as a function) that computes the square of a number. It’s quite simple but remember that it has to compute values at compile-time:

template<int n>
struct Square
{
	enum { RET = n*n };
};

Ok, that was easy. Now we have to use this metafunction inside another metafunction! We have to employ this metafunction as a template parameter. The syntax is a little bit more complicated but don’t be scared:

template <int n, template<int> class F>
class MyClassWithMetafunction { ... };

This means that MyClassWithMetafunction receives an int (n) and a class (F) that receives an int. No more. Here it is the remaining code:

// metafunction as "template parameter"
template <int n, template<int> class F>
struct Accumulate
{
	enum { RET = Accumulate::RET + F::RET };
};

template <template<int> class F>
struct Accumulate<0, F>
{
	enum { RET = F::RET };
};

Accumulate<0,F> is the usual base case that stops the recursion. At each step, Accumulate sums the result of the metafunction applied to the current n and goes on with the recursion. Wake up the functional programmer in you, he’ll understand better!

Are you fed up with TMP?! Let me show you the last example and I stop. I promise!

Sometimes we would like to know if a type has a certain function. Generally this is called Interface Checking. This (also) deal with problems I pointed out at the beginning, talking about int and mysterious code that compiles though ints don’t have nested functions (just because these functions were not called)! Suppose we have a class MyClonable that has a Clone() function:

class MyClonable {
public:
	MyClonable* Clone() const { ... }
};

We want to write a metaprogram to verify if a type has this function. To do this, a good idea is to separate the concept of checking by confining it into a separate class.

template <typename T>
class HasClone
{
public:
	HasClone() { void (*p)() = Constraints; }

	static void Constraints()
	{
		T* (T::*test)() const = &T::Clone;
	}

};

template <typename T>
class InterfaceCheck : HasClone<T> {};

InterfaceCheck<MyClonable> c; // if MyClonable didn't have Clone then this would be a compilation error

First thing to undestand: we use a “base” class (HasClone<T>) to encapsulate the checking, when we construct the base class we execute its constructor that declares a pointer to the Constraints function. Setting up this little inheritance is also convenient to force the compiler to always instantiate HasClone<T> and then check the “constraints” it brings along.

Constraints does the trick (still at compile-time): it declares a pointer to the Clone member function of the template parameter (T), but if this function does not exist, all the evil spirits wil jump out to catch you because you’ll have a compilation error. Don’t get confused with all those pointer definitions, the code is easier than you think!

I hope this post can be useful to intrigue you about metaprogramming. I heartly recommend you to write your codes, starting with simple examples (the factorial is a good start). Then you can read one of the books I mentioned before. And don’t forget to wake up the functional programmer in you!

Advertisements

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