Issue: HASH-TABLE-PACKAGE-GENERATORS

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

Issue:         HASH-TABLE-PACKAGE-GENERATORS

References:    

Category:      ADDITION

Edit history:  Version 1, 23-May-88 JonL


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.


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:

    MAKE-HASH-TABLE-ITERATION-GENERATOR (hash-table)		[Function]
      ;; Returns a function of no arguments, which iterates over 
      ;;  the entries of the argument 'hash-table' and returns three 
      ;;  values at each at each iteration:
      ;;    1. a boolean to indicate no more entries (T says "there are more")
      ;;    2. the value item (of a <key, value> pair)
      ;;    3. the key item (of a <key, value> pair)
      ;; If there are no more entries in the hash-table, then only one value
      ;;  is returned, namely NIL.


    MAKE-PACKAGE-ITERATION-GENERATOR (package iteration-type)	[Function]
      ;; First argument is a package (or, a string or symbol 
      ;;  coercible to a package); second argument is a symbol among:
      ;;      do-symbols
      ;;      do-all-symbols
      ;;      do-external-symbols
      ;;      do-internal-symbols
      ;;      do-present-symbols		{either :internal or :external}
      ;; Returns a function of no arguments, which iterates over the symbols 
      ;;  in the argument 'package' and returns three values at each iteration:
      ;;    1. a boolean to indicate no more entries (T says "there are more")
      ;;    2. a symbol (available in the indicated package)
      ;;    3. the availability type for that symbol, (i.e. one of
      ;;       :internal, :external, or :inherited).
      ;; If there are no more symbols available from the package, then only one
      ;;  value is returned, namely NIL.



Test Case: 

The following function should return T on any hash-table:

(defun test-ht-generator-test (hash-table)
  (let ((all-entries '())
	(generated-entries '())
	(generator-fn (make-hash-table-iteration-generator hash-table))
	(unique (list nil)))
    (maphash #'(lambda (key value) (push (list key value) all-entries))
	     hash-table)
    (loop 	;note -- this is the "trivial" LOOP of CLtL p121
      (multiple-value-bind (more? value key) (funcall 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:

(defun test-pk-generator-test (package)
  (unless (packagep package)
    (setq package (find-package package)))
  (let ((all-entries '())
	(generated-entries '())
	(generator-fn (make-package-iteration-generator package 'do-symbols)))
    (do-symbols (x package) 
      (multiple-value-bind (symbol accessibility) 
		(find-symbol (symbol-name x) package)
	(push (list symbol accessibility) all-entries)))
    (loop 	;note -- this is the "trivial" LOOP of CLtL p121
      (multiple-value-bind (more? symbol accessibility) (funcall 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 (null (set-difference all-entries generated-entries
				       :test #'equal))
		 (null (set-difference generated-entries all-entries
				       :test #'equal)))
     (error "Generated entries and Do-Symbols entries don't correspond"))
    t))

       

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.



Current Practice:

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


Cost to Implementors:

Moderate.  Possibly a couple days work for an implementation that
has to start completely afresh.


Cost to Users:

None.


Benefits:

Will provide a more primitive root 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:

This proposal was initiated by Dick Waters, who has ported his OSS iteration
scheme to many Common Lisps; it was who noted that only the lack of reasonable
generator functions prevented all three of the currently discussed iteration
schemes from being truly portable extensions.

The Iteration Subcommittee supports this proposal.