Re: [boost] Formal Review for Interval Library beginning

From: Guillaume Melquiond (gmelquio_at_[hidden])
Date: 2002-09-06 13:23:14

On Fri, 6 Sep 2002, Fernando Cacciola wrote:

> > Let's put it simply: the result of a comparison (in the forall/exists
> > context used in static analysis and inequations systems solving) is an
> > element of {false, maybe, true}. You need three different values; and if
> > you map it to {false, true} before returning it to the user, he/she will
> > lose a part of the information.
> >
> he/she is a part of the running program? I ask because in Doug's response I
> couldn't see the usage for the program itself.

Here is a little solver for the inequation 'f(x) > 0':

  void solve(interval x) {
    tribool cmp = f(x) > 0;
    if (f == true) {
      // we have a winner, let's warn the user
      throw x;
    } else if (f == false) {
      // to bad, we are sure there is no solution in x
      return;
    } else {
      // maybe there is a solution, let's bisect to be sure
      std::pair<interval> p = bisect(x);
      solve(p.first);
      solve(p.second);
    }
  }

The function will throw an exception when it found a solution.

> > By using a more complex type than bool, you can store this three-states
> > information. And the problem of this type being convertible or not to bool
> > afterwards is not really relevant here. What is interesting with tribool
> > is that it holds a three-states value, not that it is convertible to bool.
> >
> Are you thinking of this?
> 
> tribool rel = x < y ;
> assert ( !indeterminate(rel) ) ;
> if ( rel ) less() else not_less();
> 
> If so, isn't it already possible to achieve this with the comparison
> functions?

Yes it is. But this whole thread was not about the comparison functions
but the comparison operators.

> That is, if the user (not an external tool, but a part of the running
> program) needs to explicitely test for the indeterminate case, why would
> (s)he use operator <?

Why are we using using '+' even though we could have an 'add' function and
call it? It's the same problem.

Just think that the solver could solve 'f(x) > 0 && g(x) > 0'. So the
first line of the function body would be:

  tribool cmp = f(x) > 0 && g(x) > 0;

Don't you think it's quite a readable way to write it?

Regards,

Guillaume