3.5 Intermezzo

You can find early examples of template metaprograms in Veldhuizen (1995). Czarnecki and Eisenecker (2000) discuss this problem in depth and provide a full collection of compile-time simulations for C++ statements.

The conception and implementation of Length resembles a classic recursion example given in computer science classes: the algorithm that computes the length of a singly linked list structure. (There are two major differences, though: The algorithm for Length is performed at compile time, and it operates on types, not on values.)

This naturally leads to the following question: Couldn't we develop a version of Length that's iterative, instead of recursive? After all, iteration is more natural to C++ than recursion. Getting an answer to this question will guide us in implementing the other Typelist facilities.

The answer is no, and for interesting reasons.

Our tools for compile-time programming in C++ are templates, compile-time integer calculations, and type definitions (typedefs). Let's see in what ways each of these tools serves us.

Templates—more specifically, template specialization—provide the equivalent of if statements at compile time. As seen earlier in the implementation of Length, template specialization enables differentiation between typelists and other types.

Integer calculations allow you to make true value computations, to jump from types to values. However, there is a peculiarity: All compile-time values are immutable. After you've defined an integral constant, say an enumerated value, you cannot change it (that is, assign another value to it).

Type definitions (typedefs) can be seen as introducing named type constants. Again, after definition, they are frozen—you cannot later redefine a typedef'd symbol to hold another type.

These two peculiarities of compile-time calculation make it fundamentally incompatible with iteration. Iteration is about holding an iterator and changing it until some condition is met. Because we don't have mutable entities in the compile-time world, we cannot do any iteration at all. Therefore, although C++ is mostly an imperative language, any compile-time computation must rely on techniques that definitely are reminiscent of pure functional languages—languages that cannot mutate values. Be prepared to recurse heavily.