phs@lifia.imag.fr (Philippe Schnoebelen) (09/09/89)
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 ]
jeff@aiai.uucp (Jeff Dalton) (09/11/89)
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
donc@vaxa.isi.edu (Don Cohen) (09/12/89)
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.
barmar@think.COM (Barry Margolin) (09/12/89)
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
ok@cs.mu.oz.au (Richard O'Keefe) (09/12/89)
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...)
morrison@grads.cs.ubc.ca (Rick Morrison) (09/13/89)
In article <2084@munnari.oz.au> ok@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| morrison@cs.ubc.ca Univ. of British Columbia| morrison%ubc.csnet@csnet-relay.arpa Vancouver, B.C. V6T 1W5 | morrison@ubc.csnet (ubc-csgrads=128.189.97.20) (604) 228-4327
barmar@think.COM (Barry Margolin) (09/13/89)
In article <4932@ubc-cs.UUCP> morrison@grads.cs.ubc.ca (Rick Morrison) writes: >In article <2084@munnari.oz.au> ok@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. barmar@think.com {uunet,harvard}!think!barmar
ok@cs.mu.oz.au (Richard O'Keefe) (09/13/89)
In article <4932@ubc-cs.UUCP>, morrison@grads.cs.ubc.ca (Rick Morrison) writes: > In article <2084@munnari.oz.au> ok@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.
jeff@aiai.uucp (Jeff Dalton) (09/13/89)
In article <2084@munnari.oz.au> ok@cs.mu.oz.au (Richard O'Keefe) writes: >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. 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
jeff@aiai.uucp (Jeff Dalton) (09/13/89)
In article <29362@news.Think.COM> barmar@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
andyt@visix.UUCP (Andy Turk) (09/14/89)
In article <29362@news.Think.COM>, barmar@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. > > barmar@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 visix!andyt@uunet.uu.net "I don't know what happened to my face." -- Dizzy Gillespie
news@venera.isi.edu (News Service) (09/14/89)
------- My initial response pointed out that comparisons based on structure were fine if you consider your "objects" to be defined by EQUAL. In that case a destructive change must be regarded as changing one object into another and it is quite reasonable that its position in a total ordering should change. If you want to consider "objects" defined by EQ then of course such schemes don't work, since they are sensitive to destructive operations while EQ-ness is not. In the same way that both EQ and EQUAL are useful, both types of orderings are useful (as well as others corresponding to other notions of equivalence). In either case, it is quite possible to program your own total ordering function, though there are various expenses to consider. In *SOME* implementations of lisp the EQ ordering is trivial (namely address comparison). My initial response also pointed out that this "benefit" has to be weighed against some others with which it is incompatible, e.g., garbage collectors that move objects to improve locality of reference. I hope this is all that needs to be said on the subject. From: donc@vaxa.isi.edu (Don Cohen) Path: vaxa.isi.edu!donc
ok@cs.mu.oz.au (Richard O'Keefe) (09/14/89)
In article <881@skye.ed.ac.uk>, jeff@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.