Re: [boost] [Review:Algorithms] Order of args to clamp

Subject: Re: [boost] [Review:Algorithms] Order of args to clamp
From: Dave Abrahams (dave_at_[hidden])
Date: 2011-09-26 07:36:30

on Mon Sep 26 2011, "Jeffrey Lee Hellrung, Jr." <jeffrey.hellrung-AT-gmail.com> wrote:

> On Sun, Sep 25, 2011 at 6:25 PM, Dave Abrahams <dave_at_[hidden]> wrote:
>
>> Okay, so this is an algorithm on types for which
>> common_type<T,L,H>::type is well-defined?
>>
>> I'm already suspicious about the semantic validity of a
>> HasCommonType<X,Y> concept, but I'll let it slide for now.
>>
>
> Fair enough; it is a natural requirement to start with given the "obvious"
> implementation using conditionals.

Yeah, but now we're back at implementation-driven requirements.

> Basically, I would think
>
> clamp(x, lo, hi)
>
> and
>
> clamp((U)x, (U)low, (U)hi)
>
> should give the same result.

...right... so now should every algorithm be generalized that way, with
the attendant complications in specification?  Do we need the same
interface for, say, GCD?  Why not just ask the caller to cast to the
common type first?

>> > Returns: If x < lo or hi < x (these are mutually exclusive assuming an
>> > appropriate precise ordering), returns (U)lo or (U)hi, respectively.
>>
>> Why is that the right definition?  In your case,
>>
>>  when !(x < lo) and !(lo < x), are we returning (U)lo or (U)x
>>
>> and why is that the right (most meaningful) answer?
>
> You still have the same issue for single-type clamp for any non-total
> ordering, right?  

Right.  I'm just saying that the problem is complicated enough with a
single type.

> If you precondition single-type clamp on a strict total ordering, then
> this potentially-ambiguous case never arises, but that seems to be
> more restrictive than necessary and I can imagine useful cases that
> fall outside that domain.

For example?

> Regarding my choice of result, I'd informally describe clamping as "if x
> falls outside the interval [lo, hi], then return lo or hi, else x".  I'd
> define "[lo, hi]" as {x : !(x < lo) && !(hi < x)} (for a strict weak
> ordering, this should be everything that falls between lo and hi, plus
> everything equivalent to lo and hi).  Then I think the result above follows.

Okay.

>> I understand what that algorithm does when applied to a strict total
>> order.  *I* would describe it something like this:
>>
>>    REQUIRES: < imposes a strict total ordering over T.
>>    RETURNS: The value y of T nearest to x such that !(y < lo) and !(hi
>>    < y).
>>
>> <waveshands>where "nearest to" is suitably defined for any total
>> order.</waveshands>
>>
>> I haven't given this one enough time to percolate; I'm sure there's a
>> way to express _precisely_ what I mean in roughly that many words,
>> though.
>
> Sure.

That's a lot more comprehensible than the description you gave, though,
and you can understand it without treading into the territory of
implementation details.

>> When applied to a strict weak order, it's unclear to me which
>> element of the various equivalence classes should be returned in several
>> cases.  Now, probably someone has thought this through more deeply than
>> I, but maybe you can understand now why I'm reluctant to complicate the
>> definition of this algorithm with the consequences of multi-type
>> signatures.
>
> I think the complication you reference above primarily arises if you relax
> the strict total ordering precondition.  So let's separate concerns, unless
> you think they are intimately related: 1) What ordering should be imposed on
> operator< for single-type clamp?  2) What is the description of the
> algorithm for multi-type clamp?

Good.

> For multi-type clamp, I think you can get by if you precondition that
> operator< on U objects is a strict total ordering and that a < b is
> equivalent to (U)a < (U)b.  

So... you aren't advocating for allowing any of strict weak ordering?

> Then clamp(x, lo, hi) and clamp((U)x, (U)lo, (U)hi) will give the same
> result (which, I think, is what you want anyway), and the latter is as
> defined above.  Indeed, whatever ordering is decided upon should imply
> that clamp(x, lo, hi) and clamp((U)x, (U)lo, (U)hi) give the same
> result, and I think this almost necessitates that (a < b) == ((U)a <
> (U)b).

I think you can strike "almost" :-)

> A problem that I see is that (a < b) == ((U)a < (U)b) fails for some common
> use cases (e.g., char const * and std::string) where the clamp
> implementation still works and does what you'd expect.  
>
> But that's just an indication that the preconditions are too strong,
> if anything, I think.

Maybe.  But then, what should the preconditions *be*?

Note: you can solve that problem by asking the caller to do the
conversion ;-)

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