On Sun, Sep 25, 2011 at 6:25 PM, Dave Abrahams <dave@boostpro.com> 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@boostpro.com> 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