[boost] Formal Review: Template Metaprogramming Library (MPL)

From: Thomas Wenisch (twenisch_at_[hidden])
Date: 2002-08-01 01:32:19

At the 11th hour (well actually, 2 hours after the review period ended, at
least in my time zone), I am submitting one more review of the MPL
library.

I vote that the library be accepted.

I believe MPL has made a number of major contributions to template
metaprogramming.  As I don't know the literature (and know very little
about functional languages), I am not sure how many of these are original
in MPL and how many were previously known, but even collecting a set of
best practices is itself a contribution.  Here is my list of highlights:

  -  metafunctions as first class objects (metafunction classes)

Regardless of what these beasts are called, the idea of wrapping a
metafunction in a type is an important idea.  Perhaps, in a better C++,
where template template parameters could be generic with respect to arity,
this would not be neccessary.  However, as the language exists today, the
idea of wrapping a meta-function in a class is an important idea.  This
idea is central to MPL, and is IMHO well presented in the paper.

  -  fold and iter_fold as fundamental algorithms

>From my forays into template meta-programming, I can see that fold truly
does underly almost everything I have ever done with a typelist, even
though I could never have articulated it.
   With practice, I have become comfortable with writing the "pattern
matching" partial specializations that make my meta-functions work (and I
must credit Andrei's book for giving me the "feel" for how to do this).  
However, in trying to present these meta-functions to collegues, I have
been unable to do a good job explaining how the algorithms work.  Part of
the problem is that I really haven't developed a consistent style in how
to write these algorithms, so the code always looks a little bit
different.
   I think there would be several benefits to building my algorithms
around fold/iter_fold instead of manually writing the pattern matching.  
First, someone only needs to learn and understand iter_fold once, and then
the similarities between various algorithms become clear.  Second, I
believe my code would be more concise (tho I am not certain, as I haven't
tried rewriting any existing code with MPL yet).  But, most importantly, I
think my code would be clearer for others to understand, once they gain a
little familiarity with MPL.

  -  Analogy to STL

I understand that the value of this is still being debated.  However, I
found the analogy helpful in learning about MPL.  Even if they have no
technical advantage, I think providing iterators in MPL has great
pedagogic benefits.  Under the hood, I don't care what they are, but call
them iterators and make the syntax look like they are iterators.

  -  Amazing cross-platform support

I struggle to get my template-soup to work on both GCC 3.1 and Intel C++
6.0 on Linux, the two compilers in my world. Both are, IMHO, great
compilers, very similar (which Intel works hard to achieve), and very
standards compliant.  I still run into things all the time that one
compiler accepts that the other doesn't like.  I am amazed that MPL can
work with (almost) the same syntax across so many compilers.

Here are my gripes:

  -  Desperately want an Associative container

One of the things I use "meta-programming" for quite a bit now is for
named template parameters (here, I must give credit to the
iterator-adaptor library for showing me how).  I would love to have
mpl::map to make this easier.  As a matter of fact, I use typelists of
pair<Key,Value> more than anything else in my current metaprograms.  Maybe
list or vector + find_if is enough, maybe we need map.  I think I would
like to see map added.

  -  More example code, especially examples of code generation

I use meta-programming to generate code at compile time.  I am a big fan
of GenLinearHeirarchy and GenScatterHeirarchy.  I really liked the state
machine example in the MPL paper.  I would like to see more examples of
use cases like these where a little bit of MPL can generate a lot of
(tedious) code.

  -  Performance numbers which show compile times on "benchmarks"

Today, there are no benchmarks for meta-programming, like there are for
other applications (ie SPEC).  Benchmarks have their faults.  However, to
answer questions like the one Andrei posed (Are multiple sequence types
neccessary?), there is no better tool.  Discussions of complexity have
simply not proven convincing.

One problem with coming up with benchmarks is that we don't have a large
number of use cases of template metaprogramming to choose from.  There
isn't a bunch of C++ metaprogramming code out there for the community to
figure out what would be a good problem to measure performance on.

Thus, I would like to suggest one problem that I had to solve recently in
my own code, that might be a decent candidate for a "real-world
problem" that could be benchmarked.  I invite others to propose more
problems (and, thereby, spread the word about what can be accomplished
with meta-programming :)

The essence of my recent problem was to write a template meta-program
which could compute a total-ordering given a set of partial ordering
relationships (or give a compile error if there was a cycle in the partial
order).  I had a set of functions to be called, and a set of pairs of
partial orders that basically gave the constaint "function x must run
before function y".  My meta-program computed a legal order to call the
functions in, or generated a compile error if no legal order was possible.

If I get time (won't be this week or next, as I am going on vacation), I
will pull out the relevant pieces of my code and provide them as a
possible "non-MPL" solution.  Can vectors or some other feature of MPL
increase the compile speed of my code?  I don't know, but I'd like to find
out.

Kudos to Aleksey for writing a great library.

Best Regards,
-Tom Wenisch
Computer Architecture Lab
Carnegie Mellon University