Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Front Page / Tutorial: Metafunctions and Higher-Order Metaprogramming / Higher-Order Metafunctions

Higher-Order Metafunctions

In the previous section we used two different forms — metafunction classes and placeholder expressions — to pass and return metafunctions just like any other metadata. Bundling metafunctions into "first class metadata" allows transform to perform an infinite variety of different operations: in our case, multiplication and division of dimensions. Though the idea of using functions to manipulate other functions may seem simple, its great power and flexibility [Hudak89] has earned it a fancy title: higher-order functional programming. A function that operates on another function is known as a higher-order function. It follows that transform is a higher-order metafunction: a metafunction that operates on another metafunction.

[Hudak89]Paul Hudak. "Conception, Evolution, and Application of Functional Programming Languages," ACM Computing Surveys 21, no. 3 Pages: 359 - 411. New York: ACM Press. 1989. ISSN:0360-0300. http://doi.acm.org/10.1145/72551.72554.

Now that we've seen the power of higher-order metafunctions at work, it would be good to be able to create new ones. In order to explore the basic mechanisms, let's try a simple example. Our task is to write a metafunction called twice, which — given a unary metafunction f and arbitrary metadata x — computes:

twice(f, x) := f(f(x))

This might seem like a trivial example, and in fact it is. You won't find much use for twice in real code. We hope you'll bear with us anyway: Because it doesn't do much more than accept and invoke a metafunction, twice captures all the essential elements of "higher-orderness" without any distracting details.

If f is a metafunction class, the definition of twice is straightforward:

template <class F, class X>
struct twice
{
    typedef typename F::template apply<X>::type once;    // f(x)
    typedef typename F::template apply<once>::type type; // f(f(x))
};

Or, applying metafunction forwarding:

template <class F, class X>
struct twice
  : F::template apply<
       typename F::template apply<X>::type
    >
{};

C++ Language Note

The C++ standard requires the template keyword when we use a dependent name that refers to a member template. F::apply may or may not name a template, depending on the particular F that is passed. See the book's Appendix B for more information about template.

Given the need to sprinkle our code with the template keyword, it would be nice to reduce the syntactic burden of invoking metafunction classes. As usual, the solution is to factor the pattern into a metafunction:

template <class UnaryMetaFunctionClass, class Arg>
struct apply1
  : UnaryMetaFunctionClass::template apply<Arg>
{};

Now twice is just:

template <class F, class X>
struct twice
  : apply1<F, typename apply1<F,X>::type>
{};

To see twice at work, we can apply it to a little metafunction class built around the add_pointer metafunction:

struct add_pointer_f
{
    template <class T>
    struct apply : boost::add_pointer<T> {};
};

Now we can use twice with add_pointer_f to build pointers-to-pointers:

BOOST_STATIC_ASSERT((
    boost::is_same<
         twice<add_pointer_f, int>::type
       , int**
    >::value
));