Subscribe to 10 GOTO 10        RSS Feed
***** 1 Votes

C++ Template Metaprogramming

Icon 11 Comments
Template Metaprogramming

"Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy." --Alan Perlis

Someone requested a tutorial on TMP,however my own understanding of C++ meta-programming is still growing so I am not quite ready to tackle a tutorial. I am only a beginner when it comes to C++ meta-programming and so I welcome comment on what is presented below -- however, I also hope that people find this a useful introduction to meta-programming in C++ (specifically template meta-programming, however some of the challenges I included will require the help of the preprocessor).

First of all what is "Meta Programming"? -- Meta Programming is writing a program that writes a program. This is nothing really new, we do it all the time, every C++ template is actually "meta programming", using the preprocessor is actually "meta programming", writing scripts for a GUI generator is "meta programming" -- so lets add a little something to our definition: Intentionally using features of a language such as the C preprocessor, and C++ templates to produce compiler time (or preprocessor time) programs that generate code. Typically we do this with the purpose of simplifying or optimizing our end code.

Why use meta-programming? Meta programming is used with great effect within the Boost libraries and with often be found in libraries and frameworks that strive for enhanced performance, specialized syntax, or within generic programming for "advanced" specialization.

Who is meta programming for? Its not for the sake of your end user that if for sure. It is for your self or other programmers that may use you code. You meta-programs should strive to increase productivity, or enhance efficiency.

What can you do with meta-programming? C++ templates form a Turing complete computing language, which means that you can (at least in theory) produce any calculation that a computer is capable of doing. That does NOT mean you can write a windows GUI program in TMP -- but it does mean that in theory you could calculate pi to 1000 decimal places.

Template Meta programs are very good at manipulating C++ types, calculating numeric values, and choosing blocks of code to include in a program. They are not terribly adept at manipulating strings (although they can, it is very difficult to do much of anything terribly useful), they are not terribly great at producing output in any form other than code -- so for example making a TMP that displays prime numbers during compile time is possible but not terribly practical.

That kind of language do C++ templates form? C++ templates form a Turing complete declarative language, which is very different from C++ itself and so if you really want to learn the dark arts of TMP you should spend some time in some functional languages like LISP (Scheme, Clojure), and declarative languages like XSTL and SQL (and by these I don't mean the simple surface stuff most of us use on a day to day basis, but really "programming" with them). These kinds of languages require a different way of looking at code - such as a deep understanding of recursion -- did you even know there were several different kinds of recursion?.


What are some basic mechanisms of TMP?
#1. Calculation of constant numerical values. Templates can have two kind of parameters: Types and non-types.

Types are designated by either the keyword typename, or class.

#include<iostream>

template <typename T1, typename T2>
struct CompTypeSize { enum { value = sizeof(T1) > sizeof(T2), }; };

int main() {
    std::cout << "CompTypeSize<short, long>::value = " << CompTypeSize<short, long>::value << std::endl;
    std::cout << "CompTypeSize<long, short>::value = " << CompTypeSize<long, short>::value << std::endl;
    return 0;
}


The other kind of template parameter is a "non-type" which can be either an integral type (an enum, bool, char, int (signed or unsigned), or something that resolves to one. It can not be a floating point type or a class/struct/union type. HOWEVER, a non-type parameter may be a pointer! Most often it will be a function pointer of one kind or another, but it can also be a const char*, note it has to be a right hand value, you can't do something like this:

Myclass<"Hello"> myHello;

So to build upon the last: In this code I use a little bit of logic to select the larger of two types. I already have CompTypeSize<T1, T2> which will return a 1 for T1 being larger, and a 0 for T2, I can then use template specialization to choose between the two types giving me the LargerType<T1, T2, B> template, then finally I can bring the two templates together with GetLargerType<T1, T2> which selects the larger type based upon the return value of CompTypeSize<T1, T2>.

#include<iostream>
#include<typeinfo>

template <typename T1, typename T2>
struct CompTypeSize { enum { value = sizeof(T1) > sizeof(T2), }; };

template <typename T1, typename T2, bool B>
struct LargerType { typedef T1 larger_type; };

template <typename T1, typename T2>
struct LargerType<T1, T2, 0> { typedef T2 larger_type; };

template <typename T1, typename T2>
struct GetLargerType { 
    typedef typename LargerType<T1, T2, CompTypeSize<T1, T2>::value >::larger_type larger_type; 
};


int main() {
    std::cout << "CompTypeSize<short, long>::value = " << CompTypeSize<short, long>::value << std::endl;
    std::cout << "CompTypeSize<long, short>::value = " << CompTypeSize<long, short>::value << std::endl;
    
    GetLargerType<short, long>::larger_type iValue1 = 0;
    GetLargerType<long, short>::larger_type iValue2 = 0;

    std::cout << "typeid(iValue1).name() = " << typeid(iValue1).name() << std::endl;
    std::cout << "typeid(iValue2).name() = " << typeid(iValue2).name() << std::endl;

    return 0;
}


The above program may not be terribly useful but it demonstrates a few things that are important:
#1 Return types: TMP tend to generate outputs in 4 forms two of which are demonstrated above:
  • Templates can return numeric values, generally the enum idiom demonstrated above is used though some times static member variables are used. The enum however ensure that no storage is allocated for "intermediate" results.
  • Templates can return types using typedef. This can be useful to ensure that you select an appropriate type for whatever calculation you need to do (this is usually done by adding "traits" to types, i.e. meta-data about the type).
  • Templates can "return" customized classes -- this is the obvious one, since that is what templates were designed for anyway, but often when people talk about TMP they focus on calculating Fibonacci values, or calculating prime numbers and don't seem to mention that a great deal of power comes from being able to choose what code goes into a class.
  • Templates can "return" pointers. Less useful than the enum idiom (you have to refer to static values which tend to result storage allocation even if they are only used statically within a template).


I am sure that there are other ways in which you can "return" a value from a template, for example you can obviously "return" floating point values, but since they can't also be passed as an argument to a template this is less useful, these are the ones that readily occur to me.

The above program also shows how to use template specialization to preform conditional logic. To program we at least want to know how to take input (input are the arguments to templates), preform conditional branching (template specialization), execute loops (done though template recursion), evaluate integer expressions, and produce an output.

So lets list some common idioms used to build constructs:

Conditionals

I have already shown the basics of using template selection to do conditionals but here are a couple of more variations:

#include<iostream>

//--simple if-else conditional with a return of a type
template <bool cond, typename T1, typename T2> struct IfTypes { typedef T1 return_type; };
template <typename T1, typename T2> struct IfTypes<0, T1, T2> { typedef T2 return_type; };

// -- simple if-else conditional with a return of a number
template <bool cond, int V1, int V2> struct IfInts { enum { value = V1, }; };
template <int V1, int V2> struct IfInts<0, V1, V2> { enum { value = V2, }; };


// -- choose either the max or min value using template conditionals.
#define MIN 0
#define MAX 1
template <int MIN_OR_MAX, int V1, int V2> struct MinMax { 
    enum { 
    _result = V1 > V2,
    value = IfInts< _result, V1, V2>::value 
    }; 
};

template <int V1, int V2> struct MinMax<0, V1, V2> { 
    enum { 
    _result = V1 < V2,
    value = IfInts< _result, V1, V2>::value 
    }; 
};


// -- choose either the max or min valye using an expression
//       Note that you can't do this so easily with types.
template <int MIN_OR_MAX, int V1, int V2> struct MinMax2 { 
    enum { 
    value = MIN_OR_MAX ? 
        ((V1 > V2) ? V1 : V2) 
        : ((V1 < V2) ? V1 : V2)
    }; 
};

int main() {
    //test choosing types
    IfTypes<0, int, long>::return_type v1;
    IfTypes<1, int, long>::return_type v2;
    
    std::cout << typeid(v1).name() << std::endl;
    std::cout << typeid(v2).name() << std::endl;

    //test choosing values
    v1 = IfInts<0, 100, 200>::value;
    v2 = IfInts<1, 100, 200>::value
    std::cout << v1 << std::endl;
    std::cout << v2 << std::endl;

    //test choosing values with template expressions
    std::cout << "min = " << MinMax<MIN, 100, 200>::value << std::endl;
    std::cout << "max = " << MinMax<MAX, 100, 200>::value << std::endl;
   
    //test choosing values with a conditional
    std::cout << "min = " << MinMax2<MIN, 100, 200>::value << std::endl;
    std::cout << "max = " << MinMax2<MAX, 100, 200>::value << std::endl;

    return 0;
}


In the above I tried to demonstrate:
  • The basics of making a conditional template
  • A template can of course "call" another template
  • When evaluating numeric expressions you still have all of the usual operators available, that includes the conditional operator. However there is a big caution! The compiler will "evaluate" or "expand" both conditions! So for example you can not use the conditional operator to end recursion in templates because the compiler will expand both the true and false expressions (the compiler needs to ensure that they are of the same "type" since that is a rule for conditionals, it can only do this if it resolves all templates and works out the resulting type for all expressions).


Exercise: 1.1 Build a switch/case type of template
Exercise: 1.2 Build a function that primitive type (int/double/char etc) vs. a class/structure


Recursion/Loops:

This next template demonstrates two different loops. One calculates powers of numbers at compile time to demonstrate a very naive example, and the other will create static multi-dimentional array types.

#include <iostream>

//--recursive template to calculate a power
template<int X, int Y> struct Power { enum { value = X * Power<X, Y - 1>::value, }; };
template<int X> struct Power<X, 0> { enum { value = 1, }; };

//Utility template to add an extra dimention to a type
template<typename T, int SIZE> struct AddDimention {
    typedef T value_type[SIZE];
};

// -- recursive template to create a multi-dimentional array type.
template <typename T, int SIZE, int DIM> struct MultiDimArray {
    typedef typename AddDimention< typename MultiDimArray<T, SIZE, DIM-1>::value_type , SIZE>::value_type value_type;
    typedef value_type* value_ptr;
};

template <typename T, int SIZE> struct MultiDimArray<T, SIZE, 1> {
    typedef typename AddDimention< T , SIZE>::value_type value_type;
    typedef value_type* value_ptr;
};

int main() {
    MultiDimArray<int, 50, 3>::value_type myInt3D;
    MultiDimArray<int, 30, 3>::value_ptr myInt3Dptr;
    
    std::cout << (sizeof(myInt3D)/sizeof(int)) 
              << " == " 
              << Power<50, 3>::value
              << std::endl;
    
     std::cout << (sizeof(*myInt3Dptr)/sizeof(int)) 
              << " == " 
              << Power<30, 3>::value
              << std::endl;   
    
    return 0;
}


Exercise: 2.1 build a template that returns the LCM of two numbers
Exercise: 2.2 build a template:
AlignedArray<int, SIZE>::value_type
such that the actual size of the array is a multiple of 16 >= SIZE

Exercise: 2.3 build a factorial template (note this is a VERY common example on the web so try not to cheat).
Exercise: 2.4 Build a template to calculate integer Log base 2 + 1 of an integer (how many bits are requires to represent that number).

Code Generation

One use of meta-programming is to simplify inline code for optimizations. For example if you would like to find the cube of x it is more effeciant to calculate x*x*x then std::pow(x, 3) which is forced to use a loop. Here is a simple template for calculating the power of a number

#include <iostream>

template <int N>
struct Power {
    template <typename NUMERIC_TYPE> 
    static inline NUMERIC_TYPE of(const NUMERIC_TYPE& x) { 
        return x * Power<N-1>::of(x); 
    }
};

template <>
struct Power<0> {
    template <typename NUMERIC_TYPE> 
    static inline NUMERIC_TYPE of(const NUMERIC_TYPE& x) { 
        return 1; 
    }
};


int main() {
    std::cout << "Power<5>::of(3) = " << Power<5>::of(3) << std::endl;
    std::cout << "Power<5>::of(3.14) = " << Power<5>::of(3.14) << std::endl;
    std::cout << "Power<5>::of(3) = " << Power<5>::of(3) << std::endl;
    std::cout << "Power<10>::of(0.1) = " << Power<10>::of(0.1) << std::endl;
    std::cout << "Power<2>::of('a') = " << Power<2>::of('a') << std::endl;

    return 0;
}


Exercise: 3.1 Write a template to find the value of Ax*x + Bx + C where A, B, C are integer template parameters and x is a variable of a numeric type.


TMP Data Structures

Although there are some limitations it is possible to create some interesting data structures during compile time. Here is a simple example of creating a link-list like structure to store a series of values:
#include <iostream>

struct END { };

template <int Value, typename List = END> struct Node {
    enum { value = Value, };
    typedef List next;
};

//construct a static list of nodes
typedef Node<1, Node<1, Node<2, Node<3, Node<5, Node<8, Node<13, Node<21> > > > > > > > FibList;

//Template to get at values
template<int N> struct GetFib { 
    typedef typename GetFib<N-1>::type::next type;
    enum { value = GetFib<N-1>::type::value, };
};

template<> struct GetFib<0> { 
    typedef FibList type;
    enum { value = FibList::value, };
};

template<typename NodeList> struct CountNodes {
    enum { value = 1 + CountNodes<NodeList::next >::value, };
};

template<> struct CountNodes<END> {
    enum { value = 1, };
};

int main() {
    std::cout << "Number of notes in FibList: " << CountNodes<FibList>::value << std::endl;

    std::cout << FibList::value << std::endl;
    std::cout << FibList::next::value << std::endl;
    std::cout << FibList::next::next::value << std::endl;
    std::cout << FibList::next::next::next::value << std::endl;
    std::cout << FibList::next::next::next::next::value << std::endl;
    std::cout << FibList::next::next::next::next::next::value << std::endl;
    std::cout << FibList::next::next::next::next::next::next::value << std::endl;
    std::cout << FibList::next::next::next::next::next::next::next::value << std::endl;
    //Next line would be an error... we did not add that many notes.
    //std::cout << FibList::next::next::next::next::next::next::next::next::value << std::endl;

    std::cout << std::endl;

    std::cout << GetFib<0>::value << std::endl;
    std::cout << GetFib<1>::value << std::endl;
    std::cout << GetFib<2>::value << std::endl;
    std::cout << GetFib<3>::value << std::endl;
    std::cout << GetFib<4>::value << std::endl;
    std::cout << GetFib<5>::value << std::endl;
    std::cout << GetFib<6>::value << std::endl;
    std::cout << GetFib<7>::value << std::endl;
    std::cout << GetFib<8>::value << std::endl;


    return 0;
}


Exercise: 4.1 Write a template to find the value of a polynomial where the coefficients are stored in a static list.
Exercise: 4.2 Write a TMP binary tree structure.

Challenges: Advanced Exercises.
Challenge 1: Write a meta-program random number generator that will at least produce different random values for different lines of the source file.
Challenge 1.1: Can a meta_programming have state? If so how?
Challenge 2: Write a TMP stack (is this even possible?)



Note: At the time of this writing I have not answered most of the challenges/exercises. If you wish to post working answers to these please use the [spoiler][/spoiler] tags so that the solutions are not ruined for others. I will follow this as well as I explore these problems.

If you are thinking of writing a tutorial on TMP please feel free to borrow from my blog here but please add a link back here.

Some additional resources:
[1] Compile Time Data Structure Using Template Meta Programming by Zeeshan
[2] C++ Templates: The Complete Guide by Nicolai M. Josuttis
[3] C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond by David Abrahams and Aleksey Gurtovoy

11 Comments On This Entry

Page 1 of 1

NickDMax 

13 July 2010 - 06:27 PM
Challenge 1 Solution v0.2
Here is my first solution to a TMP random number generator. It has some serious flaws because I can not figure out a way of giving it satisfactory state.

Spoiler
0

NickDMax 

14 July 2010 - 05:38 PM
Challenge 1: Solution v0.3
This version is interesting to me. Because a template type is not expanded in a typedef (not until it is actually "instantiated" by creating an instance of that type) this version will keep tack of "state" by giving you the next type that you should use. It is kind of neat. It still has a limit of about 200 levels deep (before the compiler complains that your identifier name is too long) and the test code I gave takes *forever* to compile (01 min 25 sec) but it is a neat solution:

Spoiler


If you don't try to generate 200 values at once like that it takes far less time to compile.
0

LivingNightmare 

14 July 2010 - 06:30 PM
This made a really interesting read, and clarified things quite a bit. It's pretty hard to think about though, but maybe once I try solve the problems you gave, I'll have a better understanding of them. Never really worked too much with templates before, but this should be a good way to learn.

Just one thing I would like the clarify though, that I didn't really understand. As a programmer, when and why would I use TMP? Like I know you gave quite a few examples, but I don't see why one would choose to generate prime numbers for example or calculate powers like you did at using TMP instead of just doing it normally at run-time. You mentioned that it could increase efficiency, but I don't really see how. Sorry if these questions seem silly, but this is really new to me :P

Thanks alot :) - I'll be sure to post the code I can come up with when I get some of the solutions working :)

L.N
0

LivingNightmare 

14 July 2010 - 09:00 PM
Well, here's my attempt at exercise 2.1 (the LCM one) - This is my first meta-program :) So I'm pretty happy.
Suggestions and advice on my code is more than welcome :)

Spoiler


Thanks :) - L.N
0

NickDMax 

14 July 2010 - 09:40 PM

LivingNightmare, on 14 July 2010 - 08:30 PM, said:

Just one thing I would like the clarify though, that I didn't really understand. As a programmer, when and why would I use TMP? Like I know you gave quite a few examples, but I don't see why one would choose to generate prime numbers for example or calculate powers like you did at using TMP instead of just doing it normally at run-time. You mentioned that it could increase efficiency, but I don't really see how. Sorry if these questions seem silly, but this is really new to me :P


Well the LCM is a good example of a calculation that might be handy to have during compile time. One example I already gave is with aligning data structures or buffers, of course this operation is of such importance that most compilers actually have the ability to set alignment already but there may come an instance when you need to do it yourself -- For example some encryption systems work on blocks of data that are a specific size, if you wanted to make a template class that could easily be plugged into an encryption without having to copy the data into a buffer, you could ensure that no matter what the base type was an instance of that object would always occupy a multiple of the encryption's block size. (think about creating hash codes for an object).

Primes are another good example, as fast as the Sieve of Eratosthenes may be at run time, having a pre-calculated table of primes that you can load from a file is faster, having a pre-calculated table of primes in memory is even faster. Again to bring up cryptography but many algorithms require that you find large primes, to find a large prime you need a table of small primes. Granted this can be done other ways (store them in a binary format and load them all at once), but it is still faster than calculating them.

Then there are numbers like factorials, believe it or not your average int/long/long long/float/double can not actually calculate factorials up very high, so if you need a set of factorials you might as well just calculate them at compile time and save yourself some clock cycles in the program proper. In fact it is pretty common in calculations to have "constants" which are easier to express as a formula to calculate them than as a number, rather than evaluating that formula at run time for some constant value that you will use over and over -- save yourself some clock cycles and do it at compile time.

HOWEVER -- calculating numeric values like this is not the real power of TMP, the power of TMP is in generic programming. So you really do more things like the first example of ensuring that a template will be of a particular size, or that are selecting the most appropriate algorithm for the particular needs of a situation -- sometimes choosing the best algorithm will require your program to examine the meta-data (types, sizes, #of bytes, pointer values etc.) to determine the best algorithm -- these are choices that you don't want to have to make a run-time.
0

NickDMax 

15 July 2010 - 06:19 AM
I would also like to add that sometimes we do things to learn about them even when there is no direct application at the time only to discover their usefulness later. Mathematics has many great examples of toy questions that lead to "useless theory" which turned out to be very practical decades later. Developers like to use the word "discovery" to hide a multitude of sins. One part of developer "discovery" is to immerse yourself into a subject to just get a lay of the land and a feel for the surroundings -- this generally consists of "playing" with new languages, platforms, snippets of code etc.

So what I am saying is that it may be hard to see the application, but unless you have some experience in it you will not know how to recognize how it can help you solve your problems.
0

NickDMax 

15 July 2010 - 07:36 AM
All code available via gitHub: http://github.com/Ni...MetaProgramming -- as I learn more and more other bits of code will also appear.
0

LivingNightmare 

15 July 2010 - 03:16 PM

NickDMax, on 14 July 2010 - 10:40 PM, said:

HOWEVER -- calculating numeric values like this is not the real power of TMP, the power of TMP is in generic programming. So you really do more things like the first example of ensuring that a template will be of a particular size, or that are selecting the most appropriate algorithm for the particular needs of a situation -- sometimes choosing the best algorithm will require your program to examine the meta-data (types, sizes, #of bytes, pointer values etc.) to determine the best algorithm -- these are choices that you don't want to have to make a run-time.


So like... for example, to multiply numbers, you could obtain the size of two numbers, and then determine wether you should use the classical algorithm (if n is very small), or the karatsuba algorithm for n of "medium" size, or the FFT like algorithm for large n? - I'm not sure if that's what you meant. If it is, why would it be so bad to make that decision during runtime? I mean, all you would need is an if statement to check the size of the numbers, which can be done in O(1) time. So it's not like it would take a long time to do... right?

L.N
0

LivingNightmare 

15 July 2010 - 03:44 PM
Furthermore, I've tried solving exercise 3.1 Quadratic, but I keep getting the following error.
Spoiler


L.N
0

NickDMax 

15 July 2010 - 05:34 PM
You did not make the function static. Without the function being static you have to have an instance of the class (and object) in order to call the function.

Personally if you just have the 1 static function then, I don't see the benefit of making the function a member of a class at all (except maybe to establish a particular syntax).
0

NickDMax 

16 July 2010 - 06:39 AM
Exercise 2.1/2.2 v0.1 -- The ultimate idea here was to create an array that has an integral number of blocks of a specific size. So for example if I have an array of ints (4 bytes each) and I want and integral number of 16 byte blocks, with a minimum of 10 elements in my array, then I will need have at a minimum 10*sizeof(int) = 40 bytes and the next multiple of 16 is 48 which is 2 ints greater than 10, so I need and array of at least 12 integers to insure that I have an integral number of blocks of 16 bytes each. Of course one needs more generalized logic to work this out.

Spoiler
0
Page 1 of 1

May 2020

S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627 28 2930
31      

Recent Entries

Search My Blog

4 user(s) viewing

4 Guests
0 member(s)
0 anonymous member(s)