Re: [boost] Re: MPL containers and algorithms

From: Paul Mensonides (pmenso57_at_[hidden])
Date: 2002-07-31 16:00:49

> I understand what you mean, now. However, this relies on the assumption that
> you're going to pass over all the elements, anyway. Like I mentioned with
> the search or sort, or things in MPL that enables you to get a subrange
> "view", or "lazy" subrange, there may be cases where you _don't_ need to
> access all the elements, or access them multiple times. In those cases, it
> makes a difference how you access them.

Okay.  As I have said before, if efficiency is such a major concern, why don't
we have one tuple-style sequence type that can hold a huge number of elements?
If cons-style lists are so inefficient in certain areas, why use them at all?

> Let's take a concrete example. I'm mostly familiar with Loki, so I'll use
> Loki-style typelists as the cons-lists, and its algorithms.
>
> Say you want to delete type T in a sequence.
>
> There's already an algorithm for that in Loki, Remove<TList, T>.
>
> In MPL, it might be done like this:
>
> typedef find<Types,int>::type iter;
> typedef erase<Types,iter>::type NewTypes;
>
> Now, what if you want to erase not the type, but the type following it. In
> Loki, you'd have to write a new algorithm. It would likely be nontrivial,
> too, as you couldn't use the if-element-found-skip-it way that Remove uses.
>
> In MPL, it would be trivial:
>
> typedef find<Types,int>::type iter;
> typedef erase<Types,iter::next> NewTypes;
>
> This is just a simple example, but it shows some of the flexibility possible
> using iterators.

Nobody is saying that the design of Loki is perfect.  If there was a 'find'
algorithm in Loki, such as IndexOf (or whatever its called) that just stored the
typelist headed by 'int' (in this example) as a typedef, you have the best of
both worlds with no special effort.

typedef remove<types, T>::type new_type;

typedef index_of<types, int>::type aux_type;
typedef remove<types, aux_type::tail::head>::type new_type;

> To take the concept of passing metafunctions to algorithms, let's search for
> a type. In Loki, there's IndexOf, giving the index of a type in a typelist,
> or -1 if not found. You have the "find" counterpart in MPL, as shown above.
> If you wanted to compare on something else than type identity, there's not a
> corresponding algorithm in Loki, although you could of course make it. In
> MPL, there's "find_if". "find" is implemented in terms of "find_if", where
> it uses type identity as the predicate.

Yes, this is good about MPL.  Loki lacks in this area.

> The above examples, both with "erase" and "find", shows how you can "reuse"
> MPL components, that you asked about.

It's a good example of the flexibility of the library, but not for the validity
of multiple sequence types (I'm not talking about trees and the like here, just
sequences.).

> > And you can do even better if you specialize the algorithm that searches
> to not
> > use iterators but operate directly on the tree.  I see the point that you
> are
> > making, but I don't think that it really applies in the same sense as it
> does in
> > the STL.
>
> Yes, you can make such a specialised algorithm. This is the way it's done in
> Loki. However, without iterators, or sequence converters, such a tree would
> only be usable for that one algorithm. Not for the others.

Okay, lets take the STL associative container for example.  Though algorithms
such as 'find' will work, it is extremely inefficient to use the general
algorithm rather than the member function.  In cases other than pure sequences
(i.e. list, vector, etc.), there are just too many special cases like this.

In any case, that is not my point.  My major point is that I don't think that we
need multiple pure sequence containers.  I'll address why I don't think the same
arguments apply in my response to Fernando (forthcoming).  If we had a single
sequence type, however it is implemented, I wouldn't object to using a thin
iterator layer.  The full-fledged abstract, IMO, is just overkill.

> Yes, if you need to go through all the elements, anyway, then of course. I
> thought you meant going from one to the other _without_ going through the
> intermediate elements. That depends on something else than forward iterators
> (such as cons-lists), to get less than O(N).

Agreed.  But it virtually removes the O(N) complexity on average.

> Yes, this is, again, as in STL. There's a fair amount of "boilerplate code"
> there, too, to make it possible for the components to cooperate. However,
> somehow, noone complains about that...

Many complain about certain aspects of it.  *But* the fact that it is necessary
to have multiple pure sequence types, based on usage patterns and optimized for
various types of usage, is _the_ primary reason why the STL is well-designed.
If there was just 'vector' and 'map', the STL's abstraction would be a massive
overkill and bad design.

> Sure, if only a single algorithm applies to a structure, you may write a
> structure and its algorithm(s) together. We have that already. It's the Loki
> typelists. :)
>
> You may of course do the same with other structures, as well, making
> algorithms for a tree structure, for example.
>
> However, if you go through this exercise, then it's likely that during the
> work on extending this system, and making it more generic, you'll notice a
> not insignificant amount of code duplication, resulting from custom
> algorithms on custom containers.

This is unavoidable.  If you have a more complicated structure such as a tree,
you are going to have to implement a great many things specialized for the tree
structure, otherwise you no longer have the all-important efficiency.  Besides,
unless you use a tree structure for sorting, there has to be another logical
reason (dependant on the application) for the container to structured as a tree
(e.g. a parse tree or something).  If that is the case, you can already throw
the usefulness of most of the algorithms out the window.  They don't apply
because the nature of the data is not sequencial.

> > This depends on how you design the 'default' sequence type that the
> algorithms
> > use.  You could easily implement it lazily.
>
> Well, if you convert a sequence, to a lazy sequenze, or using a lazy
> conversion, you in effect have an iterator, I think.

Yes, and in this sense iterators aren't so bad.  However, I'm not arguing
against iterators, but against multiple pure sequence types.  The iterator layer
could be extremely thin.

> > > Besides, couldn't you use the same argument for STL?
> >
> > Yes, but with the STL there are specific needs for specific container
> types such
> > as access time, insertion time, memory use, etc..  Various types of
> optimization
> > for various needs.  These have come about over decades of study, and the
> need
> > for them proven in the field.  These same arguments do not apply here.
>
> I think they may do. However, we need much more experimentation in this
> area, and timing comparisons for using an algorithm, such as e.g. sort, on
> different sequences.
>
> > I don't think that we need multiple *sequence* types.
>
> Again, I think algorithm analysis and timing could be used to examine this
> issue.
>
> > Trees or other structures, yes,
> > but the number of algorithms that operate on trees as a sequence is rather
> > small.
> >
> > > So what would be the advantage of using sequence-converters, instead of
> > > iterators? Perhaps if the flattening is expensive, and you need to pass
> over
> > > the sequence multiple times? However, do you have an example of
> expensive
> > > flattening?
> >
> > Sequence converters would rarely be needed.  There are only so many types
> of
> > structures that would be useful.  At compile-time you don't need 10
> different
> > pure sequence types like you do at runtime.  This leads me to believe that
> only
> > three or four different container types are _useful_ total and that only a
> few
> > algorithms that operate on a sequence would be applicable to containers
> that are
> > not sequences (such as trees).
> >
> > > I guess we still haven't had much examples of that. I'm merely saying
> that
> > > the design of MPL suggests that it's powerful. I agree that comparisons
> > > between implementing things in MPL, and using Loki, could be useful.
> That
> > > would let the "rubber meet the road". However, MPL is quite new, and
> Aleksey
> > > have been quite busy making the library, in the first place, and lately
> the
> > > docs.
> >
> > Oh, I agree; it *is* powerful.  My point is that I think it is a little
> *too*
> > powerful (i.e. unnecessarily powerful).  And maybe more importantly than
> > anything else, it provides many samples of how to use the compile-time
> languages
> > of C++.  At this point, it is moot anyway, we need _something_ regardless.
> >
> > By the way, I'm not saying that the design of the MPL is bad, in fact I
> think it
> > is very clever.  I also have no problem with the existance of the MPL.
> However,
> > I think that Boost needs a simpler subset that more complicated libraries
> (such
> > as the MPL) could be built on top of.
>
> Like what? Loki's typelists?
>
> I've tried extending Loki's typelists, lately, and found it went in the
> direction of MPL. I was quite shocked by this, myself. It started with that
> I read on this list that MPL could use a sort routine, then for fun, I made
> a sort routine (implemented using Mergesort), using Loki-style typelists.
> When I first made it, I used template template parameter for the sort
> predicate, which is how it's typically done in Loki. However, as you know,
> you can't pass templates around, combine them, etc. Ok, so I changed the
> predicate to a class with a member template. One step towards MPL.

Other than compiler deficiencies, why can't you pass templates around, combine
them, etc.?  I already did this once upon a time--including binding and default
parameter deduction ala.  It is certainly possible, but it is a relatively
untouched area.

I'm not saying this is a good idea.  It is significantly more difficult to do
this, and I did it just for fun--and it relies on an extremely compliant
compiler.  I completely agree with how the MPL handles cases like these, wrap
everything in a type (including values and templates, etc.).

Paul Mensonides