Template Meta-Programming

Over the years I have learned to value the maintainability of my code first. Then I make the proper adjustments if I discover a section of code that needs to be ported, optimized or reworked in some other way. With this in mind, I thought that template meta-programming had no place in production code. I believed that meta-programs were a novelty, clever displays of skill, and not capable of much more than the trivial implementations of a factorial or Fibonacci sequence calculation. I have completely changed my mind on this topic and will show you how meta-programs can provide value and create the most maintainable implementation possible.

Template meta-programming is the practice of using templates to generate types and functions to perform computations at compile-time and generate programs. The type system in C++ requires the compiler to calculate many types of expressions for the proper code to be generated. Meta-programming takes advantage of this capability to create programs that are calculated at compile-time rather than run-time. It has been shown that the BNF grammar for templates in C++ is Turing Complete. This means that potentially any calculatable value could be calculated with the C++ compiler at compile-time. The primary restriction would be the internal compiler resources. This is quite a bit of flexibility.

Why Meta-Program?

There are three primary reasons to consider a solution based on a meta-program:

1. Improved Type-Safety
   Type-safety leads to a more correct program. The intentions of the programmer are more obvious to the compiler by way of operations that are specifically designed for a particular type. The compiler will perform less implicit casting must be performed, and be able to make better choices when generating code from your program when it is provided with more accurate information. Program structures, optimizations, and overloaded function selection are a few examples of the decisions that may be improved with more type information.
2. Increased Run-time Performance
   As I stated earlier, the compiler will perform many of the calculations, therefore all that remains to be generated for run-time is the result. The potential improvements at run-time can include both processing speed, reduced program size and a reduced memory footprint. The improved type-safety contributes tremendously to the amount of increased performance experienced from higher quality code generation.
3. Compile-time Verification
   This item could be classified as a sub-topic under improved type-safety, however, I think that it is valuable enough all by itself to list it as its own reason. Employing the use of a static_assert to verify certain aspects of a program at compile-time is a much more reliable mechanism to test invariants of a program than run-time testing. Because the invariant cannot be verified if that aspect of the program is not executed during run-time testing. However, the compiler must parse the static assertion in order to successfully compile the application. If the assertion fails, the program will fail to compile. I have used this technique to successfully verify proper transitions programmed into state-machines, accurate buffer sizes where allocated and accessed and proper definitions were created for network packet construction.

Quick Example

Generally, a mathematical calculation that uses a recursive implementation is used as an introductory example to meta-programming. I would like to demonstrate an example of a compile-time conditional expression in order to help expand your understanding of how meta-programming can be applied. First, we will create a simple expression to calculate a Boolean value at compile-time based on a type. Then we will write an expression that uses the calculated Boolean value to select the desired implementation of a function.

// We will start with defining a type that will behave as a boolean value.
//
//   selector<true>
//     AND
//   selector<false> 
//
// are considered two separate types
template <bool Predicate>
struct selector
{
};

Type, and create a construct that we can use to determine if two types are equal:

// This template simplifies type-deduction for the compiler.
// Use the selector when composing more sophisticated objects.
   
// False Case
template <typename T1, typename T2>
struct type_equal 
  : selector<false>
{
  static const bool value = false;
};

// True Case
template <typename T>
struct type_equal<T ,T> 
  : selector<true>
{
  static const bool value = true;
};

Selector meta-programming construct:

// The type_equal constant can be accessed like this without selector
//    type_equal<T1 ,T2>::value
//
// However, if a parameterized type populates a selector, the bool
// value will automatically be deduced because it is part of the type.
template <typename iterator_t>
void random_fill(iterator_t begin, iterator_t end, selector<false>)
{
  for (; begin != end; ++begin)
    *begin = rand();
}
 
//
// This version is special for Characters, use one of the 26 capital letters for the random fill.    
template <typename iterator_t>
void random_fill(iterator_t begin, iterator_t end, selector<true>)
{
  for (; begin != end; ++begin)
    *begin = 'A' + (rand() %26);
}

ll functions. The strict explicit syntax can be used, which is a bit cumbersome. There is also a streamlined version to use the random_fill call. Both examples are demonstrated below:

// Cumbersome invocation:
random_fill(begin, end, selector<type_equal <T, char*>::value>());
     
// Simpler invocation because of type deduction:
random_fill(begin, end, type_equal<T , char*>());

In Practice

template meta-programming reduces to functional programming. Functional programming treats computation as the evaluation of mathematical functions where state and mutable data is avoided. The strong type system in C++ provides the mechanism to maintain variables in the form of new types. Values are calculated and stored and accessed through static constants or enumerations. This is a major change from the imperative development style used in C++ by default. A little practice is required to make this shift in approach to how the problem is solved. However, just like picking up any new language, a little practice is all that is required and you can be dangerous. Proficient, masterful and elegant will take a bit more time, but you can reach that point if you are willing to persist.

One great aspect of meta-programming is that if it compiles, generally it will work. That is not to say that it does what you intended, or that it works correctly. The corresponding drawback is if it fails to compile, there is no tool comparable to the debugger for determining the cause of the error in your meta-program. For the most part you will revert to the equivalent of printf debugging by interpreting the compiler errors.

How Can This Be Maintainable?

That is a fair question, after all I did say that I believe meta-programming can have a place in production code. Many engineers are still afraid to experiment with templates. Therefore, I think the best way to introduce meta-constructs into a production application is by aliasing with typedefs or encapsulating with overloaded function calls. This will make the call to invoke the constructs appear in normal and natural format to any engineer that uses the methods.

This is an acceptable method because as long as the behavior of the accessible construct is well documented to the caller, the implementation details should be of little importance to the application programmer; especially if the function call produces the correct result, and does not cause a burden on performance. This will reduce the risk of an unintentional change being made to the meta-programming constructs.

Conclusion

I have just barely scratched the surface for what exists with regards to template meta-programming. I plan on discussing this further as I build up a small utility library of meta-programming constructs that can be used to construct small generic implementations that are robust and adaptable for many uses.

I would not add a meta-programming construct to your application unless there is a clear advantage over the alternative imperative implementation. Adding clever code simply to show-off your skills is best left for programming contests and pet projects. Nonetheless, what I have learned by playing with meta-programming in the last year has shown me how valuable this style can be. If nothing else, it has given me another perspective on how to approach solving a problem, even if I return to the imperative solution as my final answer.