Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ncar!ames!uhccux!munnari.oz.au!cs.mu.oz.au!ok
From: ok@cs.mu.oz.au (Richard O'Keefe)
Newsgroups: comp.lang.lisp
Subject: Re: Total ordering for Lisp objects ?
Message-ID: <2084@munnari.oz.au>
Date: 12 Sep 89 03:22:22 GMT
References: <5896@lifia.imag.fr> <865@skye.ed.ac.uk>
Sender: news@cs.mu.oz.au
Lines: 21

In article <5896@lifia.imag.fr> phs@lifia.imag.fr (Philippe Schnoebelen) writes:
> "Would it be possible to add a total ordering predicate on Lisp
> objects ?"
In article <865@skye.ed.ac.uk>, jeff@aiai.uucp (Jeff Dalton) writes:
> As you may know, Prolog has such an ordering.  I think it would also
> be useful in Lisp.

It is straightforward to define such an ordering on Prolog ground terms,
because Prolog has no assignment or replacement operations.  If we tried
to define such an ordering in Lisp, however, we would expect that
	(total-less-p '(1) '(2))        ; should be T
But consider
        (let ((a (list 1))	        ; fresh copy of (1)
              (b (list 2)))             ; fresh copy of (2)
	    (print (total-less-p a b))  ; prints T
	    (setf (car a) 2)            ; now a is (2)
	    (setf (car b) 1)            ; now b is (1)
	    (print (total-less-p a b))) ; prints NIL
The ordering of a and b has changed although a and b still point to the
"same" objects.  (Think about one stack group trying to sort a list while
another is happily mutating it...)