Re: [boost] Re: MPL containers and algorithms

From: Terje Slettebø (tslettebo_at_[hidden])
Date: 2002-08-09 15:29:17

I know that the review periode is over. However, I'm just catching up on a
few postings I haven't replied to, earlier.

>From: "Paul Mensonides" <pmenso57_at_[hidden]>

Terje:

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

This basically gives you an iterator.

You've shown that iterators are useful (!) :)

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

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

I see from later postings, that you appear to be open to that several
sequence types may be useful, after all.

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

Again, doesn't this go for STL, as well? Sure, you can use the free function
"find" on e.g. an assiciative container, but there's an even more efficient
function implemented as a member function. In other words, tailored to this
container.

The same goes for MPL. You _can_ use an unspecialised find. But you may also
provide a specialised version for that container (in the same way that
there's a member function for the run-time counterpart).

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

Again, it seems you've moved some from this, in later postings, being open
to the advantage such abstraction brings.

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

Well, as you know, one of the great strengths of STL is that you may extend
it, as well. As long as your component implements the concept required,
it'll work with the rest of STL. So even if there wasn't anything in STL,
the framework of concepts would be useful in itself. Both MPL and Loki has
such a framework, as well.

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

So what do you suggest for the design of such a metaprogramming library? You
already said a few containers could be useful, and one might have the
iterator abstraction (which you kind of gave an example of, yourself, above
here). How should it be done?

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

I understand. Well, like I said, I think performance measurements could help
to find out the possible merit of having several sequence types. Even if
there are several sequence types, then it doesn't really change the design.

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

Well, this is covered some in the MPL paper. You can, but there are some
issues. You may pass them as template template parameters, and you may
return them as member templates. But I'm almost tempted to say, why bother?
:) There's a lot of adantage in being able to treat the elements uniformly.
As you know, everything is treated as a type in MPL, including types, values
and metafunctions. This lets the components work with them, without perhaps
even knowing what they are. You can use the same algorithm for types and
values, for example. I think the same advantage is the case for templates.

It seems we agree on the complexity of passign templates around, in the
general case. If you don't wrap them up, it will simply collide all over the
place. You won't be able to treat metafunctions as first-class citicens, and
I think such uniform, generic treatment is key to its power. It lets you
relatively easily transform metafunctions, store them, pass them around,
etc.

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

Regards,

Terje