[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
- To: Moon@stony-brook.scrc.symbolics.com
- Subject: Issue: HASH-TABLE-PACKAGE-GENERATORS
- From: Jon L White <email@example.com>
- Date: Wed, 25 May 88 13:12:47 PDT
- Cc: firstname.lastname@example.org
- In-reply-to: David A. Moon's message of Tue, 24 May 88 12:06 EDT <19880524160601.7.MOON@EUPHRATES.SCRC.Symbolics.COM>
re: Proposal (HASH-TABLE-PACKAGE-GENERATORS:ADD-CREATOR-FUNCTIONS):
Add two new functions as follows, which will create upon demand a
"generator" for the table in question....
...this technique "can't" work, because of locking issues, especially in
systems that have a garbage collector that can change the hash codes of
objects. You need to be able to wrap something around the whole iteration,
not merely have a function that performs the next step in the iteration.
You are probably thinking of only one of the several ways to implement
EQ-type hash-tables. Lucid has a technique that guarantees iteration over
the contents which the table had at the time the iteration function is
created [this is almost always acceptable, since even maphash calls it "an
error" to alter the table while the iteration is in progress (except for
the trivial exception, which works in both cases)]. At worst, this technique
causes a copying of the hash-table upon a relocating garbage collection,
or when first making an entry that would otherwise be "locked-out". [Just
to clear up a point: Lucid's implementation will normally re-order "in place"
when necessary due to changing hash-codes, and do that only "lazily".]
Thus there is no absolute need to provide locking for iteration.
On the other hand, locking of global databases, for whatever purposes, is
a laudable goal. I still don't think it is required for iteration to work
in the same cases that it works in for MAPHASH. But if you think that
Symbolics' system will be compromised unless explicit interlocking is done
during hash-table or package iteration, then perhaps the necessary thing to
do is to provide context-independent locking mechanisms. Something like
the dynamically-scoped macro 'with-table-elements', but perhaps with a
re: You haven't brought out the major reason for using a generator function,
which is so that multiple iterations can be performed in parallel.
Well, I tried to say so in the following words:
Unfortunately, the only access to hash-tables and packages is through
MAPHASH and DO-SYMBOLS, neither of which is satisfactory for building
complex iteration clauses.
but it you'd like to see "complex iteration clauses" fleshed out in more
detail, then just adding the paragraph of your note would be fine, don't
re: I don't think you've looked at Symbolics' LOOP in a couple years. It
used to work the way you describe, but the way it works now is
different. It does have a generator function, but it also wraps the ...
Right, I had looked at version 6+ some time ago.
Incidentally, Lucid's implementation of packages uses the same hash-table
mechanism given to the Common-Lisp user, but with a private, undocumented
:type argument. At one time, SpiceLisp had a totally independent version
of hash-tables built into their package code. The locking issue on packages
is, to my way of thinking, much more critical than that for hash-tables in
general. But the more general solution is, of course, to provide locking
mechanisms for the hash-table implementation and let the package code use
those mechanisms where appropriate.
-- JonL --