Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!wuarchive!gem.mps.ohio-state.edu!ginosko!uunet!mcsun!ukc!edcastle!aiai!jeff
From: jeff@aiai.uucp (Jeff Dalton)
Newsgroups: comp.lang.lisp
Subject: Re: Total ordering for Lisp objects ?
Message-ID: <865@skye.ed.ac.uk>
Date: 11 Sep 89 15:01:37 GMT
References: <5896@lifia.imag.fr>
Sender: news@aiai.ed.ac.uk
Reply-To: jeff@aiai.uucp (Jeff Dalton)
Organization: AIAI, University of Edinburgh, Scotland
Lines: 50

In article <5896@lifia.imag.fr> phs@lifia.imag.fr (Philippe Schnoebelen) writes:
>After reading C. R. Eliot's note "Manipulating sets in Common Lisp" (very
>interesting, btw) in the last issue of Lisp Pointers, I have a question
>about Lisp implementations:
>
>	"Would it be possible to add a total ordering predicate on Lisp
>	objects ?"

As you may know, Prolog has such an ordering.  I think it would also
be useful in Lisp.  I brought up this possibility about a year ago on
the Common Lisp mailing list, though, and I don't remember all that
much enthusiasm for it.

For many kinds of objects (at least), it is possible to write a
comparison predicate in Lisp.  Of course, it couldn't be so simple
as just taking the address of the objects.  Instead, it would have
to be something like what happens in Prolog, where the ordering
is defined more or less as follows:

   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).

>Among others, the advantage is that representation of sets as ordered lists
>(or binary trees, ...) would be possible for any kind of data, not just
>(e.g.) numbers. I can see at least one difficulty and would like opinions
>about it. It stems from the requirement that:
>
>	During one Lisp session, two Lisp objects must always remain in the
>        same relative order. 
>
>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 ?

Probably not.

However, another possibility would be for Lisp to provide the efficient
sets rather than the lower-level tools that might be used to make them.
Then, if some reworking is needed after a garbage collection, the system
can do it automatically.  That's more or less what happens for hash tables.

Indeed, hash tables can be used to represent some kinds of sets efficiently.

Jeff Dalton,                      JANET: J.Dalton@uk.ac.ed             
AI Applications Institute,        ARPA:  J.Dalton%uk.ac.ed@nsfnet-relay.ac.uk
Edinburgh University.             UUCP:  ...!ukc!ed.ac.uk!J.Dalton