C++ template metaprogramming introduction

Disclaimer: After so many years (and blog migrations), this article might be broken or outdated. Yeah, blog migrations, that’s it. Anything that’s wrong is the fault of a blog migration, everything that’s right is because the author of this article spent countless hours researching this topic.

I try to keep the information here as relevant as possible but please let me know if you find any problems while reading this article. Some corrections have been made already, thanks to all the commenters at the bottom of this page who write to let me know when I have stuff to correct!

Template metaprogramming: A slow descent towards utter madness

There have been some articles dealing with template metaprogramming before over here. Things like template <int n>, which look really weird (but behave in an even more bizarre way). This post starts a series of articles following the contrived and tortuous path down insanity lane and into the mouth of the beast. When we are done things like typedef typename should be clearer than i=i++, should you dare to keep on reading.

animaniacs-8

First things first: Why TF would I…

Instead of explaining why let’s start backwards: assume you already want to start learning some template metaprogramming. Yeah, I’m sure there are many legitimate reasons, like job security or job security perhaps, but if you want to learn template metaprogramming the most likely explanation is you are nuts. Plain and simple.

Practical uses? Not really. Yeah, there are some (if you are a boost developer) and lets you write some neat stuff, but in your every day job you are most likely never going to use them. And that is a good thing ™, for mere mortal programmers tend to like getting their jobs done. Having said that, let’s learn some template metaprogramming!

Metawhat?

First, we need to start with a little clarification: using template <class T> to parametrize a class, something like std::vector does, is not template metaprogramming. That’s just a generic class (Java-pun intended). That is indeed a useful case for templates, but it has little fun in it.

Template metaprogramming is much more fun than mere generic classes. The template processing in C++ is a language on it’s own (no, really, like a Turing complete language and everything), though a language with very weird syntax and a very strange “design”. Design between quotes because there was no design in its initial stages, template processing is a sub-language organically grown as a side effect of adding partial templates specialization (more on this later), so don’t expect a nice language. Here, let me show you an example of another organically grown language: Microsoft’s .bat scripting. You can imagine now what kind of beast this is if we are comparing it to bat scripts, right? (Nitpickers note. yup, I do know bat scripting is not a real language as it’s not Turing complete. The comparison still stands though).

cpp

First step

Enough chatter. Let’s start with a sample program and work our way down from there:

#include <iostream>

template <int N> struct Factorial {
 static const int result = N * Factorial<N-1>::result;
};

template <> struct Factorial<0> {
 static const int result = 1;
};

int main() {
 std::cout << Factorial<5>::result << "\n";
 return 0;
}

Whoa. Lots of magic going on there, on the simplest of all template metaprogramming tricks. But I don’t feel like explaining it right now, I’m too sleepy, so I will leave that for next post.

—————————————————————————————

Template metaprogramming II: Opening the box

We saw last time how to print a factorial using only template metaprogramming, but didn’t explain anything about it. I promised to fix that in this article. Starting by the very beginning:

template <int N> struct Factorial {
	static const int result = N * Factorial<N-1>::result;
};

template <> struct Factorial<0> {
	static const int result = 1;
};

#include <iostream>
int main() {
	std::cout << Factorial<5>::result << "\n";
	return 0;
}

Why static const?

Templates get evaluated on compile time, remember? That means all that code actually executes when compiling the source, not when executing the resulting binary (assuming it actually compiles, of course). Having as a constraint the fact that all your code must resolve on compile time means only const vars make sense. Also, as you’re working with classes (templates are applied to classes, not objects) only static objects make sense.

That explains the static const thing, what about the Factorial<0>? Well it’s obviously an edge case. It describes a specific case of a Factorial. It’s a specialization! Why do we need it? Take a look again at the definition of struct Factorial: it’s a recursive definition. How do we break from the recursive loop? With a base case, obviously.

mystery5

If this is starting to remind you of anything then you are crazier than you think, and you already know some Haskel. Indeed, template metaprogramming has some resemblance to Haskel programming: no “variables”, no for-loop (only recursion), base cases (pattern matching), and cryptic error messages which makes you want to jump of a cliff.

A useful trick I learned when working with Haskel (many many years ago) is to declare the problem, instead of thinking it. For our problem the factorial of a number is defined as said number times the factorial of that same number minus one, being the factorial of 0 always 1.

Translating:

// the factorial of a number is defined as said number times
// the factorial of that same number minus one

template <int N> struct Factorial {
	static const int result = N * Factorial<N-1>::result;
};

// being the factorial of 0 always 1.
template <> struct Factorial<0> {
	static const int result = 1;
};

That’s good for a first approach… next time something more complex (and less theory, promise).

John William Waterhouse, Pandora, 1896

—————————————————————————————

Template metaprogramming III: Entering Pandemonium

If you are here and you have read the previous two parts then you are crazy. If you haven’t then go and read it, then never come back if you value your sanity at all. We saw last time an example of a factorial using template metaprogramming, now it’s time for something a little bit more fun. I was thinking on lists, but that’s a bit too much for starters: let’s do some more math. Now with fractions!

hellish-04

So, how would you express a fraction? The fun part, and you already know this, you have only types (*), there are no variables. Luckily static const int saves the day:

template <int N, int D> struct Frak {
	static const long Num = N;
	static const long Den = D;
};

Woo hoo… how boring, let’s do something on those Fraktions, so they don’t get bored… like multiplying:

template <int N, typename X> struct ScalarMultiplication {
	static const long Num = N * X::Num;
	static const long Den = N * X::Den;
};

Well that does the job, I guess, but it’s ugly. Too ugly… why would we redefine a Fraction when we already have a great definition? Let’s try again:

template <int N, typename F> struct ScalarMultiplication {
	typedef Frak<N*F::Num, N*F::Den> result;
};

OK, now you think I’m pulling your leg, but, promise, I’m not. This actually works, and it looks nice! Check out that sexy typedef: you can’t have variables, we said, so instead we return types. Frak is a type when binded to two concrete values, so Frak is a type too. Just typedef it to a result and be done with it.

How do we test if it worked? Easy:

int main() {
  typedef Frak< 2, 3 > Two_Thirds;
  typedef ScalarMultiplication< 2, Two_Thirds >::result Four_Sixths;
  std::cout << Four_Sixths::Num << "/" << Four_Sixths::Den << "\n";
}

Nice! By now you should have learned how to return new types, which are the result types for template metaprogramming devices. You should have also learned how to write a device which operates on another template device… congratulations, that’s metaprogramming. Next time, something a little bit more interesting.

pandemonium

(*) Boring theory rant: What do I mean you can’t have return values so you must use types instead? Let’s see: a variable or an attribute are both parts of an object. If I have a variable named height in a class named Person, then each person gets his own height. Even if the numeric value is the same there won’t be two shared height attributes. On the other hand static const vars are defining parts of classes, not objects; stupidity could be static const var of Person and in that case we’d all be equally stupid!

Knowing the difference between an object and a class defining characteristics, it is clear we can only use static const stuff – it’s nonsense talking about template-objects, it’s all about template classes!

—————————————————————————————

Template metaprogramming IV: Nightmares to come

By now you should have noticed the warnings were not in vain: we are exploring a bizarre side of C++ here, a side many people prefer to, wisely, ignore. Luckily it probably is too late for you, there is no way back. Only a long spiraling way down into the arms of despair and cryptic compiler error messages… mwahahahaha. But now, let’s see where we are.

vampires-nosferatu

In previous entries we learned how to return values, how to define recursive devices and how to provide a partial specialization. Let’s see know how can we use partial specialization and complex return type definitions for some more fun template metaprogramming tricks. We had a fraction and a ScalarMultiplication operation for Frak:

template <int N, int D> struct Frak {
        static const long Num = N;
        static const long Den = D;
};

template <int N, typename F> struct ScalarMultiplication {
	typedef Frak<N*F::Num, N*F::Den> result;
};

In previous entries we learned how to return values, how to define recursive devices and how to provide a partial specialization. Let’s see know how can we use partial specialization and complex return type definitions for some more fun template metaprogramming tricks. We had a fraction and a ScalarMultiplication operation for Frak:

Let’s try to add an operation to simplify a Fraction. Simplify< Frak<2, 4> > should return 1/2. Mph… simplifying a fraction means dividing it by the MCD. A quick trip to Wikipedia reveals a nice recursive way to implement an MCD device:

template <int X, int Y>	struct MCD {
        static const long result = MCD<Y, X % Y>::result;
};

template <int X> struct MCD<X, 0> {
        static const long result = X;
};

I won’t get into much detail as the link explains it a lot better than whatever I could try, but do take a look at the definition of MCD<X, 0>: that’s a partial specialization. No magic there. Back to our simplifying device, we now have all the parts for it. Going back to it’s definition we can see that simple(fraction) = fraction / mcd(fraction). Then:

template <class F> struct Simpl {
        static const long mcd = MCD<F::Num, F::Den>::result;
        static const long new_num = F::Num / mcd;
        static const long new_den = F::Den / mcd;
        typedef Frak< new_num, new_den > New_Frak;
        typedef New_Frak result;
};

Quite a mouthful, but a lot simpler than what you think as there is a lot of unnecessary code there. Until new_num and new_den, no surprises. Typedeffing a Frak is not new, either. typedef typename is something new: typename tells the compiler you’re referring to a name inside a template class, otherwise it’d try to refer to a static variable inside said class (*). Knowing what each thing does we can simplify it:

template <class F> struct Simpl {
        static const long mcd = MCD<F::Num, F::Den>::result;
        typedef Frak< F::Num / mcd, F::Den / mcd > result;
};

It is a matter of style really. In this case I’d rather use the second one because it matches better its colloquial definition, but if you think the first one is more readable go with it… it doesn’t really matter though, no one will ever even try to read this kind of code if you intend to use it in a real application.

fuseli_nightmare400

Next time: a “useful” (**) and complete template metaprogramming device, using the complete toolset we’ve been learning in this crazy templating series.

(*) Think of it this way:

struct Foo {
   typedef int Bar;
   Bar bar;
};

In a template you don’t know if Bar is a typename or varname because there’s no access to the specific template definition.
As a rule of thumb, if the compiler complains then add typenames.

(**) Results may vary according to your definition of useful.

—————————————————————————————

Template metaprogramming V: Face to face

By now we have learned the basics for a nice template metaprogramming toolkit:

  • Loops with recursive template definitions
  • Conditionals with partial template specializations
  • Returns using typedefs

Unfortunately that’s all you need for a Turing complete language, meaning now we have the power, bwahahaha! Mph, I’m sorry, back on topic, it means we can now create a fully functional and useful template metaprogramming device… to calculate fractions at compile time, nonetheless. Oh, you think that’s not useful? Well though luck, that’s all we’ll do for now:

template <int N, int D> struct Frak {
        static const long Num = N;
        static const long Den = D;
};
 
template <int N, typename F> struct ScalarMultiplication {
    typedef Frak<N*F::Num, N*F::Den> result;
};
 
template <int X, int Y>   struct MCD {
        static const long result = MCD<Y, X % Y>::result;
};
 
template <int X> struct MCD<X, 0> {
        static const long result = X;
};
 
template <class F> struct Simpl {
        static const long mcd = MCD<F::Num, F::Den>::result;
        typedef Frak< F::Num / mcd, F::Den / mcd > result;
};
 
template <typename X1, typename Y1> struct SameBase {
    typedef typename ScalarMultiplication< Y1::Den, X1>::result X;
    typedef typename ScalarMultiplication< X1::Den, Y1>::result Y;
};
 
template <typename X, typename Y> struct Sum {
    typedef SameBase<X, Y> B;
    static const long Num = B::X::Num + B::Y::Num;
    static const long Den = B::Y::Den; // == B::X::Den
    typedef typename Simpl< Frak<Num, Den> >::result result;
};

I’m sure you can figure out how to implement other arithmetic operations now. Useful, isn’t it? No? Ok then… let’s think of something even more useful. For example, trying to calculate e. I sure get tired of looking up in Google the value for e every time I need an e in my code. Not anymore!

template <int N> struct Fact {
    static const long result = N * Fact<N-1>::result;
};
template <> struct Fact<0> {
    static const long result = 1;
};

template <int N> struct E {
    // e = S(1/n!) = 1/0! + 1/1! + 1/2! + ...
    static const long Den = Fact<N>::result;
    typedef Frak< 1, Den > term;
    typedef typename E<N-1>::result next_term;
    typedef typename Sum< term, next_term >::result result;
};
template <> struct E<0> {
    typedef Frak<1, 1> result;
};

int main() {
  typedef E<8>::result X;
  std::cout << "e = " << (1.0 * X::Num / X::Den) << "\n";
  std::cout << "e = " << X::Num <<"/"<< X::Den << "\n";
  return 0;
}

Looking nice, isn’t it? You should have all what’s needed to understand what’s going on there. Even more, almost everything has been explained in previous articles, with the exception of EqBase. But that’s left as an exercise for the reader because the writer is too lazy.

cthulhu

If you think any part of the code requires clarification ask in the comments. Next, a long overdue topic: lists using template metaprogramming. Guaranteed to blow your mind into little pieces!

—————————————————————————————

Template metaprogramming VI: The Spider Webb

We have been building our template meta-foo for five chapters now, and I think we are ready to move on to more advanced topics. We will be borrowing a lot more from functional languages from now on, so you may want to actually start practicing some template metaprogramming to keep advancing.

spider

In our previous entries we worked with basic building blocks, making it quite easy to keep in mind the whole “program flow”. Now it won’t be so easy anymore, as we’ll be using real metaprogramming (i.e. templates operating on templates) so a lot more thought will be needed for each program.

Another point to keep in mind, you don’t have a debugger here. All the magic occurs at compile time so there is no gdb to step through your program to find a logic flaw. There’s a little trick to check if you are too far off from the target but, mainly, you’ll have to think for yourself. I’ll talk about this trick later on.

Let’s start with any functional programming course basics: lists. We have to think, first, how can a list make any sense when you only have types and no values. It means you can have a list like “int, char, void**, Foo”, and not something like “1, 2, 3”. Or, can you? There’s a way to trick the compiler into creating a type from a integral value:

template <int N> struct Int {
	static const int value = N;
};

Voila! Now you can create a list of numbers. For our next trick, let’s implement the list itself. No pointer magic, think of a functional definition of a list. Come on, I’ll wait… ready? OK, a list is a tuple T of two values, in which the first element, called head, is the first element of the list and the second element, called tail, is either a list or the NULL element.

Quite a mouthful… let’s go over that definition again:

// A list is a tuple T of two values
List: [ ..., ... ]

// in which the first element, called head, is the first element of the list
List: [ Head, ... ]

// and the second element, called tail,
List: [ Head, Tail]

// is either a list or the NULL element
List: [ Head, Tail]
Tail: List | Nil

So, as an example, a list of numbers could be expressed as:

	List( 1, List( 2, List( 3, NIL ) ) )

Closing up… how would you define this list in C++? Easy:

template <typename H, typename T> struct Lst {
	typedef H Head;
	typedef T Tail;
};

We need here a NIL type to use as a list ending element. We could also use a default template type, so we won’t have to write the last NIL to end a list definition. Thus we have now:

struct NIL {
	typedef NIL Head;
	typedef NIL Tail;
};

template <typename H, typename T=NIL> struct Lst {
	typedef H Head;
	typedef T Tail;
};

Nice. You should remember the following rules:

  1. We can use template to define a template class, defining a new type based on a number instead of another type 😉
  2. We can’t “store” a value in a type… unless we store it as a static value, that is.
  3. Using a convention for defining result holding variable names is very useful, as there are no interfaces and more than once we’ll be using a result from an unknown class

With that said, let’s translate the list (1, 2, 3) to Tmpl C++

template <int N> struct Int{ static const int result = N; };

typedef Lst< Int<1>, Lst< Int<2>, Lst< Int<3> > > > OneTwoThree;

Not so bad to start with. Next time we’ll be doing something a little bit more useful with this list.

One last note, initializing a static const int in the definition of the class may be non portable (some compilers seem to have trouble with it). An enum may be used instead.

cthulhu

—————————————————————————————

Template metaprogramming VII: The Enemy Within

Remember where were we last time? We had this code to define a list:

struct NIL {
	typedef NIL Head;
	typedef NIL Tail;
};

template <typename H, typename T=NIL> struct Lst {
	typedef H Head;
	typedef T Tail;
};

template <int N> struct Int{ static const int result = N; };
typedef Lst< Int<1>, Lst< Int<2>, Lst< Int<3> > > > OneTwoThree;

Now, to increase our template-foo, let’s practice some basic operations. The same operations you would implement to practice your skill any other functional language. If I remember correctly these where useful when learning Haskel: getting a list’s length, getting the Nth element, appending and prepending elements… that sort of stuff.

enemy_within_1

Let’s start with the most basic: getting the length of a list. We don’t really have a for loop so using recursion is the only way. It gets easier if we think again on our definition of list: “think of a list as tuple, two elements, the first (called head) will be the first element of the list and the second element as another list or a NIL object”. Whit this definition of a list, then it’s length turns to be 1 (the head) + the length of the remaining list (the tail), with a special case for the length of a NIL object which should always be 0. In template-speak:

template <typename LST> struct Length {
	typedef typename LST::Tail Tail;
	static const unsigned int tail_length = Length< Tail >::result;
	static const unsigned int result = 1 + tail_length;
};

template <> struct Length<NIL> {
	static const unsigned int result = 0;
};

I know. You are thinking “wait, what?”. Well, even for this basic case we need to use some esoteric language features:

  • typename is needed to tell the compiler LST::Tail is a type and not a static variable (like Length::result is). Did you remember that from chapter IV?
  • We have to use recursive templates, but you probably already figured that out. You should remember this from chapter II.
  • We must provide a specialization of a template. You should also remember this from chapter II.

Obviously, you can write it this way too:

template <typename LST> struct Length {
	static const unsigned int result = 1 + Length< typename LST::Tail >::result;
};

template <> struct Length<NIL> {
	static const unsigned int result = 0;
};

The rest of the “basic” list-operations are quite similar, but I’ll leave that for another post.

Space-Dog-The-Enemy-Within-star-trek

—————————————————————————————

Template metaprogramming VIII: A Rough Whimper of Insanity

Remember last time? We learned how to get the lenght of a list. This time I’ll introduce some more of these basic ops. Let’s begin with “Nth”: getting the Nth element of a list; which, remember, in this case is a type, not a concrete element. This means the Nth element will be something like int, char, const char*, not 1, 2 or 3. We introduced a trick to get around this limitation before using a template <int>, go there to refresh your memory if needed.

manson1a

So, what would the coloquial definition of “Nth” be? I’d put it like “The operation Nth for a list equals the head of the list for N = 0 and Nth (minus one) of the tail otherwise”. A little bit more formally:

Nth(0, lst) <- lst.head
Nth(n, lst) <- Nth(n-1, lst.tail)

Translating this to C++ should be a breeze to you now. Try it, I’ll wait. Ready? OK, this is MY answer:

template <typename LST, int N> struct Nth {
	typedef typename LST::Tail Tail;
	typedef typename Nth<Tail, N-1>::result result;
};

template <typename LST> struct Nth<LST, 0> {
	typedef typename LST::Head result;
};

Though the structure is very similar to the previous “basic operation”, getting the length of a list, the concept is quite different. This time we’re defining a return type recursively. Try it out. Beware: if you want to print an element you’ll need something like “Nth::result”. If you are using the Int class we defined somewhere above, “Nth::result” will yield “Int”, and you can’t do “cout << Int << endl;”. You’ll need an extra “::result” in there. Try to think why that’s needed yourself.

Finally, think of another caveat of the Nth template device: what happens if you specify an element which is out of range? This is also an easy answer, and you can check it yourself by running “Nth< Lst, 42>”.

Anyway, that was too easy. Let’s try a more complex operation now.

How can we check if an element exists on a list? Seems easy enough, an element is included in a list if the head equals the element itself or if the element is included in the tail. In the pseudo language I just invented:

Includes(lst.head, lst) <- true
Includes(e, lst) <- Includes(e, lst.tail)

Looks easy, right? Well, there’s a bug there, can you spot it? Yeah, we’re missing the false condition. We should add a third specialization:

Includes(lst.head, lst) <- true
Includes(e, NIL) <- false
Includes(e, lst) <- Includes(e, lst.tail)

Again, let’s translate the pseudocode to C++. Try it, I’ll wait. Ready? OK, this is MY answer:

template <class Elm, class LST> struct Includes {
	typedef typename LST::Head Head;
	typedef typename LST::Tail Tail;

	static const bool found = (Elm == Head);
	static const bool found_tail = Includes<Elm, Tail>::result;
	static const bool result = found || found_tail;
};

template <class Elm> struct Includes <Elm, NIL> {
	static const bool result = false;
};

Looks nice, doesn’t it? Too bad it won’t work, you can’t compare two types. What would (int == char) mean in C++? We need a helper there, some kind of trick to compare two types. We can use partial template specialization again:

template <class X, class Y> struct Eq { static const bool result = false; };
template <class X> struct Eq<X, X> { static const bool result = true; };

With this little struct now we can write our include operation this way:

template <class Elm, class LST> struct Includes {
	static const bool result = Eq<Elm, typename LST::Head>::result ||
				                     Includes<Elm, typename LST::Tail>::result;
};

template <class Elm> struct Includes<Elm, NIL> {
	static const bool result = false;
};

Very esoteric looking, the right mix of Haskel, C++ and booze to ensure job security for life. Next time we’ll find a way to search for the position of an element, a somewhat more complicated task.

—————————————————————————————

Template metaprogramming IX: Absolute Zero

By now we should have learned how to perform loops, branching and returns using templates. Let’s add a couple of useful operations to our library: append and prepend.

novaAbsoluteZero_main_image

Prepending an element to a list is very easy: the result is a list (oh surprise) consisting of a head (the element we want to add) and a tail (the old list). In the pseudocode I’ve been using so far:

Prepend(e, lst) <- LST(e, lst)

And in C++ (trivial, this time):

template <typename Elm, typename LST=NIL> struct Prepend {
	typedef Lst<Elm, LST> result;
};

Appending is a little bit more difficult, as we need to first find the end of the list. Think for a second how would you define it… back? Ok, I’d define it this way: appending an element to the list yields a list, consisting of the same head and the result of appending said element to the tail. The null case, as usual, is appending an element to a NIL list; in this case the result is a list with the element itself. So:

Append(e, NIL) <- LST(e)
Append(e, lst) <- LST(lst.head, Append(e, lst.tail))

Looks complicated but it follows the same structure as the rest of the basic-ops:

template <class Elm, class LST> struct Append {
	typedef typename LST::Head Head;
	typedef typename LST::Tail Tail;

	typedef typename Append<Elm, Tail>::result Next;
	typedef Lst<Head, Next> result;
};

template <class Elm> struct Append<Elm, NIL> {
	typedef Lst<Elm> result;
};

Easy. Now, what happens if we want to add a default value for Lst, so we can use Append to create lists? Easy too, but we need a façade this time; just rename Append to _Append, then

// This is here just because I wanted a default param 😀
template <typename Elm, typename Lst=NIL> struct Append {
	typedef typename _Append<Elm, Lst>::result result;
};

I promised to add one more operation to our toolbox, returning the position of an element, but this post is getting quite long and I’m afraid it may be too much for the average attention span of a programmer… we’ll leave it for next time.

vampires-nosferatu

—————————————————————————————

Template metaprogramming X: Zero Minus Ten

So far we’ve learned the basic constructs of template metaprogramming (loops, branching, return values) and some basic list operations (getting the length of a list, appending and prepending elements, checking if an element is included in a list). Let’s put it all together by creating an operation to return the position of an element. It’ll be very useful later on too.

Essenpreis2

If we go back to the Includes operation we can get some help to define the Position operation: the position of an element in a list is one plus the position of the element we’re searching for in the tail, or zero if the head equals said element. The operation is not defined if the element is not in the list.

Translating to pseudo-code:

Position (lst.head, lst) <- 0
Position (e, lst) <- 1 + Position(e, lst.tail)

The translation to C++ is not so trivial this time. Try it, I’ll wait… ready? OK, let’s start

template <class Elm, class Lst> struct Position {
	typedef typename Lst::Head Head;
	typedef typename Lst::Tail Tail;
	static const bool found = (Head == Elm);
	static const int result = found? 0 : 1 + next;
	static const int next = Position<Elm, Tail>::result;
};

Looks easy… but doesn’t work. First problem, we can’t compare two types, remember? We need to use Eq<X, Y> again. Second problem, although we said the operation is undefined if the element is not included on the list, it would be nice if we could force the compiler to fail if (or when) that happens. Otherwise the user will face a horrible compiler error saying something along the lines of “template instantiation depth exceeds maximum”. Let’s rewrite the operation using a façade again, but adding an Assert:

template <typename Elm, typename LST> struct _Position {
	typedef typename LST::Head Head;
	typedef typename LST::Tail Tail;

	static const bool found = Eq<Elm, Head>::result;
	static const int result = (found)? 0 : 1 + _Position<Elm, Tail>::result;
};

template <typename Elm, typename LST> struct Position {
	typedef typename Assert<Includes< Elm, LST >::result>::check include;
	static const int result = _Position<Elm, LST>::result;
};

Oh, we haven’t defined assert yet! There’s another problem, too: even if it won’t compile, the compiler will try to expand _Position< …, NIL > indefinitely, causing an error after too many nested template calls. Not nice. We need to add a case to make the compiler stop:

/******************************************************/

// Helper: Will fail to compile if the assert is false
class Assertion{};
template <bool cond, class T=Assertion> struct Assert {
	typedef typename T::fail check;
};
template <> struct Assert<true> {
	typedef void check;
};

/******************************************************/

template <typename Elm, typename LST> struct _Position {
	typedef typename LST::Head Head;
	typedef typename LST::Tail Tail;

	static const bool found = Eq<Elm, Head>::result;
	static const int result = (found)? 0 : 1 + _Position<Elm, Tail>::result;
};

// The compiler will try to expand the position check
// after NIL has been reached if this isn't here
template <typename Elm> struct _Position<Elm, NIL> {
	static const int result = 0;
};

template <typename Elm, typename LST> struct Position {
	typedef typename Assert<Includes< Elm, LST >::result>::check include;
	static const int result = _Position<Elm, LST>::result;
};

All that code for such a simple operation, man. Also, see what we did with Assert<>? It seems making a compile fail is actually quite easy. That’s what I have most experience with. The compiler error a user will get is not very nice, though. Probably something like “No type fail in Assertion”. You can make that error much more explicit by using a more descriptive name as the second template argument to Assert.

We’ve been through quite a lot, and our toolboox should be quite big already. Next time we’ll start steering towards some sort of applicability, trying to use some of all these stuff to implement a real, useful and working program… assuming that’s even possible.

—————————————————————————————

Template metaprogramming XI: Hidden Agenda

Wow, number eleven already. We’re getting more chapters here than Final Fantasy games. I didn’t even imagine there was so much to write about such an esoteric language features like templates. I do wonder if anyone will actually read it, but that’s a completely different problem.

malboro

Enough meta-meta talk: what can we do with all the things we have learned? We can calculate pi and e, we already showed that as an example on one of the first chapters. This chapter I’m going to write about what motivated me to explore the bizarre underworld of template metaprogramming. Some time ago I had to work with a Berkeley DB researching the feasibility of developing a magic cache for (real) DB table. Leaving aside the discussion of whether this is a good idea (the project did have a good reason to be researched) I hit a major roadblock when trying to provide a façade for every table; something like this:

virtualtemplate

See the problem? To do something like that we’d need a virtual template method, and you can’t have that. After seeing that I thought to myself “Hey, I’ll use templates!”. Then I had two problems, but the damage was done, I couldn’t go back. What kind of contorted device could we implement to make such a devious requirement work? I’ll leave you to think it, the answers I came up with next week.

—————————————————————————————

Template Metaprogramming XII: You Really Got a Hold on Me

Remember our virtual template method problem, from the other time? (I know, I said the answer was scheduled for a week after that post, but then I just forgot about it). May be we could avoid the virtual part by keeping a list of all our caches… how would we know which one should we dispatch the message to? Easy, using templates.

Instead of a list let’s keep two, for twice the fun. One for the rows cache, another for the PKs. We can use PK to know which ROW Cache should we choose. Let’s try to write a pseudo code for it:

ROW get_row(PK id) {
    pos <- Position of PK in pks_lst
    return cache[ pos ].get_row( id )
}

Doesn’t look too hard. Building on our previous toolbox, let’s use Eq, Position and the definition of a list:

struct NIL {
    typedef NIL head;
    typedef NIL tail;
};

template < class H, class T=NIL> struct Lst {
    typedef H head;
    typedef T tail;
};

template <class X, class Y> struct Eq { static const bool result = false; };
template <class X> struct Eq<X, X> { static const bool result = true; };

template <class Elm, class LST> struct Position {
    private:
    typedef typename LST::head H;
    typedef typename LST::tail T;
    static const bool found = Eq<H, Elm>::result;
    public:
    static const int result = found? 1 : 1 + Position<Elm, T>::result;
};

template <class Elm> struct Position<Elm, NIL> {
    static const int result = 0;
};

class Facade {
    typedef Lst<int, Lst<char, Lst<float> > > Lst;

    public:
    template <class PK> int find(PK) {
        return Position< PK, Lst >::result;
    }
};

#include <iostream>
using std::cout;

int main() {
    Facade f;
    std::cout << f.find(1.0) << "\n";
    return 0;
}

Great, now we can find an element on a list of types. The real virtual dispatch for the next entry 😀

—————————————————————————————

Template Metaprogramming XIII: Heart of Darkness

Last time we had a virtual template dispatch problem… we got to the point of knowing which was the index of the cache we were searching for, now we need to actually retrieve an instance of that cache. That’s a problem. Why? To begin with, there are no instances, only types!

The next logical step would be to create a Map device, to map a list of types to a list of instances… let’s see how can we do that, in pseudocode

instances( H|T ) <- [ create_instance(H), instances(T) ]
instances( NIL ) <- NIL

Looks easy. How can we map that to c++?

template <class Lst> struct Instance {
    typedef typename Lst::head Elm;
    Elm instance;
    Instance< typename Lst::tail > next;
};
template <> struct Instance<NIL> {};

#include <iostream>
using std::cout;

int main() {
    typedef Lst<int, Lst<char, Lst<float> > > Lst;
    Instance<Lst> lst;
    lst.instance = 1;
    lst.next.instance = 'a';
    lst.next.next.instance = 3.1;
    std::cout << lst.next.instance << "\n";
    return 0;
}

All those next.next.next.instance look ugly. Let’s use some more meta-magic to get the Nth instance (why not a [] operator? several reasons, you can’t mix non-const ints with templates nicely, there would be problems to define the return type… all those options are workable but it’s easier if we do this in another device.

template <typename LST> struct Nth {
	typedef typename LST::tail Tail;
	typedef typename Nth::result result;
};
template <typename LST> struct Nth {
	typedef typename LST::head result;
};

Remember that one from the toolbox? Now we know how to get a specific index position, yet getting the instance is a different problem (the Nth device returns a type, not an instance). We should do something different, the problem is knowing the return type. What’s the return type for the Nth instance of the Instances list?

   type <- Nth(TypesLst, Type)
   type var <- NthInstance(InstancesLst, N)

Not so easy, right? This is the translated C++:

template <int N, typename TypeLst> struct NthInstance {
    // This one isnt easy...
    
    // This is the next type in the list
    typedef typename TypeLst::tail TypeNext;

    //  * Nth::result is the Nth type in Lst (i.e. char, int, ...)
    typedef typename NthInstance<N-1, TypeLst>::NthInstanceType NthInstanceType;

    //  * typename Nth::result & is a reference to said type and the ret type
    template <InstancesLst>
    static NthInstanceType& get(InstancesLst &instances_lst) {
        return NthInstance::get(instances_lst.next);
    }
};

// Remember, just for fun we choose a 1-based system (wtf..)
template <typename TypeLst> struct NthInstance<1, TypeLst> {
    typedef typename TypeLst::head NthInstanceType;

    template <InstancesLst>
    static NthInstanceType& get(InstancesLst &instances_lst) {
        return instances_lst.instance;
    }
};

And the code from fetching the instance itself is even more difficult, so I’ll leave that for next time.

—————————————————————————————

Template Metaprogramming XIV: Marathon

If you remember previous entry, we got our evil device to the point of getting a specific instance using only a type hint. Now we need to put all the code together. I won’t add much to the code, you should be able to parse it yourself.

/***********************************************/
struct NIL {
    typedef NIL head;
    typedef NIL tail;
};

template <class H, class T=NIL> struct Lst {
    typedef H head;
    typedef T tail;
};
/***********************************************/

/***********************************************/
template <class X, class Y> struct Eq { static const bool result = false; };
template <class X> struct Eq<X, X> { static const bool result = true; };
/***********************************************/

/***********************************************/
template <class Elm, class LST> struct Position {
    private:
    typedef typename LST::head H;
    typedef typename LST::tail T;
    static const bool found = Eq<H, Elm>::result;
    public:
    static const int result = found? 1 : 1 + Position<Elm, T>::result;
};

template <class Elm> struct Position<Elm, NIL> {
    static const int result = 0;
};
/***********************************************/


/***********************************************/
template <typename LST, int N> struct Nth {
	typedef typename LST::Tail Tail;
	typedef typename Nth<Tail, N-1>::result result;
};

template <typename LST> struct Nth<LST, 0> {
	typedef typename LST::head result;
};
/***********************************************/


/***********************************************/
template <typename Lst> struct Instances {
    typedef typename Lst::head Elm;
    Elm instance;
    Instances<Lst::tail> next;
};
template <> struct Instances<NIL> {};
/***********************************************/


/***********************************************/
template <int N, typename TypeLst> struct NthInstance {
    // This one isnt easy...
    
    // This is the next type in the list
    typedef typename TypeLst::tail TypeNext;

    //  * Nth::result is the Nth type in Lst (i.e. char, int, ...)
    typedef typename NthInstance<N-1, TypeLst>::NthInstanceType NthInstanceType;

    //  * typename Nth::result & is a reference to said type and the ret type
    template <InstancesLst>
    static NthInstanceType& get(InstancesLst &instances_lst) {
        return NthInstance::get(instances_lst.next);
    }
};

// Remember, just for fun we choose a 1-based system (wtf..)
template <typename TypeLst> struct NthInstance<1, TypeLst> {
    typedef typename TypeLst::head NthInstanceType;

    template <InstancesLst>
    static NthInstanceType& get(InstancesLst &instances_lst) {
        return instances_lst.instance;
    }
};
/***********************************************/


class Facade {
    typedef Lst<int, Lst<char, Lst > > Lst;
    Instances<Lst> instances;

    public:
    template <typename PK> int find(PK) {
        return Position<PK, Lst>::result;
    }

    template <typename PK>
    // This is a difficult one... it should be parsed like this:
    //  1) Get the desired instance position using Position::result 
    //  2) Get the type @ the desired position with NthInstance::Type
    //  3) Define said type as a return type (with an & at the end, i.e. make
    //      it a reference to the return type)
    typename NthInstance< Lst, Position::result >::NthInstanceType&
    get_instance(PK) {
        const int idx_position = Position<PK, Lst>::result;
        typedef typename NthInstance<idx_position>::NthInstanceType IdxType;
        IdxType &idx = NthInstance<idx_position>::get( instances );
        return idx;
    }
};

#include <iostream>

int main() {
    Facade f;
    int &a = f.get_instance(1);
    char &b = f.get_instance('a');
    float &c = f.get_instance(1.0);
    a = 42; b = 'n'; c = 4.2;
    std::cout << f.get_instance(1) << "\n";
    std::cout << f.get_instance('a') << "\n";
    std::cout << f.get_instance(1.0) << "\n";
    a = 43; b = 'm'; c = 5.2;
    std::cout << f.get_instance(1) << "\n";
    std::cout << f.get_instance('a') << "\n";
    std::cout << f.get_instance(1.0) << "\n";
    return 0;
}

The only thing missing now is a map, to convert a primitive type to an index type, but that’s trivial and so it will be left as an exercise for the reader (?). We just implemented the most evil code in the whole world. Next time, the conclusions.

—————————————————————————————

Template Metaprogramming XV: Gemini

This is the end. My only reader, the end. After 15 chapters of template metaprogramming you should have learned why staying away from them is a good idea, but if you have been following this series then you should know now when and why they could be useful.

These posts were a compendium of mostly isolated data I found during my travels through the depths of metaprogramming tricks, there are books and people much more capable than me if you want to learn more about this subject (Modern C++ Design by Andrei Alexandrescu comes to mind).

The whole idea of having a cache and a virtual template method was nice, but after seeing the result I decided it was best to have a factory method and an IDL. It may not be so l33t, but whoever has to maintain the code after me will be grateful.

darkside

Advertisements

21 Comments on “C++ template metaprogramming introduction”

  1. James says:

    This is fantastic. Apparently some poor soul made a ray tracer using template metaprogramming. I had no clue how that could be done, but after reading this article I better understand how.

  2. troublero says:

    I have played off an on with meta-template programming for some years now. What I missed most from working in C#. But like all knowledge there is a cost. What I think your article misses that the more you use it. the more it will reflect in the image size of the software.

  3. Marie says:

    I may have missed a step but I just don’t understand where the X comes from in this part :
    “Woo hoo… how boring, let’s do something on those Fraktions, so they don’t get bored… like multiplying:
    1 template struct ScalarMultiplication {
    2 static const long Num = N * X::Num;
    3 static const long Den = N * X::Den;
    4 };”

    • Hi Marie, this article has survived many blog migrations so it’s quite possible that some code samples are broken. I’ll take a look at that one, thanks for reporting!

      • Nope, wasn’t the migrations that broke it, just a plain old “author didn’t proof-read” problem. The X in there should actually be a template parameter, like in the example below that one. I fixed it in the article.

  4. Matt says:

    I may be missing something, but shouldn’t ScalarMultiplication only multiply the Numerator instead of multiplying both?

  5. Ashkan says:

    Thank you for your great post. I initially could not compile the program to calculate E! here is a modified working sample:

    template struct Frak {
    static const long Num = N;
    static const long Den = D;
    };

    template struct MCD {
    static const long result = MCD::result;
    };

    template struct MCD {
    static const long result = X;
    };

    template struct Simpl {
    static const long mcd = MCD::result;
    typedef Frak result;
    };

    template struct ScalarMultiplication {
    typedef Frak< Simpl<Frak >::result::Num*F::Num, Simpl<Frak >::result::Den > result;
    };

    template struct SameBase {
    typedef Frak< ScalarMultiplication::result::Num ,(X1::Den / MCD::result)*Y1::Den> X;
    typedef Frak< ScalarMultiplication::result::Num ,(Y1::Den / MCD::result)*X1::Den> Y;
    };

    template struct Sum {
    typedef SameBase B;
    static const long Num = B::X::Num + B::Y::Num;
    static const long Den = B::Y::Den; // == B::X::Den
    typedef typename Simpl< Frak >::result result;
    };

    template struct Fact {
    static const long result = static_cast(N) * Fact::result;
    };
    template struct Fact {
    static const long result = 1;
    };

    template struct E {
    // e = S(1/n!) = 1/0! + 1/1! + 1/2! + …
    static const long Den = Fact::result;
    typedef Frak term;
    typedef typename E::result next_term;
    typedef typename Sum::result result;
    };
    template struct E {
    typedef Frak result;
    };

    #include
    int main() {
    typedef E::result X;
    std::cout << "e = " << (1.0 * X::Num / X::Den) << "\n";
    std::cout << "e = " << X::Num <<"/"<< X::Den << "\n";;
    return 0;
    }

    • Hi Ashkan, thanks for taking the time to fix some of my broken code 🙂
      Unfortunatelly wordpress tends to eat the ‘s, so it won’t really work. I got quite a few complaints about broken code and typos, so I recently took the time to go over the code samples and made sure they compile again. I think most of them should be fixed. If not, just keep complainign!

      • Gamer2015 says:

        I’ll just add this here:

        Your Denominator in V in Sum and therefore also in SameBase are wrong.
        When getting to the same base the bases are usually multiplied so you should end up with these typedefs for R1 and R2 in SameBase (note: ratio is Frak)

        template class SameBase {
        static const long Den = TRatio1::Den * TRatio2::Den;
        public:
        typedef ratio X;
        typedef ratio Y;
        };
        Note that you could simplify them if you want.

  6. Richard says:

    Thank you for the awesome post!

    I found the following ‘NthInstance’ on my visual studio 2010 works:

    template struct NthInstance
    {
    typedef typename TypeList::Tail TypeNext;

    typedef typename NthInstance<N-1, TypeNext>::NthInstanceType NthInstanceType;
    
    
    template <typename InstanceList> 
    static NthInstanceType& get(InstanceList& instances_lst)
    {
        return NthInstance<N-1, TypeNext>::get(instances_lst.next);
    }
    

    };

    In ‘Facade’, the following ‘get_instance’ works:
    template
    typename NthInstance<Position<PK, Lst>::result, Lst>::NthInstanceType&
    get_instance(PK)
    {
    const int idx_position = Position<PK, Lst>::result;
    typedef typename NthInstance<idx_position, Lst>::NthInstanceType IdxType;
    IdxType& idx = NthInstance<idx_position, Lst>::get( instances );
    return idx;
    }

    BTW, I cannot play with the 1-based in ‘NthInstance<1, TypeLst>’ due to compiler crash. It works if revert to 0-based.

    • Thanks for the comment Richard. Crazy stuff with templates is always a good way to test a compiler. Having said that, this article is a bit old so while the general information in it should still be valid there may be differences in newer compilers.

  7. Daniel Strul says:

    Thank you for this amazing tutorial! It allowed me yesterday to write my first ever TMP program… I must say, at some point I concluded I was gone far enough into crazyland and came back to plain old, simple C++ concurrency 😉
    In any case, AFAICS your tutorial remains pretty up-to-date. From what I could gather, there are only two minor points that might be worth updating:
    – You may replace static constants with enums, which are more portable;
    – You may use template aliases: they’re pretty simple to use and make code much more readable.
    I believe this would make this tutorial pretty “modern C++” with regards to the features you describe.

  8. Anonymous says:

    So sad after reading to the final part… Thank you so much! I’ve learnt a lot the same time enjoy reading your humor!

  9. Lauris says:

    Thanks for material!

    I think for Sum there should be:
    static const long Den = B::X::Den * B::Y::Den;
    because SameBase just updates numerator.

    Or fix SameBase to update also denumerator.

  10. Liviu Sandu says:

    First, I must thank you for such a wonderful tutorial.
    Compiling the code from Template Metaprogramming XIV: Marathon didn’t work on Visual Studio 2012. At first sight, IntelliSense points out an error here:

    class Facade {
    typedef Lst<int, Lst<char, Lst > > Lst;

    Error message: argument list for class template Lst is missing.

    This looks sensible, but I am sure there is more than meets the eye. The error may be somewhere else.
    Please, can you help me to get the code compiled? There is a lot to learn from it and it’s a pitty not to.

    Thank you

    • Hi Liviu! Thanks for the kind words.

      It looks like that line is defining a typedef to its own type (so, something like “typedef MyType MyType”). I’m not sure that’s legal C++. Some cases are accepted by gcc.godbolt.org, some are not, but: I don’t want to go dig in the standard now and I don’t have access to a Windows build server anyway, so I’d recommend changing the typedef name, or removing the typedef altogether and simply using the full type name.

      Since that snippet isn’t a particularly good example of proper C++, I’m going to say that the error was caused by the years of refactoring this article, or by extreme carelessness of the author 🙂

  11. Liviu Sandu says:

    Hello Nicolas

    Based on Richard’s notes, I dared to change a bit the code and, in the end, it got compiled under Visual Studio 2012 and worked.

    I copy it below just because I think that, as well as I learned, others like me should learn too.

    The code relies on the structures defined in the previuos posts. Actually, I compiled and ran them ALL in one go. As far as I remember, I didn’t change anything in the code from posts before “Template metaprogramming XI: Hidden Agenda”. If wrong, I can copy all the code I used. The changes would be very small.

    /***********************************************/
    template
    struct Instances
    {
    typename Lst::Head instance;
    Instances next;
    };

    template <>
    struct Instances
    {
    };
    /***********************************************/

    /***********************************************/
    template
    struct NthInstance
    {
    // This one isn’t easy…

    // This is the next type in the list
    typedef typename TypeLst::Tail TypeNext;
    
    //  * Nth::result is the Nth type in Lst (i.e. char, int, ...)
    typedef typename NthInstance<N-1, TypeNext>::NthInstanceType NthInstanceType;
    
    //  * typename Nth::result & is a reference to said type and the ret type
    template <typename InstancesLst>
    static NthInstanceType& get(InstancesLst& instances_lst)
    {
        return NthInstance<N-1, TypeNext>::get(instances_lst.next);
    }
    

    };

    // We choose a 0-based system
    template
    struct NthInstance<0, TypeLst>
    {
    typedef typename TypeLst::Head NthInstanceType;

    template <typename InstancesLst>
    static NthInstanceType& get(InstancesLst& instances_lst)
    {
        return instances_lst.instance;
    }
    

    };
    /***********************************************/

    class Facade
    {
    typedef Lst<int, Lst<char, Lst > > Lst;
    Instances instances;

    public:
    // This is a difficult one... it should be parsed like this:
    //  1) Get the desired instance position using Position::result 
    //  2) Get the type @ the desired position with NthInstance::Type
    //  3) Define said type as a return type (with an & at the end, i.e. make
    //      it a reference to the return type)
    template <typename PK>
    typename NthInstance<Position<PK, Lst>::result, Lst>::NthInstanceType&
    get_instance(PK)
    {
        const int idx_position = Position<PK, Lst>::result;
        typedef typename NthInstance<idx_position, Lst>::NthInstanceType IdxType;
        IdxType& idx = NthInstance<idx_position, Lst>::get( instances );
        return idx;
    }
    

    };

    int main() {
    Facade f;
    int &a = f.get_instance(1);
    char &b = f.get_instance(‘a’);
    float &c = f.get_instance(1.0F);
    a = 42; b = ‘n’; c = 4.2F;
    std::cout << f.get_instance(1) << “\n”;
    std::cout << f.get_instance(‘a’) << “\n”;
    std::cout << f.get_instance(1.0F) << “\n”;
    a = 43; b = ‘m’; c = 5.2F;
    std::cout << f.get_instance(1) << “\n”;
    std::cout << f.get_instance(‘a’) << “\n”;
    std::cout << f.get_instance(1.0F) << “\n”;
    return 0;
    }

  12. Arty McLabin says:

    tag a friend and don’t say anything


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