Issue: HASH-TABLE-PACKAGE-GENERATORS

[Jon L White <edsel!jonl@labrea.stanford.edu>]

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 
broader utility?  


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
you think?


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 --