[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Issue: HASH-TABLE-PACKAGE-GENERATORS (version 5)
- To: cl-cleanup@sail.stanford.edu
- Subject: Issue: HASH-TABLE-PACKAGE-GENERATORS (version 5)
- From: David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>
- Date: Tue, 22 Nov 88 19:27 EST
- References: <8811101832.AA05895@bhopal>
I have updated this according to suggestions from JonL and MLY. I
elaborated on the description of <package-list> with more detail than
was in MLY's suggestion. I also added examples and fixed the typo in
the discussion of package iteration and one or two other typos and
misspellings. I'm happy with this version if everyone else is.
!
Issue: HASH-TABLE-PACKAGE-GENERATORS
References: Issue: DO-SYMBOLS-DUPLICATES
Category: ADDITION
Edit history: Version 1, 23-May-88 JonL
Version 2, 6-Oct-88 JonL (convert to "with" scoping).
Version 3, 7-Oct-88 JonL (mly's syntax for package iterator)
Version 4, 8-Nov-88 JonL (fix example; clarify some nits)
Version 5, 22-Nov-88 Moon (improve syntax for package iterator,
add examples, fix typos)
Problem description:
The Iteration subcommittee would like the several iteration proposals to be
writable in portable Common Lisp code. Unfortunately, the only complete
access to hash-tables and packages is through MAPHASH and DO-SYMBOLS (and
DO-EXTERNAL-SYMBOLS and DO-ALL-SYMBOLS); none of these existing primitives
is satisfactory for building complex iteration clauses. In particular,
these primitives are fully packaged and do not allow control over the
individual operations of starting the iteration, stopping the iteration,
and advancing to the next step of the iteration.
Proposal (HASH-TABLE-PACKAGE-GENERATORS:ADD-WITH-WRAPPER)
Add two new macros WITH-HASH-TABLE-ITERATOR and WITH-PACKAGE-ITERATOR
to the language as follows:
WITH-HASH-TABLE-ITERATOR ((<next-fn> <hash-table>) &body body) [Macro]
Within the lexical scope of 'body', the name <next-fn> is defined
via MACROLET such that successive invocations of (<next-fn>) will
return the items, one by one, from the hash-table which is obtained
by evaluating <hash-table> only once.
An invocation (<next-fn>) returns three values as follows:
;; 1. a boolean indicating whether an entry is returned (T says yes)
;; 2. the key item (of a <key, value> pair)
;; 3. the value item (of a <key, value> pair)
;; After all entries have been returned [by successive invocations of
;; (<next-fn>)], then only one value is returned, namely NIL.
WITH-PACKAGE-ITERATOR ((<next-fn> <package-list> [Macro]
&rest <symbol-types>)
&body body)
Within the lexical scope of 'body', the name <next-fn> is defined
via MACROLET such that successive invocations of (<next-fn>) will
return symbols, one by one, from the packages that are elements
of the list which is obtained by evaluating <package-list> only once.
Each element of <package-list> can be a package or the name of a
package.
The order of symbols returned does not necessarily reflect the order
of packages in <package-list>. When <package-list> has more than
one element, it is unspecified whether duplicate symbols are
returned once or more than once. Even when <package-list> has only
one element, it is unspecified whether symbols inherited from
multiple packages are returned more than once. See the proposal
DO-SYMBOLS-DUPLICATES:ALLOWED.
As a convenience, the value of <package-list> can be a package or
the name of a package; this is equivalent to a list of one element.
An argument of NIL is treated as an empty list of packages.
The <symbol-types> subform consists of one or more symbols from the
set {:INTERNAL, :EXTERNAL, :INHERITED}. Their order does not
matter. The <symbol-types> subform is not evaluated. This controls
which symbols accessible in a package are returned.
:INTERNAL means the symbols that are present in the package and
not exported.
:EXTERNAL means the symbols that are exported.
:INHERITED means the symbols that are exported by used packages and
not shadowed.
If more than one <symbol-type> is specified, all symbols that
satisfy at least one of the <symbol-types> are returned.
WITH-PACKAGE-ITERATOR signals an error if no <symbol-types> are
specified or if a <symbol-type> not recognized by the implementation
is specified. Implementations are permitted to extend this syntax
by recognizing additional symbol types.
An invocation (<next-fn>) returns four values as follows:
;; 1. a boolean indicating whether a symbol is returned (T says yes)
;; 2. a symbol (accessible in the indicated package)
;; 3. a package (in which the symbol is accessible)
;; 4. the accessibility type for that symbol; i.e. one of
;; :INTERNAL, :EXTERNAL, or :INHERITED
;; After all symbols have been returned [by successive invocations of
;; (<next-fn>)], then only one value is returned, namely NIL.
It is unspecified what happens if any of the implicit interior state
of an iteration is returned outside the dynamic extent of the WITH-...
form (such as by returning some closure over the invocation form).
Any number of invocations of with-hash-table-iterator and
with-package-iterator can be nested, and the body of the innermost one
can invoke all of the MACROLET'ed macros, provided all those macros
have distinct names.
Test-case:
The following function should return T on any hash-table, and signal
an error if the usage of 'with-hash-table-iterator' doesn't agree
with the corresponding usage of 'maphash'.
(defun test-hash-table-iterator (hash-table)
(let ((all-entries '())
(generated-entries '())
(unique (list nil)))
(maphash #'(lambda (key value) (push (list key value) all-entries))
hash-table)
(with-hash-table-iterator (generator-fn hash-table)
(loop
;;Note -- this is the "trivial" LOOP of CLtL p121
(multiple-value-bind (more? key value) (generator-fn)
(unless more? (return))
(unless (eql value (gethash key hash-table unique))
(error "Key ~S not found for value ~S" key value))
(push (list key value) generated-entries))))
(unless (= (length all-entries)
(length generated-entries)
(length (union all-entries generated-entries :test #'equal)))
(error "Generated entries and Maphash entries don't correspond"))
t))
The following function should return T on any package, and signal
an error if the usage of 'with-package-iterator' doesn't agree
with the corresponding usage of 'do-symbols'.
(defun test-package-iterator (package)
(unless (packagep package)
(setq package (find-package package)))
(let ((all-entries '())
(generated-entries '()))
(do-symbols (x package)
(multiple-value-bind (symbol accessibility)
(find-symbol (symbol-name x) package)
(push (list symbol accessibility) all-entries)))
(with-package-iterator (generator-fn package
:internal :external :inherited)
(loop
;;Note -- this is the "trivial" LOOP of CLtL p121
(multiple-value-bind (more? symbol pkg accessibility)
(generator-fn)
(unless more? (return))
(let ((l (multiple-value-list (find-symbol (symbol-name symbol)
package))))
(unless (equal l (list symbol accessibility))
(error "Symbol ~S not found as ~S in package ~A [~S]"
symbol accessibility (package-name package) l))
(push l generated-entries)))))
(unless (and (subsetp all-entries generated-entries :test #'equal)
(subsetp generated-entries all-entries :test #'equal))
(error "Generated entries and Do-Symbols entries don't correspond"))
t))
The following function prints out every interned symbol:
(defun print-all-symbols ()
(with-package-iterator (next-symbol (list-all-packages)
:internal :external)
(loop
;;Note -- this is the "trivial" LOOP of CLtL p121
(multiple-value-bind (more? symbol) (next-symbol)
(if more?
(print symbol)
(return))))))
Examples:
The following macro definitions show how certain builtin Common Lisp
macros and functions could have been defined in terms of the proposed
primitives. They are intended as illustrative examples, not as new
specifications of those builtin Common Lisp facilities.
(defun maphash (function hash-table)
(with-hash-table-iterator (next-entry hash-table)
(loop (multiple-value-bind (more key value) (next-entry)
(unless more (return nil))
(funcall function key value)))))
(defmacro do-symbols ((var &optional (package `*package*) result-form)
&body body)
`(with-package-iterator (next-symbol (list ,package)
:internal :external :inherited)
(loop (multiple-value-bind (more ,var) (next-symbol)
(cond (more ,@body)
(t (return ,result-form)))))))
(defmacro do-all-symbols ((var &optional result-form) &body body)
`(with-package-iterator (next-symbol (list-all-packages)
:internal :external)
(loop (multiple-value-bind (more ,var) (next-symbol)
(cond (more ,@body)
(t (return ,result-form)))))))
(defmacro do-external-symbols ((var &optional (package `*package*) result-form)
&body body)
`(with-package-iterator (next-symbol (list ,package)
:external)
(loop (multiple-value-bind (more ,var) (next-symbol)
(cond (more ,@body)
(t (return ,result-form)))))))
Rationale:
The particular way in which hash-tables and packages are represented
need not be 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 iterator macros are put into an
implementation, then MAPHASH and DO-<mumble>-SYMBOLS are trivial usages
of them; but no _efficient_ use of the current primitives will provide
the effect of the new macros, namely a form that _returns_ the elements
of a table "one by one".
Current Practice:
Nobody does it this way, but both Symbolics and Lucid are not far off.
Cost to Implementors:
Moderate. Possibly a couple day's to a week's work for an implementation
that has to start completely afresh. Something like this is already being
done by the standard package macros [CLtL, p187].
Cost to Users:
None.
Benefits:
Will provide a more basic primitive for iterating over hash-tables and
packages; will permit new iteration paradigms to be written in portable code.
Aesthetics:
All other things being equal, it is better to have more general primitives
than less general ones.
Discussion:
The Iteration Subcommittee supports this proposal (or, "used to" --
JonL 6-Oct-88).
One must be careful not to assume that the invocation (<next-fn>) is a
"generator" function call -- since <next-fn> is MACROLET'd in an
implementation dependent way, it could even turn into a special form like
(if something
(values nil)
(yet-another-function-call))
The scoping called for herein may not be quite so useful to the "generators"
style proposals; in particular they offer an interface wherein one may
create a "generator" function of indefinite extent that returns, one-by-one,
the elements of the table. The constrained scoping implicit in these
WITH-... macros is not so much for any kind of optimization, but rather
for coordination of such hash-table "locking" as may occur in multi-
processing implementations like Symbolics. Nevertheless, Dick Waters
thinks these macros should be put in anyway, since it clearly is a
requirement for a portable LOOP, and can be use in a limited context
(i.e., not "indefinite scope") for portable versions of ITERATE and OSS.
Of course, if an implementation _can_ support an indefinite extent for
a "generator" object returned out of the iterator forms, it is allowed
to do so by this proposal.