From: Philippe Schnoebelen
Subject: Total ordering for Lisp objects ?
Date:
Message-ID: <5896@lifia.imag.fr>
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 ?"
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 ?
Are there other places in Lisp where the stability requirement forbids one
to use advanced implementation techniques ? Which ones ?
Are there any languages (or specific implementations) where such an
ordering relation exists ? What are the consequences ?
Thanks,
--Philippe
[ Followups are to comp.lang.lisp ]
From: Jeff Dalton
Subject: Re: Total ordering for Lisp objects ?
Date:
Message-ID: <865@skye.ed.ac.uk>
In article <····@lifia.imag.fr> ···@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: ········@uk.ac.ed
AI Applications Institute, ARPA: ·················@nsfnet-relay.ac.uk
Edinburgh University. UUCP: ...!ukc!ed.ac.uk!J.Dalton
From: Don Cohen
Subject: Re: Total ordering for Lisp objects ?
Date:
Message-ID: <9582@venera.isi.edu>
In article <····@lifia.imag.fr> ···@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 <···@skye.ed.ac.uk> ····@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.
From: Barry Margolin
Subject: Re: Total ordering for Lisp objects ?
Date:
Message-ID: <29267@news.Think.COM>
In article <···@skye.ed.ac.uk> ····@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.
······@think.com
{uunet,harvard}!think!barmar
From: Richard O'Keefe
Subject: Re: Total ordering for Lisp objects ?
Date:
Message-ID: <2084@munnari.oz.au>
In article <····@lifia.imag.fr> ···@lifia.imag.fr (Philippe Schnoebelen) writes:
> "Would it be possible to add a total ordering predicate on Lisp
> objects ?"
In article <···@skye.ed.ac.uk>, ····@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...)
From: Rick Morrison
Subject: Re: Total ordering for Lisp objects ?
Date:
Message-ID: <4932@ubc-cs.UUCP>
In article <····@munnari.oz.au> ··@cs.mu.oz.au (Richard O'Keefe) writes:
>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...)
I don't get. How does this argue against defining a total ordering
on LISP objects? Admittedly the above example violates referential
transparency, but this is a result of the use of destructive assignment.
-----------------------------
Rick Morrison | {alberta,uw-beaver,uunet}!ubc-cs!morrison
Dept. of Computer Science| ········@cs.ubc.ca
Univ. of British Columbia| ··················@csnet-relay.arpa
Vancouver, B.C. V6T 1W5 | ········@ubc.csnet (ubc-csgrads=128.189.97.20)
(604) 228-4327
From: Barry Margolin
Subject: Re: Total ordering for Lisp objects ?
Date:
Message-ID: <29362@news.Think.COM>
In article <····@ubc-cs.UUCP> ········@grads.cs.ubc.ca (Rick Morrison) writes:
>In article <····@munnari.oz.au> ··@cs.mu.oz.au (Richard O'Keefe) writes:
>>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...)
>I don't get. How does this argue against defining a total ordering
>on LISP objects? Admittedly the above example violates referential
>transparency, but this is a result of the use of destructive assignment.
It doesn't argue against defining a total ordering, but it does argue
against copying Prolog's algorithm, which specifies that the ordering
of two structured objects is a function of the ordering of their
contents. Prolog has no destructive assignment, so it doesn't suffer
such problems.
A recursive ordering relation also loses when circular structures are
involved. Again, Prolog doesn't have these (destructive assignment is
necessary to create them).
Barry Margolin
Thinking Machines Corp.
······@think.com
{uunet,harvard}!think!barmar
From: Jeff Dalton
Subject: Re: Total ordering for Lisp objects ?
Date:
Message-ID: <881@skye.ed.ac.uk>
In article <·····@news.Think.COM> ······@think.COM (Barry Margolin) writes:
>Prolog has no destructive assignment, so it doesn't suffer
>such problems.
But Prolog has something very like destructive assignment, namely
variable instantiation. For example, you might have a structure
that contains an uninstantiated variable, and then its position
in the total ordering will change after you instantiate the variable.
-- Jeff
From: Richard O'Keefe
Subject: Re: Total ordering for Lisp objects ?
Date:
Message-ID: <2101@munnari.oz.au>
In article <···@skye.ed.ac.uk>, ····@aiai.uucp (Jeff Dalton) writes:
> But Prolog has something very like destructive assignment, namely
> variable instantiation. For example, you might have a structure
> that contains an uninstantiated variable, and then its position
> in the total ordering will change after you instantiate the variable.
In NU-Prolog, termCompare(Order, Term_1, Term_2) "delays until Term_1
and Term_2 are instantiated enough for comparison to be made under the
standard ordering, that is, until any further instantiation would not
change the ordering already determined." (NU-Prolog 1.3 manual, TR 86/10.)
Enough already. Back to the regular "why doesn't the SNARK package work
in BELLMAN Lisp on a BEAVER-98" topic.
From: Andy Turk
Subject: Re: Total ordering for Lisp objects ?
Date:
Message-ID: <217@visix.UUCP>
In article <·····@news.Think.COM>, ······@think.COM (Barry Margolin) writes:
> It doesn't argue against defining a total ordering, but it does argue
> against copying Prolog's algorithm, which specifies that the ordering
> of two structured objects is a function of the ordering of their
> contents. Prolog has no destructive assignment, so it doesn't suffer
> such problems.
> Barry Margolin
> Thinking Machines Corp.
>
> ······@think.com
> {uunet,harvard}!think!barmar
In the case of Prolog, you don't need destructive assignment to screw up
an enduring term order. The problem is that of unbound variables. Unbound
variables CAN be modified ONCE. If you sort two terms that have unbound vars
in them, then if the order cannot be established from the ground parts of the
terms, there should be no order between the two terms. However, most
Prologs will actually use the implementation's representation of unbound
variables (pointers) to come up with an ordering. Obviously, this order can
change if any of the variables used to order the terms are bound at a later
time.
--
-------------------------------------------------------------------------
Andrew K. Turk ···········@uunet.uu.net
"I don't know what happened to my face." -- Dizzy Gillespie
From: Richard O'Keefe
Subject: Re: Total ordering for Lisp objects ?
Date:
Message-ID: <2092@munnari.oz.au>
In article <····@ubc-cs.UUCP>, ········@grads.cs.ubc.ca (Rick Morrison) writes:
> In article <····@munnari.oz.au> ··@cs.mu.oz.au (Richard O'Keefe) writes:
> >But consider [code deleted]
> >The ordering of a and b has changed although a and b still point to the
***********************************************************************
> >"same" objects.
***************
> I don't get. How does this argue against defining a total ordering
> on LISP objects? Admittedly the above example violates referential
> transparency, but this is a result of the use of destructive assignment.
It has nothing to do with referential transparency. The point is that
because Lisp has destructive assignment, it is not possible to define an
enduring total order on Lisp objects *based on their shape*. My posting
was a follow-up to Jeff Dalton's where he was talking about a possible
total ordering based on the type and elements of objects (their shapes),
like the ordering used in Prolog. My point is that a Lisp ordering *can't*
work _that_ way because the elements of objects can change.
From: Jeff Dalton
Subject: Re: Total ordering for Lisp objects ?
Date:
Message-ID: <880@skye.ed.ac.uk>
In article <····@munnari.oz.au> ··@cs.mu.oz.au (Richard O'Keefe) writes:
>In article <···@skye.ed.ac.uk>, ····@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.
A couple of people have now pointed out that, in Lisp, the order of
objects might change if the objects were modified. Well, that's true,
but similar problems occur with equal (equal objects become unequal)
and with equal hash tables (an object might hash differently after a
change). So this problem does not mean that such an order relation
would be useless or impossible any more than equal hash tables are
useless or impossible.
For and eql-like ordering, I'd be happy with Barry Margolin's
suggestion of an object-id table based on a "weak" hash table.
-- Jeff