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

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2001-12-11 16:51:50

----- Original Message -----
From: "David A. Greene" <greened_at_[hidden]>

> Good, this is a useful exercise.
>
>  > // Now we can define GenScatterHierarchy
>  >
>  >    template <class TList, class Transformation>
>  >    struct GenScatterHierarchy {
>  >         typedef boost::mpl::for_each<
>  >             TList, EmptyType, inherit_transformed<Transformation>
>  >         >::state type;
>  >    };
>
> This is certainly much more readable.  "Aggregating" the
> pieces-parts into inherit_transformed improved my understanding
> 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.

> For me, recursion is just much more
> natural.  Perhaps this isn't true for most.

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 find the analogy between the use of the STL and the use of MPL makes
>  > things much easier.
>
> 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. I did a lot of work with an earlier
version of MPL, and sometimes had to implement my own recursive
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'm sure most of us have had the same experience with STL: a hard problem
became lots easier because:
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

> I suppose one
> could argue that a typelist is just another sequence,

Yes.

> which it
> certainly is, but due to the limited interface we 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.

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

> The STL algorithms break down somewhat with the associative
> containers.  Their recursive structure makes std::find (as
> an example) a non-ideal tool.  Thus we have the member find
> which (in my implementation) does not mention iterators until
> setting up the return value (pity that it is not implemented
> with recursion :)).  Use the right tool for the job, as
> always.  I'm not arguing that iteration  isn't useful for
> metaprogramming.  I just take issue with it being presented
> as the universal way of doing things.

The associative containers have no more got a recursive structure than
std::list does. What they have is a tree structure. It's not a pity that
they're not implemented with recursion; a recursive implementation would be
slow.

-Dave