Re: [boost] Re: MPL containers and algorithms

From: Paul Mensonides (pmenso57_at_[hidden])
Date: 2002-08-12 20:02:29

----- Original Message -----
From: "Douglas Gregor" <gregod_at_[hidden]>

> The phyisical limits on instantiation depth come from memory limitations.
> Either you run out of heap+swap to hold the instantiations (I haven't found
> this to be a problem -- 10,000 instantiations isn't really many at all) or
> you run out of stack space. I'm sure we could easily test this, I'm just
> being lazy about it :)

Well, I wouldn't say that compiler limits on instantiation depth is primarily
based on memory limitation.  I'd say it is a way for the compiler to reasonably
detect infinite recursion.

> > A vector of types that is large is difficult to maintain because there are
> > so many elements.  Maybe I don't understand what you mean by type-vectors.
> > What I mean by them is a series of types that is defined in a tuple-like
> > fashion:

[...]

> > ...Or something similar.  In other words, constant-time random access.
>
> That's one form of type-vector, but not the type that Burton et al. used. They
> used type vectors that look like this:

[...]

I see what you mean, but why couldn't this be done with a regular type-vector?
Just efficiency at huge sizes?  10,000 elements isn't that many compared to a
database, but having a database encoded in the source is just plain ugly! :) I'm
still wondering if this example even applies.  As in, can this sequence (up to
several thousands) even be run through an MPL algorithm?

> > > The typevector example I've given is _not_ speculation; it's not a
> > > what-if. It's research that was presented at WCGP'02 last month and will
> > > be published as part of the proceedings of that conference; I can send
> > > the preproceedings version of the paper privately to any interested
> > > persons.
> >
> > Unless I'm completely misunderstanding you, it only shows the utility of
> > type-vectors.  My question is, what is the utility of cons-style lists if
> > you already have a full blown type-vector implementation?
>
> This form of typevector has very different characteristics from typelists.
> It's quite compact to create even for very large typevectors in this style,
> but it can't be used as a general metaprogramming sequence because most
> sequence operations just can't be done with it. How would you write
> push_front for this typevector? insert? Basically, it boils down to this
> style of typevector being great for big, immutable compile-time data
> structures but it can't be used in more dynamic scenarios.

I see exactly what you mean.  I not sure that this is really a good example or
not depending on whether the MPL could even operate on such a thing in totality.

> Typelists, on the other hand, are great for small, dynamic data structures.
> You can insert into a typelist, reverse a typelist, splice typelists, etc.
> All these operations you can't do with the style of typevectors described
> above.

You can do all of the above with a type-vector also--just not the fixed one
above.  In fact, what kinds of algorithms would even apply to a completely fixed
type-vector?  I doubt that any MPL algorithm could actually operate on a 10,000
element sequence directly.  It would have to be done repeatedly with small
chunks.  Mapping a chunk of elements to a type-vector would be pretty easy.

> > I'm not making the case for typelists, I'm making the case that multiple
> > pure sequence types are not necessary.  I totally agree that type-vectors
> > of some kind are inherently faster than cons-style lists.  Do you have
> > another example that implemented with a typelist that is inherently better
> > implemented with a typelist?
>
> Most of the metaprograms out there fall into this category. But not all :)

I've never seen a metaprogram that used a typelist that couldn't be implemented
with a type-vector--and vice versa.