Re: [boost] Submission: typelist

From: Andrei Alexandrescu (andrewalex_at_[hidden])
Date: 2001-11-27 17:28:57

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

Another prefatory remark, not too jokey this time, is that typelists are
essential to a very large subset of Loki. As I mentioned in another post,
typelists are used in Factory, Functor, Tuple, Visitor, DoubleDispatcher,
and the two hierarchy generators. In the future I'm sure Observer,
Composite, and other generic components I work on will use typelists as
well. That's why I started by submitting typelists to boost as part of my
plan of submitting the whole Loki to boost.

Following the typelist submission, a number of legitimate questions arose.

One is the use of macros in building typelists, which is a problem in dire
need for a good solution. I plan to deprecate macro usage at the expense of
some readability. Another one is the naming convention, which generated many
opinions and a couple of good ideas; still there is no clear winner,
although I hope we'll find one. The third issue, one that this post is
about, is integration and overlapping functionality between the part of Loki
that I submitted, and code that's already in boost.

I finally had the time to sit down and analyze mpl. It is an impressive
library; obviously, much creative work has been invested in it. Mpl offers
pretty much all that Loki's typelists do, and much much more.

The sheer sizes of the two libraries is witness to the comprehensiveness of
mpl. Loki's typelists consist of one file and depends on two other
general-purpose files; in addition, one file implements a test suite. The
mpl library consists of 127 files, and 40 files implement a test suite.

While Loki's typelists implement a basic facility of aggregating and
manipulating collections of types, mpl implement a full-fledged library with
rich algorithms and an unified approach to constructing them.

Also, mpl works on less-potent compilers that don't implement partial
specialization, feature used copiusly everywhere in Loki, including in the
typelists themselves. (It should be noted, however, that to date I got two
complete ports of Loki to MSVC in my inbox, and that Mat Marcus posted a
port of Loki's typelists to MSVC to boost already. Thanks Mat!)

This being said, I decided to keep the submission as it is, and here's why.

In spite of them being bare-bones, Loki's typelists in their actual form
proved themselves very useful in a host of generic components. Moreover,
they are quite easy to understand, use, and write algorithms for.

By comparison, mpl's typelist facility is extremely hard not only to
understand (which I think I did), but also - and I consider this very
important - hard to use in client code as well.

Let's take for example a reasonably simple algorithm: compute the length of
a typelist. Loki's version is the classic functional recursive algorithm:
the length of the null typelist is zero, and the length of a non-null
typelist is one plus the length of its tail.
I argue that one can explain this algorithm to anyone who understands basic
templates.

        template <class TList> struct length;

        template <> struct length<null_typelist>
        {
            enum { value = 0 };
        };

        template <class T, class U>
        struct length< typelist<T, U> >
        {
            enum { value = 1 + length<U>::value };
        };

Mpl's equivalent facility is 'size' and looks like below:

template<typename SequenceTag>
struct size_algorithm_traits
{
    template<typename Sequence> struct algorithm
    {
     private:
        typedef typename mpl::begin<Sequence>::iterator first_;
        typedef typename mpl::end<Sequence>::iterator last_;

     public:
        BOOST_STATIC_CONSTANT(long, value =
            (mpl::distance<first_,last_>::value)
            );
    };
};

template<typename Sequence>
struct size
    : size_algorithm_traits<
          typename mpl::sequence_traits<Sequence>::sequence_category
          >::template algorithm<Sequence>
{
};

To understand this, you don't really have to look up 'begin' and 'end';
intuition says they mean the beginning and the ending of the sequence being
measured. (As an aside, their definition is not trivial at all.) Then,
you'll have to figure out what sequence_traits is, and what algorithm inside
it means. Finally, you'd figure out that distance computes the distance
between two compile-time iterators.

But showing one well-chosen example is not really a nice thing to do; one
can argue there are things you cannot do (or do in a very arcane way) with
typelists, and are a breeze with mpl's typelists. Yet, the "well-chosen
example" is the most basic facility one would ever imagine.

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
{
};

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.

My and others' experience with Loki's typelists has proven that they have a
terrific power/complexity ratio. They are compact, no more complex than they
have to be, easy to use, and enable very powerful idioms - some of which
Loki exploits. By comparison, mpl's power/complexity ratio seems very low to
me; 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.

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.

Loki's typelists are well documented and quite popular. I'd love to see them
in boost so I can continue submitting Loki to boost. In fact, typelists
would be very useful to a ton of other boost facilities (tuples are the best
example). True story, although it might sound like a blatant lie: I'm not
posting this from home and I needed to paste some code from Loki into this
post. While looking for typelist.zip on the boost files section, I found a
header called stack_aligned_variant.hpp. I delved into variants quite some,
so I took a look, and guess what I found in there - a little ad-hoc typelist
facility similar to Loki's. (The code doesn't make it clear whether the
facility is inspired from Loki or elsewhere, or invented independently by
its author. By the way, if it was inspired by Loki, an acknowledgement would
be appreciated.) By the way, for a Variant implementation that uses
typelists for both computing alignment and for the implementation itself,
you may want to take a look at
http://www.oonumerics.org/tmpw01/alexandrescu.pdf.

Factionalism, I believe, is the last thing that we need here. That's why I
hope to integrate Loki with boost, and I think that would add a lot of value
to boost. I suggest that some of Loki's facilities keep their current name
unless an obviously better name comes up, because Loki's names are widely
publicized and already in use. I'd be glad to use facilities in boost that
are better designed than those in Loki (such as type_traits). I also agree
to integrate with code in boost that was copied from Loki (initially without
acknowledgement, for which I had to ask), though I can't stop myself from
noticing the irony. But I don't find it reasonable to port Loki to a
typelist facility of which design I don't agree with.

Cheers,

Andrei