Re: Circular structures [was Re: IEEE 754 floating-point arithmetic is not completely ordered]

[Jens Axel Søgaard <jensaxel@xxxxxxxxxxxx>]

Bradley Lucier wrote:
> On Apr 16, 2005, at 10:53 AM, Jens Axel Søgaard wrote:

> > > Well, it depends on what your goal is. ...
> >
> > Here are some potential goals:
> > ...
> > 3) default-compare should define a total order on almost all Scheme 
> > values
>
> What is "almost all"?  How do a and b compare in the following?
>
> [descartes:~/programs/folding/2] lucier% gsc
> loading /usr/local/Gambit-C/gambcext.scm
> Gambit Version 4.0 beta 12
>
>  > (define a (cons #f #f))
>  > (set-car! a a)
>  > (set-cdr! a a)
>  > (define b (cons #f #f))
>  > (set-car! b b)
>  > (set-cdr! b b)
>  > (equal? a b)   ;;; doesn't terminate

In the proposal default-compare is not defined on circular structures.
Theoretically I think (I am not sure though) it is possible to
define an order on graphs.

> Is default-compare compatible with equal?

The current proposal for default-compare is:

 (define (default-compare x y)
     (select-compare x y
       (null?    0)
       (pair?    (default-compare (car x) (car y))
                 (default-compare (cdr x) (cdr y)))
       (boolean? (compare-boolean x y))
       (char?    (compare-char    x y))
       (string?  (compare-string  x y))
       (symbol?  (compare-symbol  x y))
       (number?  (compare-number  x y))
       (vector?  (compare-vector default-compare x y))
       (else (error "unrecognized types" x y))))

Which means they are almost compatible :-)

The return value of equal? of two non-eq? symbols with the
same spelling is left unspecified by R5RS where as
default-compare is required to return #t.

Similary the return value of equal? of an exact number
and an inexact number that are numerically equal unspecified.

Apart from that, the domain of default-compare doesn't include
e.g. procedures as equal? does.


--
Jens Axel Søgaard