Thinking In C++. Volume 2: Practical Programming

When the compiler attempts to instantiate Factorial<12>, it finds it must also instantiate Factorial<11>, which requires Factorial<10>, and so on. Eventually the recursion ends with the specialization Factorial<1>, and the computation unwinds. Eventually, Factorial<12>::val is replaced by the integral constant 479001600, and compilation ends. Since all the computation is done by the compiler, the values involved must be compile-time constants, hence the use of enum.^[66] When the program runs, the only work left to do is print that constant followed by a newline. To convince yourself that a specialization of Factorial results in the correct compile-time value, you could use it as an array dimension, such as:^.

double nums[Factorial<5>::val];

assert(sizeof nums == sizeof(double)*120);

Compile-time programming

So what was meant to be a convenient way to perform type parameter substitution turned out to be a mechanism to support compile-time programming. Such a program is called a template metaprogram (since you’re in effect "programming a program"), and it turns out that you can do quite a lot with such a beast. In fact, template metaprogramming is Turing complete because it supports selection (if-else) and looping (through recursion); so theoretically you can perform any computation with it.^[67] The factorial example above shows how to implement repetition; write a recursive template and provide a stopping criterion via a specialization. The following example shows how to compute Fibonacci numbers at compile time by the same technique^.

//: C05:Fibonacci.cpp

#include

using namespace std;

template

struct Fib {

   enum {val = Fib::val + Fib::val};

};

template<>

struct Fib<1> {

   enum {val = 1};

};

template<>

struct Fib<0> {

   enum {val = 0};

};

int main() {

   cout << Fib<5>::val << endl;   // 6

   cout << Fib<20>::val << endl;  // 6765

} ///:~^.

Fibonacci numbers are defined mathematically as:

The first two cases lead to the template specializations above, and the rule in the third line becomes the primary template^.

Compile-time looping

To compute any loop in a template metaprogram, it must first be reformulated recursively. For example, to raise the integer n to the power p, instead of using a loop such as in the following lines:^.

int val = 1;

while (p--)

  val *= n;

you would have to think of it as a recursive procedure:

int power(int n, int p) {

  return (p == 0) ? 1 : n*power(n, p - 1);

}

This can now be easily rendered as a template metaprogram as follows:

//: C05:Power.cpp

#include

using namespace std;

template

struct Power {

  enum {val = N * Power::val};

};

template

struct Power {

  enum {val = 1};

};

int main() {

  cout << Power<2, 5>::val << endl;  // 32

} ///:~

Note that we need to use a partial specialization for the stopping condition, since the value N is still a free template parameter. This program only works for non-negative powers, of course^.

The following metaprogram adapted from Czarnecki and Eisenecker^[68] is interesting in that it uses a template template parameter, and simulates passing a function as a parameter to another function, which "loops through" the numbers 0..n^.

//: C05:Accumulate.cpp

// Passes a "function" as a parameter at compile time

#include

using namespace std;

// Accumulates the results of F(0)..F(n)

template class F>

struct Accumulate {

   enum {val = Accumulate::val + F::val};

};

// The stopping criterion (returns the value F(0))

template class F>

struct Accumulate<0, F> {

   enum {val = F<0>::val};

};

// Various "functions":

template

struct Identity {

   enum {val = n};

};

template

struct Square {

   enum {val = n*n};

};

template

struct Cube {

   enum {val = n*n*n};

};

int main() {

   cout << Accumulate<4, Identity>::val << endl; // 10

   cout << Accumulate<4, Square>::val << endl;   // 30

   cout << Accumulate<4, Cube>::val << endl;     // 100

} ///:~^.

The primary Accumulate template attempts to compute the sum F(n)+F(n‑1)…F(0). The stopping criterion is obtained by a partial specialization, which "returns" F(0). The parameter F is itself a template, and acts like a function as in the previous examples in this section. The templates Identity, Square, and Cube compute the corresponding functions of their template parameter that their names suggest. The first instantiation of Accumulate in main( ) computes the sum 4+3+2+1+0, because the Identity function simply "returns" its template parameter. The second line in main( ) adds the squares of those numbers (16+9+4+1+0), and the last computes the sum of the cubes (64+27+8+1+0)^.

Loop unrolling