The Artima Developer Community
Sponsored Link

The C++ Source
A Deeper Look at Metafunctions
by David Abrahams and Aleksey Gurtovoy
August 23, 2004

<<  Page 2 of 3  >>

Advertisement

3.1.5  Implementing Division

Division is similar to multiplication, but instead of adding exponents, we must subtract them. Rather than writing out a near duplicate of plus_f, we can use the following trick to make minus_f much simpler:

struct minus_f
{
    template <class T1, class T2>
    struct apply
      : mpl::minus<T1,T2> {};
};

Here minus_f::apply uses inheritance to expose the nested type of its base class, mpl::minus, so we don't have to write:

typedef typename ...::type type

We don't have to write typename here (in fact, it would be illegal), because the compiler knows that dependent names in apply's initializer list must be base classes.[2] This powerful simplification is known as metafunction forwarding; we'll apply it often as the book goes on.[3]

Syntactic tricks notwithstanding, writing trivial classes to wrap existing metafunctions is going to get boring pretty quickly. Even though the definition of minus_f was far less verbose than that of plus_f, it's still an awful lot to type. Fortunately, MPL gives us a much simpler way to pass metafunctions around. Instead of building a whole metafunction class, we can invoke transform this way:

typename mpl::transform<D1,D2, mpl::minus<_1,_2> >::type

Those funny looking arguments (_1 and _2) are known as placeholders, and they signify that when the transform's BinaryOperation is invoked, its first and second arguments will be passed on to minus in the positions indicated by _1 and _2, respectively. The whole type mpl::minus<_1,_2> is known as a placeholder expression.

Note

MPL's placeholders are in the mpl::placeholders namespace and defined in boost/mpl/placeholders.hpp. In this book we will usually assume that you have written:

#include<boost/mpl/placeholders.hpp>
using namespace mpl::placeholders;

so that they can be accessed without qualification.

Here's our division operator written using placeholder expressions:

template <class T, class D1, class D2>
quantity< 
    T
  , typename mpl::transform<D1,D2,mpl::minus<_1,_2> >::type
>
operator/(quantity<T,D1> x, quantity<T,D2> y)
{
   typedef typename 
     mpl::transform<D1,D2,mpl::minus<_1,_2> >::type dim;

   return quantity<T,dim>( x.value() / y.value() );
}

This code is considerably simpler. We can simplify it even further by factoring the code that calculates the new dimensions into its own metafunction:

template <class D1, class D2>
struct divide_dimensions
  : mpl::transform<D1,D2,mpl::minus<_1,_2> > // forwarding again
{};

template <class T, class D1, class D2>
quantity<T, typename divide_dimensions<D1,D2>::type>
operator/(quantity<T,D1> x, quantity<T,D2> y)
{
   return quantity<T, typename divide_dimensions<D1,D2>::type>(
      x.value() / y.value());
}

Now we can verify our "force-on-a-laptop" computation by reversing it, as follows:

quantity<float,mass> m2 = f/a;
float rounding_error = std::abs((m2 - m).value());

If we got everything right, rounding_error should be very close to zero. These are boring calculations, but they're just the sort of thing that could ruin a whole program (or worse) if you got them wrong. If we had written a/f instead of f/a, there would have been a compilation error, preventing a mistake from propagating throughout our program.

3.2  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 Press New York, NY, USA Pages: 359 - 411, 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 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
));

3.3  Handling Placeholders

Our implementation of twice already works with metafunction classes. Ideally, we would like it to work with placeholder expressions too, much the same as mpl::transform allows us to pass either form. For example, we would like to be able to write:

template <class X>
struct two_pointers
    : twice<boost::add_pointer<_1>, X>
{};

But when we look at the implementation of boost::add_pointer, it becomes clear that the current definition of twice can't work that way.

template <class T>
struct add_pointer
{
    typedef T* type;
};

To be invokable by twice, boost::add_pointer<_1> would have to be a metafunction class, along the lines of add_pointer_f. Instead, it's just a nullary metafunction returning the almost senseless type _1*. Any attempt to use two_pointers will fail when apply1 reaches for a nested ::apply metafunction in boost::add_pointer<_1> and finds that it doesn't exist.

We've determined that we don't get the behavior we want automatically, so what next? Since mpl::transform can do this sort of thing, there ought to be a way for us to do it too—and so there is.

3.3.1  The lambda Metafunction

We can generate a metafunction class from boost::add_pointer<_1>, using MPL's lambda metafunction:

template <class X>
struct two_pointers
  : twice<typename mpl::lambda<boost::add_pointer<_1> >::type, X>
{};

BOOST_STATIC_ASSERT((
    boost::is_same<
        typename two_pointers<int>::type
      , int**
    >::value
));

We'll refer to metafunction classes like add_pointer_f and placeholder expressions like boost::add_pointer<_1> as lambda expressions. The term, meaning "unnamed function object," was introduced in the 1930s by the logician Alonzo Church as part of a fundamental theory of computation he called the lambda-calculus.[4] MPL uses the somewhat obscure word lambda because of its well-established precedent in functional programming languages.

Although its primary purpose is to turn placeholder expressions into metafunction classes, mpl::lambda can accept any lambda expression, even if it's already a metafunction class. In that case, lambda returns its argument unchanged. MPL algorithms like transform call lambda internally, before invoking the resulting metafunction class, so that they work equally well with either kind of lambda expression. We can apply the same strategy to twice:

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

Now we can use twice with metafunction classes and placeholder expressions:

int* x;

twice<add_pointer_f, int>::type           p = &x;
twice<boost::add_pointer<_1>, int>::type q = &x;

3.3.2  The apply Metafunction

Invoking the result of lambda is such a common pattern that MPL provides an apply metafunction to do just that. Using mpl::apply, our flexible version of twice becomes:

#include <boost/mpl/apply.hpp>

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

You can think of mpl::apply as being just like the apply1 template that we wrote, with two additional features:

  1. While apply1 operates only on metafunction classes, the first argument to mpl::apply can be any lambda expression (including those built with placeholders).

  2. While apply1 accepts only one additional argument to which the metafunction class will be applied, mpl::apply can invoke its first argument on any number from zero to five additional arguments.[5] For example:

    // binary lambda expression applied to 2 additional arguments
    mpl::apply<
        mpl::plus<_1,_2>   
      , mpl::int_<6>
      , mpl::int_<7>
    >::type::value // == 13
    
Guideline

When writing a metafunction that invokes one of its arguments, use mpl::apply so that it works with lambda expressions.

3.4  More Lambda Capabilities

Lambda expressions provide much more than just the ability to pass a metafunction as an argument. The two capabilities described next combine to make lambda expressions an invaluable part of almost every metaprogramming task.

3.4.1  Partial Metafunction Application

Consider the lambda expression mpl::plus<_1,_1>. A single argument is directed to both of plus's parameters, thereby adding a number to itself. Thus, a binary metafunction, plus, is used to build a unary lambda expression. In other words, we've created a whole new computation! We're not done yet, though: By supplying a non-placeholder as one of the arguments, we can build a unary lambda expression that adds a fixed value, say 42, to its argument:

mpl::plus<_1, mpl::int_<42> >

The process of binding argument values to a subset of a function's parameters is known in the world of functional programming as partial function application.

3.4.2  Metafunction Composition

Lambda expressions can also be used to assemble more interesting computations from simple metafunctions. For example, the following expression, which multiplies the sum of two numbers by their difference, is a composition of the three metafunctions multiplies, plus, and minus:

mpl::multiplies<mpl::plus<_1,_2>, mpl::minus<_1,_2> >

When evaluating a lambda expression, MPL checks to see if any of its arguments are themselves lambda expressions, and evaluates each one that it finds. The results of these inner evaluations are substituted into the outer expression before it is evaluated.

<<  Page 2 of 3  >>


Sponsored Links



Google
  Web Artima.com   
Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us