C++ Programming/Template/Template Meta-Programming

From Wikibooks, the open-content textbooks collection

[edit] Template Metaprogramming Overview

Template metaprogramming (TMP) refers to uses of the C++ template system to perform computation at compile-time within the code. It can, for the most part, be considered to be "programming with types" -- in that, largely, the "values" that TMP works with are specific C++ types.

Because template metaprogramming is something of an unintended use of C++'s template system, it is frequently somewhat cumbersome, though powerful. It also challenges the capabilities of older compilers; generally speaking, compilers from around the year 2000 and later are able to deal with much practical TMP code.

Traits classes could also be considered a primitive form of template metaprogramming; given input of a type, they compute as output properties associated with that type (for example, std::iterator_traits<> takes an iterator type as input, and computes properties such as the iterator's difference_type, value_type and so on). More sophisticated TMP came later.

[edit] History of TMP

Historically TMP is something of an accident; it was discovered during the process of standardizing the C++ language that its template system happens to be Turing-complete, i.e., capable in principle of computing anything that is computable. The first concrete demonstration of this was a program written by Erwin Unruh which computed prime numbers although it did not actually finish compiling: the list of prime numbers was part of an error message generated by the compiler on attempting to compile the code. TMP has since advanced considerably, and is now a practical tool for library builders in C++, though its complications mean that it is not generally appropriate for the majority of applications or systems programming contexts.

template <int p, int i>
class is_prime {
public:
   enum { prim = (p==2) || (p%i) && is_prime<(i>2?p:0),i-1>::prim
        }; 
}; 
 
template<>
class is_prime<0,0> {
public:
   enum {prim=1};
}; 
 
template<>
class is_prime<0,1> {
 public:
   enum {prim=1};
}; 
 
template <int i>
class D {
public:
   D(void*);
}; 
 
template <int i>
class Prime_print {      // primary template for loop to print prime numbers
public:
   Prime_print<i-1> a; 
   enum { prim = is_prime<i,i-1>::prim
        }; 
   void f() {
       D<i> d = prim ? 1 : 0;
       a.f();
   } 
}; 
 
template<>
class Prime_print<1> {   // full specialization to end the loop
  public:
    enum {prim=0}; 
    void f() {
        D<1> d = prim ? 1 : 0;
    }; 
}; 
 
#ifndef LAST 
#define LAST 18 
#endif 
 
int main()
{
   Prime_print<LAST> a; 
   a.f(); 
}

[edit] Example: Compile-time Factorial

Calculating factorials is naturally done recursively: 0! = 1, and for n>0, n! = n*(n-1)!. In C++ TMP, this corresponds to a class template "factorial" whose general form uses the recurrence relation, and a specialization of which terminates the recursion.

First, the general (unspecialized) template says that factorial<n>::value is given by n*factorial<n-1>::value:

template <unsigned n>
struct factorial
{
  enum { value = n * factorial<n-1>::value };
};

Next, the specialization for zero says that factorial<0>::value evaluates to 1:

template <>
struct factorial<0>
{
  enum { value = 1 };
};

And now some code that "calls" the factorial template at compile-time:

 
int main() {
  // Because calculations are done at compile-time, they can be
  // used for things such as array sizes.
  int array[ factorial<7>::value ];
}

[edit] Example: Compile-time "If"

The following code defines a meta-function called "if_"; this is a class template that can be used to choose between two types based on a compile-time constant, as demonstrated in main below:

template <bool Condition, typename TrueResult, typename FalseResult>
class if_;
 
template <typename TrueResult, typename FalseResult>
struct if_<true, TrueResult, FalseResult>
{
  typedef TrueResult result;
};
 
template <typename TrueResult, typename FalseResult>
struct if_<false, TrueResult, FalseResult>
{
  typedef FalseResult result;
};
 
int main()
{
  if_<true, int, void*>::result number(3);
  if_<false, int, void*>::result pointer(&number);
}

TODO Document the code above implementing if_

[edit] Building Blocks

TODO Lay out some of the basic building blocks of TMP.

[edit] Conventions for "Structured" TMP

TODO Describe some conventions for "structured" TMP.