Re: [boost] Re: MPL containers and algorithms

From: Fernando Cacciola (fcacciola_at_[hidden])
Date: 2002-08-01 09:25:29

----- Original Message -----
From: "Paul Mensonides" <pmenso57_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Wednesday, July 31, 2002 6:18 PM
Subject: Re: [boost] Re: MPL containers and algorithms

> > Fair enough, but you should notice that your entire argument seems to
based
> > in the axiomatic statement that I remarked above.
> > IMO, the bottom line of this discussion is that Andrei and you think
that
> > compile-time programming differs from run-time programming so much that,
as
> > you said, the conventional run-time needs (such as efficient random
access
> > time, head-tail appending time, insertion time, permutation time,
etc...)
> > don't apply to compile-time.
>
> Not between run-time and compile-time.  Between imperative and functional
> programming.
>
OK.

> Template metaprogramming, regardless of what it looks like, is
> functional programming.
>
I know.

> > You have to prove, or at least, explain a lot more deeply, this point
> > precisely. Why different sequence-types are undoubtly useful in
run-time,
> > but not in compile-time? It all boils down to this.
>
> Primarily, because the reasons that we have multiple run-times containers
don't
> apply to functional programming.  For example, the only reason that you
wouldn't
> always use std::vector as your sequence type is that insertion requires
copying
> all of the elements and possibly reallocating all of the memory.  You use
> std::vector for fast access, and push_back is on average very efficient.
This
> is unlike template metaprogramming in nearly every regard.  Insertion
*always*
> requires copying, and (if you count the innards of the compiler) *always*
> requires reallocating.  You use std::list to avoid this cost of insertion.
It
> is fast because it only has to *modify* a few pointers, but this _is not
> possible_ in a functional environment.  You have to copy the entire
sequence
> anyway.  Furthermore, this copying is not particularly expensive because
it is
> mostly just copying a reference into some compiler's internal structure of
> identifiers.
>
I think that your arguments above are correct but incomplete. Let me
explain:

You are saying that mutating operations have different complexities on
different data structures, which is correct as we all know, and that those
complexity differences are irrelevant for FP (funtional programming).
So far I agree. FP don't have truly mutating operations, only 'generative'
operations, which are not the same.

If I understood you and Andrei correctly, generative operations won't
benefit significantly from different data structures.
Let's say I also agree here by taking your word for it.

But that's not all...

Different data structures have also different non-mutating and
non-generative operation complexities.
For instance:

Vectors and Matrices have O(1) Access and Omin-Directional traversal.
Singly-connected Lists and Directed Graphs have O(N) Access and
Uni-Directional traversal.
Doubly-connected Lists and Undirected Graphs have O(N) Access and
Omni-Directional traversal
Balanced-Trees have O(logN) Search  and Multi (but not necessarily
Omni)-Directional traversal.

Furthermore, some specific structures support traversals which are just not
supported at all by other structures.
For example, Cycles support "Circulation" (that is, you can traverse all the
elements of the sequence regardless of where you start).

The question, I think, would be this: Do these differences in Access and
Traversal Capabilities matter for Functional and/or Compile-Time
programming?

I understand Andrei suspicion and his appropriate request for sound examples
in order to help answer the above.
I myself, *a priori*, find hard to believe that such fundamental
abstractions are useless in a different computational model. Their different
mutating/generative properties might be irrelevant, but not their different
access capabilities .

I won't come up with a sound example in the short/mid term mainly because I
might not find the need for it myself, but I think it will come eventually
once MPL becomes widely used.

Off the top of my head, I imagine that I could hard-code meta-graphs (not
list-like nor tree-like) to express some relation between types (say,
promotion rules), and code up special iterators so as to use MPL algorithms.
Maybe MPL is not directly up to graph-related algorithms right now, probably
because STL isn't either; but such extensions are likely to be easy to build
upon the current model just like the BGL is built upon STL concepts.
This could prove that the multiplicity of data-structures and the generic
iterator-oriented algoritms were a good choice.

> Given that this is the case, the most efficient solution would be to
always use
> a tuple-like (i.e. vector-like) container that can hold a huge number of
> elements.  On the other hand, the most extensible solution would be to use
a
> cons-style list.  One or the other is fine, but both is unnecessary.
>
I find this a bit odd: You are saying yourself that there are at least two
possibilities with clearly different properties, but you conclude that even
then, having both at the same time is unnecessary. How is that?
If on one situation I only need to *look at*  a fixed, hard-coded sequence,
I would like to use a tuple-like since it's efficient.
If on a different context I need to *generate* a sequence I would use a
cons-style list because it's flexible.
Why wouldn't I want to have the two options to choose from?

Fernando Cacciola
Sierra s.r.l.
fcacciola_at_[hidden]
www.gosierra.com