Re: [boost] Formal Review for Interval Library beginning

From: Fernando Cacciola (fcacciola_at_[hidden])
Date: 2002-09-06 14:31:49

----- Original Message -----
From: "Guillaume Melquiond" <gmelquio_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Friday, September 06, 2002 3:23 PM
Subject: Re: [boost] Formal Review for Interval Library beginning

> 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.
>
OK. Good example...
I saw this comming when I wrote the last part of my previous post (when I
asked if you were thinking of "tribool rel = x < y").

> > > 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.
>
I didn't mention comparison functions before, you are right, but the fact
that they exist and can be used makes my point. See below...

>
> > 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.
>
If this operator has a consistent signature: T operator + ( T,T); then go
ahead and use it.
But if the operator has a varing return type, then IMHO it is an invitation
to trouble because operators communicate strongly about its semantics.
This is not the case with domain specific functions: users are prepared to
deal with all sorts of peculiarities when specific functions are used.
If I write (x+y) I better make sure it behaves just like anyone would expect
it.
If it doesn't, say for instance, that it returns an "expansion number" which
avoids overflow by adding explicit terms so not the loose range (IOWs, it
returns (x+y) algebraically if required); I better use a function call:

extended_arithmetic::result_type r = extended_arithmertic::add(x,y);

>
> 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?
>
No. I think it's quite short, but not really readable. It hides too many
important things: for example, g(x) will be called even if the first
condition is false... but it is not the usual case, so I might have wrote
that expecting the shortcut to ocurr (as most people do)

Fernando Cacciola
Sierra s.r.l.
fcacciola_at_[hidden]
www.gosierra.com