Re: [boost] Formal Review for Interval Library beginning

From: Sylvain Pion (pion_at_[hidden])
Date: 2002-09-03 22:33:33

On Tue, Sep 03, 2002 at 01:10:11PM -0400, Douglas Gregor wrote:
> * I'm not a big fan of the comparison policy. Policies are great for code 
> reuse, but when they are used to decide between different syntactic forms for 
> equivalent semantics things can get _very_ confusing. This code is quite 
> ambiguous:
> 
>   template<typename T, typename Traits>
>   void foo(interval<T, Traits> x, interval<T, Traits> y)
>   {
>     if (x < y) {
>       // ...
>     }
>   }
>   
>   Checking 'x < y' has no well-defined semantics, because 'foo' has no way to 
> know what the comparison policy is.

Actually, there _is_ a way to do something.  This is essentially the way CGAL
uses its interval arithmetic class, so it's a real life example which works
great (I can detail more if you want).  See below.

> [Comparisons - potential solution]
> My proposed solution is:
>   * Use a 3-state boolean type for the result of comparisons between 
> intervals. The 'tribool' type I posted a few weeks ago is one such type that 
> I believe would give a reasonable semantics.
>   * Remove comparison policies entirely. With an accepted 3-state boolean 
> type, there will be one semantics for 3-state boolean values that users will 
> need to learn, so an interval comparison 'i < j' has a single, well-defined 
> semantics in terms of 3-state boolean values and its narrowing to a standard 
> 'bool' will be consistent.

I'm not sure I could live with that proposed solution.  I worked on this
library in order to generalize my own implementation (which is CGAL's) in
directions that I was sure would be useful to me or someone else.  With your
proposition, this library would not be useful to me anymore, and here comes
why :

I agree that the _internal_ logic of tribool is consistent, and I think
everybody agrees that we need to support it as a possible return type of the
comparisons operators.  I would have been happy to get rid of the
Comparison_policy.  But IMHO, we can't :(

The question is what do you do when you need to convert to a bool, i.e. what
does the following do :

  if (x<y)

Obviously, only the indeterminate/overlap case poses a problem.
Here are the "constraints" for my application :
- I want to re-use my template code that assumes a comparison is always safe
  (i.e. as in the total order of the reals), in short, I don't want to change a
  piece of template code that assumes exact arithmetic, and truely boolean
  comparisons (that's similar to your example basically).
- I _need_ to be able to detect if there has been some indeterminate
  comparisons while I was running a piece of code (the whole point of IA).
  Setting a global variable of throwing an exception are working alternatives,
  since I don't want to modify the code of the template function.

The current tribool always converts indeterminate to false without any
exception or any way to see that, so you _have_ to modify the code to
explicitly detect the indeterminate case, e.g. using something like :

  if (x<y) {...}
  else if (!(x<y) {...}
  else { /* my special case */ }

Hence I can't buy tribool for my application.

On the contrary, the Comparison_policy mecanism allows that, it allows to
choose the notification by either an exception or setting a global variable,
or whatever you want.

My application doesn't try to do any sane logic on 3 states, but it needs to be
able to detect if there has been a bad comparison somewhere, in which case a
completely different course of action needs to be done (this is the unexpected
case basically, hence its relation to exceptions).

That is one of the fundamental needs of interval arithmetic : certify the
results, be able to detect if something wrong happened during some
computations.

Moreover, the Comparison_policy is flexible enough to emulate the behaviour of
Profil/BIAS (interval inclusion is what the comparison operators mean there),
hence makes it useful to a whole bunch of people who use that library for
interval analysis.

Face it, each and every existing interval arithmetic library provides a
different semantic for the comparisons.  Hence the two reasonnable choices are
either not to define them at all so that the user defines them himself if he
needs to, or provide some defaults and a way to change the behavior, hence the
existence of Comparison_policy.  If you enforce it in some way to a fix choice,
then it means that code has to be modified to take the syntax you impose.

These are the actual practical arguments that lead to the necessity of
abstraction in Comparison_policy.
We found them convincing.  What about you ?

> * rounded_transc_dummy seems very dangerous, because it will allow
> meaningless code to compile. I think Jeff Garland already brought this up,
> but a call to sin(interval<T>) should not compile if it isn't going to do
> anything useful. 

I would tend to agree.

On a general note, seeing the other messages, I must say that I think we
cannot, and we shoudn't necessarily, try to fit any existing kind of interval
in this library, because they are just conceptually different beasts.
At some point, you have to stop abstracting.

Maybe the name of the class "interval" is then too general
(the suggestion boost::math::interval could fix that I think), but the library
name is "Interval _Arithmetic_ library".  Please don't forget that.
The primary goal of this library is interval arithmetic and interval analysis,
and we went to some great length to satisfy all needs for this particular
domain.

Thanks a lot for the review !

-- 
Sylvain