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

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2001-12-11 20:49:40

----- Original Message -----
From: "David A. Greene" <greened_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Tuesday, December 11, 2001 6:12 PM
Subject: Re: [boost] typelists: MPL tutorial + partial review

> David Abrahams wrote:
>
> >>greatly.  Still, a looping construct to generate trees seems
> >>a little "out of place."
> >
> > While it's technically a tree, the algorithm to build it is entirely
linear.
> > There's nothing "tree-like" about GenScatterHierarchy, really.
>
>
> Which GenScatterHierarchy are you talking about?  I was
> referring to Loki's implementation.  It's recursive in
> that it uses inheritance directly, "slicing off" members
> of the typelist.  Not having looked at the MPL for_each
> implementation, I assume it does much the same thing.  But

"tree-like" and "recursive" are two separate issues. Quoting from Mat's
original posting:

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

That is a linear structure. Yes, technically it's a tree, but you could also
think of it as a chain with the types hanging off one level deep at each
node in the chain. As Mat points out, Loki's result contains more
intermediate classes, but it has essentially the same structure (that the
types are "scattered" all over the page notwithstanding).

> this sort of typelist manipulation to me fits more naturally
>
> in the context of inheritance than in iteration.  Perhaps I'm
> just too biased by a particular typelist implementation.

The typelists aren't implemented very differently in Loki and MPL. MPL just
went a little further in generalizing them so that the same algorithms could
work on other compile-time sequences.

> > What happened to me was that as the metafunction (which sometimes has an
> > associated runtime function) became more complex, just getting all of
the
> > right pieces into the terminator of the recursion became difficult.
> > Sometimes it was a big advantage to be able to break out the expression
for
> > termination into a separate meta-expression (e.g. with find_if).
>
> I can see your point here.  I'm not arguing the for_each
> should be eliminated.  I don't have the experience or
> authority to say that.  But simple things should be
> simple, and GenScatterHierarchy as presented by Mat is
> not.  Your version was clearer, but did require the
> aggregation of several meatfunctions into one class.

No, it didn't. That class represented a single metafunction object.

> >>I think it is somewhat deceptive.  The names and arguments look
> >>familiar, but the STL algorithms work smoothly because iteration
> >>is a natural interface to containers/sequences.
> >>
> >
> > That's somewhat presumptuous of you.
>
> What's presumptuous?  I'm sorry if I gave offense, that
> was certainly not my intention.  If I've got something
> wrong, please correct me.  I'm learning, so forgive an
> intermediate-level Boost newbie.

It seemed as though you were saying that either I was somehow deceived by
the similarity of STL/MPL idioms or that I was trying to deceive others. I
did a LOT of heavy-duty metaprogramming with MPL, so I think my experience
is valid. I certainly have no intention of deceiving others - I am putting
this argument forth because the experience left a big impression on me.

> > metafunctions. I kept going back to MPL because it really did save
thought
> > cycles. The metaprogramming problems I was solving were hard, and having
> > some prepackaged algorithms and an idiom to work in was a big help. It
was
> > worth the (not insignificant) investment to learn how to use it without
any
> > documentation.
>
> I have not once argued that some MPL constructs aren't useful.
> What I argued was that their use for GenScatterHeirarchy was
> more confusing than equivalent Loki code.  I'm arguing that
> a framework to allow recursive algorithms should be included.

I think a framework to allow recursive algorithms is a subset of the
framework in MPL. Basically, you get the "quoted" function object idiom, and
that's it. You can always write your own recursive algorithms with MPL type
lists. The termination are detected slightly differently to allow for
different sequences, but that's about it.

> > 1. Someone defined a framework of concepts through which many problems
could
> > be understood and decomposed
> > 2. They provided a suite of useful basic components
>
> Of course.  MPL provides that.  Loki provides another.  I
> just happen to think that some problems map better onto
> recursion than iteration.

No argument from me. I don't think GenScatterHierarchy is one of them,
though ;-)

I did write a number of recursive metafunctions with MPL also, FWIW. It
became a last resort, though.

> >>have for C++ metaprogramming (no vararg templates, etc.),
>
> >>recursion is a natural way to represent them.
> >
> > Just like list or (if you have it) slist. Even lisp programmers all know
you
> > can use "pure recursive" programming, but they also have for_each,
find_if,
> > lambda.... Often these are implemented with recursion under-the-hood,
just
> > like MPL algorithms.
>
> Right!  Keep for_each!  I'm just asking for more options.

You've got them. Anyone can ignore the algorithms and hand-code recursion if
they so choose.

> >>The simple observation that (partial) specialization is used to
> >>provide a terminator/sentinel points to the natural use of
> >>recursion in metaprogramming.
> >
> > I don't understand that argument.
>
>
> Just as recursive functions have a termination condition,
> recursive metaprograms have a termination specialization.

Well, not neccessarily. Let's look at a normal recursive factorial function:

int fact(int x)
{
    return x == 1 ? x : x * fact(x - 1);
}

Note that the termination condition is NOT expressed by a separate copy of
the function. You can do the same thing with metaprograms using a type_if
construct. So you don't need a specialization for termination of a recursive
algorithm. The separate copy for termination, although easier to code, is
often harder to read.

> When I think of "list" I think "linear."  Of course it _can_
> be represented recursively.

Like a tree.

> > What they have is a tree structure.
>
> Which is a recursive structure.  Child nodes are trees.

Okay, I see now that this is just the way you think of it and not meant to
correspond to any absolute reality ;-)

> With my poor analogy I was trying to point out that
> straight iteration from start to finish isn't
> always the best solution, even though it might
> get the right answer.

No doubt. However, a type list is a linear (as opposed to a tree or graph)
structure, so it lends itself to linear processing. There are all kinds of
ways to stop partway through.

> Please, I don't mean to take away from the work that's
> been done on MPL.  I don't wish to participate in a
> flamewar.  I just wanted to present first impressions
> from a relatively new Boost user.  Perhaps that's not
> useful because I don't have enough experience with
> Boost or metaprogramming.

First impressions are important. The impressions of new boost users are
important. I just want to be sure that when we draw conclusions based on
those first impressions, we're not being distracted by the irrelevant. I
think the binders and composers in Mat's original example made things look
complicated to the point where they obscured the value of the MPL algorithm
decomposition.

-Dave