RE: [boost] Formal Review for Interval Library beginning

From: David Bergman (davidb_at_[hidden])
Date: 2002-09-03 14:26:46

Doug wrote:

> * I don't understand the reasoning behind the definition of <=. The
> documentation says "...another misleading interpretation of the
comparison 
> is: (still with the example of compare_certainly) [a, b] < [c, d] is
true if 
> and only if it is true for each pair of element in [a, b] and [c, d].
But 
> [a, b] <=[c, d] is true if and only if it is true for at least one
pair." 
>   Why choose this (to me, non-obvious) semantics? Given a comparison
such as 
> [3,5] <= [4,6], why would we consider this true? I view an interval 
> comparison [3,5] <= [4,6] as the comparison x <= y where x is in [3,5]
and y 
> is in [4,6], so the result is indeterminate (x could be 5 when y is 4,
but x 
> could also be 3 when y is 6, so either true or false is possible).
What 
> interpretation of [3,5] <= [4,6] leads to a value of (certainly) true?

Guillaume wrote:

> You are right, there is two interpretation of <=. And it was also one
of the conflicting?
> point during the design phase of the library.

> First, you can say that [a,b] <= [c,d] is true iff it is true for each
pair of elements.

> But you can also say that [a,b] <= [c,d] is the same as !([a,b] >
[c,d]). And unfortunately,  > this interpretation is not equivalent to
the previous one.

My comment: no, you can not say that (partial order)

> So we had to choose an interpretation. And we finally choosed the
second one. The reason is: > an user who is not attentive enough may
transform "if !(a <= b)" in "if (a > b)". If it was > the first
interpretation, the program would suddenly be incorrect. It can even be
more
> dangerous if you are using an algorithm that was not written by
yourself: how can you be
> sure the programmer didn't do this mistake, and this error never
appeared before because
> nobody was using intervals with it.

My comments to Guillaume's comment:

You chose the wrong one ;-)

Here we have that implicit strictness and totality of orderings lurking
again...

Note that intervals, by the definition given in your library and in
Interval Arithmetics are *partial orderings* w.r.t. "compare_certainly",
no matter what numeric homeomorphically embedded basis we use.

The user should be forced to realize that he has left total orderings
and went into the land of partial orderings, where the "if !(a <= b)"
and "if (a > b)" equivalence does not hold. Such shortcuts are *only*
allowed in total orderings, else we would end up with the rather
unpleasant "(a <= b) != (a < b || a == b)", which is the case here...

Also, the implicit "equivalence as incomparability" is only a vivid
alternative when sorting vectors, IMEHO.

I would love to see this library (1) extend its reach a bit, to make use
of those "nifty meta-programming constructs" C++ provides us with, i.e.,
be a bit more flexible w.r.t types and (2) handle the ordering of
intervals in a more logically sound manner. Till then my vote would be
to reject the library.

/David