Introduction
In my last column, I introduced you to C++ template metaprogramming. In this column, I’ll continue this discussion with some more simple examples designed to show you the relevance of template metaprogramming in everyday software development. Remember that your primary source for advanced C++ design techniques in general and template metaprogramming techniques in particular is Andrei Alexandrescu’s book [1].
C++ Template Metaprogramming
So what is this C++ template metaprogramming business all about? In my last column, I explained that C++ has a built-in mechanism to write programs that are executed entirely at compile time. The input to such a metaprogram is in the C++ code that you write, and its output is injected into that code. Here’s the first example again that I gave you in my last column:
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; }
When the compiler encounters the expression META_FACTORIAL<5>::RET in the first line of main, it instantiates the class template META_FACTORIAL with the template parameter n set to 5. This in turn will kick off recursive instantiations with n set to 4, 3, 2, 1, and 0, respectively. The recursion ends when n equals 0, because we have provided an explicit specialization of META_FACTORIAL for this case, and this explicit specialization does not contain any further nested occurrences of META_FACTORIAL. The net effect of this recursive instantiation process is that the expression META_FACTORIAL<5>::RET evaluates to 120 at compile time. The remarkable thing here is that in the executable code generated by the compiler, no trace remains of the way in which 5! was calculated. The executable code that is generated is bit-by-bit identical to the one that is generated from the following source code:
int main() { std::cout << 120 << std::flush; return 0; }
In other words, our class template META_FACTORIAL can be viewed as a function, which, at compile time, calculates the factorial of a natural number in the exact same way as the following ordinary C++ function would:
int factorial(int n) { if(0 == n) return 1; return n * factorial(n-1); }
The metafunction META_FACTORIAL uses nested template instantiations to implement the recursion, and it uses explicit template specialization to implement the if construct. It is therefore fair to say that C++ has a built-in metalanguage that allows us to write programs that will be executed at compile time. In my last column, I christened this metalanguage MetaC++. MetaC++ is a rather clunky language in practice, but that does not reflect poorly on its designers, because there are none. Template metaprogramming was not conciously and deliberately built into C++. It was discovered after the fact that C++ templates could be used for the purpose of writing metaprograms.
Template Metaprogramming with Types
It’s certainly cute to calculate the factorial of a natural number at compile time, but the relevance of this for day-to-day software development is rather limited, to put it mildly. What makes C++ template programming so useful in practice is the fact that MetaC++ functions can operate not only on integers, but also on types. To illustrate this, I will now dig a little deeper into an example that I used in my last column, namely, the infamous reference-to-reference problem. Consider the following class template:
template<typename Func> class X { typedef typename Func::first_argument_type first_arg; public: X(const first_arg& theFirstArg) : m_theFirstArg(theFirstArg) {} private: first_arg m_theFirstArg; };
This class template expects its template argument to be an adaptable binary functor (i.e., a functor that, among other things, provides a typedef named first_argument_type). Objects of type X store an element of type Func::first_argument_type, and the value to be stored is provided to the constructor of X as a const reference. Perhaps you have already guessed where I stole this code snippet. One of the most useful utilities in the STL is the function adapter binder1st. This adapter takes an adaptable binary functor and turns it into a new functor that behaves much like the original functor, except that the first argument is now bound to a fixed value. This fixed value is supplied to binder1st upon construction, together with the function object that is being adapted. Even without looking at the details of the implementation, it is quite obvious that an object of type binder1st must store two things: the original functor that is being adapted, and the value that is to be substituted for the original functor’s first argument. My class template X above is nothing but a shameless excerpt from the definition of binder1st.
Chances are that in the STL implementation you are using binder1st’s handling of the first-argument caboodle looks exactly like my class template X above, and it therefore has the exact same problem: if the type Func::first_argument_type happens to be a reference type, which is quite likely to be the case in practice, then the constructor signature:
X(const first_arg& theFirstArg);
will cause a compilation error, because the compiler is looking at a reference to reference, which it rightfully refuses to deal with. And even if you could get past that point somehow, the member m_theFirstArg would now be stored as a const reference. In the special case of STL’s binder1st, that’s probably exactly what you want, but, in other situations, you may well want to store a value copy. This whole mess is one of those problems that keeps biting you if you use the STL consistently, as you should, and it is one of the main reasons why we need our compilers to support partial template specialization. For those of you who have the good fortune to be working with a compiler that already supports partial template specialization, the good news is: C++ template metaprogramming saves. We’ll write two MetaC++ functions that each take a type as their argument and return a type. The first one, called NONCONST, strips the const qualifier, if any, from its type argument. The second one, called NONREF, strips the reference, if any, from its type argument.
template<typename U> class NONCONST { public: typedef U RET; }; template<typename U> class NONCONST<const U> { public: typedef U RET; }; template<typename U> class NONREF { public: typedef U RET; }; template<typename U> class NONREF<U&> { public: typedef U RET; };
Now if we apply the composition of NONREF and NONCONST to the type first_arg in the declaration of class X above, then we’ll get to the “raw” underlying type, stripped of the reference, if any, and the const qualifier, if any. We can then let the constructor take a const reference to that raw type, and we can declare m_theFirstArg to be of that raw type:
template<typename Func> class X { typedef Func::first_argument_type first_arg; typedef NONCONST<NONREF<first_arg>::RET>::RET raw_first_arg; public: X( const raw_first_arg& theFirstArg) : m_theFirstArg(theFirstArg){} private: raw_first_arg m_theFirstArg; };
Listing 1 shows an extended version of the example above, where the various class templates and their partial specializations that make up the MetaC++ functions NONCONST and NONREF have been given static member function trace. The constructor of X calls the trace functions of NONCONST and NONREF to show you exactly how these two MetaC++ functions go about producing the type raw_first_arg from the given type first_arg. The main function in Listing 1 shows what happens in the four cases where first_arg is int, const int, int&, and const int&. The output of main is:
Default NONREF<U> Default NONCONST<U> Default NONREF<U> NONCONST<const U> NONREF<U&> Default NONCONST<U> NONREF<U&> NONCONST<const U>
One thing I need to say here is that you should not write MetaC++ functions like NONREF and NONCONST yourself. Check out Andrei Alexandrescu’s type_traits, which are part of his Loki library (see [1] for details), or Boost’s type_traits [3] for some amazing techniques to get information about types and transform types at compile time. Boost’s call_traits [4] also solve the reference-to-reference problem, although they don’t give you a way to “strip” qualifiers, like the NONCONST and NONREF above do. One of the reasons why I’m harping on examples of this kind is because I want you to get excited enough so that you go and download libraries like Loki [1] and Boost [2]. And if your compiler does not yet support partial template specialization, go and get the Boost stuff anyway. There are lots of things in there that you can start using right away. For example, did you know that they have a regular expression library now? All the neat stuff you could only do in perl, awk, sed, Emacs Lisp, or Python is now available to you in C++, ready to use with a nifty STL-style interface on top of it. You can give your productivity an enormous, well, boost, by putting all that good stuff to work for you. Did I mention that it’s not only open source, carefully tested, peer-reviewed, and maintained by its authors, but also absolutely free?
Literate Programming in MetaC++
Let us look at the pseudocode for the MetaC++ function NONREF:
type NONREF(type U) { if( U is a reference type ) return (the type referenced by U); else return U; }
If you compare this to the actual MetaC++ implementations of this function above, you’ll see that there is little visible trace of the simple logical structure seen in the pseudocode. This is of course due to the fact that C++ template metaprogramming is not something that was designed as a programming language. It is, and I hope I’m not offending anybody by saying this, a kludge that harnesses a C++ language feature that was meant for a different purpose. Therefore, template metaprogramming code is notoriously unpleasant to read. As soon as it gets a little more complex than our simple examples, you typically have to work your way through complicated partial template specializations before you can see the basic logical structure behind the whole thing. However, it is possible to improve this situation by making an effort to write template metaprograms in a somewhat literate way. It is true that MetaC++ is never going to look pretty, and there are people who say that trying to make it pretty is a quixotic effort to begin with. Let’s give it a try anyway. If nothing else, you can view the following discussion as a little exercise in template metaprogramming, which actually illustrates some rather important points.
First off, it is possible to make the if-else branching more visible by defining a MetaC++ function IF. IF takes three template parameters, a bool and two types. It returns the first type if the Boolean parameter is true, and the second type otherwise:
template< bool cond, typename Then, typename Else > class IF; template<typename Then, typename Else> class IF<true, Then, Else> { public: typedef Then RET; }; template<typename Then, typename Else> class IF<false, Then, Else> { public: typedef Else RET; };
Notice how I’m using the fact that a C++ class template does not require a default implementation. It is possible to give just a forward declaration and one or more specializations, partial or explicit, as the case may be. In this particular case, the two partial specializations are exhaustive, so it would be possible to make one of them the default, like this:
template< bool cond, typename Then, typename Else > class IF { public: typedef Then RET; }; template<typename Then, typename Else> class IF<false, Then, Else> { public: typedef Else RET; };
However, in my opinion, the first version with the two specializations is more literate, so we’ll go with that. Next, we write a MetaC++ function that implements the condition that the MetaC++ function NONREF needs to test, namely, whether a given type is a reference type:
template<typename U> class ISREF { public: enum{ RET=false }; }; template<typename U> class ISREF<U&> { public: enum{ RET=true }; };
Finally, we need a MetaC++ function that strips the reference from a reference type:
template<typename U> class UNREF; template<typename U> class UNREF<U&> { typedef U RET; };
Again, I am using the fact that C++ class templates do not require a default implementation. UNREF is defined only for reference types. We can now take a shot at re-implementing NONREF in a more literate way:
template<typename U> class NONREF { public: typedef IF< ISREF<U>::RET, UNREF<U>::RET, U >::RET RET; };
Unfortunately, this isn’t going to work quite yet. If we use NONREF as defined above on a reference type, as in:
NONREF<int&> i;
then all is well. We have just declared a plain integer variable named i. However, if we try to use NONREF on a non-reference type, as in:
NONREF<int> i;
then this won’t compile. The compiler complains that the expression UNREF<U>::RET, which occurs in the if branch in the definition of NONREF, is not defined when U is int. That’s true, because UNREF, being true to its name, is defined only for reference types. But that’s not a problem, you might exclaim, because we’re in the else case, and therefore, we don’t need UNREF<int>::RET. We need int itself, like it says in the else case. And yet, the compiler’s complaint is legitimate. The problem is, and I did actually mention this in my last column, that when template metaprograms are executed, there isn’t the kind of laziness that we are accustomed to from working with ordinary languages. When an if-else construct is encountered at run time and the if condition is false, then whatever is in the if branch doesn’t get executed. Not so at compile time. When the compiler encounters:
IF< ISREF<U>::RET, UNREF<U>::RET, U >::RET;
with U set to int, then it must instantiate IF with the three given types, one of which is UNREF<int>::RET, which does not exist. The fact that ISREF<int>::RET evaluates to false, and therefore UNREF<int>::RET is never really needed, is of no concern to the compiler. From a MetaC++ point of view, the function in the if branch gets called even if the if condition evaluates to false.
Here’s a simple trick to work around this problem, and you should make a note of this because it is quite likely the kind of thing that will bite you in your own MetaC++ programs. We need to make it so that the class template IF can be instantiated without having to get UNREF<int>::RET. To this end, we first define a MetaC++ function ID, which simply returns its argument:
template<typename U> class ID { public: typedef U RET; };
Then we rewrite NONREF like this:
template<typename U> class NONREF { public: typedef IF< ISREF<U>::RET, UNREF<U>,ID<U> >::RET::RET RET; };
The net effect of this is the same: IF will now return either UNREF<U> or ID<U>, as the case may be, and taking RET on this takes us to what we want NONREF to return. Moreover, NONREF<U> will now compile (or shall we say run?) successfully for any type U. Of course, when we write:
NONREF<int> i;
then the expression UNREF<int>, for which there is no definition, will still occur inside NONREF<int>. But since we no longer have the ::RET attached to it, as was the case before, nothing is needed from the template instantiation UNREF<int>. And lo and behold, the C++ Standard stipulates that in this situation, the compiler is required to be lazy and not even look for a definition of UNREF<int>. In other words, there is just enough laziness at compile time to let us get away with this use of the undefined template instantiation UNREF<int>.
In conclusion, is our new definition of NONREF with the IF, the ISREF, and the UNREF prettier than the original one with the two specializations? Maybe not; I don’t know. But I insist that it is more literate, for what it’s worth. Also, we have some reusable components now, like ISREF, and more importantly, IF. (A comprehensive discussion of MetaC++ control structures can be found in Czarnecki’s and Eisenecker’s book [5]). Moreover, this discussion gave me the opportunity to remind you of two aspects of C++ that are important for template metaprogramming. Number one, class templates don’t need a default implementation. Number two, C++ template instantiation is lazy in the sense that you may use an instantiation for which there is no definition, as long as you don’t do anything that would force the compiler to go look for a definition.
References
[1] Andrei Alexandrescu. Modern C++ Design (Addison-Wesley, 2001).
[3] <www.boost.org/libs/type_traits>
[4] <www.boost.org/libs/utility/call_traits.htm>
[5] Krzystof Czarnecki and Ulrich W. Eisenecker. Generative Programming, Methods, Tools, and Applications (Addision Wesley, 2000).
Thomas Becker works as a senior software engineer for Zephyr Associates, Inc. in Zephyr Cove, Lake Tahoe. He can be reached at [email protected].
