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

From: Aleksey Gurtovoy (agurtovoy_at_[hidden])
Date: 2002-04-17 20:41:23

Paul Mensonides wrote:
> 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.

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.

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.

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

>
> 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?

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

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

Aleksey