Re: [boost] Formal Review for Interval Library beginning

From: Guillaume Melquiond (gmelquio_at_[hidden])
Date: 2002-09-06 08:11:40

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.

> 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. 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.

> 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.

> 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.

> 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.

> 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.

> 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).

> 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 syntaxis.

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.

Regards,

Guillaume

PS: Please don't misunderstand me. I didn't take part in boost::tribool
and I'm not doing its eulogizing (I don't use it myself). However, I think
it's a powerful tool and it's well adapted to some uses of intervals. So
it would be sad to discard this possibility.