RE: [boost] Formal Review for Interval Library beginning

From: David Bergman (davidb_at_[hidden])
Date: 2002-09-03 19:46:03

Herve,

You do not agree, apparently, that defining '<=' as '! >' is illogical
in your case. But if you view it in the light of the induced
"equivalence" relation not being an equivalence at all, as you noted, an
not even a congruence relation, you do still not think it is illogical.

I argue (to take one implication) that
    ' a <= b && ! (a==b) ' 
Should *always* imply
        ' a < b '.
In the case these operators are defined and '==' is any equivalence
relation, consistent with '<' (a == b && a < c   ===>  b < c). I mean,
remember that '<=' is read as "less than or equal"... So in the case
where we have a "less" (as here) and an "equal" (as here, which is the
standard extensional equivalence of sets, actually, not your
"overlapping") the logical implication of "less than or equal" (<=) is
rather clear :-)

Here we have ' [2, 5] <= [4, 6] && !([2, 5] == [4, 6]) ' but *not* ' [2,
5] < [4, 6] '.

The simple truth is that you cannot, as you noted yourself, use the
induced equivalence relation (induced by the STL-default behavior, of
'<=' defined as '! >'). It is not a sound relation for "being
equivalent", and not even formally an equivalence relation.  

And even if we welcome inconsistencies, logically speaking, there should
be a pragmatic reason for the choice. But, not disturbing the
STL-provided default behavior for '<=' is IMEHO not a wise pragmatic
choice. I would not want to do a QuickSort on a list of intervals using
STL, since we would end up with a mess. But as far as I can read from
the comments made by you and Guillaume I see this "transparency" w.r.t
numerical operations and existing numerical code to be the reason for
your choice.

I think you might have to revise that decision before putting this quite
powerful tool in the hands of old complaining logicians like me ;-)

By the way, have I mentioned that the library seems very useful and I
would gladly use it for a few Quantum Physics simulations I am working
on in my spare time. It is just that it lacks a certain consistency and
generality (w.r.t types) which I think are corner stones for Boost. But,
do not care too much about my opinion, I am a Boost newbie.

Regards,

David 

-----Original Message-----
From: boost-bounces_at_[hidden]
[mailto:boost-bounces_at_[hidden]] On Behalf Of Herve Bronnimann
Sent: Tuesday, September 03, 2002 5:11 PM
To: boost_at_[hidden]
Subject: Re: [boost] Formal Review for Interval Library beginning

On Tue, Sep 03, 2002 at 04:36:10PM -0400, David Bergman wrote:
> The C++ Standard gives us a default implementation of "<=" in terms of
> "! >". That default behavior should be overridden when that is no 
> longer true w.r.t. logic. That is why I used the hard word "wrong", 
> cause it is "wrong" as in illogical to have (in a domain with proper 
> equivalence)
> 
> 	a <= b   !=   a < b || a == b

On the other hand, out of sheer honesty, and because someone else might
notice and hold it against me not to say it loud, I have to agree with
you on one point. Even though on all the examples you supplied, !(a<b) &
(!(b<a) means overlap, there is a snag: this is not an equivalence
relation. Indeed, [0,2] overlaps with [1,4], which overlaps with [3,5],
but [0,2] does not overlap with [3,5].

What this means is that there is no hope of defining operator< in a way
that is compatible with the operator< for the base type, idem for
operator>, <=, and >=, and still hope to have nice mathematical
properties. But I take this as one more reason to proceed as we did,
i.e. carefully and documentedly, providing extra functions cerlt, etc.
Those should be useful in whatever you are doing since they essentially
reduce to bounds comparison.

The other option is, like Profil/BIAS, to define operator< in terms of
subset, superset, etc. That has the mathematical consistency.

By the way, I appreciate the discussion and the arguments provided so
far have been fair. I was not expecting less from the gentle boosters.
Regards,
-- 
Hervé
_______________________________________________
Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost