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

From: Vesa Karvonen (vesa.karvonen_at_[hidden])
Date: 2001-07-27 08:40:57

From: "Vladimir Prus" <ghost_at_[hidden]>
> On Thursday 26 July 2001 18:27, Vesa Karvonen wrote:
[...]
> 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.

No. That is not necessary. You can always resort to the traits (metacode) +
dispatch technique.

> In my opinion, concept
> support in language should allow to declare class a model of concept
> everywhere

I agree. A suitably flexible form of constrained genericity would do.

> 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++)

Perhaps. Unfortunately, as you have indicated yourself, it is difficult to
create such external concepts.

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

This is what I meant. It is really ugly that the dispatching function has to
be overly generic. If C++ didn't have namespaces, such functions would really
cause fatal problems - a library would effectively reserve specific function
template signatures. Even with namespaces, they can cause lots of trouble, as
it is more difficult to reuse names of overly generic functions.

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

If the type returned by the concept emulation is not matched by any specific
implementation, then dispatch function will call itself, because it is the
only function that matches. This can be avoided by naming the implementation
functions differently (e.g. _helper), but this is ugly.

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

Ok, I see the problem.

I think that the problem of adding future concepts could be partially solved
by using extendable generators. Unfortunately, in order to add concepts to an
implementation, you have to change its type and recompile. This is not very
different from adding concepts to a separate traits class. In both cases you
will end up recompiling possibly major subsets of your code. Depending on how
you have structured your code, either approach may be superior. For instance,
if you have legacy code, which makes no use of the traits, it does not need to
be recompiled. Unfortunately everything that refers to the traits needs to be
recompiled. On the other hand, if you are using the generator approach, you
might simply regenerate the types of the implementations where you need the
additional concepts and leave old code alone. Unfortunately, if you need to
pass implementations of the exact same types to legacy code, then you are out
of luck with the generator approach (and need to use conversions or modify and
recompile the old code).

> > > 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 plans to write a generative container library, but with the amount of
resources I currently have in use for the project, it will take many months
before it is usable.

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

Oops... It should have been 574.

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

Wait for my resource library, though it will also take some time before it is
ready, as I need to finalize the template metaprogramming library first.