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

From: Vladimir Prus (ghost_at_[hidden])
Date: 2001-07-26 09:59:05

On Thursday 26 July 2001 18:27, Vesa Karvonen wrote:
> > 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 difference, I think, lies in the way information of concept is stored. In 
your approach, unless I misunderstood it, container is responsible for 
providing it. It makes general despatch function unneeded. But is it the 
right way in general? What if some new algorithm requires some new concept? 
You'd have to change declarations of the containers. In my opinion, concept 
support in language should allow to declare class a model of concept 
everywhere and concept emulation should use the same approach. (This is 
different from how it's in Haskell, IIRC, but I don't think this makes any 
argument for C++)

> The problem with the above approach is that it defeats the compile-time
> type checking and overloading capabilities of C++. 
Only for despatching function. Both typechecking and overloading are used 
when actualy function need to be selected. Or you meant something other?

> 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. 
Example will help.

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

I meant that if one tries to feign concepts, creating compile time list with 
long series of template specialization is a not good solution. Moreover, it 
seems impossible to add elements to compile time list. Therefore, all the 
concepts should be listed in one place, which is a serious limitation.

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

> 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.
Once again, example will help, especially for those who haven't read 
Generative Programming.

-- 
Regards,
Vladimir