[boost] Re: MPL containers and algorithms

From: Andrei Alexandrescu (andrewalex_at_[hidden])
Date: 2002-07-31 18:15:07

"Paul Mensonides" <pmenso57_at_[hidden]> wrote in message
news:002e01c238d7$cb763140$7772e50c_at_c161550a...
> > 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.  Template metaprogramming, regardless of what it looks like,
is
> functional programming.

It's both at the same time. We have STL that uses an imperative language
(granted, C++ also have little bits of functional language artifacts) and
defines code that will evaluate at runtime, and MPL that uses a pure
functional language and defines code that will evaluate at runtime.

So we have two differences here, one that concerns means and the other that
concerns ends.

(1) imperative versus functional
(2) run time versus compile time

To me they are both big differences. In fact, I believe they are each a
world of differences. Trying to design a compile-time library that uses a
functional language for compile-time evaluation, to match a run-time library
that uses an imperative language for run-time evaluation, is an interesting
intellectual exercise. At the same time, it is not obvious to me on why this
decision was made. From all I saw, it only leads to extra futile
contortions.

Pure functional languages have other primitive constructs than imperative
languages. Furthermore, C++ compile-time tasks are different from run-time
tasks in both size and nature. Maybe it would be fancy to sort the words in
Shakespeare's Hamlet at compile time, but then maybe not in C++. Other
languages are better at it.

I asked for concrete, real-world examples, of tasks that suck with
s-expressions and are stellar with something else. (To wit, with the STL you
can easily provide clear examples of tasks that are cool with vector and bad
with list.) Got no response. I am not convinced.

To repeat: It would be great to see some *real-world* convincing and
compelling examples that have the following features:

(1) Performs a sensible task that one might imagine herself having to do (by
the way, "say you want to sort a hierachy of 100,000 classes rooted in
Widget" does not qualify).

(2) Implemented with s-expressions, the algorithm is terribly slow.

(3) Implemented with some other structure, the algorithm is consistently
faster, when compared to (2), on all compilers it's been tried.

If such examples have been given, I'd appreciate a copy or link instead
of... well, something else.

I see people comparing typelist functionality in Loki with MPL. This is a
red herring. Loki's typelists are heavily KISSed. Basically Loki defines the
bare minimum it can get by. So it's easy, but not productive, to illustrate
examples that compare an exisiting facility in MPL with a nonexistant
facility in Loki. It's not, and it never was, about that. As it's been said,
nobody claims that Loki's design is perfect or even good. The right question
is, how much burden there is for supporting multiple containers as opposed
to focusing on s-expressions only. A compile-time facility fostering
simplicity of means and unity would be more appealing to me that one that's
more complicated to be like the STL. Unless, of course, salient examples
show up.

> > 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.
>
> 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 quoted all of the above because I so much agree with it :o). By the way,
don't things work the other way? That is, it's great when a library comes
with examples illustrating its usefulness. I guess that's easier and more
natural than people coming with example of that library's lack of
usefulness - process that puts those people in a bad light, as your truly
knows :o).

Andrei