RE: [boost] typelists: MPL tutorial + partial review

From: Aleksey Gurtovoy (alexy_at_[hidden])
Date: 2001-12-12 11:58:25

Mat Marcus wrote:
> 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...

Overall, the tutorial is very good: you took exactly the direction Dave and
I have been considering in our documentation effort, the technical side of
presentation is impressive, and your writing is good :). The only general
thing that I would like to note here is that some of the examples presented
below can have a much simpler implementation; it's important to not over do
it in terms of complexity while presenting the library to the first-time
users :). On the other hand, simpler implementation would eliminate all
these cool binders, composers and loops :).. hmm, seems like there is a need
for a sequel tutorial :).

[...]

> 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 is very good, have nothing to add here!

> 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".

'for_each' name is an artifact of the previous versions of MPL which had
"real", STL-like 'for_each', i.e. the one that took "generative" function
class with state. The approach has proved impractical, and in the version
you work with 'for_each' has been assigned the semantics of 'accumulate',
but without a name change - which obviously was a mistake. In the most
recent revision of the library (which I haven't checked into CVS yet)
'accumulate' and 'for_each' are synonyms, and the latter is deprecated (we
have some code that needs to be rewritten before I can remove it).

> 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). 

In the boost::mpl documentation these are called "function classes" (by
analogy with function objects), as opposite to (I hope) self-explanatory
"class template metafunctions" (both of the concepts are particular
instances of more general "metafunction" concept).

[...]

> 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;
>    };
> 

This is one particular example that I would implement differently. Dave have
already posted an example of implementation that is very close to what I am
thinking of, but for the sake of demonstration of what I think is a "native
MPL solution" :), here is my code:

    namespace aux {
    // auxiliary function class; will be applied to each element
    // in a sequence T0,T2,..Tn to produce the following multiple
    // inheritance hierarchy:
    // [type n] <+- [type n-1] .. <+- [type 0] <+- [empty]
    //           +- F(Tn)          +- F(T1)     +- F(T0)

    template<typename F>
    struct node_generator
    {
        template<typename Base, typename T>
        struct apply
        {
            struct type // [type i]
                : Base // [type i-1] or [empty]
                , boost::mpl::unary_function<F,T>::type // F(Ti)
            {
            };
        };
    };
    } // namespace aux

    template<typename Types, typename F>
    struct derived_class_generator // "GenScatterHierarchy"
    {
        struct empty {}; // [empty]
        // for each element in 'Types' call 'aux::node_generator<F>'
        typedef boost::mpl::accumulate< // former for_each
              Types
            , empty
            , aux::node_generator<F>
            >::type type;
    };

where usage example could be something like this:

    // usage example
    struct holder_gen
    {
        template<typename T> struct apply
        {
            struct type { T m_value; };
        };
    };

    typedef derived_class_generator<
          boost::mpl::type_list<char,short,long>
        , holder_gen
        >::type my_tuple_t;

One particular difference here, comparing to the Dave's version, is that his
code guarantees that nodes in the hierarchy will have a particular type
(InheritTwo<>), while mine doesn't ('cause I don't think that's needed), and
in theory it saves a few more lines :). In theory, because apparently the
trick is needed to compile the above example under MSVC, so
'aux::node_generator' should in fact look like this:

    namespace aux {
    template<typename T1, typename T2>
    struct inherit_two : T1, T2
    {
    };

    template<typename F>
    struct node_generator
    {
        template<typename Base, typename T>
        struct apply
        {
            typedef typename boost::mpl::unary_function<F,T>::type
element_t;
            typedef inherit_two<Base, element_t> type;
        };
    };
    } // namespace aux
    
    // the rest of the example is the same

[...]
> 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);
> 
>    };

Again, this is something that I would implement differently:

    // a modified 'derived_class_generator' definition
    template<typename Types, typename F>
    struct derived_class_generator
    {
        struct empty
        {
            // NEW: provide the result class with 'field_list'
            // member, that will contain a list of 
            // F(T0),F(T1),..,F(Tn) node types
                typedef typename boost::mpl::transform<
                  Types
                , boost::mpl::type_list<>
                , F
                >::sequence field_list;
        };
        
        typedef typename boost::mpl::accumulate< // former for_each
              Types
            , empty
            , aux::node_generator<F>
            >::type type;
    };

    // 'field' function implementation
    template<long N, typename T>
    typename boost::mpl::at<N, typename T::field_list>::type&
    field(T& t)
    {
            typedef typename boost::mpl::at<N, typename T::field_list>::type
field_t;
            return static_cast<field_t&>(t);
    }

and the usage is pretty much as expected:

    int main()
    {
            my_tuple_t t;
            field<0>(t).m_value = 10;
            field<1>(t).m_value = 5;
            field<2>(t).m_value = 7;
            // field<3>(t).m_value = 1; // error
    }

MSVC does compile this one :). I've uploaded the example file
(derived_class_gen.cpp) to the MPL directory in the files section, if it's
of any interest.

> 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.

Do you have any specific suggestions in mind (besides 'for_each' :)?

> 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. 

This is true right now, but to my best knowledge there are no inherit
limitations in the library design that would prevent one to have as
effective (in terms of compile-time resources) type list and algorithms
implementation as you might possibly have.

> One particular
>    problem is that small type_lists are padded with a lot of unused
>    types.

It's not exactly that. Type lists are not padded with unused types, these
types are just a part of type list generator "signature", and that's why
they appear in the error messages. One way to get rid of them is to inherit
from type_list instead of typedef-ing it:

   struct my_list : boost::mpl::type_list<char,short,long> {};

Another way is to write
    
    typedef boost::mpl::type_list<char,short,long>::type my_list;

instead of

    typedef boost::mpl::type_list<char,short,long> my_list;

Tradeoffs are everywhere :).

> 
> * 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?

Thanks for you contribution, Mat!

--
Aleksey