Introduction
OK, OK, I know what you’re thinking. You’re thinking, he’s done with his pass through the STL, he’s written about traits and policies, now he needs to write about more topics in generic programming in general, and he can’t think of anything that a real software engineer would be interested in. Template metaprogramming. Who has ever heard of such a thing, and why would I even care. He’s just desperate for things to write about. Not so. The fact of the matter is that many of the nifty techniques that you encounter in the Boost library [1], in Andrei Alexandrescu’s book and his Loki library [2], and in other places where people share cutting-edge C++ programming techniques, are really examples of template metaprogramming. Once you’ve taken a step back and looked at template metaprogramming from a conceptual point of view, you will find it much easier to understand things such as compile-time lists, type traits, and the like. Right now, it may seem to you that stuff like that is just for C++ geeks who don’t have anything better to do than play with a bunch of obscure C++ template features. My hunch is that these ideas will enter the mainstream of C++ programming sooner than many people think. It is true that at first you are more likely to use libraries that employ these techniques than to use them in the code that you yourself write. But then, in my experience, libraries tend to be 50-percent code reuse and 50-percent inspiration to write my own code in a certain way. And even if you steadfastly refuse to ever write anything that even remotely resembles template metaprogramming, what if you’re asked to work with someone else’s code that uses these techniques? In short, as a professional C++ developer, you simply cannot afford to be clueless about template metaprogramming and the ideas that have sprung from it.
Before I tell you what template metaprogramming is, I need to mention the fact that this is not really a feature that was intentionally built into the C++ language. Templates were added to C++ for all the good reasons that you’ve read about in your introductory books (e.g., to be able to write container classes without having to specify the type of element that goes into the container). It wasn’t until after the fact that people noticed that there was much more to C++ templates than anybody had thought [3]. An excellent introduction to template metaprogramming can be found in Chapter 10 of Czarnecki’s and Eisenecker’s book on generative programming [4].
Another thing I need to address (once again) before I can get to the point of this column is the subject of Microsoft’s support of C++ template features. Microsoft’s Visual C++ 6.0 compiler supports neither template template parameters [5] nor partial template specialization, and the first .NET release is no improvement in this respect. However, for the first time since I started this column, I have the pleasure to report that this extremely annoying situation is going to change in the near future [6]. In previous columns, I have always gone out of my way to present only examples that do not use partial template specialization in order to keep VC++ users from deserting me. In the second part of this column, I will be using partial template specialization for the first time. If I didn’t, I would be withholding some of the most important, interesting, and exciting techniques in C++ template programming. I urge you to read on, though, even if your compiler currently cannot handle the examples. You don’t want to fall behind on your professional expertise just because of temporary limitations imposed by someone’s tool.
Template Metaprogramming with Integers
So what’s a C++ template metaprogram? It’s a program that is executed by the C++ compiler when it compiles your “real” program. The input to the metaprogram is in the C++ code that you write, and its output is injected into that code. But how exactly is it done, and how do templates figure into all this? The best answer to that question is to look at an example. To emphasize the point that a C++ template metaprogram is a real program, I’ll use the one example that every teacher of programming languages has always used as the first example of a program, namely, the calculation of the factorial of a natural number.
Recall that the factorial of a non-zero natural number n is defined as:
n! = 1 * 2 * ... * (n-1) * n
and 0! is defined to be 1. In C++, the factorial can therefore be computed as follows:
int cpp_factorial(int n) { assert(0 <= n); int fact = 1; for(int i=1; i<=n; ++i) { fact *= i; } return fact; }
Alternatively, the factorial can be computed using recursion:
int cpp_r_factorial(int n) { assert(0 <= n); if( 0 == n ) return 1; return n * cpp_r_factorial(n-1); }
Because of its simplicity, this is a favorite example for teachers and authors to demonstrate recursive programming. Notice, however, that the factorial is also the standard example of a function where the use of recursion is possible, but rather ill advised. The time required for calculating the factorial of n increases linearly with n in both the recursive and the non-recursive version. The space required for the calculation, however, is constant in the non-recursive version and linear in the recursive version, which makes the recursive version an extremely poor choice. There are other algorithms, such as the traversal of trees without child-to-parent node back pointers, where the space consumption required by a recursive implementation is unavoidable, even in non-recursive versions. In those cases, the simplicity and elegance of the recursive implementation usually makes it the preferred choice.
All that being said, let us now look at the factorial as a C++ template metaprogram. Here’s how it’s done:
template<int n> class META_FACTORIAL { public: enum{ RET = n * META_FACTORIAL<n-1>::RET }; }; template<> class META_FACTORIAL<0> { public: enum{ RET = 1 }; }; int main() { std::cout << META_FACTORIAL<5>::RET << std::flush; return 0; }
This program will output 120, which is the factorial of 5. So what’s going on here? First of all, notice that META_FACTORIAL is a class template that takes a template argument of type int. We’re all accustomed to seeing template parameters that are types, as in:
template<typename T> class X{ /* ... */ };
but sometimes we have to remember that C++ allows template arguments that are values (integers in our case) and not types. The other thing to notice here is that the definition of the class template META_FACTORIAL contains a nested occurrence of META_FACTORIAL itself, namely, the expression:
META_FACTORIAL<n-1>::RET
When the compiler instantiates META_FACTORIAL with the template argument 5 in our main function, this nesting triggers a compile-time recursion. Regardless of implementation details, every C++ compiler conceptually has a template instantiation stack. When the expression:
META_FACTORIAL<n-1>::RET
is encountered during the processing of META_FACTORIAL<5>, the compiler pushes whatever it has so far for META_FACTORIAL<5> on that stack and begins instantiation of META_FACTORIAL with the template argument set to 4. This is repeated until META_FACTORIAL<0> is encountered, for which we have provided an explicit specialization. In this specialization, the enum value of RET is set to 1. This enables the compiler to resume processing META_FACTORIAL<1>, META_FACTORIAL<2>, and so on, popping things off its template instantiation stack up to the top level of META_FACTORIAL<5>. In the process, the enum values of RET in the various instantiations of META_FACTORIAL are set to 1, 2, 6, 24, and 120, respectively. In the end, the compiler has recursively calculated 5!.
The remarkable thing here is that in the final compiled code no trace remains of the compile-time calculation. If you want to spend a few minutes on a real eye-opener, compile and run the code above, then add the line:
std::cout << 120 << std::flush;
to your main function. Look at the executable code that your compiler generates. You will see that the two lines:
std::cout << META_FACTORIAL<5>::RET << std::flush; std::cout << 120 << std::flush;
have produced the exact same machine code. Our factorial program has been executed entirely at compile time, and its output has been injected into the C++ code that was then translated into machine code.
So, as you can see, it’s not too hard to understand how our metaprogram gets executed at compile time. What makes C++ compile-time programs often a little hard to comprehend is that the language they are written in is so different from what we expect a programming language to look like. For easier reference, let us call this language MetaC++. (I just made this up; it is not an established technical term.) Let us look at our factorial metaprogram again and see what MetaC++ language constructs we have used. MetaC++ functions are C++ class templates. Our META_FACTORIAL is a MetaC++ function. MetaC++ functions receive their arguments via template parameters. In our case, there is just one argument, an integer. A MetaC++ function does not formally have a return value, which seems odd at first. The return value of our META_FACTORIAL is a public enum value, which I have conveniently named RET. Obviously, a C++ class template can have more than one public enum value, and it can have other public things that can be retrieved at compile time, such as typedefs. The totality of all such public items can be viewed as the “return value” of a MetaC++ function. Thus, MetaC++, for all its clunkiness, has one major advantage over most conventional programming languages: you never have to worry about how to go about returning several items. The old shall-I-package-the-return-values-in-a-structure-or-use-reference-arguments headache has just disappeared.
MetaC++ functions can be called recursively, and that is how we have implemented the loop construct of the original C++ implementation cpp_factorial. Recursion is, in fact, the only way to do loops in MetaC++, which automatically makes it an inefficient language. As I said earlier, the factorial is the standard example of a loop that should not be implemented recursively because of space inefficiency. But then, in practice, efficiency is not usually a major concern in C++ compile-time programming.
Finally, our factorial metaprogram demonstrates a way to express an if-construct in MetaC++, namely the explicit specialization of meta_factorial for the argument value 0. This explicit specialization amounts to a MetaC++ implementation of the equivalent C++ lines:
if( 0 == n ) return 1;
Under certain circumstances, MetaC++ also allows the conditional operator ?: to express an if-construct. I’ll come back to that at the end of this column.
I said before that C++ template metaprogramming is not just for geeks, but gives rise to important programming techniques. Now what’s so important about being able to calculate a factorial at compile time? Nothing much, I’ll have to admit. There are possible applications of compile-time calculations with natural numbers and integers, such as the calculation of hash values at compile time, but it would require quite a stretch of the imagination to call that mainstream C++ programming. The real relevance of C++ template metaprogramming lies in the fact that it can operate not only on integers, but also on types [7].
Template Metaprogramming with Types
Recall that functions in the meta-language MetaC++ are C++ class templates. These MetaC++ functions take their arguments via template parameters, and they can return anything that can be retrieved from the class template at compile time. Our MetaC++ function META_FACTORIAL above took one argument, an int, and it returned an int via a public enum value. But C++ class templates can have parameters that are types, and we can retrieve typedefs from a class template at compile time. Therefore, MetaC++ functions can take types as arguments and return types. Those are the ones that are most useful in real-life C++ programming. Here’s an example that is simple but important and useful nonetheless. It is a MetaC++ function that solves the reference-to-reference problem, which I mentioned in my last column in connection with STL function object adapters. The following class template illustrates the essence of the reference-to-reference problem:
template<typename T> class R2RProblem { typedef typename T::SomeType S; public: void Foo(S& anS) { /* modify anS */ } };
This class template has a member function Foo that takes an argument of type S by reference. The type S is given indirectly as a typedef that comes out of the template parameter T. For example, suppose we have a class SomeClass that looks like this:
class SomeClass { public: typedef int SomeType; };
Then if we use SomeClass as the template argument for R2RProblem, as in:
R2RProblem<SomeClass> x;
then R2RProblem::Foo gets the signature:
void R2RProblem::Foo(int&);
The reference-to-reference problem occurs when SomeType is a reference type, as in:
class SomeOtherClass { public: typedef int& SomeType; };
Now if we try to instantiate the class template R2RProblem with SomeOtherClass as the template argument, as in:
R2RProblem<SomeOtherClass> x;
then Foo ends up having the signature:
void R2RProblem::Foo(int&&);
which the compiler will reject as an illegal reference to reference. In order to fix this, we want to change the original declaration of Foo from:
void Foo(S& anS)
to something like:
void Foo(META_REF(S) anS);
where META_REF is a compile-time function that takes a type as its argument, returns a type, and behaves as indicated by the following pseudo-code:
META_REF(S) { if( S is a reference type ) return S; return S&; }
Since we already know how to express the if-construct in our C++ compile-time metalanguage MetaC++ using specialization, implementing META_REF in MetaC++ is now a cinch:
template<typename S> class META_REF { public: typedef S& RET; }; template<typename U> class META_REF<U&> { public: typedef U& RET; };
If we now declare Foo as:
void Foo(typename META_REF<S>::RET anS);
then the class R2RProblem does not deserve its name anymore. If S is a non-reference type, then the default implementation of META_REF applies, and META_REF<S>::RET is S&. If S is a reference type, say U&, then the partial specialization of META_REF kicks in, and META_REF<S>::RET is U& (i.e., it is S itself). In other words, for non-reference types S, we have slapped a reference on S, but for reference types S, we have done nothing, thus avoiding the second reference that caused the problem before.
Make sure you understand this example thoroughly. Understand what it does, and understand that we are looking at a compile-time function that takes a type as its argument, returns a type, and has an if-construct inside. You are now set to enter a whole new world of cutting-edge C++ programming. If you look at Boost’s call_traits [8] or Andrei Alexandrescu’s type_traits (Section 2.10. of [2]), you’ll find many MetaC++ functions that are similar to the example above. But that is only the beginning. Andrei Alexandrescu’s book [2] will take you to a veritable wonderland of C++ template metaprogramming.
Template Metaprogramming and Laziness
I said earlier that it is sometimes possible to use the conditional operator ?: to express the if-construct in MetaC++. Here’s a silly example:
template<int n> class SILLY { public: enum{ RET = n>0 ? 42 : 43 }; };
This is a metafunction taking an integer argument that “returns” 42 when its argument is positive, and 43 otherwise. Let us now take another look at cpp_r_factorial, the recursive version of the C++ implementation of the factorial. It is entirely possible to rewrite that function using the conditional operator ?:, like this:
int cpp_r_factorial_alt(int n) { assert(0 <= n); return 0 == n ? 1 : n * cpp_r_factorial_alt(n-1); }
Therefore, you may be tempted to do the same for the metafunction META_FACTORIAL, replacing the explicit specialization gimmick with operator ?:, like this:
template<int n> class BAD_META_FACTORIAL { public: enum{ RET = n==0 ? 1 : n * BAD_META_FACTORIAL<n-1>::RET }; };
This will, perhaps somewhat surprisingly to you, cause an infinite recursion. The compiler will instantiate BAD_META_FACTORIAL<n> for infinitely descending n, until the limit on the template nesting depth puts it out of its misery [9]. Why is it that in the run-time version cpp_r_factorial the use of operator ?: does not cause an infinite recursion, and here it does? The answer lies in the subtleties of lazy evaluation. The C++ Standard requires that at run time all logical and conditional expressions are evaluated lazily (from left to right if applicable). For example, suppose you have a boolean variable cond and a function foo returning a bool. Assume further that the if-condition:
if(cond && foo())
is encountered at run time, and the current value of cond is false. Lazy evaluation, as required by the Standard, guarantees that in this situation foo will not be called. The same applies to operator ?:. If the expression:
x ? y : z;
is encountered and x evaluates to true, then only y but not z will be evaluated, and vice versa.
But all this applies to evaluation at run time. When the enum value:
RET = n==0 ? 1 : n * BAD_META_FACTORIAL<n-1>::RET
in the class BAD_META_FACTORIAL above is encountered at compile time, the compiler does instantiate BAD_META_FACTORIAL<n-1> regardless of whether n equals zero or not. C++ template instantiation works quite lazily in several other respects. (I’ll come back to that in my next column.) However, there is no such thing as lazy evaluation of logical and conditional expressions at compile time. If your template metaprogram causes an infinite recursion at compile time, the explanation is most likely that you have intuitively relied on lazy evaluation when you shouldn’t have [10].
References
[2] Andrei Alexandrescu. Modern C++ Design (Addison-Wesley, 2001).
[3] If there is one person who is to be credited with the discovery of C++ template metaprogramming, then I believe it would have to be Erwin Unruh, who in 1994 wrote a metaprogram that calculated prime numbers at compile time and printed them out as compiler warnings.
[4] Krzystof Czarnecki and Ulrich W. Eisenecker. Generative Programming, Methods, Tools, and Applications (Addison-Wesley, 2000).
[5] For an explanation of template template parameters and partial template specialization, see my February 2002 column, “STL & Generic Programming: Policy-Driven Design,” and my December 2001 column, “STL & Generic Programming: Traits Classes,” in C/C++ Users Journal, respectively.
[6] I occasionally meet people who avoid C++ templates and the generic programming techniques that they are used for. Their argument is, “If Microsoft doesn’t think it is important, why would I?” If you are one of those people, your world has just changed: <www.gotw.ca/microsoft>.
[7] From a purely theoretical and academic point of view, using integers in template metaprogramming is of course more important than using types. It can be shown that template metaprogramming with just integers is a Turing-complete language. Again, I believe it was Erwin Unruh who first presented a back-of-the-envelope proof of this fact. If you are interested in these more theoretical aspects of programming, Hopcroft and Ullman’s Introduction to Automata Theory, Languages, and Computation (Addison-Wesley, 2000) is a good place to start.
[8] <www.boost.org/libs/utility/call_traits.htm>
[9] The Standard requires a template nesting depth of at least 17, but the actual value is compiler-dependent. Some compilers allow you to set it via an option.
[10] On some compilers, infinite template recursion generates some of the most entertainingly bizarre error messages. Check out <www.bdsoft.com/tools/stlfilt.html> to help you improve your compiler’s template-related error messages.
Thomas Becker works as a senior software engineer for Zephyr Associates, Inc. in Zephyr Cove, Lake Tahoe. He can be reached at [email protected].
