< must be transitive in Scheme

[John Cowan]

R4RS says under the discussion of =, <, >, <=, and >= that "these predicates are required to be transitive", and notes "The traditional implementations of these predicates in Lisp-like languages are not transitive". The same language appears in R[56]RS and the current draft of R7RS-small. However, the current editors don't understand what it means. It doesn't have anything to do with non-finite values, because those weren't standardized until R6RS.

Does anyone understand what the issue is here? We'd appreciate being enlightened.

--
John Cowan http://ccil.org/~cowan co...@ccil.org
Monday we watch-a Firefly's house, but he no come out. He wasn't home.
Tuesday we go to the ball game, but he fool us. He no show up. Wednesday he
go to the ball game, and we fool him. We no show up. Thursday was a
double-header. Nobody show up. Friday it rained all day. There was no ball
game, so we stayed home and we listened to it on-a the radio. --Chicolini

[Ludovic Courtès]

John Cowan <johnw...@gmail.com> skribis:

> R4RS says under the discussion of =, <, >, <=, and >= that "these
> predicates are required to be transitive", and notes "The traditional
> implementations of these predicates in Lisp-like languages are not
> transitive". The same language appears in R[56]RS and the current
> draft of R7RS-small. However, the current editors don't understand
> what it means. It doesn't have anything to do with non-finite values,
> because those weren't standardized until R6RS.

Is it just that (A < B) ∧ (B < C) ⇒ (A < C) ?

Ludo’.

[John Cowan]

On Monday, November 5, 2012 9:25:44 AM UTC-5, Ludovic Courtès wrote:

> Is it just that (A < B) ∧ (B < C) ⇒ (A < C) ?

Indeed. But why are "traditional implementations" not transitive? The answer was supplied to us privately by Bradley Lucier. The traditional implementation in question was, if any argument was inexact, to convert all arguments to inexact numbers before comparing them. That might throw away information necessary to preserve transitivity.

[Alex Shinn]

Note it's still unclear if coercing down to inexact
ever actually breaks transitivity. If anyone is
aware of an example I'd like to know.

--
Alex

[Jussi Piitulainen]

I think the rationale in Steele's CLtL2 (p. 290 in my copy, indexed at
"transitivity, accuracy") is meant to be such. I quote:

| Let _a_ be the result of (/ 10.0 single-float-epsilon), and let _j_
| be the result of (floor a). ..., all of (<= a j), (< j (+ j 1)), and
| (<= (+ j 1) a) would be true; transitivity would then imply that
| (< a a) ought to be true ...

The first ellipsis states:

| ... (= a (+ a 1.0)) is true, by the definition of
| single-float-epsilon ...

I think in Scheme _j_ would be (floor (inexact->exact a)), and the
claimed breakdown of transitivity would be this:

(and (<= a (exact->inexact j))
(< j (+ j 1))
(<= (exact->inexact (+ j 1)) a)
(not (< a a)))

Hope I got this right. Apologies in advance.

[Alex Shinn]

Thanks! I was supplied another example as well:

(let ((a (- (expt 2 1000) 1))
(b (inexact (expt 2 1000)))
(c (+ (expt 2 1000) 1)))
(assert (if (and (= a b) (= b c))
(= a c)
#t)))

The CLtL example would translate as:

(define single-float-epsilon
(do ((eps 1.0 (* eps 2.0)))
((= eps (+ eps 1.0)) eps)))

(let* ((a (/ 10.0 single-float-epsilon))
(j (exact a)))
(assert (if (and (<= a j) (< j (+ j 1)))
(not (<= (+ j 1) a))
#t)))

--
Alex