Re: [boost] Interval Library and comparison operators

From: Joel Young (jdy_at_[hidden])
Date: 2002-09-05 15:15:09

Hi David,

I added your three partitionings to my page.  

http://www.cs.brown.edu/people/jdy/intervals/

If one wants the relation deduction to work as expected in the language
then I believe the partitions need to be complete.  That means that if
you specify < and == then > must be everything else?  The everything
else can be troubling.

If we have partial orderings then that is fine by me.  I have no trouble
with that.  Just don't assume that the definition of ">" is obvious when
"<" is provided and vice versa.

> Partial orderings always have, and should have, these "undefined
> regions". What is the problem with that? 

Nothing,

> Forcing those regions to be defined by either (1) introducing
> inconsistencies, such as defining '<=' or (2) using obscure tribools
> will not help.

Doesn't the behavior we would like out of the standard library/STL force
us to do that?  Does "not less than" need to be deducible from < and ==? 

I agree absolutely that <= should be < .or. == .  My original point
was that forcing point-point relations on intervals is troublesome...

If the underlying number system isn't totally ordered then things
can get really fun.  I haven't thought about that very much at all.

I guess what it comes down to is that "<, ==, >" is not rich enough a
language to discuss the relationships between intervals.  I got the
impression that people were falling into a trap with naive choices for
== and < and then expecting the deduced operations to have some useful
meaning in C++.

Joel
--------
From: "David Bergman" <davidb_at_[hidden]>
Date: Thu, 5 Sep 2002 14:41:37 -0400
  To: <boost_at_[hidden]>
Subj: RE: [boost] Interval Library and comparison operators

Joel,

No matter what ordering chosen, the equivalence and '<=' syntactic sugar
(yes, it should be regarded as syntactic sugar for '< || ==') still
should be as proposed by you.

So, back to the ordering. Which one is the most natural choice? Hmm,
there are obviously three orderings that popup:

1. The lexicographic (yes, that is a properly chosen name) ordering,
where
' [a1, a2] < [b1, b2] ' iff ' a1 < b1 || a1 == b1 && a2 < b2 '

2. The (strict; some people are strict about strictness ;-) subset
ordering, where
' A < B ' iff A is a subset of B; when all end points reside in the
same chain, this is reduced to ' b1 <= a1 && a2 <= b2 && !(A == B) '  

3. The "complete position" ordering (have no proper name for it...),
where
' [a1, a2] < [b1, b2] ' iff ' a2 < b1 && a1 < b1 '
the extra conjunct ' a1 < b1 ' is needed to ensure that all end
points are in the same chain, since we else can get A < B && B < A, if
the points lie in a circle.

Note that all these orderings are non-total if the underlying "number"
system is not totally ordered.

In the case the underlying "number" system is totally ordered, ordering
(1) is the only one being total. We have obviously discussed ordering
(3) the most in this thread.

Partial orderings always have, and should have, these "undefined
regions". What is the problem with that? Forcing those regions to be
defined by either (1) introducing inconsistencies, such as defining '<='
to be '!>', or (2) using obscure tribools will not help.

We all have to realize that at least two of the orderings above are
partial, there is not much we can do about it.

No matter what ordering chosen, '<=' should be regarded as syntactic
sugar for '< || ==' in the case there exists an equivalence, such as
here...

I must be extremely stupid/ignorant not to see the problem by these
fairly straight-forward definitions, so I hope someone will enlighten
me, so I also can join the "tribool and complex ordering" choire ;-)

David

-----Original Message-----
From: boost-bounces_at_[hidden]
[mailto:boost-bounces_at_[hidden]] On Behalf Of Joel Young
Sent: Thursday, September 05, 2002 2:13 PM
To: boost_at_[hidden]
Cc: jdy_at_[hidden]
Subject: Re: [boost] Interval Library and comparison operators

From: "David Bergman" <davidb_at_[hidden]>
> Guillaume,
>
> What is the rationale behind *not* defining
> 
> [a, b] == [c, d]    as    a == c && b == d
> 
> And
> 
> A <= B       A < B || A == B

The key question is how are you going to define less than and still keep
it symmetric with greater than and not have an undefined region?

When you project the rich interval-interval relation space into only
three relations, it is non-trivial to have a nice projection that
maintains a nice definition of equality.

Joel
_______________________________________________
Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost