Re: [boost] Re: string_algo Formal Review

From: Pavol Droba (droba_at_[hidden])
Date: 2003-10-22 01:04:10

On Tue, Oct 21, 2003 at 05:48:27PM -0400, David Abrahams wrote:
> Pavol Droba <droba_at_[hidden]> writes:
> 

[snip]

> > InputContainerConcept:
> > {
> >
> > /////// types
> >
> > 	 typedef ... value_type;
> > 	 typedef ... size_type;
> > 	 typedef ... iterator;
> > 	 typedef ... const_iterator;
> > 	 typedef ... difference_type;
> >
> > ////// operations
> >
> > 	 iterator begin();
> > 	 const_iterator begin() const;
> > 	 iterator end();
> > 	 const_iterator end() const;
> > 	 
> >  	 size_type size();
> > 	 bool empty();
> > };
> >
> > These properties are exactly the properties the STD Container
> > concept, except of construction/destuction method, and swap.
> 
> I wonder if swap ought to be included, despite the fact that you
> don't need it.
>

Problem with the swap is, that it is not possible to implement it
for some useful types of containers (For instance c-arrays). Given
the fact that it is not need in this context, it would be unwise to 
require it and remove the possibility to use less defined containers.
 
> > This concept allows to access the values contained in the container,
> > without altering the state of the container itself. It means, the it
> > is not possible to change, what elemnts are containd by this
> > container.  It is sufficient for those arguments in algorithms with
> > are not altered (i.e. immutable arguments)
> >
> > container_traits, one of the core facilities defined in theis
> > library, wraps this concept, and allows to access some of legacy C
> > structure (C-arrays and string) using this interface.
> 
> Whoa.  You'll never get a C array to have a begin() member function.
> This statement needs to be tightened up.  If your algorithms can
> actually operate on C arrays directly, your need to change your
> description of InputContainerConcept so that it's phrased in terms of
> container traits.  Regardless, you should also be as specific as the
> standard is about the requirements on nested types and return types
> of begin/end, etc.
> 

Sorry, the definition is not exact. I have used the C++ syntax, but I 
merely wanted to list the requiremnts. The fact is, that it is not
required, that f.e. a container have .begin() member function. It is only
required, that such a function is accessible. Having the container_traits
and freestanding begin(), it is well defined for C-arrays.

> > iterator_range also implements this concept for a pair of iterators.
> >
> > In the string_algo library, a container satifying this concept can
> > be used as any non-result argument (i.e. the argument, whose type is
> > not used as a result).
> 
> Really, "any?"  You have no char or integral non-result arguments?  I
> see that you have output iterator non-result arguments.
> 

Please do not take all my wording so explicitly exact. I have studied mathematics,
and I'm very well aware, that formal scientific wording is perfect, but
it is not very explanatory in many places

I will try to be more precise in docs. 

What I meant with the non-result argument is of cause, "a container argument with non-result type".
There are other types of paramters, but either they type is fully specified, or their
an specification is clear. As a matter of fact, thare are only 4 significant types of template
arguments used in addition to containers:

1. Predicates - any functional object, accepting the required value type as an argumnet and returning bool
2. Finder - Presicely specified in docs
3. Formater - detto.
4. Iterator - these are mostly use in the implemetation detail, but the name of template argument always 
              matches the required iterator type

(Note: I you will look through the library in a great detail, you will probably find more types,
 but, I'm pretty sure, that there won't be any problem with their interpretation )

[snip]

> > 2. Copy variant, that returns the copy of the modyfied input. This
> > variant also uses the same type as input for the result. For all
> > algorithms, SeqeuenceConcept is sufficient, however for some of
> > them, standard ContainerConcept (Std 23.1) is sufficient. In
> > addition to InputContainer, there is a need for a construction,
> > because the new copy of the container is required.
> 
> You need to be specific about which algorithms need Sequence and
> which need Container.

 From the point of this review, it will be safer to assume, that SequenceConcept
is always required. There are exceptions, but it is only a minority.
It is possible that it the future, in some algorithms, the requirements
will be lowered.
 
Regards,

Pavol