HASH-TABLE-PACKAGE-GENERATORSMAPHASH 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.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, but which are not exported; :EXTERNAL means the symbols that are present and exported; :INHERITED means the symbols that are exported by used packages and that are not shadowed. When more than one argument is supplied for <symbol-types>, then a symbol is returned if its accessibility matches any one of the <symbol-types> specified. 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 accessibility 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 one the indicated packages)
3. the accessibility type for that symbol; i.e. one of
:INTERNAL, :EXTERNAL, or :INHERITED
4. the package from which the symbol has been accessed.
After all symbols have been returned [by successive invocations of
(<next-fn>)], then only one value is returned, namely NIL.
The fourth return value is one of the packages present or named in the
<package-list> argument. The meaning of the second, third, and fourth
values is that the returned symbol is accessible in the returned package
in the way indicated by the second return value:
:INTERNAL ==> present, and not exported,
:EXTERNAL ==> present, and exported,
:INHERITED ==> not present (thus not shadowed) but inherited
from some used package.
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.
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 (possibly more than once):
(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))))))
The following could be an acceptable definition of the function MAPHASH, implemented by WITH-HASH-TABLE-ITERATOR"
(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)))))
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".
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.
The following macro definitions show how Common Lisp's DO-mumble-SYMBOLS macros could have been defined in terms of WITH-PACKAGE-ITERATOR. They are intended as illustrative examples, not as new specifications of those built-in Common Lisp facilities. [PARSE-BODY is as defined in Guy Steele's "Clarifications" of 6-Dec-85.]
(defmacro do-symbols ((var &optional (package `*package*) result-form) &body body &environment env) (multiple-value-bind (body decls docstring) (parse-body body env) `(with-package-iterator (next-symbol (list ,package) :internal :external :inherited) (let (more? ,var) ,@decls (loop (unless (multiple-value-setq (more? ,var) (next-symbol)) (setq ,var nil) (return ,result-form)) ,@body)))))
(defmacro do-external-symbols ((var &optional (package `*package*) result-form) &body body &environment env) (multiple-value-bind (body decls docstring) (parse-body body env) `(with-package-iterator (next-symbol (list ,package) :external) (let (more? ,var) ,@decls (loop (unless (multiple-value-setq (more? ,var) (next-symbol)) (setq ,var nil) (return ,result-form)) ,@body)))))
(defmacro do-all-symbols ((var &optional result-form) &body body &environment env) (multiple-value-bind (body decls docstring) (parse-body body env) `(with-package-iterator (next-symbol (list-all-packages) :internal :external) (let (more? ,var) ,@decls (loop (unless (multiple-value-setq (more? ,var) (next-symbol)) (setq ,var nil) (return ,result-form)) ,@body)))))
------- "Why not define <next-fn> as a local function as if defined by FLET rather than a macro as if defined by MACROLET? "
"a macro gave more scope to the implememtation to optimize without losing anything essential in these circumstances."