[std-interval] Interval comparison operators

[Guillaume Melquiond]

Le dimanche 28 mai 2006 à 16:55 +0000, first.i.last at comcast.net a
écrit :

> > First, I'm a bit confused. You are speaking of "subsets of the
> > machine number line" while the proposal is clearly aimed at
> > representing (convex) subsets of the real number line. I hope
> > this was only an oversight.
> 
> It was not an oversight.  It may have been a poor chioce of adjective
> in the document and a copy/paste omission on your part.  In fact it
> says "CONTIGUOUS subsets of the machine number line"[emphsis added].
> Perhaps it should have said convex rather than contiguous.  In this
> context I think they mean the same thing (denotation) except that the
> term contiguous suggests (connotation) continuity, which is a
> fundamental property that line segments and typical intervals do have,
> but that sets in general do not have.

Then I need to stress again that our proposal deals with intervals of
the _real_ number line. The machine number line is a discrete set of
values with its own arithmetic operators. An interval arithmetic can be
built on it, but this is not the one described in our proposal, while
the Boost interval library would support it for example (this interval
arithmetic is especially useful to statically certify the behavior of
floating-point applications).

[...]

> > Concerning your neighborhood model, I disagree. You are
> > saying that "the certain and possible comparison functions
> > are based on this model". But somebody performing global
> > optimization or value-range propagation will use them, while
> > the intervals are nothing like a neighborhood.  So certain and
> > possible comparisons should not be associated to a "point
> > model" in my opinion.
> 
> The sticking point here appears to be that "intervals are nothing like
> a neighborhood".  If they are not, what are they like?  I.e., what
> conceptual model do you believe the certain/possible comparisons to be
> based upon?

The natural interval extension of the comparison operators between real
numbers are comparison operators between intervals that return a value
in interval<bool> (which also happens to be the powerset of bool).
Certain and possible comparisons are two kind of maps from the powerset
of bool to bool. There is no need to speak of models, this is just a
reasonable way of constraining interval operators to a bool result.

[...]

> > Later, you say that "empty interval arguments should always
> > yield false". This statement contradicts your line-segment
> > model, since the empty set is included in every set.
> 
> What is the contradiction?  Equivalence and ordering comparisons do
> not deal with subsets.  The functions in() and contains() should
> affirm that an empty interval is included in every other interval.
> But the empty interval is neither less then nor more than any other
> interval.

It seems I didn't understand what your line-segment model is. I thought
its comparison operators were based on the set inclusion relation (hence
the functions slt, sle, and so on, as they are named in a few interval
arithmetic libraries, Sun's one for example).

> And given the the empty interval is not part of the machine number
> line one can claim that it is Not an Interval (NaI).  So, just as NaN
> is not equal to any other floating point value, not even an identical
> NaN, NaI should not be equal to any other interval, not even an
> identical NaI.

The empty interval _is_ an interval. It is not unreasonable to add a NaI
value in the same way there is a NaN floating-point value, but this does
not mean there is no empty interval. Would you forbid intersecting two
intervals that do not overlap?

> > It also goes against your neighborhood model, since the
> > classical interpretation is: if something is not possible,
> > then its contrary is certain (and reciprocally).
> 
> The classical interpretation fails anytime a NaN is encountered
> because they are not part of the number line.  Similarly empty
> intervals are not intervals (they need have no sensible bounds nor
> center/radius).  Moreover the classical interpretation cannot be
> applied to intervals at all because there are more relationships
> amoung intervals than there are among points on the machine number
> line.

NaN are not real numbers, they are never encountered in common
arithmetic on real numbers. Our proposal is about convex subsets of the
real numbers, not about convex subsets of machine numbers. I meant
classical interpretation to refer to computer science fields where the
"certain" and "possible" words are commonly used: probability
computations, fuzzy logic, and so on.

[...]

> But there is an opposing viewpoint.  When adding up a column of
> figures, say measurements taken during an experiment, one might want
> to know how accurate the total was.  Adding up intervals constructed
> from the measurements and their associated errors makes it trivial to
> find the error for the total of the measurements.  So the utility of
> intervals for common-place calculations is extremely high.  One need
> not be doing a global optimization to prefer intervals over built-in
> types.

How will it help to have comparison operators do midpoint comparisons on
this example?

[...]

Best regards,

Guillaume