[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Issue: HASH-TABLE-PACKAGE-GENERATORS (version 4)

Final nits:
    <KMP@STONY-BROOK.SCRC.Symbolics.COM>: Sun, 9 Oct 88 02:45 EDT
    <barmar@Think.COM> Thu, 13 Oct 88 10:23 EDT
    <jonl@LUCID.COM> Mon, 17 Oct 88 16:45:13 PDT
and dded discussion about syntax of with-package-iterator.

-- JonL --

!

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)

Problem description:

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


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>                         [Macro]
                            &key external internal inherited)
                           &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 the items, one by one, from the package which is obtained 
    by evaluating <package> [only once].  

    An invocation (<next-fn>) returns three values as follows:
      ;;    1. a boolean indicating whether an entry is returned (T says yes)
      ;;    2. a symbol (available in the indicated package)
      ;;    3. the availability type for that symbol; i.e. one of
      ;;       :INTERNAL, :EXTERNAL, or :INHERITED,  or unspecified for 
      ;;       the DO-ALL-SYMBOLS case.
      ;; After all entries have been returned [by successive invocations of
      ;;   (<next-fn>)], then only one value is returned, namely NIL.

    The keyword arguments are flags indicating which kinds of symbols are 
    wanted; they are not "evaluated".  The following combinations are 
    recognized:
    +----------+----------+-------------+-------------------------------------
    | external | internal | inherited   |   CLtL macro equivalent 
    +----------+----------+-------------+-------------------------------------
    |    T     |    T     |     T       |    DO-SYMBOLS
    |    T     |    T     |    NIL      |    DO-PRESENT-SYMBOLS      [not CLtL]
    |    T     |   NIL    |     T       |    <none> 		  [unspecified]
    |    T     |   NIL    |    NIL      |    DO-EXTERNAL-SYMBOLS
    |   NIL    |    T     |     T       |    <none> 		  [unspecified]
    |   NIL    |    T     |    NIL      |    DO-INTERNAL-SYMBOLS     [not CLtL]
    |   NIL    |   NIL    |     T       |    DO-INHERITED-SYMBOLS    [not CLtL]
    |   NIL    |   NIL    |    NIL      |    DO-ALL-SYMBOLS
    +----------+----------+-------------+--------------------------------------
    In the default case, equivalent to DO-ALL-SYMBOLS, the value of the
    <package> argument is ignored.  The lines marked "[not CLtL]" mention
    package iterator macros found in some implementations of Common Lisp;
    their meaning should be self-explanatory.  The lines marked "unspecified" 
    may be extended by an implementation to have the implied meaning.

    In accord with common practice, the options that include any "inherited"
    symbols, and the DO-ALL-SYMBOLS option, are allowed to present the 
    same symbol multiple times.  This is because a symbol may be "inherited"
    from several different used packages; and a symbol may be present in 
    several different packages (in the DO-ALL-SYMBOLS case).  See the 
    proposal DO-SYMBOLS-DUPLICATES:ALLOWED.

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).


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 t :external t :inherited t)
      (loop 	
	;;Note -- this is the "trivial" LOOP of CLtL p121
	(multiple-value-bind (more? symbol 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 functions prints out every interned symbol:

(defun print-all-symbols () 
  (with-package-iterator (next-symbol nil)
    (loop
      ;;Note -- this is the "trivial" LOOP of CLtL p121
      (multiple-value-bind (more? symbol) (next-symbol)
	(if more? 
           (print symbol)
	   (return))))))


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.

There has been some concern that the syntax of keyword arguments to 
WITH-PACKAGE-ITERATOR may be problematical; especially, it seems odd
that the <package> argument is a required argument, but is not used
at all in the case when the keyword arguments select a DO-ALL-SYMBOLS
meaning.  This is a constraint that isn't easy to express in the existing 
CL language: namely, that the <package> argument is required if and only
if any of the keyword arguments are supplied as non-nil.  One way out of 
this bind is to let the <package> argument be optional, defaulting to the
symbol *PACKAGE*.  Then the example above for 'print-all-symbols' could
be written as:
  (with-package-iterator (next-symbol) ...)
instead of:
  (with-package-iterator (next-symbol nil) ...)
or, instead of:
  (with-package-iterator 
        (next-symbol nil :external nil :internal nil :inherited nil )
     ...)