Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!usc!venera.isi.edu!donc
From: donc@vaxa.isi.edu (Don Cohen)
Newsgroups: comp.lang.lisp
Subject: Re: Total ordering for Lisp objects ?
Summary: bad idea
Message-ID: <9582@venera.isi.edu>
Date: 11 Sep 89 21:40:30 GMT
References: <5896@lifia.imag.fr> <865@skye.ed.ac.uk>
Sender: news@venera.isi.edu
Reply-To: donc@vaxa.isi.edu.UUCP (Don Cohen)
Organization: USC-Information Sciences Institute
Lines: 27

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 ?"
You can easily build your own - just keep track of your previous (arbitrary)
decisions and be sure to make the same one the same way.  Of course this may
be expensive if you compare lots of things.
...
>>Assuming that, for cons cells, the order is simply the relative position in
>>memory of the cells, is it still possible to use copy-compact GC
>>algorithms ?, or other more sophisticated (e.g.  generation-scavenging)
>>techniques ?
One technique that would certainly be lost if you tried to preserve address
order is the technique of moving things around to improve paging performance
which is now done by symbolics and TI garbage collectors.  I happen to think
that this is a very valuable technique indeed.

In article <865@skye.ed.ac.uk> jeff@aiai.uucp (Jeff Dalton) writes:
>
>   1st numbers, in some reasonable order
>     (complex numbers have to be a special case)
>   Then atoms (symbols) in alphabetical order
>   Then terms, first by arity, then by functor, and
>     finally by the arguments (left to right).
Note that this ordering considers EQUAL objects to be unordered.
If you want a total ordering that only considers EQ objects unordered then
it's a lot harder.