Template Metaprogramming and Recursion

November 14, 2016

Recently, I have been playing around with template metaprogramming in C++. Whereas ordinary C++ programming is concerned with the domain of values at runtime, metaprogramming extends this to compile time and to programming in the domain of types. This blog post concentrates on the first aspect: compile time computation in the domain of values.

Compile time calculations using constexpr

C++11 and later standards offer two ways of programming at compile time. One is concerned with values, much like ordinary C++. That is, this form of compile time computation takes values known at compile time to produce new values. There are two ways about this: using constexpr functions and templates.

If a function is marked as constexpr, that function may be invoked and evaluated at a compile time. For instance, the following program will compile. It computes the faculty1 of a number n at compile time using constexpr functions. Had faculty not been marked constexpr, the program would not have compiled as the size of a static array needs to be known at compile time.

C++11 restricts calculations within a constexpr function to one return statement. C++14 lifts this restriction allowing a broader range of statements and expressions in constexpr functions. This means that clang++ and g++2 allow you to reformulate the above program as:

Compile time computation on values using templates

However, even in C++98 programers could construct compile time programs. They would use templates instead. The formulation of such compile time programs is very different. Here, there’s no way around it: you have to formulate your programs using recursion and types. Let’s convert the first variant of the faculty function to a template:

This way of calculating a faculty is much more contrived. For each value of N a separate a specialization of the class template it is generated. This specialization contains a static const member value that is equal to the faculty of N, which is calculated using the corresponding member of faculty<N-1>. Recursion is terminated by the explicit specialization for N = 0.

The analogy is clear. Where the first program relied on functions being called recursively, the template version uses recursively created types. The latter is arguably less intuitive and it is easy to see then why constexpr functions were proposed.

Compile time computation on types

However, there are occasions when there is no way around templates. Namely when the computation also revolves around types, rather than values only. E.g., what if the input to a computation is not an integer, but the type int itself? Then we are working in the domain of types and templates are our only option.

But that’s, for another blog post.

  1. The faculty of a number n greater than 0 is denoted by n! and is equal to n \times n - 1 \times \ldots \times 1. The exception is 0!, which is defined to be 1. This operation lends itself to a mathematical definition: for any n > 0, n! = n \times (n-1)!. The recursion ends for n = 0, as 0! = 1 by definition.

  2. Those using Visual C++ 2015 are out of luck