RE: [boost] Interval Library and comparison operators

From: David Bergman (davidb_at_[hidden])
Date: 2002-09-05 11:58:24

Guillaume,

What is the rationale behind *not* defining

        [a, b] == [c, d]    as    a == c && b == d

And

        A <= B       A < B || A == B
?

This was suggested by both me and Joel.

NB: STLs default definition of '<=' as '!>' is a *convenience* method to
not have to define that operation when you have a *total* ordering.

A lot of us reviewing the library suddenly see other possibilies, and
maybe would want a general interval abstraction, where (at least the
more advanced portion of) the mathematical operations are separated in a
separate header, as suggested by someone earlier in the thread, or
extend it to handle sequences of intervals, such as suggested by
Gennadiy, or allow for traversal, which was suggested by Gennadiy (I
think...) and me. 

I understand that one has to draw a circle somewhere, as Herve put it,
and agree completely that this library should handle interval
arithmetics, and nothing else. I originally suggested traversal, but
that might lead us away from the main purpose.

I actually think the interval arithmetic should be separated, into

   1. interval core definitions, including '<', '==' and set operations
   2. arithmetical operations on intervals
   3. non-arithmetical operations on intervals

And there should be openings for distribution descriptors for
probabilistic applications, as suggested by someone. That could be added
as a separate extension (header file)

This way, one could use (1) for those strange applications, such as date
intervals, where no (advanced) arithmetics is needed ;-)

Regards,

David

-----Original Message-----
From: boost-bounces_at_[hidden]
[mailto:boost-bounces_at_[hidden]] On Behalf Of Guillaume Melquiond
Sent: Thursday, September 05, 2002 4:32 AM
To: boost_at_[hidden]
Subject: [boost] Interval Library and comparison operators

At present, the Interval Arithmetic Library is being reviewed. And it
seems a lot of discussions centers on comparison operators. I'm not
surprised of this situation since we, the library authors, already had
heated discussions when we began to design the library.

However, due to the strong beliefs of some reviewers on this subject, I
fear an interval library will never be able to make its way through a
formal review and be accepted into Boost. So I'm sorry to start a new
thread on this subject, but I feel it's necessary.

First, let's summarize the behavior of the current library. The interval
class uses a comparison policy in order to define the 6 relational
operators == != < > <= >=. Such a policy has to define two functions.
These functions take two intervals and return a boolean.

One of the functions explains how the operator < is defined. Then, from
this definition, the interval library can infer the behavior of > <= >=.
The operators <= and >= are respectively defined by !> and !<.

The other function describes the behavior of ==. And the library uses
this description in order to infer the operator !=.

There are also a bunch of explicit comparison functions whose semantic
is clearly defined and not subject to change.

Next, let's see what were the different points that were raised until
now. Please excuse me if I attribute some comments to the wrong
reviewer.

1. The first comment came from Carl Daniel who wanted boolean
expressions manipulating interval comparisons to handle the
undeterminate case. Then, Douglas Gregor seconded it: he wanted the
comparison operators to return a tribool rather than a bool.

As it was explained, it's just a matter of changing the return type of
the comparison operators from a boolean to an user-defined type
(specified by the comparison policy). Normally, this modification of the
library should not raise any objection, should it?

But it seems Fernando Cacciola doesn't agree with me on this point and
is against adding the return type to the comparison policy.

2. Later Douglas Gregor proposed that all the comparison operators
return a tribool and that comparison policies and explicit comparison
functions should purely and simply be removed.

I am against that for two reasons. First it would force the use of
tribool on the user. Secondly, in order to compute a tribool result, a
comparison operator may need two number comparisons rather than only one
in the boolean case; and as you may know, conditional executions are one
of the bottlenecks of modern processors. Third, expicit comparison
functions increase the readability of a program; but I'm probably the
only one to think this way :-).

3. Next came the question of <= and >=. I think David Bergman was the
first to disagree with their definition being !> and !<.

As he explained, the orders we are considering are partial so we don't
have to use the previous interpretation and may use the following one:
x<=y iff for each element a in x and each element b in y, a<=b.

This interpretation is more interesting, but unfortunately, it's not the
way the STL expects the comparison operators to be defined. So Peter
Dimov proposed a really simple solution: to just suppress <= and >=
since their definition gives rise to confusion.

Another solution would be to add a third function to the comparison
policy in order for the library to correctly handle <= and >=.

4. Then came Joel Young and his 13 relational operators.

I find this way of describing relations really nice; but unless I'm
missing the point, I don't see how it solves the previous problems. Or
was it meant to completely remove all the comparison operators?

5. Finally, Fernando Cacciola proposed to modify the syntax of
comparison operators and to use instead: certainly(x < y), possibly(x <
y), etc.

It's an interesting syntax; and I'm ready to admit that, by using some
C++ techniques, it is possible to avoid the performance drawback of the
tribool version. However, as he stated it himself, it doesn't solve the
previous problems.

I hope I didn't forget any idea; feel free to contradict me on this
point. I also would like to remind to the reviewers that a lot of
interval arithmetic libraries actually used didn't propose a way to
handle comparison operators.

Please give (or remind) your opinion on these problems. The comparison
operators are probably the most awkard point of this library; and I hope
this thread will allow a consensus to emerge, and that no reviewer will
afterwards raise the comparison operators issue as a reason to reject
the library.

Best regards,

Guillaume

_______________________________________________
Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost