Re: typelists: MPL tutorial + partial review

From: Mat Marcus (mmarcus_at_[hidden])
Date: 2001-12-11 18:17:36

     Mark == "David A. Greene" <greened_at_[hidden]>

     Mark> The last thing I want to do is fan the flames and create
     Mark> more division.  I am simply stating my experience.

Thanks. I was hoping to stimulate some concrete disussion. I sat down
to respond to your comments, but then I noticed that Dave already
addressed a number of them. There are a few things I would like to
add. First, I should mention that this code was not meant to be the
definitive version of GenScatterHierarchy. It is simply a late night
exercise in trying to understand and express how one might use MPL on
a real world task. Also, I should point out that I am interested in
Loki and MPL as well as any other metaprogramming aids.

     Mark> Oh my.  project1st<_1,...>?  next<_1>?  If I follow this
     Mark> correctly, _1 means two different things in the same
     Mark> instantiation!  Those "little classes" show up here.  I
     Mark> realize that they perform the same function as the typedefs
     Mark> in Loki's GenScatterHeirarchy, but _shouldn't_ they be
     Mark> bundled up with the class?  It's unfortunate that a for-loop
     Mark> implementation requires one to explode what once was a
     Mark> relatively simple little self-contained package.

Yes, the _1 placeholder variable needs further exploanation. Just as
in Jaako and Gary's lambda library the underscored variables represent
the parameters to the metafunction. At each iteration _1 will be bound
to the element from the container.  See
<http://www.oonumerics.org/tmpw01/jarvi.pdf> for a good discussion.

     Mat > * Use reduction (for_each) instead of awkward, non-portable
     Mat > pattern matching.

     Mark> I would instead argue that reduction (at least in this case)
     Mark> is very much more awkward than recursion.  What you're
     Mark> trying to do maps nicely onto recursion because hierarchies
     Mark> are trees and trees are recursive structures.

It is true that the reduction approach required the definition of
InheritTwo.  Dave did a nice job of explaining InheritTwo's role in
GenScatterHierarchy.  I originally intended to illustrate both forms
but somehow I let it fall throught the cracks.

Let's spend some time debating the readability of for_each/reduce style
algorithms versus recursive algorithms when implementing typelist
algorithms.  While typelists and std::lists are by no means the same,
there is a certain amount of leverage to be gained from a programmer's
understanding of STL.  I am reasonably comfortable with
std::accumulate and after an initial learning curve I find the
following metacode to be analagous:

   template <class TList, class Unit, class Root = EmptyType>
   struct GenLinearHierarchy {
     typedef boost::mpl::for_each<
       TList             // container
       , Root            // intial state
       , Unit            // BinaryFunction
       >::state type;
   };

Compare this with:

    template
     <
         class T1,
         class T2,
         template <class, class> class Unit,
         class Root
     >
     class GenLinearHierarchy<Typelist<T1, T2>, Unit, Root>
         : public Unit< T1, GenLinearHierarchy<T2, Unit, Root> >
     {
     };

     template
     <
         class T,
         template <class, class> class Unit,
         class Root
     >
     class GenLinearHierarchy<Typelist<T, NullType>, Unit, Root>
         : public Unit<T, Root>
     {
     };

Perhaps it's because I don't spend enough time with functional
programming languages, but as a C++ programmer by trade I can read and
write metacode in the first style more rapidly then the second.

One thing I noticed when porting Loki typelists was that there was
quite a bit of repetition in the pattern matching. In the original
code there are often three cases: a general typelist case, an atomic
case, and a null case. Though this form of pattern matching offers a
kind of functional purity/elegance, in some cases one might argue that
this is simply a long winded way of expressing the desire to visit
each element in a typelist.

BTW, another interesting side effect of this implementation is that the
resulting scatter hierarchy has fewer intermediate classes (see the
diagram on page 66 of MC++D). This is also true for the linear
hierarchy.

     Mark> As for non-portability, it's not correct to call something
     Mark> non-portable because some compilers are broken.  Blame the
     Mark> compiler vendors, not the programmer.  We need a better term
     Mark> for this because non-portability implies something that is
     Mark> implementation-defined in the standard which is not the case
     Mark> (AFAIK) for partial specialization and template template
     Mark> parameters.

Fair enough. What I'm really getting at is that I really want to use
this stuff today, not in two+ years when most people will have
standardized on compilers that are up to the job.

     Mat > * "Dynamically" compose metafunctions with compose_f_gxy

     Mark> In your examples the use of composition is not at all
     Mark> obvious.

Forgive me. This is only a midnight hobby after all :-) I think Dave
answered this in his post. I will add one comment. I really like the
STL lambda example that Jaako and Gary give in their 2001 Template
metaprogramming Workshop paper (see URL above):

// Here is an awkward example using STL compose and bind 2nd
vector<double> angles;
vector<double> sines;
const double pi = 3.14159265358979323846;
...
assert(sines.size() >= angles.size());
transform(angles.begin(), angles.end(),
   sines.begin(),
   compose1(negate<double>(),
     compose1(ptr_fun(sin),
       bind2nd(multiplies<double>(), pi / 180.0))));

//With a lambda facility the above code becomes much simpler:
transform(angles.begin(), angles.end(),
   sines.begin(),
     - bind(sin, _1 * pi / 180.0));

MPL already has simple placeholders (_1 and _2) and I expect that a
lambda facility for MPL could alleviate the need for compose.

     Mark> Loops could be useful.  I don't have enough experience to be
     Mark> sure.  But they're not a catch-all.

Agreed.

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

     Mark> What exactly is nightmarish?

I assume you are joking here. But just in case, here is one particular
stumbling block that I am currently facing:

     Mark> I don't think it's fair to knock Loki because it wasn't
     Mark> coded with broken compilers in mind.

By the way I'm not knocking Loki. I think Loki is cool. As I mentioned
above, I don't want to wait two years until we move to an adequate
compiler; I want to use it today. I am just trying to focus our Loki,
MPL discussion.

     Mark>   You work shows that it is possible to maintain a nice
     Mark> recursion interface while still achieving working code on
     Mark> such platforms.

Thanks. But I'm not sure I understand what you mean by a recursion
interface? The interface to the hierarchy generators is more or less
unchanged. Do you mean recursive implementation.  Well that is there
too under the hood.  It seems convenient to have some higher level
abstractions so that I don't have to repeat the pattern matching code
endlessly. While the applicitave for_each style may take some learning
I believe that it is a useful way to factor out common code, just as
stl::for_each offers a way to visit each element in a sequence.

  -Mat