Template metaprogramming

From Free net encyclopedia

Template metaprogramming is a programming technique in which templates are leveraged 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.

1 Factorial with recursion
2 Benefits and drawbacks of template metaprogramming
3 See also
4 References
5 External links

[edit]

Factorial with recursion

What exactly "programming at compile-time" means is best illustrated with this simple example:

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

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

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

Using template metaprogramming, one could write

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

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

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

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().

In the D programming language, the factorial template would look like:

template Factorial(int n)
{
 static if (n == 1)
   const Factorial = 1;
 else
   const Factorial = n * Factorial!(n-1);
}
// Factorial!(4) == 24

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;
}

When the compiler instantiates the templated function defined above, the following code will be produced:

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

The compiler's optimizer is able to un-roll the 'for' loop because the template parameter 'dimension' is a constant at compile-time. For a real implementation of this technique, see this post on flipcode.com.

In C++, template metaprogramming is Turing-complete, meaning that any computation expressible by a computer 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.

[edit]

Benefits and drawbacks of template metaprogramming

Compile-time versus execution-time tradeoff: Since all templated code is processed, evaluated and expanded at compile-time, compilation will take longer while the executable code may be more efficient. Though this overhead generally is miniscule, for large projects, or projects relying pervasively on templates, it may be significant.
Generic programming: Template metaprogramming allows the programmer to focus on architecture and delegate to the compiler the generation of any implementation required by client code. Thus, template metaprogramming can accomplish truly generic code, facilitating code minimisation and maintainability.
Readability: The syntax and idioms of template metaprogramming are esoteric compared to conventional C++ programming, and advanced, or even most non-trivial, template metaprogramming can be very difficult to understand. Metaprograms can thus be difficult to maintain by programmers unexperienced in templated metaprogramming.
Portability: Due to differences in compilers, code relying heavily on template metaprogramming (especially the newest forms of metaprogramming) might have portability issues.

[edit]

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 Du Toit: Metaprogramming GPUs with Sh, A K Peters, ISBN 1568812299
Manuel Clavel: Reflection in Rewriting Logic: Metalogical Foundations and Metaprogramming Applications, ISBN 1575862387