[boost] Interval Library and comparison operators

From: Guillaume Melquiond (gmelquio_at_[hidden])
Date: 2002-09-05 03:31:51

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