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

Subject: Re: [boost] [Review:Algorithms] Order of args to clamp
From: Jeffrey Lee Hellrung, Jr. (jeffrey.hellrung_at_[hidden])
Date: 2011-09-26 01:07:00

On Sun, Sep 25, 2011 at 6:25 PM, Dave Abrahams <dave_at_[hidden]> wrote:

>
> on Sun Sep 25 2011, "Jeffrey Lee Hellrung, Jr." <
> jeffrey.hellrung-AT-gmail.com> wrote:
>
> > On Sun, Sep 25, 2011 at 10:48 AM, Dave Abrahams <dave_at_[hidden]>
> wrote:
> >
> >>
> >> on Sun Sep 25 2011, Steven Watanabe <watanabesj-AT-gmail.com> wrote:
> >>
> >> >> Here's an exercise:
> >> >>
> >> >> 1. Write down the documentation for both the multi-type and
> single-type
> >> >>    "clamp" algorithms.  Describe both the concept requirements on the
> >> >>    algorithm parameters, and the result of each algorithm (without
> >> >>    making reference to its implementation).
> >> >>
> >> >
> >> > It seems fairly straightforward.  All that's necessary
> >> > is to require that comparing objects of different types
> >> > is equivalent to converting to the same type and then
> >> > comparing and define the result to be the same as though
> >> > we converted first and called the single type version.
> >>
> >> So, do the exercise.  And, BTW, which of the types involved is "the same
> >> type" in this case?
> >>
> >
> > Okay, I'll try.
> >
> > clamp(T x, L lo, H hi) -> common_type<T,L,H>::type
> >
> > Let U = common_type<T,L,H>::type.
>
> 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.

> > Precondition:  operator< defines an ordering on objects of type U.   For
> any
> > 2 objects a and b of types A and B, respectively, where A and B are each
> one
> > of {T,L,H}, a < b is equivalent to (U)a < (U)b.  !(hi < lo).
> >
> > [Note: I'm not sure yet precisely what "ordering" would be desired
> > here (probably a "strict weak ordering" is sufficient, as for many
> > other STL algorithms, but I confess I'm a bit rusty on various
> > ordering properties),
>
> Try http://cpp-next.com/archive/2010/02/order-i-say (I just did, as
> review).
>

Yeah, that's a good summary :)

> > and it should certainly be specified if you want
> > to be precise, but it's the same ordering as would be required for
> > clamp(T,T,T), so it's somewhat tangential to this exercise.]
>
> I'm not sure.  It's crucial to the question of what you mean by this
> algorithm, and it probably affects the ultimate complexity of your
> requirements.  That is, I believe there will be some relationship
> between the ordering requirements chosen for the single-type algorithm
> and the requirements you end up with for the three-type algorithm.
>

Yeah upon further reflection, it does matter, but I think it can nonetheless
be deduced based on the ordering chosen for the single-type clamp.
Basically, I would think

clamp(x, lo, hi)

and

clamp((U)x, (U)low, (U)hi)

should give the same result.

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

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.

> Otherwise, returns (U)x.  [Note: I believe the above requirements
> > yield at least 2 nontrivially different implementations: (x < lo ? lo
> > : hi < x : hi ? x) or (hi < x ? hi : x < lo ? lo : x).]
> >
> > Is this what you had in mind?
>
> Not quite.  I still don't know what this algorithm means.  I don't think
> I know enough about what it means to convert a value of one type to its
> common type with two others.

That is something I left out (not intentionally), but I think it's
sufficient to precondition on the relationship between a < b and (U)a <
(U)b.

 You also didn't show the algorithm
> description for the case where they're all required to be the same type,
> so we can compare.
>

Well I had intended it to be the same as the multi-type case, with T == L ==
H == U.

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

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

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

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.

- Jeff