[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Common LISP omissions: Locatives
Date: Wed, 10 Jun 87 10:53:14 EDT
From: dml@nadc.arpa (D. Loewenstern)
We have been using Common LISP and have noticed two
important omissions in the language.
1) Locatives ("LOCF" as found in ZetaLISP).
2) A COLLECT macro.
[I won't address COLLECT in this particular message]
A primary reason for locatives would be to create your own
"hash-on-eq" functions. Common LISP provides SXHASH which
hashes on equal. A serious problem occurs if the keys are
circular objects.
Locatives have no relevance to hashing on EQ. The Zetalisp feature you
are thinking of is %POINTER, not LOCF. %POINTER is a function that
returns a number which is the address of its argument. LOCF is a macro
that returns a locative that designates the cell that is designated by
the generalized variable (in the SETF sense) that is LOCF's first
subform. The possible operations on locatives are getting the contents
of the cell, changing the contents of the cell, making the cell
"unbound", checking whether the cell is "unbound", comparing two
locatives for equality, and recovering the object that contains the cell.
It's pretty easy to make your own variant of SXHASH that detects
circularities, although it's bound to be a little slower. I believe
the IBM VM/LISP people published a paper on this a while back.
Date: 10 June 1987, 15:13:19 EDT
From: Timothy Daly <DALY@ibm.com>
We also have felt the need to do hashing-on-eq type of operations.
That is, we would like to be able to hash a pair consisting
of (address of left subtree . address of right subtree).
Unfortunately, SXHASH will walk both subtrees which is much
too expensive. We could think of no portable way to implement
this in common lisp. Since the language gives us no way to
implement this it does not seem that locatives are a frill.
There -is- no portable way to implement hashing-on-eq efficiently,
because it is inherently dependent on the implementation details of the
system's garbage collector. For example, in many systems a garbage
collection changes the numerical value of the addresses of objects. In
these systems, anything that depends on the numerical values of
addresses of objects has to be recomputed after a garbage collection.
It's difficult to come up with a portable and efficient way of doing
that, particularly in systems with multiple levels of garbage
collection, which several systems do in somewhat different ways. It's
even harder to do it in a way that doesn't impose an efficiency burden
on systems where garbage collection does not change the numerical values
of object addresses. This is why Common Lisp did not attempt to provide
a hash-on-eq primitive, that is, a function that returns a number given
an object, without looking at the contents of the object, and always
returns the same number for the same object.
There is a portable -inefficient- way to implement hashing-on-eq, which
is to use a hash table :test #'eq to remember what hash code you have
assigned to each object. I have actually used this. However, this is
usually too inefficient to be seriously considered.
Date: Wed, 10 Jun 1987 11:35 EDT
From: "Scott E. Fahlman" <Fahlman@C.CS.CMU.EDU>
We considered adding locatives early in the original design process, but
decided that they didn't make much sense except on machines with
hardware support for forwarding pointers.
Locatives have no relevance to forwarding pointers, nor do they have any
relevance to hardware support.
However, I agree that locatives should not be in Common Lisp. My reason
is that only some of the possible Lisp implementation techniques for
object representation permit the efficient implementation of locatives.
It is always possible to implement locatives, as T has demonstrated, but
it isn't always possible to implement them efficiently. It seems
inappropriate to design the language in a way that would rule out some
otherwise reasonable implementation techniques (BIBOP, for example).