Re: [boost] Boost.Algorithm design question

Subject: Re: [boost] Boost.Algorithm design question
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2011-10-07 12:11:20

Dave Abrahams wrote:
> on Thu Oct 06 2011, "Phil Endecott" <spam_from_boost_dev-AT-chezphil.org> wrote:
>>     clamp(val,lo,hi) = val<lo ? lo : val>hi : hi : val;
>>
>> vs.
>>
>>     clamp(val,lo,hi) returns the middle value when (val,lo,hi) are
>>     ordered according to operator<
>
> Wow, that certainly is stark.  When I try to describe it better in
> words, it reads just like your implementation.  But I'm not sure what
> that proves.  Swap is a trivial algorithm.  Isn't it best described as
> "exchanges the values of its arguments?"

Swap is a good example.  Saying "exchanges the values of its arguments" 
relies on the semantics of English, which is problematic; what does 
"exchange" mean?  If it's a synonym for "swap" then we're saying "swap: 
it does what it says it does".  But maybe "exchange" means something 
different; if I go into a shop and say "I bought these two shirts 
yesterday but they're the wrong size; may I please exchange them?", I 
do not expect the sales assistant to just 'swap' them and give them 
back to me (though if someone ever did do that, I'd give them a 
programming job).

On the other hand, defining swap in terms of its implementation is not 
ideal either because of the temporary:

     tmp = a;  a = b;  b = tmp;

The need to use a temporary is not inherent in the algorithm; if I'm 
swapping ints my processor might be able to do that with a single 
instruction and no (apparent) temporary.  And then there are classic 
nasty tricks like

     a -= b;  b += a;  a = b-a;

So at the very least it is necessary to say "has the same 
externally-observable effects as ...".

Or it could be written as a postcondition:

     swap(a,b)
     postcondition:   a == b'  &&  b == a'

(where I'm using ' to mean "the previous value of".)   But of course 
that requires that == is defined.  Yet surely it is perfectly 
acceptable to swap objects for which operator== is not defined.

In the spec, I can see the "exchanges" language used in 20.2.2 and this 
in 17.6.3.2:

     the object referred to by t has the value originally held by u
     and [vice-versa]

which just leads to the question, what does to "have the value" mean, 
if not operator== ?

Really there is no good solution for things at this level.  My view is 
that (in C++) we can only usefully specify algorithms that are rather 
more complex than these things (I suggest "sort" and above).  For those 
more complex things we can "brush under the carpet" the nasty details 
at the bottom level and yet still provide some useful information to 
the user.  For trivial algorithms, nothing is left.

Regards,  Phil.