Re: [boost] Re: loki::type_list == boost::mpl::list_node

From: Paul Mensonides (pmenso57_at_[hidden])
Date: 2002-04-16 17:14:28

> > Ok I've read most of it now including "Loop unrolling" 2.3.8.  Firstly
> > might I say it is a superb document and I will remember to refer to it
> > before I try to understand the code in future.
>
> Well, I think you flatter us. It's very rough, still, but I'm glad it's
> useful.

Aleksey and David, I just finished reading the MPL document today, and there are
some things that I disagree with.  Before I get to them however, I'd like to say
that I think there are many very good ideas such as meta-function classes,
compile-time polymorphism, and uniformity of 'return value' names.  I'd also
like to say that I am a strong proponent of both template and preprocessor
meta-programming.  However, I think that the document uses some arguments for
the way that the MPL is structured that I just don't buy.  For instance, 2.3.7
says:

"The truth is that there is no single "best" type sequence implementation for
the same reasons that there will never be a single "best" runtime sequence
implementation."

I don't buy this analog to runtime usage of runtime containers.  There are
basically two types of typelists, a recursive-style typelist and a
iterative-style typelist.  The problem with the recursive-style is that it
causes more template recursion.  On the other hand, iterative-style typelists
have an absolute upper-bound.  I think that upperbound is somewhat analogous to
a compiler-defined limit on instantiation depth, it isn't a solution to that
problem.  Rather, it is another way to define define the same type of
limitation.

I also don't by the argument that typelists are not the only useful compile-time
sequence.  Given the tools for meta-programming that we have, all other types of
meta-data (besides types themselves) can be stored in a 'list-of-types'.  That
is part of the principle of your meta-function classes.

The reasons that there are different runtime containers in the STL mostly about
access-time, storage usage, and frequency of insertion or removal.  I don't buy
the argument that these types of trade-offs really apply.  The only thing that
really does apply, is that iterative typelists, ala...

template<class T0, class T1 = null_t, class T2 = null_t /* etc. */>
struct iterative_typelist {
    template<int I, int D = 0> struct subscript;
    template<int D> struct subscript<0, D> {
        typedef T0 type;
    };
    template<int D> struct subscript<1, D> {
        typedef T1 type;
    };
    template<int D> struct subscript<2, D> {
        typedef T2 type;
    };
    /* etc. */
};

...are inherently more efficient on today's compilers because they do not
involve heavy instantiation depth.  Other than some arbitrary limit on how many
types can be in the list, there is no reason *not* to use this type of typelist.

On the other hand, recursive typelists, ala...

template<class T, class U> struct recursive_typelist {
    typedef T head;
    typedef U tail;
};

...have no upper boundary (theoretically), and much of the instantiation depth
of these typelists can be alleviated with something like the 'fold_step'
typedefs in the MPL document.

So, so far I can think of these areas in which one implementation is better than
another:

* number of instantiations - (compilation speed)
* depth of instantiations - (compiler limit)
* iterative upper-bound - (library limit)

That brings me to my main point, meta-iterators.  This is a facility that
abstracts--fundamentally--whether a sequence is recursive or iterative.  I think
this adds an unnecessary level of complexity, increases template instantiation,
and brings no real benefit--given that I disagree that any more than one
typelist facility is necessary.  Basically, I think that you should just choose
one facility and define the library around it.  That is the most efficient
possible situation.  If you must have two separate typelist facilities
(iterative and recursive), there should be a clean separation between them.
After all, it isn't difficult to define a conversion facility to convert from
one to another.

In summary, I agree with Andrei that iterators are an unnecessary artifact that
don't bring any real benefit.  On the other hand, I think that the library is an
ingenious collection of meta-programming constructs.  My main gripe is that I
think the library takes abstraction too far and that the purpose of that
abstraction is based on principles that just don't apply.  Please, don't take
this as an insult or even a criticism of the library.  Rather take it as an
opinion that the library is not really 'general-purpose' and as such, I don't
think that it has much hope of making it into the standard library of C++0x.

Paul Mensonides