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.
> 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
> Let's call this problem: 'non-locality'.
> (because I need to look outside the scope, in some typedef, the meaning
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.
> (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)
> "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.
> 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
> 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:
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
> (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.
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk