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;
>>> 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
> 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:
> 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 18.104.22.168:
> 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== ?
-- Dave Abrahams BoostPro Computing http://www.boostpro.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk