typelists: MPL tutorial + partial review

From: Mat Marcus (mmarcus_at_[hidden])
Date: 2001-12-11 05:12:16

1. Introduction

There has been a fair amount of general philosophical discussion
lately about Loki and MPL. I think we might benefit by examining more
concrete use cases to get a better feel for what is offered. To
continue in this direction, today I will report on some recent
experiences using MPL. I have been spending my spare cycles over the
last week or so trying to figure out some of MPL's key mechanisms. In
a recent article I reported on implementing Loki's HierarchyGenerators
to work with MSVC (see
        <http://groups.yahoo.com/group/boost/message/20944> ).
In this article I will implement HierarchyGenerators using MPL. Along
the way I hope to:

      * Further our review of typelists by offering a concrete usage
        example with a possible move towards AbstractFactory
      * Provide a tutorial on using boost::mpl
      * Offer a partial review of boost::mpl
      * Begin a port of Loki's HierarchyGenerators to MSVC

If I manage to work out some additional VC bugs I can post an MPL
version of HierarchyGenerators to the files section.

Note: this article represents my own attempt to understand
MPL. Aleksey, please correct me where I'm mistaken. Also, it's late at
night and I'm sure there are plenty of mistakes below...

2. GenLinearHierarchy

2.1 GenLinHierarchy Specification

GenLinearHierarchy accepts three inputs: a list of types, a "glue
metafunction", and an optional root class. In return
GenLinearHierarchy<TList, Glue, Root>::type generates a linear
hierarchy which is best described by the following example picture.
Lets look at:

   GenLinearHierarchy<
     type_list<Window, Button, ScrollBar>, EventHandler, EmptyType>::type

In this example is EmptyType is just a struct with no members, and
EventHandler<T,...> provides one virtual function which OnEvent. That
is:

   struct EmptyType {};

   template <class T, class Base>
   struct EventHander : public Base
   {
     virtual void OnEvent(T& obj, int eventID) = 0;
   };

Then GenLinearHierarchy will give us:

   EmptyType
       ^
       |
       |
   EventHander<Window, EmptyType>
       ^
       |
       |
   EventHandler<Button, EventHander<Window, EmptyType> >
       ^
       |
       |
   EventHandler<ScrollBar, EventHandler<Button,
                        EventHander<Window, EmptyType> > >
       ^
       |
       |
   GenLinearHierarchy<type_list<Window, Button, ScrollBar>,
                                        EventHandlerQuoted,
                                        EmptyType> >::type

2.2 GenlinearHierarchy MPL implementation

The implementation in MPL is a one-liner.

   template <class TList, class Glue, class Root = EmptyType>
   struct GenLinearHierarchy {
     typedef boost::mpl::for_each<TList, Root, Glue>::state type;
   };

Client code will look like this:

   template <class T, class Base>
   struct EventHander : public Base
   {
     virtual void OnEvent(T& obj, int eventID) = 0;
   };

   BOOST_MPL_MAKE_F_YX_TMPL(EventHandlerQuoted, EventHandler);

   GenLinearHierarchy<type_list<Window, Button, ScrollBar>,
                      EventHandlerQuoted,
                      EmptyType> >::type v;

This example requires some explanation. First let's examine
for_each. For_each behaves somewhat like std::accumulate. In fact,
"reduce" might be a better name for it. For_each accepts a type_list,
an initial state, and a binary "quoted metafunction". First, for_each
applies the "quoted metafunction" to the initial state and the first
element of the type-list to obtain the next state2. Then for_each
applies the "quoted metafunction" to state2 and the second type_list
element to obtain state3, and so on. For_each returns the final state
as a nested typedef named "state".

But what is a "quoted metafunction"?  Well, all MPL algorithms expect
any of their arguments which happen to be metafunctions to be wrapped
up in a struct. This technique is described in Czarnecki and
Eisenecker's Generative Programming Book as an alternative to using
template template parameters. I find it very helpful to think of these
struct-wrapped metafunctions as "quoted". (Here I borrow the #'
concept from common lisp. In common lisp, functions must be #' quoted
to be passed as parameters to other functions. Another alternative
would be to talk about the address of a metafunction but that seems
more confusing. Perhaps someone will come up with a better name). A
quoted metafunction is eval-ed (applied) by calling its nested apply
template. An example will probably help here:

Plain old template, EventHandler:

   template <class T, class Base>
   struct EventHander : public Base
   {
     virtual void OnEvent(T& obj, int eventID) = 0;
   };

Metafunction, EventHandlerMF, returning EventHandler:

   template <class T, class Base>
   struct EventHanderMF
   {
     typedef EventHadler<T, Base> type;
   };

Quoted Metafunction, EventHandlerQuoted, for use with MPL algorithms:

   struct EventHandlerQuoted {
     template<typename T, typename Base>
     struct apply {
       typedef EventHandler<T, Base> type;
     };
   };

MPL provides some convenience macros for creating "quoted
metafunctions" from normal metafunctions. So instead of writing
EventHandlerQuoted by hand as above we can simply write:

   BOOST_MPL_MAKE_F_XY(EventHandlerQuoted, EventHandlerMF);

Sometimes it is convenient to create a quoted metafunction directly
from a template so I added another macro to do so:

   BOOST_MPL_MAKE_F_XY_TMPL(EventHandlerQuoted, EventHandler);

There are also X (one argument) and YX (reverse arguments)
versions. MPL also provides unary_function and binary_function that,
amongst other things, can be viewed as a way to create a metafunction
from a quoted metafunction.  To summarize, the following types are
equivalent

   ::boost::mpl::binary_function<EventHandlerQuoted, T, Base>::type

   EventhandlerQuoted::template apply<T, Base>::type

   EventHandlerMF<T,Base>::type

   EventHandler<T,Base>

It is worth noting that the first form can fare better with VC 6/7
then the second form above. (See my previous article
   <http://groups.yahoo.com/group/boost/message/20944>
for more details.)

3. GenScatterHierarchy

3.1 GenScatterHierarchy Specification

Like GenLinearHierarchy, GenScatterHierarchy generates a class with
interesting ancestors. In this case however we use multiple
inheritance to create a tree of ancestors. Let's examine the class
diagram for GenScatterHierarchy<type_list<char, short, int>,
HolderQuoted> > :

     // Node is an apply-based metafunction which will produce a node
     // which inherits from its second argument and HolderQuoted applied to its
     // first argument.
     //
     //             HolderQuoted<char>  EmptyType
     //                             \   /
     //                              \ /
     //         HolderQuoted<short>   *
     //                          \   /
     //                           \ /
     //      HolderQuoted<long>    *
     //                       \   /
     //                        \ /
     //                         *
     //                        /
     //                       /
     //              GenScatterHierarchy
     //
     //                               * = implementation class: name ommitted

Note that Loki uses a slightly different tree.

3.2 MPL GenScatterHierarchy Implementation

// First we declare some building block templates and metafunctions:
   template <class L, class R>
   struct InheritTwo : public  L , public R
   {
     typedef L Left;
     typedef R Right;
   };

   template <class ScatterHier>
   struct LeftParent
   {
     typedef typename ScatterHier::Left type;
   };

   template <class ScatterHier>
   struct RightParent
   {
     typedef typename ScatterHier::Right type;
   };

   BOOST_MPL_MAKE_F_X(LeftParentQuoted, LeftParent);
   BOOST_MPL_MAKE_F_X(RightParentQuoted, RightParent);
   BOOST_MPL_MAKE_F_YX_TMPL(ReverseInheritTwoQuoted, InheritTwo);

// Now we can define GenScatterHierarchy

   template <class TList, class QuotedMF>
   struct GenScatterHierarchy {

   public:
     typedef boost::mpl::for_each<
       TList          // for each type in TList
       , EmptyType    // begin with state EmptyType
       , boost::mpl::compose_f_gx_hy<
         ReverseInheritTwoQuoted
         , boost::mpl::identity<boost::mpl::_1>
         , QuotedMF>
          // apply binary metafunctor mapping <oldState, aType>
          // to InheritTwo<unary_function<Unit,aType>::type, oldState>
     >::state type;
   };

We employ mpl::for_each once again. The twist here is our use of
mpl::compose. Compose is just as useful in mpl as it is in stl. We
prefer not to have to create the appropriate quoted metafunction by
hand. So instead we "dynamically" generate it with compose_f_gx_hy. In
pseudo-meta-code this looks like:ReverseInheritQuoted(_1,
QuotedMF(_2)).  Here _1 and _2 are place holders for the arguments to
the composed metafunction.

4 Fields

4.1 Fields Specification

Loki defines accessor function templates for scatter hierarchies. One
form of accessor accepts an integer index and returns a reference to
the part of the object which instantiates the type at that index. In
other words:

GenScatterHierarchy<type_list<char, short, long>,
                     HolderQuoted>::type h;
Fields<1>(h); // refers to the Holder<short> part of h.

4.2 Fields Implementation

   template <int N, class TList, class QuotedMF>
   inline typename ::boost::mpl::unary_function<QuotedMF,
     typename boost::mpl::at<N, TList>::type>::type&
   Fields(typename GenScatterHierarchy<TList, QuotedMF>& obj)
   {
     typedef boost::mpl::for_loop<
       boost::mpl::int_t<N + 1>
       , boost::mpl::lt<boost::mpl::size<TList>::value>
       , boost::mpl::next<boost::mpl::_1>
       , GenScatterHierarchy<TList, QuotedMF>
       , boost::mpl::compose_f_gxy<
          detail::RightParent
          , ::boost::mpl::project1st<boost::mpl::_1,boost::mpl::_2>
          >
       >::executed::state hier;

     typedef typename
       ::boost::mpl::unary_function<detail::LeftParent, hier>::type&
         typeref;
     return typeref(obj);

   };

Here we make us of mpl::for_loop. For_loop is a bit more complicated
than for_each. Instead of iterating over all the elements in a
type_list, the compile time for_loop uses an initial type, a condition
and an incrementation step just like a run time for loop. In this case
we are looping from N+1 to the size of our type_list, with an
increment of 1. We start with GenScatterHierarchy<TList, Unit> as our
initial state. Each time through the loop we take the right
parent. When the loop is done we take the left parent to give us the
desired result. In cheesy runtime style pseudo-code we calculate the
return type as follows:

   for (J=N+1, State = GenScatterHierarchy; J < TList.Size(); ++i)
     State = RightParent(State);
   tpedef LeftParent(State) ReturnType;

5. Conclusions

* MPL is quite powerful. In this small example we were able to:
     * Use reduction (for_each) instead of awkward, non-portable
  pattern matching.
     * "Dynamically" compose metafunctions with compose_f_gxy
     * Employ integer based for_loops
     * Take advantage of a simple compile time lambda/currying facility.
     * MPL offers many other facilities not described here

* MPL needs documentation now. I believe some mpl naming conventions could
   be improved as well.For me things did seem simpler once I started
   thinking in terms of quoted metafunctions. But the learning curve is
   high.

* MPL seems to tax the compiler somewhat more than Loki. One particular
   problem is that small type_lists are padded with a lot of unused
   types.

* MPL does not rely on template templates or partial
   specialization. It does a pretty good job encapsulating compiler
   limitations. Of course metaprogramming VC 6/7 remains
   somewhat nightmarish, and the port here is still not complete.

Any comments?
  - Mat