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

From: Paul Mensonides (pmenso57_at_[hidden])
Date: 2002-04-17 22:08:54

> If by "iterative-style typelists" you refer to something like our
> 'tiny_list' example, then you've missed the point. It's not amied as a
> solution to a nested template instatiation depth limitations when one is
> declaring a large type sequence "inline" (list100<t1,t2,...,t100>) - in
> fact, MPL 'list' implementation doesn't have this problem - defining a
> 'list100' is as cheap as defining a 'list2' (iterating through them is not,
> of course).
>
> The motivation to have something implemented along the lines of 'tiny_list'
> example is different, and it addresses much more important issues. The
> simplistic 'cons'-based list is a forward access sequence with constant time
> insertion at front and linear insertion time in the middle; that imposes
> severe limitations on what you can do with a sequence. Basically, it
> prohibits you from using certain algorithmic solutions because they will
> take ages to compile.

'tiny_list' is exactly the type of thing that I'm talking about by iterative
typelists.  Your argument doesn't carry weight because at small numbers of
types--where iterative typelists could actually be 'feasible' without the
preprocessor--the difference is negligible.  In large cons-lists, processing is
obviously going to slow down, however this is the exact situation when a
iterative list becomes so inane that it could be termed a 'hack'.  According to
you, what *ever* is the benefit of a cons-style typelist if you have a huge
iterative-style one?  It can't be on how it is accessed, because it is easy to
define a 'mapping-mode' to access it in a given way.  For the sake of argument,
why would you need any other type of list then a completely random access one
that is really huge?

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

What is the possible benefit of anything else?  If you think this is better,
design the library around something like this.

> In short, the exact kind of type sequence that you are using directly
> affects your design space. A generic metaprogramming library should allow
> you to make that decision for yourself - and assist you after you've made
> your choice.

Given a typelist like the one above, it is trivial to define different 'views'
of this data.

> > 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.
>
> You've again misread what we were saying. It's the word "list" there ("type
> *lists* are not the only useful
> compile-time sequence"), meaing "forward access linear sequence", that is
> given an accent. The whole paragraph you are reffering to has an entire
> different meaning.

Fine.  That doesn't negate the fact that the library is designed in such a way
that the type of sequence is abstracted from the implementation of the
algorithms.  The problem is that *only* when typelists are very big does it
become a really serious issue.  If you have an iterative sequence that goes that
high, what is ever the point of using a cons-style list?

> > 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.
>
> Huh? So, basically you are saying that it doens't matter for you that your
> algorithm instead of 10 takes 100 sec to compile?

No, it does matter, obviously.  What I'm saying is that the library could be
optimized *even more* if was built around a certain type of sequence
directly--whether that is a recursive sequence or an iterative sequence.  If you
want to take the STL as a comparison, there are many STL algorithms that are
reimplemented for certain types of containers.  The reason is obviously for
efficiency.  So what it really comes down to, is that abstraction often comes at
a huge price.  Trying to alleviate that runtime price is one of the prime
reasons that meta-programming exists.  Also, I've seen several other posts that
are talking about this type of 'optimization' for a specific sequence already.
That defeats the purpose of abstraction in everything but the name of an
algorithm.

> > 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.
>
> There are a lot of reasons not to use the above type list implementation in
> the real world. And with however clever implementation you will come up
> with, it won't cover all use cases.

Oh, yeah?  It is simply the way that you look at the meta-data.  The types of
things that you are talking about don't apply.  Algorithms that actually
*operate* on some type of tree structure will not work if there is no tree
structure.  For instance, the STL defines its algorithms to work on a *sequence*
of data.  That implies that the data can be ordered into a sequence.  If the
data can be ordered in a sequence, then it can be ordered in the sequence type
above.

> > 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.
>
> Again, it's not about nested template instantiation limits.

Agreed.  It is about efficiency.

Paul Mensonides