Issue: HASH-TABLE-PACKAGE-GENERATORS

[David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>]

    Date: Tue, 24 May 88 01:14:08 PDT
    From: Jon L White <edsel!jonl@labrea.stanford.edu>

    Problem description:

    The Iteration subcommittee would like the several iteration proposals to be
    writeable in portable Common Lisp code.  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.

A laudable goal, but...

    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.

    ....
    Rationale:

    The particular way in which hash-tables and packages are represented
    need not standardized, or even exposed to the user.  Yet a simpler handle 
    on them is needed for the various iteration paradigms to be written in 
    portable code.  In fact, after these generator-creator functions are put 
    into an implementation, then MAPHASH and DO-<mumble>-SYMBOLS are trivial 
    usages of them; but no _efficient_ use of these current primitives will 
    provide generator functions.

You haven't brought out the major reason for using a generator function,
which is so that multiple iterations can be performed in parallel.  Many
of the iteration proposals, including LOOP and OSS, allow a programmer to
specify an iteration that iterates simultaneously over the elements of
a hash table and a range of integers, or even over the elements of two
hash tables.  Making the advance-to-next-state primitive available is
necessary in order to be able to call this primitive twice on two different
hash tables; no nesting of calls to MAPHASH can perform such a simultaneous
iteration.

    Current Practice:

    Both Symbolics and Lucid already have similar generators in their
    own implementations of LOOP. 

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
whole thing in a macro, which expands into a generic function invocation
with two arguments:  the hash table, and a closure of the body of the
iteration.  There is no need for a standard function to create the
generator, since it is simply passed to the body as an argument.  Note:
the body closure is called once, and iterates inside itself; it is not
called repeatedly, the way the functional argument to maphash is.

This is for hash-tables, but packages can be treated similarly.

Here's a relevant code extract:

;;; table must be a hash table.
;;; generator-var is bound to a generator function, which takes no arguments.
;;; Each time the generator function is called, it returns the next entry of the
;;; hash table, expressed as three values: the value, the key, and a flag.
;;; The flag is nil if the table has been exhausted, otherwise it is the
;;; next generator function to use (in all implemented cases, the generator
;;; function remains constant, but this provides the flexibility to let it change).
;;; When the flag is nil, the first two values are meaningless.
;;; The values returned by with-table-elements are the values returned by the body.
(defmacro with-table-elements ((table generator-var) &body body)
  `(with-table-elements-1 ,table #'(lambda (,generator-var) ,@body)))

(defgeneric with-table-elements-1 (table function)
  (declare (downward-funarg function)))

I have no objection to sending you more of the code if you want to see it,
but I doubt that it would be illuminating.