[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
- To: Jon L White <email@example.com>
- Subject: Issue: HASH-TABLE-PACKAGE-GENERATORS
- From: David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>
- Date: Tue, 24 May 88 12:06 EDT
- Cc: cl-cleanup@SAIL.STANFORD.EDU
- In-reply-to: <8805240814.AA04704@bhopal.lucid.com>
Date: Tue, 24 May 88 01:14:08 PDT
From: Jon L White <firstname.lastname@example.org>
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...
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.
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
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.