17.1 A First Example of a Metaprogram

Ru-Brd

In 1994 during a meeting of the C++ standardization committee, Erwin Unruh discovered that templates can be used to compute something at compile time. He wrote a program that produced prime numbers. The intriguing part of this exercise, however, was that the production of the prime numbers was performed by the compiler during the compilation process and not at run time. Specifically, the compiler produced a sequence of error messages with all prime numbers from two up to a certain configurable value. Although this program wasn't strictly portable (error messages aren't standardized), the program did show that the template instantiation mechanism is a primitive recursive language that can perform nontrivial computations at compile time. This sort of compile-time computation that occurs through template instantiation is commonly called template metaprogramming .

As an introduction to the details of metaprogramming we start with a simple exercise (we will show Erwin's prime number program later on page 318). The following program shows how to compute at compile time the power of three for a given value:

  // meta/pow3.hpp  #ifndef POW3_HPP  #define POW3_HPP  // primary template to compute  3  to the  N  th  template<int N>  class Pow3 {    public:      enum { result=3*Pow3<N-1>::result };  };  // full specialization to end the recursion  template<>  class Pow3<0> {    public:      enum { result = 1 };  };  #endif  // POW3_HPP  

The driving force behind template metaprogramming is recursive template instantiation. ^[1] In our program to compute 3 ^N , recursive template instantiation is driven by the following two rules:

^[1] We saw an example of a recursive template in Section 12.4 on page 200. It could be considered a simple case of metaprogramming.

1. 3 ^N = 3 * 3 ^{N - 1}

2. 3 = 1

The first template implements the general recursive rule:

 template<int N>  class Pow3 {    public:      enum { result = 3 * Pow3<N-1>::result };  }; 

When instantiated over a positive integer N , the template Pow3<> needs to compute the value for its enumeration value result . This value is simply twice the corresponding value in the same template instantiated over N-1 .

The second template is a specialization that ends the recursion. It establishes the result of Pow3<0> :

 template<>  class Pow3<0> {    public:      enum { result = 1 };  }; 

Let's study the details of what happens when we use this template to compute 3 ⁷ by instantiating Pow3<7> :

  // meta/pow3.cpp  #include <iostream>  #include "pow3.hpp"  int main()  {      std::cout << "Pow3<7>::result = " << Pow3<7>::result                << '\n';  } 

First, the compiler instantiates Pow3<7> . Its result is

 3 * Pow3<6>::result 

Thus, this requires the instantiation of the same template for 6 . Similarly, the result of Pow3<6> instantiates Pow3<5> , Pow3<4> , and so forth. The recursion stops when Pow3<> is instantiated over zero which yields one as its result .

The Pow3<> template (including its specialization) is called a template metaprogram . It describes a bit of computation that is evaluated at translation time as part of the template instantiation process. It is relatively simple and may not look very useful at first, but there are situations when such a tool comes in very handy.

Ru-Brd