Re: [boost] Formal Review for Interval Library beginning

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

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

> On Thu, 5 Sep 2002, Fernando Cacciola wrote:
>
> > I have a very specific interest in this library and although I haven't
said
> > so already, I really liked what I saw of it so far.
>
> Thanks.
>
> > It is just that I haven't got the time to look closer yet.
>
> > Q: What was the original objection to the comparison policies?
> > Unless I've missread something, the original objection was that they
loose
> > contextual information about the semantic of relational boolean
expressions.
> > That is, it was raised that code like the following is a bit unclear in
> > unusual ways:
> >
> > my_interval x,y ;
> > my_interval z = std::max(x,y);
> >
> > because the semantics of the operator '<' is hidden in the typedef for
> > 'my_interval'.
> >
> > Let's call this problem: 'non-locality'.
> > (because I need to look outside the scope, in some typedef, the meaning
> > (x<y))
>
> This "non-locality" is indeed a problem. But the user should not hesitate
> to convert an interval to another type with the correct comparison policy.
>
True, but the problem is not that a given interval doesn't has the correct
comparison, but rather that a user doesn't know what it has.
This is a very important problem for generic code. In my case, all numerical
algorithm are generic, for example. I can't change the comparison policy
from within the generic code simply because 'T' might not be
boost::interval.

>
> > AFAICT, initially it was not raised as a problem that the
> > policy-specifications didn't cover all required cases.
> >
> > Q: What are the problems with a 'bool' return type for the policies?
> > It could be said that the relational operators could benefit from
returning
> > a non-boolean type.
> > But, why would it be neccesary that they return a non-boolean type?
> > Returning a non-boolean type would be useful in order to define the
mapping
> > between the interval-interval inner comparisons and a boolean value.
> > But, isn't it the purpose of a user-defined interval-interval function
> > returning a 'bool' to supply this mapping?
>
> The problem is not in the user supplying such a mapping. But the user may
> want raw results rather than mapped results.
I don't understand what you mean with raw/mapped results.
Isn't interval-interval comparisons *always* mapped?

> Unless the mapping is not a
> pure function, some information will be lost. As I explained in another
> mail, in static analysis and inequations system solving, the three states
> are important. So it isn't interesting to force a mapping to bool.
>
I don't get it. The C++ conditional statements require boolean expressions,
so you are forced to map to bool, is it just a question of when and how.

> > So, if I have a comparison policy which allows me to define a mapping
> > between interval-interval comparisons and bool, why would I need the
> > additional possibility of defining this mapping not as a functionality
of
> > the policy itsef but as the functionality of a proxy-class as tribool?
That
> > is, what *additional* purpose could have a non-boolean return type?
(which
> > is not covered by the original policy specification).
> > AFAICT, tribool would be used to 'define' the mapping which I can do
already
> > via the policies.
> >
> > IMO,
> > (1) comparison policies as were originally designed -with a fixed bool
> > return type-; and
> > (2) any class type with an implicit conversion to bool (such as tribool)
> >
> > serve the same purpose: to map interval-interval comparisons to bool.
>
> Not exactly. It would be the same only if the tribool was systematically
> converted to bool.
>
Could you elaborate how is tribool or any other proxy like class not
systematically converted to bool?
AFAICT, tribool consistently maps:

true_value->true
false_value->false
indeterminate->false.

Thus,

Using tribool as in:

if ( x < y ) .... else ...  // assume (x<y) returned tribool

has the exact same effect of a policy which, after it decided the logical
answer based on whatever semantic it applies, narrows indeterminate to
false.

Could you elaborate specifically which uses could have tribool which cannot
be covered with a comparison policy returning bool?

> > Therefore, I believe that the library should choose either one or the
other.
> > This is what I meant to strongly recommend, not that it chooses tribool
or
> > any other fancy tool.
> >
> >
> > I see two overlapping alternatives:
> >
> > A) Use comparison policies with only bool return types
> > (and possibly with extended function sets to resolve the
> > relational-identities problem)
> >
> > B) Use a high-level proxy class which is returned by relational
operations
> > and which defines the mapping-to-bool either as:
> >
> >   B.1) an implicit conversion to bool.
> >   B.2) explicit functions taking the proxy as argument and returning
bool.
> >
> > tribool is really just an example of (B.1).
>
> What I said before should have convinced you that it isn't the case.
>
Not yet :-)

> > Notice that such a proxy could encode all the information it wants.
> > With the proxy approach, it might be possible to evaluate all of the
> > possible relations with all possible semantics (for instance, as shown
by
> > Joel), by using a syntax of the form:
> >
> > map(x .op. y)
> >
> > where
> > "map" is a discriminator function returning bool and used to select the
> > semantic of the relation.
> > ".op." is any of the relational operators
> > "x .op. y" is not a boolean expression but an instance of the proxy feed
to
> > the discriminator.
>
> Please remember that Joel's model defines a binary relation as being the
> union of some of the 13 fundamental relations. So the proxy should be able
> to handle 2^13 different binary relations. It's quite a heavy job.
>
No, In the scheme I proposed, the handling is done by the discriminator,
which encodes both the choice of semantic (witch order to use)  and the
conversion to bool (what to do with the indeterminate case).
The proxy itself is used only to transport information. For instance, it
could have just the two numbers and tag specifying the relation (<,>,etc..).

> > Now...
> >
> > You have properly explained that a specific proxy such as tri-bool won't
> > cover all the required cases while comparison policies do.
> > I knew this when I post my comments; so I agreed that tribool couldn't
be
> > fixed in the interface.
> >
> > But then I stated that, since it can't be fixed, tribool shouldn't
coexist
> > with the policy-approach because of the reasons I now gave above.
> >
> > Still, I wanted to explore general proxies, and I intended this to be
the
> > core of my post. Perhaps I shouldn't have even mentioned tribool.
> >
> > So, here I go again:
> >
> > It is always possible to define a proxy which handles properly all
> > interval-interval comparisons; and that therefore the true problem is
how to
> > define the mapping between this unique universal proxy returned by all
> > relational operators and bool.
>
> With Joel's model, this unique universal proxy should compute 13 tests to
> find the zone of the half-plane currently occupied by the two
> intervals; and some of these tests may require 4 number comparisons (the
> position of a point in a rectangle). Obviously, some of these
> number comparisons are redundant. But, I think something like 20 tests are
> required to correctly define the proxy.
>
> So, yes, it's universal. But I don't think the users are ready for such an
> universality.
>
You were correct if the proxy required exhaustive test, but as I said
before, it only keeps information that can be used by discriminators.

> > IMHO, a consistent and complete solution to this proxy-2-bool problem is
to
> > simply disallow implicit bool conversions and *require* explicit
functions.
> >
> > But requiring the use of explicit functions to map relational
expressions
> > (non-boolean) is unlikely to be accepted by end users.
> > If we think *only* in this last inconvinience, the proxy should have
some
> > implicit bool conversion for end users to like it (**but notice that I
would
> > have it without implicit conversions, as I said so before**).
> > But then this implicit conversion needs to be selected by the user,
which
> > means that the proxy itself is required to be a policy class.
> > I concluded that a proxy with implicit bool conversions will suffer
> > *exactly* from the *only* problem I see with comparison policies:
> > non-locality.
>
> If you use implicit comparison, then the current comparison policy is
> enough (and compare_full is quite easy to use).
>
Agreed.

> > OTOH, a proxy *without* implicit conversions will have strong local
> > semantics (context-free meaning), so it would totally solve all the
problems
> > raised so far AFAICT.
> > It appears that this is still the case, so the only drawback I see in
this
> > scheme is its involved syntax.
>
> And its complexity.
>
> > A last note: I think I've just made clear that I've never advocated
implicit
> > conversions.
> > (But I admit that I might have failed to say so clearly before)
> > Just for the records, I definitely never thought of overloading && and
||
> > for the proxy classes.
>
> For tribool, these operators are overloaded and it's quite interesting
> since it allows to write expressions like '(x < y && a >= b || c > d)' and
> it correctly handles the intermediary case.
>
But Sylvain pointed out that overloading && and || affects sequence points,
so these expressions can have different side effects than the same
expressions with booleans. I think this is deep ('cause its too subtle)
drawback.

BTW, Douglas made a very important observation that I think went unnoticed:

Regarding interval-interval relational expressions, there are two different
issues that are not uniquely defined:

1) The semantic of the relation. (how to define x<y)
2) The handling of indeterminate cases.

Currently, comparison policies deal with both.

I understand that the reason to allow policies to return tribool is to
decouple (2) from the policy itself.
I'm arguing against that because:  (2) *can* be done by the policy itself
and then we don't have to deal with relational operators with differing
return types.
As I said in my first post, I dislike relational operators with varing
return types.
That is:
IMHO, allowing the user the specify the behavior of:  "bool operator <
 interval, interval)"
is of different order of genericity that allowing it to specify:  "T
operator <  ( interval, interval)"
because the latter is carrying the genericity from outside the operator
itself.

However, the proxy approach (with consistent signature) can also be used to
decouple (1) from (2), by using compound discriminators:

if ( certainly( lexicographically(x<y) ) ) ....

interval_relop rel = subset(x<y);
if ( indeterminate(rel) )
 IDontKnow()
else
 if ( !certainly(rel) )
   IsNotLess()
else
  ItIsLess();

Again, this whole scheme could work only if users were to totally drop the
idea of using relational operators directly in boolean contexts; and it is a
pity that this is the only reason this entire issue is a problem.

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