The availability of non-type template parameters makes it possible to perform integer computations at compile-time. For example, the following template computes the factorial of its argument:

template< unsigned n >
struct factorial
{
    static const unsigned value = n * factorial<n-1>::value;
};

template<>
struct factorial<0>
{
    static const unsigned value = 1;
};

The program fragment above is called a metafunction, and it is easy to see its relationship to a function designed to be evaluated at runtime: the ‘metafunction argument’ is passed as a template parameter, and its ‘return value’ is defined as a nested static constant. Because of the hard line between the expression of compile-time and runtime computation in C++, metaprograms look different from their runtime counterparts. Thus, although as in Scheme the C++ metaprogrammer writes her code in the same language as the ordinary program, only a subset of the full C++ language is available to her: those expressions which can be evaluated at compile-time. Compare the above with a straightforward runtime definition of the factorial function:

unsigned factorial(unsigned N)
{
    return N == 0 ? 1 : N * factorial(N - 1);
}

While it is easy to see the analogy between the two recursive definitions, recursion is in general more important to C++ metaprograms than it is to runtime C++. In contrast to languages such as Lisp where recursion is idiomatic, C++ programmers will typically avoid recursion when possible. This is done not only for efficiency reasons, but also because of ‘cultural momentum’: recursive programs are simply harder (for C++ programmers) to think about. Like pure Lisp, though, the C++ template mechanism is a functional programming language: as such it rules out the use of data mutation required to maintain loop variables.

A key difference between the runtime and compile-time factorial functions is the expression of the termination condition: our meta-factorial uses template specialization as a kind of pattern-matching mechanism to describe the behavior when N is zero. The syntactic analogue in the runtime world would require two separate definitions of the same function. In this case the impact of the second definition is minimal, but in large metaprograms the cost of maintaining and understanding the terminating definitions can become significant.

Note also that a C++ metafunction's return value must be named. The name chosen here, value, is the same one used for all numeric returns in the MPL. As we'll see, establishing a consistent naming convention for metafunction returns is crucial to the power of the library.

How could we apply our factorial metafunction? We might, for example, produce an array type of an appropriate size to hold all permutations of instances of another type:

// permutation_holder<T>::type is an array type which can contain 
// all permutations of a given T.

// unspecialized template for scalars
template< typename T >
struct permutation_holder
{
    typedef T type[1][1];
};

// specialization for array types
template< typename T, unsigned N >
struct permutation_holder<T[N]>
{
    typedef T type[factorial<N>::value][N];
};

Here we have introduced the notion of a type computation. Like factorial above, permutation_holder template is a metafunction. However, where factorial manipulates unsigned integer values, permutation_holder accepts and ‘returns’ a type (as the nested typedef type). Because the C++ type system provides a much richer set of expressions than anything we can use as a nontype template argument (e.g. the integers), C++ metaprograms tend to be composed mostly of type computations.

The ability to programmatically manipulate collections of types is a central tool of most interesting C++ metaprograms. Because this capability is so well-supported by the MPL, we'll provide just a brief introduction to the basics here. Later on, we'll revisit the example below to show how it can be implemented using MPL.

First, we'd need a way to represent the collection. One idea might be to store the types in a structure:

struct types
{
    int t1;
    long t2;
    std::vector<double> t3;
};

Unfortunately, this arrangement is not susceptible to the compile-time type introspection power that C++ gives us: there's no way to find out what the names of the members are, and even if we assume that they're named according to some convention as above, there's no way to know how many members there are. The key to solving this problem is to increase the uniformity of the representation. If we have a consistent way to get the first type of any sequence and the rest of the sequence, we can easily access all members:

template< typename First, typename Rest >
struct cons
{
    typedef First first;
    typedef Rest rest;
};

struct nil {};

typedef
      cons<int
    , cons<long
    , cons<std::vector<double>
    , nil
    > > > my_types;

The structure described by types above is the compile-time analogue of a singly-linked list; it has been first introduced by Czarnecki and Eisenecker in [CE98]. Now that we've adjusted the structure so that the C++ template machinery can ‘peel it apart’, let's examine a simple metafunction which does so. Suppose a user wished to find the largest of an arbitrary collection of types. We can apply the recursive metafunction formula which should by now be familiar:

// choose the larger of two types
template<
      typename T1
    , typename T2
    , bool choose1 = (sizeof(T1) > sizeof(T2)) // hands off!
    >
struct choose_larger
{
    typedef T1 type;
};

// specialization for the case where sizeof(T2) >= sizeof(T1)
template< typename T1, typename T2 >
struct choose_larger< T1,T2,false >
{
    typedef T2 type;
};

// get the largest of a cons-list
template< typename T > struct largest;

// specialization to peel apart the cons list
template< typename First, typename Rest >
struct largest< cons<First,Rest> >
    : choose_larger< First, typename largest<Rest>::type >
{
    // type inherited from base
};

// specialization for loop termination
template< typename First >
struct largest< cons<First,nil> >
{
    typedef First type;
};

int main()
{
    // print the name of the largest of my_types
    std::cout
        << typeid(largest<my_types>::type).name()
        << std::endl
        ;
}

There are several things worth noticing about this code:

While these techniques are, of course, a valuable part of the arsenal of any good C++ metaprogrammer, their use tends to make programs written in what is already an unusual style harder-to-read and harder-to-write. By encapsulating commonly-used structures and dealing with loop terminations internally, the MPL reduces the need for both tricky hacks and for template specializations.