Template metaprogramming

Template metaprogramming is a programming technique in which templates are used in unusual ways so that the compiler, in the act of compiling the code, executes a program. The output of these programs range from compile-time constants in the resulting executable to data structures. The technique is used primarily in the C++ programming language.

The meaning of "programming at compile-time" means is best illustrated with a simple example:

Contents

1 Factorial with recursion 2 See also 3 References 4 External links

Factorial with recursion

In C++, a factorial function can be written recursively as follows:

int factorial(int n) {
  if (n == 1)
    return 1;
  else
    return n * factorial(n - 1);
}

// factorial(4) == (4 * 3 * 2 * 1) == 24

Using template metaprogramming, one could write

template <int N>
struct Factorial {
  enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<1> {
  enum { value = 1 };
};

// Factorial<4>::value == 24

The template metaprogramming solution uses template specialization to provide the ending condition for the recursion. While the two versions are similar, in the latter case, Factorial<4>::value is computed at compile time. This has the natural consequence that Factorial<x>::value can only be used if x is known at compile time, that is if x is a constant or the result of a call to sizeof().

Template metaprogramming does have its practical uses even though its syntax looks clumsy. It may be used to create n-dimensional vector classes where n is known at compile time. The benefit over a more traditional n-dimensional vector is that the loops can be unrolled, resulting in very optimized code.

Consider this example of the addition operator. An n-dimensional vector addition might be written as

template<int dimension>
Vector<dimension>& Vector<dimension>::operator+=(const Vector<dimension>& rhs) {
  for (int i = 0; i < dimension; ++i) {
    value[i] += rhs.value[i];
  }
  return *this;
}

With template metaprogramming, the loop can be unrolled at compile-time, resulting in code similar to

template<>
Vector<2>& Vector<2>::operator+=(const Vector<2>& rhs) {
  value[0] += rhs.value[0];
  value[1] += rhs.value[1];
  return *this;
}

Note that it results in code like that, but is not programmed like that. But it demonstrates that the loop is gone and so is the loop's overhead. For a real implementation of this technique, see this post on flipcode.com (http://www.flipcode.com/cgi-bin/msg.cgi?showThread=Tip-UnrollingLoopsMeta&forum=totd&id=-1).

In C++, template metaprogramming is Turing-complete, meaning that any computation expressable by a comptuer program can be computed, in some form, by a template metaprogram.

Template metaprograms have no mutable variables—that is, no variable can change value once it has been initialized. A result of this is that, unlike run-time C++, template metaprogramming is a form of functional programming. For this reason, flow control in metaprograms is done through recursion, as seen above.

See also

• Comparison of generics to templates
• More on metaprogramming.

References

• Krzysztof Czarnecki, Ulrich W. Eisenecker: Generative Programming: Methods, Tools, and Applications, Addison-Wesley, ISBN 0-201-30977-7
• Andrei Alexandrescu: Modern C++ Design: Generic Programming and Design Patterns Applied, Addison-Wesley, ISBN 3-8266-1347-3
• David Abrahams, Aleksey Gurtovoy: C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond, Addison-Wesley, ISBN 0-321-22725-5
• David Vandervoorde, Nicolai M. Josuttis: C++ Templates: The Complete Guide, Addison-Wesley, ISBN 0-2017-3484-2
• Michael McCool, Stefanus DuToit: Metaprogramming GPUs with Sh, A K Peters, ISBN 1568812299
• Manuel Clavel: Reflection in Rewriting Logic: Metalogical Foundations and Metaprogramming Applications, ISBN 1575862387

External links

• The Boost Metaprograming Library (Boost MPL) (http://www.boost.org/libs/mpl/doc/)
• The Spirit Library (built using template-metaprogramming) (http://www.boost.org/libs/spirit/)
• The Boost Lambda library (use STL algorithms easily) (http://www.boost.org/libs/lambda/doc/)
• "The" article by Todd Veldhuizen from 1995 (http://osl.iu.edu/~tveldhui/papers/Template-Metaprograms/meta-art.html)