More C++ Idioms/Metafunction

Metafunction

Intent

• To encapsulate a complex type computation algorithm
• To generate a type using compile-time type selection techniques

Motivation

Templates are a powerful feature of C++, which can be used to perform arbitrary computations at compile-time, which is known as template metaprogramming. Some of the basic examples of the computations performed at compile-time are: (1) selection of a type based on compile-time constants or (2) computing factorial of a number. As a matter of fact, C++ templates is a turing complete sub-language of C++. Metafunction idiom is the principal way of writing compile-time algorithms in C++.

Algorithms -- compile-time or run-time -- should be encapsulated so that they are easier to use and reuse. Conventionally, run-time algorithms are encapsulated in functions that are invoked, obviously, at run-time. Metafunctions, on the other hand, are compile-time analogs of run-time functions. Traditional functions accept values/objects as parameters and return values/objects. However, metafunctions accept types and compile-time constants as parameters and return types/constants.

Solution and Sample Code

A metafunction, contrary to its name, is a class template. Implementation of metafunctions is often based on template specializations. For example, consider the following IF metafunction, which is compile-time equivalent of run-time if statement. Depending upon the value of the first parameter, IF metafunction yields either an int or a long in the example below.

template <bool, class L, class R>
struct IF
{
  typedef R type; 
};

template <class L, class R>
struct IF<true, L, R>
{
  typedef L type; 
};

IF<false, int, long>::type i; // is equivalent to long i;
IF<true,  int, long>::type i; // is equivalent to int i;

Factorial metafunction below is another example showing how a recursive factorial computation algorithm can be encapsulated using C++ templates. This metafunction yields an integral value rather than a type.

template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};
 
template <>
struct Factorial<0> 
{
    enum { value = 1 };
};
 
// Factorial<4>::value == 24
// Factorial<0>::value == 1
void foo()
{
    int x = Factorial<4>::value; // == 24
    int y = Factorial<0>::value; // == 1
}

Metafunction and Type Generator

Metafunction is a more general idiom than the type generator idiom. The intent of the metafunction idiom is to encapsulate compile-time computation whereas, type generator simplifies specification of a type. Metafunctions that produce type(s) as a result of a compile-time computation are type generators, but not every metafunction is a type generator. For example, the Factorial metafunction shown before produces an integral value, not a type. Metafunctions are often implemented using compile-time control structures or other metafunctions.

Libraries such as Boost.MPL provide a large collection of metafunctions and compile-time data structures to simplify C++ template metaprogramming.

Higher order metafunctions

These are metafunctions that accept other metafunctions as parameters and use them during computation. This is conceptually similar to a function accepting a pointer to another function or a function object as a parameter at run-time. The only difference is that metafunctions exist only at compile-time. boost::mpl::transform is an example of such a higher order metafunction.

Known Uses

Boost.MPL

Related Idioms

• Type Generator

References

A Deeper Look at Metafunctions -- David Abrahams and Aleksey Gurtovoy