[boost] Re: string_algo Formal Review

From: David Abrahams (dave_at_[hidden])
Date: 2003-10-22 08:34:44

Pavol Droba <droba_at_[hidden]> writes:

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

Understood; you're right.

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

You still need a tight definition of the requirements.

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

Problem is, your informal wording is not very explanatory for _me_.
Furthermore, I'm trying to point out what's needed in the docs and
you implied that this document is supposed to fill in the missing
pieces, but there's a lot still missing.

> I will try to be more precise in docs. 

OK.

> What I meant with the non-result argument is of cause, "a container
> argument with non-result type".  

Since I don't know what a container is (there seems to be some
fuzziness around the area of built-in arrays) this only helps a
little.

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

I'm sorry, we seem to have a disagreement about the importance of
tight specification.  Others may disagree with me, but personally I
think you should take this more seriously.

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com