Re: Boost algorithm library (Was: [boost] New upload: algorithm.zip 1)

From: Vesa Karvonen (vesa.karvonen_at_[hidden])
Date: 2001-07-26 09:27:59

From: "Vladimir Prus" <ghost_at_[hidden]>
> On Thursday 26 July 2001 01:55, Vesa Karvonen wrote:
> > I think that the essential question is: What support should a container
> > library provide for extending the library?
> >
> > My opinion is that a generic C++ container library should provide means
for
> > writing generic overloaded functions on containers, and STL specifically
> > does not provide such support. This means that in order to write
overloaded
> > algorithm wrappers for standard containers, you need to repeat the
wrappers
> > for each container (10x work) or change the names of the algorithm
> > functions (ugly).
>
> Or just reimplement all the STL algorithms in namespace boost with
> appropriate changes.

Hmm... Perhaps I don't understand what you are implying.

The problem is that Boost can not possibly implement all algorithms with
appropriate changes. The set of algorithms on sequences is infinite. The
support that I'm advocating (*top level overloading*) is designed to make it
easier to write algorithms for containers, regardless of whether those are
standard algorithms or just written by a C++ code monkey, like me, for a
specific application.

> > Providing generic overloading support is not difficult. Basically, all you
> > need to do is to make sure that a container is-a instance of a class
> > template with a single template parameter, so that you can write an
> > algorithm on the template, that basically uses "pattern matching" to
enable
> > overloading:
> >
> >     template<class base, class t, class bin_op>
> >     t accumulate(const container<base>& c, t x, bin_op op);
>
> I have tried something similar some time ago. In my case class
> Container<base>, derived from class Concept, simply had reference to base
> object. Other component was function metaclass, which accessed compile time
> list containing all the concepts class implements and created object derived
> from all concepts, for example:
> class A {};
> class B {};
>
> void find_c(const SortedContainer<B>&,  const T&);
> void find_c(const Container<B>&, const T&);

I believe these are all template functions:
template<class T1, class T2>
> void find_c(const T1& t1, const T2& t2)
> {
> // Supposing that T1=B and B is declared as model of SortedContainer and
> // FunnyConcept then metaclass will return metaclass_t<B> object which
> // will be derived from SortedContainer<B> and FunnyConcept<B>
> find_c(metaclass(t1), t2);
> }

I think that it is important to emphasize that this is similar to, but not the
same as the support I'm advocating (*top level overloading*). The support I'm
advocating is specifically designed to largely reduce the need to write overly
generic dispatching functions.

The problem with the above approach is that it defeats the compile-time type
checking and overloading capabilities of C++. The above kind of code could
easily cause an infinite loop that would only be detected in run-time. The
same kind of infinite loop can not occure when there is no need for a
dispatching function. You could also name the dispatching function differently
from the implementation functions, but this is not ideal. Ideally you would
not need the dispatching functions at all, instead the container library (and
language) would support overloading (based on constrained genericity).

> The biggest problem was creating those compile-time lists of concepts, and I
> don't have a good solution.

I'm not sure about what you mean by this, but creating compile-time lists is
not extremely difficult. If you need to put metafunctions in a list, you must
use member templates.

Perhaps you mean that it was difficult to (automatically) create the list of
concepts for a particular container or something like that.

 [snip]
> > It is not too difficult to construct containers like that. For example,
you
> > can use 3 type of layers:
> > - body layers (these implement the container)
> > - concept layers (these describe the type of the container for
overloading)
> > - constructor layer (this layer contains all the constructors appropriate
> > for the container type)
>
> OK, this is reasonable. In fact, all is needed is to write wrappers for all
> containers in namespace boost.

Yes, it should be possible to adapt an existing container into the above
framework without modifying existing code. However, the highest payoff comes
when the container library comes with an extendable generator. By extendable,
I mean that the generator should support user-defined layers, which means that
a user can write the necessary metacode in order for the generator to be able
to integrate a user defined layer into a concrete layered architecture.

I have a number of relatively simple ideas on how to make such a generator.
Basically all you need to do is to perform the ordering of layers in metacode
instead of manually (as is implied in step 4 on page 547 in Generative
Programming). The sorting information then needs to be represented in an
extendable way. The way I have in mind is to write predicates for each layer
that determine which layers should be before and which should be after the
layer (or possibly report a conflict). This is basically a description of a
directed graph. The sorter then finds a topological ordering of the graph (or
reports a conflict) and instantiates the layered architecture.

> It is also possible to create something like
> 'container_traits', write algorithm wrappers and use traditional despatch
> methods.

As I already indicated, and I suppose you may be talking about a slightly
different kind of solution, the problem with the overused "pure abstraction" +
"traits" approach is that it does not support top level overloading. You end
up writing overly generic functions. This partially or completely defeats the
C++ compile-time type checking and overloading facilities.