Re: [boost] Re: MPL containers and algorithms

From: Paul Mensonides (pmenso57_at_[hidden])
Date: 2002-08-09 17:15:12

> This basically gives you an iterator.
>
> You've shown that iterators are useful (!) :)

It isn't really an iterator.  In this sense, it is just a typedef.  The analogy
to iterators only applies in the presence of multiple sequence types.

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

No, I see utterly no utility in multiple 'sequence' types.  I do see valid
reasons to have other types of structures such as trees, etc..  However, trees
and the like are not sequences.  They must be crushed into a sequence (no matter
how you do it), and I am saying that this 1) vastly decreases the number of
relevant 'generic' algorithms and 2) the remaining algorithms will likely need
to be specialized anyway.

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

Yes, and that is exactly my point.  The member functions of the STL containers
(minus the iterator accessors) are *not* part of the STL abstraction model.
Only containers as sequences represented by iterators to algorithms (to
summarize the STL concept).

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

Nope. :) Other structures, yes.  Other sequences, no.  And furthermore, the
similarities between a vector (for example) and a tree are too minute to justify
the abstraction.

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

This is true, but it has yet to be shown that this applies to template
metaprogramming (more specifically, 'template meta-functional-programming').
This is still an open question:  Can you give me one non-contrived example that
demonstrates that a vector-like sequence is faster than a cons-like sequence
*and* vice versa?

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

There are many things that I like about the MPL.  My main problem is that the
MPL uses the STL's model to prove the utility of the MPL's model.  It doesn't
use the reasons *behind* the STL's model.  I haven't seen a single example that
justifies this design model.  IMO, it comes down to these questions:  what is
the real-world utility of multiple *sequence* types, and if there is none, what
is the *actual* utility of abstracting algorithms for non-sequence structures
that are likely to be specialized anyway?

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

All that I ask is for one realistic example that shows a worthwhile increase in
speed using one sequence vs. another and vice versa.  I realize this is not an
easy thing to quantify, but that quantification is necessary to show the
utility.

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

I agree with this as far as pure metaprogramming goes, and I like this aspect of
the STL.  It is a different situation when you are using metaprogramming to
facilitate real code.  A template-template binding and deduction mechanism would
be useful for such a thing.  Also, if we don't use it, it is not likely to get
improved. :)

> 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 don't disagree with the utility of this abstraction.  However, I do disagree
with this reason for it.  You can easily encode any of the above into a type at
will.  What that engenders is a simple subset with more elaborate designs built
on top of it.

Paul Mensonides