Re: [boost] Re: MPL containers and algorithms

From: Terje Slettebø (tslettebo_at_[hidden])
Date: 2002-07-31 06:17:35

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

> > > The only times that this makes any sense is when you are directly
> > > processing many elements at one time (i.e. one per 'iteration')
> >
> > I'm not sure what you mean here, could you explain?
>
> In the case above, the access time (from the beginning of a cons-style
list) is
> irrelevant.  Because the algorithm operates on each element one at a time,
the
> access times are O(1).

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.

> This contrasts with something like this:
>
> template<class A, class B, class C>
> struct vector {
>     typedef A type_a;
>     typedef B type_b;
>     typedef C type_c;
> };
>
> template<class A, class B, class C>
> struct for_each< vector<A, B, C> > {
>     typedef vector<
>         typename process<A>::type,
>         typename process<B>::type,
>         typename process<C>::type
>         > type;
> };
>
> An equivalent using a cons-style list would of course have an access time
of
> O(n):
>
> template<class> struct for_each;
> template<class A, class B, class C>
> struct for_each< typelist<A, typelist<B, typelist<C, null_t> > > > {
>     typedef typelist<
>         typename process<A>::type,
>         typelist<
>             typename process<B>::type,
>             typelist<
>                 typename process<C>::type,
>                 null_t
>                 >
>             >
>         > type;
> };
>
> The above raises some issues regarding the supposed 'reuse' of algorithms
also.
> You get _specializations_ of algorithms in many cases anyway.

Yes, you may get specialisations of some algorithms, for efficiency reasons,
even though not strictly necessary for it to work, similar to how
std::advance is specialised for different iterator types, using the most
efficient way available for a given iterator.

As mentioned, more experimentation could be needed to investigate this,
using different kinds of sequences for algorithms, and compare results.

> If so, what is
> the point of using iterators, which, BTW, imply iterating over a sequence
one at
> a time--thereby obviating the O(n) access time from the beginning of a
> cons-style list.

We've covered the possible efficiency, earlier (that you may not have to
pass over all the elements, or pass over them several times), so let's
consider flexibility.

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.

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.

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

> > > or when you are
> > > using a sequence of types to hold unrelated arbitrary types.
> >
> > And here.
>
> If you use a container of types to hold types that are not used in a
related
> fashion.  For example, if I changed some template class to wrap all the
template
> parameters into one type--rather than disparate template parameters:
>
> template<class T, class allocator>
>
> template<class args>
>     // where type_at<0, args>::type == T
>     // and type_at<1, args>::type == allocator

I understand now.

> > Like I said, if you store it as a binary search tree, i.e. you have
> > key/value pairs, then you may do an O(log N) rather than O(N) search.
>
> 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.

> > > Otherwise, element
> > > access is the same.  It takes O(1) to go from element A to element B
in
> > both a
> > > cons-style typelist and a vector (i.e. tuple-style list).
> >
> > It depends on what A and B is. Surely, you don't mean that going from
the
> > beginning to the end of a cons-list, unless you provide something like
> > random access iterators for it, is O(1)?
>
> If you step through a cons-style list or tuple-style list one element at a
time,
> the access complexity is O(n) either way.  Each step has an access
complexity of
> O(1)--in _both_ cases.

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

> > > This means that you are
> > > already providing the algorithm to flatten it, but you are doing it
_all
> > over
> > > the place_ instead of in a single place.
> >
> > All over the place? You mean as algorithms use iterators? For an
algorithm
> > to use iterators, it's more or less the same as using a cons-list. For
> > containers, then, true, they would have to some way provide a way to
flatten
> > the sequence. You could have this as an external algorithm if you like,
too,
> > a sequence converter, as you suggest, such as e.g.:
>
> I mean the definition of generic iterators even when they don't apply to a
large
> class of algorithms.
>
> > I can't see how this makes a big difference to the argument about
decoupling
> > sequences from algorithms. In the first case, you perform a conversion,
in
> > the latter case, you provide access, making it possible to access the
> > sequence in the required order.
> >
> > Specifically, the latter way doesn't need to mean more code than the
former
> > way. So what do you mean with something having to be done "all over the
> > place"?
>
> I mean that it always as to be done in order to use the algorithms, even
if only
> a single algorithm applies to the structure.

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

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.

> > A difference is that the latter case is "lazy", performing the
conversion
> > only when needed, while the former case transforms the whole sequence,
> > first. This could make a performance difference. Especially if the
sequence,
> > itself, is lazy, generating only elements when required.
>
> 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.

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

Then, I thought it would be nice to be able to combine metafunctions, as
well. So before I knew it, I was on my way to make function composition,
binders, lambda (which I had recently understood how worked, looking at the
MPL sources), and had I continued, I'd probably continued with iterators, as
well. At that point, I realized that it was no point in me starting to
duplicate all the work that had gone into MPL, when MPL is already there.

Sure, it was fun. :) It was exciting. Until I realized I was making MPL...
:)

If I had gone on to adding iterators, as well, it would have been a major
change in the library. They have quite different design philosophy. In
short, there wouldn't have been much left of the original Loki typelists in
that case.

In any case, as MPL is a set of concepts, as well (like STL concepts. Yes, I
do think there are similarities, here. :) ), then as has been pointed out,
you may use it without actually using any MPL code. The same goes for Loki's
typelists.

Regards,

Terje