Re: [boost] Submission: typelist

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2001-11-27 18:27:52

----- Original Message -----
From: "Andrei Alexandrescu" <andrewalex_at_[hidden]>

> This is going to be a very long post, and if you are interested in the
> subject I'd appreciate if you read it through. I will try to keep is as
> short and as clear as possible.
>
> First, let me make a half-joking prefatory remark. I've been scared to
death
> of submitting Loki to boost because I feared that in a very short time I
> will become terribly unpopular with the boost community. That seems to be
a
> self-fulfilling prophecy, and it's possible that this post materializes
that
> prophecy :o).

Please don't misinterpret the reaction you're seeing. I don't think you've
even come close to unpopularity. Boost places a high premium on
collaboration, and we generally push rather hard for people to put their
heads together when it looks like there is a potential benefit.

> Allow me to present another example: given a typelist, find the type at
> position n. Again, Loki implements that algorithm in a straight recursive
> functional way: if the index is zero, return the head. Otherwise, recurse
to
> the tail of the list and n - 1. The algorithm is simple and
self-sufficient.
> Here's the code:
>
>         template <class TList, unsigned int index> struct type_at;
>
>         template <class head, class tail>
>         struct type_at<typelist<head, tail>, 0>
>         {
>             typedef head type;
>         };
>
>         template <class head, class tail, unsigned int n>
>         struct type_at<typelist<head, tail>, n>
>         {
>             typedef typename type_at<tail, n - 1>::type type;
>         };
>
> The similar mpl facility is implemented as follows:
>
> template<typename SequenceTag>
> struct at_algorithm_traits
> {
>     template<long N, typename Sequence> struct algorithm
>     {
>      private:
>         typedef typename mpl::begin<Sequence>::iterator first_;
>         typedef typename mpl::for_loop<
>               mpl::int_t<0>
>             , mpl::lt<N>
>             , mpl::next<mpl::_1>
>             , first_
>             , mpl::compose_f_gxy<
>                     mpl::next<mpl::placeholder>
>                   , mpl::project1st<mpl::_1,mpl::_2>
>                   >
>             > loop_;
>
>      public:
>         typedef typename loop_::executed::state type;
>     };
> };
>
> template<long N, typename Sequence>
> struct at
>     : at_algorithm_traits<
>           typename mpl::sequence_traits<Sequence>::sequence_category
>           >::template algorithm<N, Sequence>::type
> {
> };

To be fair, Andrei, you should compare a version of Loki typelists that
works without partial specialization.

I had hoped that when Aleksey and I "discovered" that map/accumulate seemed
to be /the/ fundamental iteration algorithm, things like the above would
have been rewritten to use it. Maybe Aleksey can explain why he's still
using for_loop<>. It may be that it's just in an intermediate state, with
for_loops not yet replaced by an alternative.

In any case, I believe that primitive algorithms such as size/length
probably make the most sense when written recursively, to reduce the burden
on the compiler's template instantiation mechanism, if nothing else!

> It doesn't take long to realize that mpl implements a whole language that
> has iteration (for_loop), values (int_t), comparisons (lt), incrementation
> (next), functional composition (compose_f_gxy) - all this on top of C++'s
> template facility, which is an extraordinary feat. I'm sure that with
> application, a programmer can understand and use this language. I'm also
> sure that inventing this language was a fascinating, challenging process.
>
> I also find this to be a misdirected effort. The way templates are
designed,
> pattern matching and recursion work best and most naturally with them. I
> hope the examples above illustrated this assertion quite eloquently.
Forcing
> iteration and state onto the template facility is an interesting
> intellectual exercise, but quite frankly the result turns my coolness
factor
> in the negative range.

In my experience writing some pretty heavy metaprograms, it was certainly
the case that for simple jobs a recursive formulation made the most sense.
When things got more complicated, on the other hand, the cost of writing
specializations to deal with termination conditions began to grow. Once I
was doing things of a certain complexity, the specializations required for a
hand-written algorithm started to badly hurt readability. It made an
enormous difference to be able to rely on pre-packaged algorithms which
capture easily understood semantics, and to be able to use simple modifiers
like composition, etc. Also, I don't think it's a coincidence that Aleksey
and Emily both came up with similar idioms for metaprogramming.

Our challenge is to provide a library which makes complicated things simpler
and simple things really simple. I don't think MPL is there yet. I don't
know about Loki.

> in particular, I didn't find new things that one can do with mpl but
> can't do with Loki's typelists - although I could be wrong here.

I never understood how to measure that, anyway: anything you can do with
C++, you can do (theoretically) with assembler. The real difference is in
expressiveness.

> One more thing, which I'm not sure how relevant it is. Many readers of
MC++D
> told me that Chapter 3 was the hardest of the book, but once they groked
it,
> it all was nice & easy. (Chapter 3 is all about typelists.) Now I'd say
that
> if typelists have a steep learning curve, we're talking about a cliff in
the
> case of mpl. Again, I didn't find any justification for asking that toll.

Having not looked at the mpl code since the "accumulate rewrite", I can't
comment on the current state. The snips you posted certainly seems to bear
out your argument, though. It was definitely cliff-like when I was using mpl
earlier, but my impression was that Aleksey and I had cleared up a number of
issues neccessary to make it simpler. In large part, the steepness was due
to idioms neccessary to support VC6. Oh, BTW, the cliff wasn't too bad when
I was just /using/ the algorithms. Trying to read them could sometimes be
painful, though.

-Dave