RE: [boost] Submission: typelist

From: Aleksey Gurtovoy (alexy_at_[hidden])
Date: 2001-11-28 10:53:28

Andrei Alexandrescu wrote:
> > To be fair, Andrei, you should compare a version of Loki 
> > typelists that works without partial specialization.
> 
> Maybe, but I don't think so. Mpl's whole design is like that. 

Like what? There is very little in "MPL design" that is affected by the fact
that the library was written to work on compilers without partial
specialization. 

It's not the implementation of type_list or an implementation of some
specific algorithm like 'at' or 'size' in MPL that matters; in fact, if you
look at the big picture, that specific type_list implementation is may be
the least important component in the whole library! What matters is the
conceptual framework, the idea of how an extensible compile-time library of
the algorithms, sequences and function classes should look like, and
apparently some people has missed this.

It's not a problem to implement type_list, whatever creation method it uses
(nested "cons", macros, make_type_list<>::type notation, etc.), and whatever
naming convention it adapts. It's not a problem to implement a couple of
core type_list algorithms like 'size', 'at', 'push_front', etc. that are
tied to this specific type_list implementation, but provide best possible
compile-time performance. It _is_ much more resource-consuming to implement
at least a basic set of the sequence algorithms provided by equivalent
run-time libraries (STL in particular), - and yes, they _are_ obligatory to
have! - and tying those algorithms' implementation to your specific
type_list - _that_ would be a misgiuded effort!

Like it or not, but there is no and never will be the single "best"
type_list or tuple implementation, "one size that fits all", for the same
reasons why there will never be the single "best" std::vector
implementation, and because there are _already_ quite a number of type_list
and tuple implementation around being used, and, most important (which may
be an eye-opening fact for some), because "type list" is not the only
possible compile-time sequence that is useful. Again, the need for different
types of compile-time "containers" (as well as true sequences) arises from
the same fact that dictates a need to have all these lists, vectors, deques,
etc. stuff in the standard library - different containers have different
functional and performance characteristics that affect a lot of things,
starting with applicability and efficiency of particular algorithms, and
ending up with expressiveness/verbosity of the user code that uses them. (If
you don't think that compile-time algorithms' performance is that important,
most probably it's just because your metaprogramms are relatively simple;
you might want to read Dave's paper on the topic to get a sense of the issue
-http://users.rcn.com/abrahams/instantiation_speed/index.html; also, besides
compilation times themselves, there is another compile-time resource that is
very affected by a particular combination of algorithms/containers
combination - maximum number of recursively nested template instantiations,
which is in some sense ever more important). Boost::mpl library currently
provides three different types of compile-time sequences -
mpl::type_list/mpl::value_list (they are identical from a
performance/categorical point of view), mpl::type_vector and
mpl::value_range, and mpl::type_map is coming. Those templates _are_
different. They provide different compile-time performance. They are in
different sequence categories. Some of them are more expressive in
representing particular kind of sequences than the other. For example, as
Dave already said, mpl::type_vector allows compile-time random access, and
_constant time_ insertion/removal time in any position. It's an important
difference from typical type_list implementation that is a basically a
forward-access sequence with linear insertion/removal times, and yes, there
are C++ applications where it does matter. Another example is value_range
sequence, which represents an immutable random-access sorted sequence of
integer constants; for instance, mpl::value_range<0,100> ==
value_list<0,1,2,3,4,5,6,7,8,9,..,99> (except the fact that the former one
provides a random-access functionality), and I much prefer writing the first
expression in place of the second one.

Now, returning to the algorithms and MPL design. Currently the library
provides ~20 sequence algorithms (not counting core sequence operation like
'size', 'at', 'push_[back,front]', 'pop_[back,front]', etc.), and I consider
most of them essential to any library that pretends to be useful in the real
world (for the record, the algorithms are: for_each, find, find_if.hpp,
count, count_if, contains, equal, copy, copy_if, transform, replace,
replace_if, remove, remove_if, merge, sort,..). Now, consider implementing
each of these algorithms separately (the approach Loki takes) for each
sequence type MPL currently provides - you get 3 * 20 = 60 algorithms.
That's a huge amount of code, don't you think? And that's not the whole
picture yet, because some of the algorithms operate on two or more
sequences, and I don't even want to think how to deal with this. And again,
that's not the whole picture yet, because even with this amount of code your
library is still useless to a user who had invented her own type_list
implementation. 

Of course, your library may as well ignore all these issues; providing
specific type_list implementation + a couple of core specialized algorithms
is an option too. But when our libraries clearly have different scopes -
which is fine, and still one way or another the components you submit should
be "compatible" with the framework provided by boost::mpl. 

I do understand you strive for simplicity of loki::type_list implementation
and the core algorithms like 'size', 'empty', 'at', etc, and "integrating
with MPL" _does not_ force you to sacrifice this goal. All core sequence
algorithms in MPL are _inteded_ to be overridden by the most effective
implementation possible for the particular kind of compile-time data
structure. For example, the default 'size' algorithm implementation that you
cited is, well, default! That's it - the only must requirement for the
(immutable) sequence type in MPL is to provide implementation of
begin<>/end<> meta-functions. Everything else - all non-mutating algorithms!
- will "just work", although, of course, some they may be not the most
effective one - for example 'size'. So if you decide to provide a more
efficient implementation - do it! In fact, you are encouraged to do it,
because, although currently it's not obvious, "minimum possible overhead"
_is_ a library goal. And if you put the pieces together, you will see, for
example, that for 'size' for mpl::value_range<> sequence is defined as 

    template<>
    struct size_algorithm_traits<mpl::half_open_range_tag>
    {
        template<typename Range> struct algorithm
        {
            BOOST_STATIC_CONSTANT(long, value = Range::finish -
Range::start);
        };
    };

Of course, there is still a top-level 'size' algorithm wrapper:

    template<typename Sequence>
    struct size 
        : size_algorithm_traits< 
              typename mpl::sequence_traits<Sequence>::sequence_category
              >::template algorithm<Sequence> 
    {
    };

But even with this, things do look much simpler now, don't they? Also note,
that algorithm traits are mostly an implementation detail here, although
they do have an important role in adapting the "foreign" types of sequences
with minimal amount of code.

> Sure. I'm not sure how this appies to what I was discussing. 
> I made the point that Loki's typelist is much simpler. Then I 
> made the point that it is also just as powerful.

It is not, it's more like a specific fine-tuned implementation of quite
small subset of functionality provided by MPL framework. Loki is intrusive
and does not scale, and MPL is not and does.

> I don't know, but quite frankly I couldn't say with a 
> straight face that mpl::at (which does use some 
> algorithms) is simple.

It's not, and there is no reason to not write your own version that will
replace the default one.

Aleksey