C++ Programming/Templates/Template Meta-Programming

Template Meta-programming overview

Template meta-programming (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. Using types as the basic objects of calculation allows the full power of the type-inference rules to be used for general-purpose computing.

Compile-time programming

The preprocessor allows certain calculations to be carried out at compile time, meaning that by the time the code has finished compiling the decision has already been taken, and can be left out of the compiled executable. The following is a very contrived example:

#define myvar 17

#if myvar % 2
   cout << "Constant is odd" << endl;
#else
   cout << "Constant is even" << endl;
#endif

This kind of construction does not have much application beyond conditional inclusion of platform-specific code. In particular there's no way to iterate, so it can not be used for general computing. Compile-time programming with templates works in a similar way but is much more powerful, indeed it is actually Turing complete.

Trait classes are a familiar example of a simple form of template meta-programming: given input of a type, they compute properties associated with that type as output (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).

The nature of template Meta-programming

Template meta-programming is much closer to functional programming than ordinary idiomatic C++ is. This is because 'variables' are all immutable, and hence it is necessary to use recursion rather than iteration to process elements of a set. This adds another layer of challenge for imperative programmers learning TMP: as well as learning the mechanics of it, they must learn to think in a different way.

Limitations of Template Meta-programming

Because template meta-programming evolved from an unintended use of the template system, it is frequently cumbersome. Often it is very hard to make the intent of the code clear to a maintainer, since the natural meaning of the code being used is very different from the purpose to which it is being put. The most effective way to deal with this is through reliance on idiom; if you want to be a productive template meta-programmer you will have to learn to recognize the common idioms.

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. Even when the compiler supports it, the compile times can be extremely large and in the case of a compile failure the error messages are frequently impenetrable. For a template instantiation debugger, see TempLight.

Some coding standards may even forbid template meta-programming, at least outside of third-party libraries like Boost.

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.[1] TMP has since advanced considerably, and is now a practical tool for library builders in C++, though its complexities mean that it is not generally appropriate for the majority of applications or systems programming contexts.

#include <iostream>

template <int p, int i>
class is_prime {
public:
	enum { prim = ( (p % i) && is_prime<p, i - 1>::prim ) }; 
};

template <int p>
class is_prime<p, 1> {
public:
	enum { prim = 1 };
};

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() {
		a.f();
		if (prim)
		{
			std::cout << "prime number:" << i << std::endl;
		}
	} 
};

template<>
class Prime_print<1> {   // full specialization to end the loop
public:
	enum { prim = 0 };
	void f() {}
};

#ifndef LAST 
#define LAST 18 
#endif

int main()
{
   Prime_print<LAST> a; 
   a.f(); 
}

Building blocks

Values

The 'variables' in TMP are not really variables since their values cannot be altered, but you can have named values that you use rather like you would variables in ordinary programming. When programming with types, named values are typedefs:

struct ValueHolder
{
   typedef int value;
};

You can think of this as 'storing' the int type so that it can be accessed under the value name. Integer values are usually stored as members in an enum:

struct ValueHolder
{
   enum { value = 2 };
};

This again stores the value so that it can be accessed under the name value. Neither of these examples is any use on its own, but they form the basis of most other TMP, so they are vital patterns to be aware of.

Functions

A function maps one or more input parameters into an output value. The TMP analogue to this is a template class:

template<int X, int Y>
struct Adder
{
   enum { result = X + Y };
};

This is a function that adds its two parameters and stores the result in the result enum member. You can call this at compile time with something like Adder<1, 2>::result, which will be expanded at compile time and act exactly like a literal 3 in your program.

Branching

A conditional branch can be constructed by writing two alternative specialisations of a template class. The compiler will choose the one that fits the types provided, and a value defined in the instantiated class can then be accessed. For example, consider the following partial specialisation:

template<typename X, typename Y>
struct SameType
{
   enum { result = 0 };
};

template<typename T>
struct SameType<T, T>
{
   enum { result = 1 };
};

This tells us if the two types it is instantiated with are the same. This might not seem very useful, but it can see through typedefs that might otherwise obscure whether types are the same, and it can be used on template arguments in template code. You can use it like this:

if (SameType<SomeThirdPartyType, int>::result)
{
   // ... Use some optimised code that can assume the type is an int
}
else
{
   // ... Use defensive code that doesn't make any assumptions about the type
}

The above code isn't very idiomatic: since the types can be identified at compile-time, the if() block will always have a trivial condition (it'll always resolve to either if (1) { ... } or if (0) { ... }). However, this does illustrate the kind of thing that can be achieved.

Recursion

Since you don't have mutable variables available when you're programming with templates, it's impossible to iterate over a sequence of values. Tasks that might be achieved with iteration in standard C++ have to be redefined in terms of recursion, i.e. a function that calls itself. This usually takes the shape of a template class whose output value recursively refers to itself, and one or more specialisations that give fixed values to prevent infinite recursion. You can think of this as a combination of the function and conditional branch ideas described above.

Calculating factorials is naturally done recursively: $0!=1$, and for $n>0$, $n!=n\times (n-1)!$. In 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 ];
}

Observe that the factorial<N>::value member is expressed in terms of the factorial<N> template, but this can't continue infinitely: each time it is evaluated, it calls itself with a progressively smaller (but non-negative) number. This must eventually hit zero, at which point the specialisation kicks in and evaluation doesn't recurse any further.

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()
{
  typename if_<true, int, void*>::result number(3);
  typename if_<false, int, void*>::result pointer(&number);

   typedef typename if_<(sizeof(void *) > sizeof(uint32_t)), uint64_t, uint32_t>::result
      integral_ptr_t;
	  
   integral_ptr_t converted_pointer = reinterpret_cast<integral_ptr_t>(pointer);
}

On line 18, we evaluate the if_ template with a true value, so the type used is the first of the provided values. Thus the entire expression if_<true, int, void*>::result evaluates to int. Similarly, on line 19 the template code evaluates to void *. These expressions act exactly the same as if the types had been written as literal values in the source code.

Line 21 is where it starts to get clever: we define a type that depends on the value of a platform-dependent sizeof expression. On platforms where pointers are either 32 or 64 bits, this will choose the correct type at compile time without any modification, and without preprocessor macros. Once the type has been chosen, it can then be used like any other type.

For comparison, this problem is best attacked in C90 as follows

# include <stddef.h>
typedef size_t integral_ptr_t;
typedef int the_correct_size_was_chosen [sizeof (integral_ptr_t) >= sizeof (void *)? 1: -1];

As it happens, the library-defined type size_t should be the correct choice for this particular problem on any platform. To ensure this, line 3 is used as a compile time check to see if the selected type is actually large enough; if not, the array type the_correct_size_was_chosen will be defined with a negative length, causing a compile-time error. In C99, <stdint.h> may define the types intptr_t and uintptr_t.

Debugging TMP

As of 2017, this cannot be done in any meaningful way. Generally it is easier to throw out the templates and start over than try to decipher the byzantine maze of compiler output that results from a single-byte typo in a template metaprogram.

Consider these observations from Herb Sutter, secretary for the C++ standardization committee:

   Herb: Boost.Lambda, is a marvel of engineering… and it worked very well if … if you spelled it exactly right the first time, and didn’t mind a 4-page error spew that told you almost nothing about what you did wrong if you spelled it a little wrong. …

   Charles: talk about giant error messages… you could have templates inside templates, you could have these error messages that make absolutely no sense at all.

   Herb: oh, they are baroque.

Source: https://ofekshilon.com/2012/09/01/meta-programming-is-still-evil/