Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ncar!ames!think!barmar
From: barmar@think.COM (Barry Margolin)
Newsgroups: comp.lang.lisp
Subject: Re: Total ordering for Lisp objects ?
Message-ID: <29267@news.Think.COM>
Date: 11 Sep 89 22:32:50 GMT
References: <5896@lifia.imag.fr> <865@skye.ed.ac.uk>
Sender: news@Think.COM
Organization: Thinking Machines Corporation, Cambridge MA, USA
Lines: 41

In article <865@skye.ed.ac.uk> jeff@aiai.uucp (Jeff Dalton) writes:
>  Instead, it would have
>to be something like what happens in Prolog, where the ordering
>is defined more or less as follows:
...
>   Then terms, first by arity, then by functor, and
>     finally by the arguments (left to right).

Terms are the Prolog objects analogous to Lisp lists, structures,
arrays, etc. (i.e. all structured objects).  There's one big
difference, though -- Prolog terms are immutable (they sometimes
appear to be modified when atoms are unified, but they aren't).  In
Lisp, the total ordering should not be affected by operations such as
RPLACA.

One way to define a total ordering on Lisp objects is to simply assign
them unique IDs as you compare them.

(defvar *object-id-table* (make-hash-table :test #'eql))
(defvar *object-id-number* 0)

(defun get-object-id (object)
  (or (gethash object *object-id-table*)
      (setf (gethash object *object-id-table*) (incf *object-id-number*))))

(defun object-< (object1 object2)
  (< (get-object-id object1) (get-object-id object2)))

A couple of years ago there was discussion on the COMMON-LISP mailing
list about "soft" hash tables; these are hash tables that don't
prevent their keys from being GCed (i.e. if an object is ONLY
referenced as the key in some associations in soft hash tables, it is
considered garbage).  The above is a perfect application for such
things.  (Note: soft hash tables are not in the Common Lisp standard,
although several CL implementations have them as an extension).

Barry Margolin
Thinking Machines Corp.

barmar@think.com
{uunet,harvard}!think!barmar