Walking through your first template metaprogram in C++
From the Wikipedia article on Metaprogramming:
First, lets get the preliminaries out of the way:
It allows us to do a compile time recursion and that's what I'm going to show you.
Look at this piece of code:
Doesn't that look dandy! Its that same old factorial function again! So, what's new? Firstly, notice that instead of templating the structure via a typename, we have chosen to template it over a compile time constant. So, creating an object of this structure will require code such as:
The static member allows us to directly access values that are calculated at compile time. In essence, you can think of it as the return value of the computation. Before we move further into the analysis, let me answer a couple of questions that can arise:
Sharp programmers might have noticed that there is no base case in this piece of code: You're right!
So, here's the base case:
So, when the compiler tries to instantiate factorial<1> and comes across factorial<0>::value, it will choose this base case and terminate the recursion. Once all the constants have been determined, they are multiplied by the compiler and the result is stored in the resulting executable. So, the value of 5! can be used at runtime without any computation of any sort, all it requires of you is to substitute factorial<5>::value wherever you need it.
A side-effect of this evaluation is that all lower factorial structures are also instantiated. Thus, when you instantiate factorial<5>, you get for free the values of factorial<4>, factorial<3> etc. Also, use of factorial<4> later in the program will not cause additional template instantiations because C++ compilers follow a single template instantiation rule: viz. no template will be instantiated more than once. This allows for a very important optimization: memoization that's right memoization and not memorization (though the two are pretty similar). You can have a look at the Wikipedia entry on memoization for info, but for the impatient, it allows you to code a fibonacci number generator like this:
If you had coded an analogous recursive function for evaluation at runtime, you should have been spanked by your computer science/engineering professors because that's the worst way to evaluate the fibonacci series as it has a time complexity of O(2^n) which is exponential in the size of the problem. However, because of the one template instantiation rule, its perfectly alright to do this at compile time. While evaluating fibonacci_term::value , the compiler has already instantiated fibonacci_term
Meta-programming is not just about compile time computations and tricks like this. Its far greater application lies in the capability of manipulation of the C++ type system. Most metaprogramming techniques are applied to make libraries hide their implementations better and allow you to write simpler, cleaner code without reams of types in angle brackets.
Type manipulation tricks are best left to another blog entry. For now, you can check out:
[1] C++ Template Metaprogramming - Concepts, Tools and Techniques from Boost and beyond
This is a book by the authors of the Boost.MPL (the Boost Meta-Programming Library). The MPL has loads of tools to make metaprogramming easier as well as hacks to work around the deficiencies in various C++ compilers.
[2] The Boost TypeTraits library - This library makes type manipulation a breeze, thanks to the consistent interface and excellent documentation.
Hope you liked it. Comments always welcome.
The files for the examples are listed below. All of them have been compiled and tested using the Visual C++ 2005 compiler and should work with most other compilers. In case you have troubles, let me know.
[1] factorial.cpp
[2] fibonacci.cpp
The commplete source code including makefiles can be found here. A Jamfile is included for those who use Bjam.
Metaprogramming is the writing of computer programs that write or manipulate other programs (or themselves) as their data, or that do part of the work at compile time that is otherwise done at run time. In many cases, this allows programmers to get more done in the same amount of time as they would take to write all the code manually.Unfortunately, metaprogramming is not directly supported by C++ and resources on template metaprogramming are few and far between. I'll try to document my knowledge of metaprogramming as I learn it and hope that it proves useful for one such as myself hunting the web for information.
First, lets get the preliminaries out of the way:
- Templates are used to create generic code (but you already know that, don't you?)
Code like:
template<typename T> std::string to_string(T const & object) {
return object.to_string();
}
is used to allow the to_string function to be called on all objects that have a to_string() member function. - Template specializations are created to handle certain datatypes in a special manner (or in technospeak - to provide a custom instantiation of generic code)
So, code like:
template<> std::string to_string<int>(int I) { std::ostringstream o; o << I; return o.str(); } ensures that calls to to_string that take an int for a parameter will use the second definition of to_string and not the more generic first definition. This allows us to provide a string representation of an int even though it does not have a member function named to_string. Thus, the body of a templated piece of code can be changed completely from its generic counterpart in a template specialization. - The compiler always chooses the most specialized definition of a function. This is somewhat akin to function overloading. So, given a choice between to_string<t> and to_string<int>, it will always choose to_string<int> for an integer parameter.
It allows us to do a compile time recursion and that's what I'm going to show you.
Look at this piece of code:
template<int N>
struct factorial {
struct factorial {
static const long value = N*factorial<N-1>::value;
};
Doesn't that look dandy! Its that same old factorial function again! So, what's new? Firstly, notice that instead of templating the structure via a typename, we have chosen to template it over a compile time constant. So, creating an object of this structure will require code such as:
factorial<5> five_factorial;
But why would you want an empty object? Remember: static structure and class variables do not occupy any space in objects and factorial<N> has only static members. So, what's the use of the static member?The static member allows us to directly access values that are calculated at compile time. In essence, you can think of it as the return value of the computation. Before we move further into the analysis, let me answer a couple of questions that can arise:
- Where's the computation taking place?
- It is taking place at compile time when the template is initialized/instantiated and its being done by the compiler while the templated code is being compiled. Effectively, the compiling process is the runtime for template metaprogramming.
- Where's the recursion in the code?
- The instantiation of factorial<N> requires the value of factorial<n-1>::value which is of-course a static member in factorial<N-1>. So, this template is also instatiated and the recursion takes place.
Sharp programmers might have noticed that there is no base case in this piece of code: You're right!
So, here's the base case:
template<>
struct factorial<0> {
static const long value = 1;
};
So, when the compiler tries to instantiate factorial<1> and comes across factorial<0>::value, it will choose this base case and terminate the recursion. Once all the constants have been determined, they are multiplied by the compiler and the result is stored in the resulting executable. So, the value of 5! can be used at runtime without any computation of any sort, all it requires of you is to substitute factorial<5>::value wherever you need it.
A side-effect of this evaluation is that all lower factorial structures are also instantiated. Thus, when you instantiate factorial<5>, you get for free the values of factorial<4>, factorial<3> etc. Also, use of factorial<4> later in the program will not cause additional template instantiations because C++ compilers follow a single template instantiation rule: viz. no template will be instantiated more than once. This allows for a very important optimization: memoization that's right memoization and not memorization (though the two are pretty similar). You can have a look at the Wikipedia entry on memoization for info, but for the impatient, it allows you to code a fibonacci number generator like this:
template<int N>
struct fibonacci_term {
static const int value = fibonacci_term<n-1>::value + fibonacci_term<n-2>::value;
};
template<>
struct fibonacci_term<1> {
static const int value = 1;
};
template<>
struct fibonacci_term<0> {
static const int value = 0;
};
If you had coded an analogous recursive function for evaluation at runtime, you should have been spanked by your computer science/engineering professors because that's the worst way to evaluate the fibonacci series as it has a time complexity of O(2^n) which is exponential in the size of the problem. However, because of the one template instantiation rule, its perfectly alright to do this at compile time. While evaluating fibonacci_term
Meta-programming is not just about compile time computations and tricks like this. Its far greater application lies in the capability of manipulation of the C++ type system. Most metaprogramming techniques are applied to make libraries hide their implementations better and allow you to write simpler, cleaner code without reams of types in angle brackets.
Type manipulation tricks are best left to another blog entry. For now, you can check out:
[1] C++ Template Metaprogramming - Concepts, Tools and Techniques from Boost and beyond
This is a book by the authors of the Boost.MPL (the Boost Meta-Programming Library). The MPL has loads of tools to make metaprogramming easier as well as hacks to work around the deficiencies in various C++ compilers.
[2] The Boost TypeTraits library - This library makes type manipulation a breeze, thanks to the consistent interface and excellent documentation.
Hope you liked it. Comments always welcome.
The files for the examples are listed below. All of them have been compiled and tested using the Visual C++ 2005 compiler and should work with most other compilers. In case you have troubles, let me know.
[1] factorial.cpp
[2] fibonacci.cpp
The commplete source code including makefiles can be found here. A Jamfile is included for those who use Bjam.
Comments
Post a Comment