Re: [boost] Boost.Algorithm design question

Subject: Re: [boost] Boost.Algorithm design question
From: Dave Abrahams (dave_at_[hidden])
Date: 2011-10-07 16:10:57

on Fri Oct 07 2011, "Phil Endecott" <spam_from_boost_dev-AT-chezphil.org> wrote:

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

Not unless you're prepared to rewrite the whole standard, it's not.  The
whole standard relies on the semantics of English.

> what does "exchange" mean?  If it's a synonym for "swap" then we're
> saying "swap: it does what it says it does".  

You are going to penalize my description of the algorithm because it's
well-named?  C'mon, man.  Let's just imagine the name of that algorithm
was "befungle."

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

But that wouldn't be a reasonable interpretation of my spec, because it
would be incomplete.  It would leave everything in an unspecified state.

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

Well, no, not surely.  Many people (e.g. Stepanov, Lakos,... and I guess
me) think that having an operator== is essential to value semantics and
that your copy constructor, assignment operator, and swap lack verfiable
correctness without it.

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

Exactly.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com