[plt-scheme] Re: When does eqv? differ from eq? , from equal?

I am going to split hairs a little bit.Where (eq? X Y) is undefined 
('unspecified' in the R6RS document), R6RS yet requires eq? to return either 
#t or #f. Apparently 'unspecified' can have slighly different meanings at 
various places in the R6RS document.

R5RS requires

(let ((x (lambda ( ) '( ))))
 (eq? x x))

to yield #t, whereas according to R6RS it may return #t or #f (may be even 
inconsistently).

I wonder why R6RS dropped the requirement made in R5RS. Allowing inlining? 
Boy oh boy, two references to the same variable are no longer required to be 
*eq?* in all cases, even without side effects lying around.

In practice we have:

(define-struct x (y))
(define sxa (make-x 1))
(eq? (sxa (begin (set-x-y! sxa 2) sxa))) ; probably --> #t (eq? implemented 
as pointer comparison)
(define sxb (make-x 1))
(equal? (sxb (begin (set-x-y! sxb 2) sxb))) ; probably --> #f (equal? 
implemented as recursive content comparator)

So here we have an example where an implementation may return #t for eq? and 
yet return #f for equal?. This seems counterintuitive. Also look at "we 
change, therefore we are the same" in the Seasoned Schemer.

I don't know the answers, but a fundamental theoreme of lambda calculus 
states that there are no complete non trivial predicates. This also negates 
the existence of complete non trivial equivalence relations. As (eq? var-x 
var-x) is not even required to return #t, we even loose on reflexivity. So 
much is clear though: there are several ways to define equaility, but in 
practice all of them may fail when compared to the abstract mathematical 
notion of equality (which probably is a cumbersome subject too) In 
mathematics you may see axioms like x=x, but can we be sure this is true? 
When we dress x with information on its place in the text (left or right of 
the equal sign) it can also be argued that x=x cannot be true. Hence much 
depends on how we interpret variable references or more generally how we 
deal with symbols (in the mathematical sense, I mean)

Jos

----- Original Message ----- 
From: "Jacob Matthews" <jacobm at cs.uchicago.edu>
To: <kbohdan at mail.ru>
Cc: <plt-scheme at list.cs.brown.edu>
Sent: Tuesday, October 07, 2008 9:57 AM
Subject: Re: [plt-scheme] Re: When does eqv? differ from eq? , from equal?


> On Mon, Oct 6, 2008 at 11:20 PM,  <kbohdan at mail.ru> wrote:
>
>> Does it mean that eq? [behavior] is platform specific?
>> Looks worse than worse which is better :)
>
> Depends on what you mean by eq's behavior -- you have to distinguish
> between the behavior it's guaranteed to exhibit and behavior it may
> happen to exhibit. eq? is defined by R6RS to be #t or #f in some
> cases, and is undefined in many other cases. For instance,
>
> (eq? '() '()) is defined to be #t
> (eq? (list 1) (list 1)) is defined to be #f
> (let ([x (list 1)]) (eq? x x)) is defined to be #t
> (eq? (lambda (x) 1) (lambda (x) 2)) is defined to be #f
> (boolean? (eq? X Y)) is defined to be #t for any values X, Y
>
> (eq? (expt 10 100) (expt 10 100)) is undefined
> (eq? 2 2) is undefined
> (eq? (lambda (x) x) (lambda (x) x)) is undefined
> (eq? (lambda (x) x) (lambda (y) y)) is undefined
> (let ([x (lambda () 1)]) (eq? x x)) is undefined
> (eq? (lambda (x) 72) (lambda (x) (if (valid-claim?
> fermats-last-theorem) 72 43))) is undefined
> (eq? (lambda () #f) (lambda () (valid-claim? p-equals-np))) is
> conjectured but not proven to be undefined
>
> mzscheme (and every other Scheme implementation) returns _something_
> for all those undefined cases. But a portable program should never
> rely on that return value. If you write programs that only use eq? in
> the cases where it is defined by R6RS (which is probably a good
> practice, even if you're only intending your program to run in
> mzscheme), then its behavior is totally implementation-independent.
> Otherwise you're on your own.
>
> -jacob
>
> PS I say these things to explain eq?, not defend it. I'm not too happy
> myself with the fact that equal? means "happens to be the same at this
> moment" but eq? doesn't really mean "necessarily equal," or much of
> anything else in particular. And eqv?, the function that started this
> whole topic, is useless as near as I can tell, since it is defined to
> be eq? unless you know the values you're comparing are numbers or
> characters (or a handful of "empty" values) in which case you're
> better off using a type-specific comparison function.
>
> But then again, every programming language I know of has at least a
> few frustrating dark corners when it comes to equality. It's a much
> harder problem than it appears. This is especially true in the
> presence of mutation, where the notions "happens to be the same right
> now" and "necessarily equal" are very often conflated. But even in
> totally pure settings, "equality" is overloaded to mean lots of
> different, similar-but-sometimes-slightly-different things. I was
> reminded of this most recently when I wrote a bit of graph-traversal
> code in Haskell, with the data representation something like  "data
> Vertex = V [(Char, Vertex)]", and graph cycles constructed with tricks
> like "let aStar = Vertex [('a', aStar)] in aStar". This is a perfectly
> legitimate way to define a graph in Haskell, but how do you tell if
> you've already traversed a given node?
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>