1.4. Metaprogramming in C++

In C++, it was discovered almost by accident [Unruh94], [Veld95b] that the template mechanism provides a rich facility for native language metaprogramming. In this section we'll explore the basic mechanisms and some common idioms used for metaprogramming in C++.

1.4.1. Numeric Computations

The earliest C++ metaprograms performed integer computations at compile time. One of the very first metaprograms was shown at a C++ committee meeting by Erwin Unruh; it was actually an illegal code fragment whose error messages contained a sequence of computed prime numbers!

Since illegal code is hard to use effectively in a larger system, let's examine a slightly more practical application. The following metaprogram (which lies at the heart of our little compiler test above) transliterates unsigned decimal numerals into their binary equivalents, allowing us to express binary constants in a recognizable form.

   template <unsigned long N>


   struct binary


   {


       static unsigned const value


          = binary<N/10>::value << 1   // prepend higher bits


            | N%10;                    // to lowest bit


   };





   template <>                           // specialization


   struct binary<0>                      // terminates recursion


   {


       static unsigned const value = 0;


   };





   unsigned const one   =    binary<1>::value;


   unsigned const three =   binary<11>::value;


   unsigned const five  =  binary<101>::value;


   unsigned const seven =  binary<111>::value;


   unsigned const nine  = binary<1001>::value;

If you're wondering "Where's the program?" we ask you to consider what happens when we access the nested ::value member of binary<N>. The binary template is instantiated again with a smaller N, until N reaches zero and the specialization is used as a termination condition. That process should have the familiar flavor of a recursive function calland what is a program, after all, but a function? Essentially, the compiler is being used to interpret our little metaprogram.

Error Checking There's nothing to prevent a user from passing binary a number such as 678, whose decimal representation is not also valid binary. The result would make a strange sort of sense (it would be 6x22 + 7x21 + 8x20), but nonetheless an input like 678 probably indicates a bug in the user's logic. In Chapter 3 we'll show you how to ensure that binary<N>::value only compiles when N's decimal representation is composed solely of 0s and 1s.

Because the C++ language imposes a distinction between the expression of compile-time and runtime computation, metaprograms look different from their runtime counterparts. As in Scheme, the C++ metaprogrammer writes her code in the same language as the ordinary program, but in C++ only the compile-time subset of the full language is available to her. Compare the previous example with this straightforward runtime version of binary:

   unsigned binary(unsigned long N)


   {


       return N == 0 ? 0 : N%10 + 2 * binary(N/10);


   }

A key difference between the runtime and compile time versions is the way termination conditions are handled: our meta-binary uses template specialization to describe what happens when N is zero. Terminating specializations are a common characteristic of nearly all C++ metaprograms, though in some cases they will be hidden behind the interface of a metaprogramming library.

Another important difference between runtime and compile time C++ is highlighted by this version of binary, which uses a for loop in lieu of recursion.

   unsigned binary(unsigned long N)


   {


       unsigned result = 0;


       for (unsigned bit = 0x1; N; N /= 10, bit <<= 1)


       {


           if (N%10)


               result += bit;


       }


       return result;


   }

Though more verbose than the recursive version, many C++ programmers will be more comfortable with this one, not least because at runtime iteration is sometimes more efficient than recursion.

The compile-time part of C++ is often referred to as a "pure functional language" because of a property it shares with languages such as Haskell: (meta)data is immutable and (meta)functions can have no side effects. As a result, compile-time C++ has nothing corresponding to the non-const variables used in runtime C++. Since you can't write a (non-infinite) loop without examining some mutable state in its termination condition, iteration is simply beyond reach at compile time. Therefore, recursion is idiomatic for C++ metaprograms.

1.4.2. Type Computations

Much more important than its ability to do compile time numeric computations is C++'s ability to compute with types. As a matter of fact, type computation will dominate the rest of this book, and we'll cover examples of it in the very first section of the next chapter. By the time we're through, you'll probably think of template metaprogramming as "computing with types."

Although you may have to read Chapter 2 to understand the specifics of type computation, we'd like to give you a sense of its power. Remember our YACC expression evaluator? It turns out we don't need to use a translator to get that kind of power and convenience. With appropriate surrounding code from the Boost Spirit library, the following legal C++ code has equivalent functionality.

   expr =


         ( term[expr.val = _1] >> '+' >> expr[expr.val += _1] )


       | ( term[expr.val = _1] >> '-' >> expr[expr.val -= _1] )


       | term[expr.val = _1]


       ;





   term =


         ( factor[term.val = _1] >> '*' >> term[term.val *= _1] )


       | ( factor[term.val = _1] >> '/' >> term[term.val /= _1] )


       | factor[term.val = _1]


       ;





   factor =


         integer[factor.val = _1]


       | ( '(' >> expr[factor.val = _1] >> ')' )


       ;

Each assignment stores a function object that parses and evaluates the bit of grammar on its right hand side. The behavior of each stored function object, when invoked, is determined entirely by the type of the expression used to construct it, and the type of each expression is computed by a metaprogram associated with the various operators used.

Just like YACC, the Spirit library is a metaprogram that generates parsers from grammar specifications. Unlike YACC, Spirit defines its domain language as a subset of C++ itself. If you don't see how that's possible at this point, don't worry. By the time you finish this book, you will.