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;
>> 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
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.
In the spec, I can see the "exchanges" language used in 20.2.2 and this
the object referred to by t has the value originally held by u
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk