Re: Scheme style auto-resizing hashtable (fwd)

[Jay Glascoe <jglascoe@jay.giss.nasa.gov>]

On Fri, 6 Nov 1998, Maciej Stachowiak wrote:

> 
> I'd like to see parameter signatures for these.
> 
> > constructors:
> > 
> >         make-dictionary
> >         make-dictionaryv
> >         make-dictionaryq
> > 
> > behavior modifiers:
> > 
> >         dictionary-enable! 
> >         dictionary-disable!
> >         dictionary-change-type!
> > 

think of "dictionaryv", "dictionaryq", and "dictionaryx" as "dictionary"
sub-types.  They all inherit directly from "dictionary" but over-ride the
equality predicate and hashing function.  BTW, I finally got the
"dictionaryx" type up and running, YES!  it looks like this

guile> (make-dictionaryx equal? hasher)

(#(dictionaryx 0 #t #t
   #<primitive-procedure equal?>
   #<primitive-procedure hasher>) .
 #(() () () ())) 

guile> (make-dictionaryx (lambda (key1 key2) (equal? key1 key2))
                         (lambda (key) (hasher key)))
(#(dictionaryx 0 #t #t #<procedure (x y)> #<procedure (x)>) .
 #(() () () ()))

I detract the "dictionary-change-type!" procedure.  Once a "dictionaryq"
always a "dictionaryq";  OO languages don't usually let you change an
objects class.

> Couldn't these all be encapsulated into a generic
> disctionary-set-parameter!, it seems annoying to have so much
> interface just to set a few tunable parameters.

I like it.  Right now, along with the 4 distinct dictionary types, I have
options "auto-shrink" and "store-hash".  So that's 4 distinct types and 4
possible option settings.  That yields a whopping 16 dictionaries, all of
which exhibit unique behaviors.  (yes, an infinite number if you count the
arguments to "make-dictionaryx").

My point: dictionary construction is as wide 
("make-dictinoary''/'v'/'q'/'x'")  as it is deep
("dictionary-enable/disable!").  I believe it's an efficient interface.  I
could go with something like "dictionary-toggle-option", but I think what
I have now is more Guile-ish.

> > the big three basic operations:
> > 
> >         dictionary-insert!
> >         dictionary-lookup
> >         dictionary-remove!
> > 

I believe these are good names for any collection-type data-structure. 
IMHO, ref/set!/delete! are about as meaningful as foo/biz!/baz!  What the
hell does "ref" mean?  Why is e.g. "vector-set!" entirely different from
plain old "set!".  Does "delete!" mean get rid of an entry or delete the
whole damn data structure?

> In my opition, consistency is even more important than
> meaningfulness. 

mm.

> Hence, these should be renamed to `dictionary-set!',
> `dictionary-ref' and `dictionary-delete!' respectively.

mm, no.

> Also there
> should probably be a `dictionary-add!' which inserts a given key-value
> cons cell, guaranteeing to share the memory.

"list->dictionary", and "dictionary-add-list!" should provide the
functionality you're looking for:

(list->dictionary (list key-value-cons-cell))

and

(dictionary-add-list! dictionary (list key-value-cons-cell))

> >         dictionary-foreach            <-> ???
> 
> Er, that should be -for-each, not -foreach, again for consistency.

*sigh* okay, you're the second person to criticize my spelling  ;)
I said "foreach" was good because, if we have a MOP OO system, then it
wouldn't collide with "for-each".  But, heck, why not invite Scheme's
basic list type to take part in the MOP?

> Although this might seem nice as a convenience,
> 
> (dictionary-insert-alist! my-dict my-assoc)
> 
> is barely shorter than the (IMO more clear)
> 
> (for-each (lambda (x) (dictionary-add! my-dict x)) my-assoc)
> 
> > 	dictionary-consume-alist!  -- delete alist while
> > 				   -- inserting pairs (to conserve memory)
> 
> I don't understand how this can possibly work. You can't "delete" an
> object in Scheme per se, you can only remove all references to it, at
> which point it gets GC'd. 

By doing set-c[ad]r!'s, I can reduce any alist down to (<last pair>).  I
then do (set-car! list '()) and (set-cdr! list '()) to get it down to
((())).  The dictionary is left with sole ownership of the all the pairs
(unless somebody else is holding on to one of the pairs).

If you do

(dictionary-consume-alist! dictionary big-huge-alist)

then, as "big-huge-alist" is deleted and "dictionary" is filled, the
dictionary will use the memory no longer used by the alist. 

> > 	dictionary-insert-dictionary!
> > 	dictionary-consume-dictionary! -- delete buckets while 
> >                                    -- inserting entries
>
> Same points as above, except that it is vaguely meaningful to clear a
> dictionary while copying it into another. Are these operations really
> common enough that making the API bigger by including them directly is
> a good thing?

possibly general "dictionary-add!" and "dictionary-consume!" procedures
that check the type of their second argument, and behave accordingly.

> > statistics:
> > 	
> > 	dictionary-stats
> > 	dictionary-more-stats
> > 
> 
> `dictionary-stats' is gratuitous enough as it is that there don't need
> to be two of them :-)

yes, but someone with a "dictionaryx" may be seriously interested in
knowing how well their hasher function is working.


> > the rest:
> > 
> >         dictionary-clear!
> >         dictionary-copy!
> > 
> 
> If anything I think a non-desctructive `dictionary-copy' would be more
> useful than `dictionary-copy!'. The latter is unlikely to be much more
> efficient, and it seems a nuisance to have to have a spare dictionary
> object lying around to copy into.

you're right.  Actually, I meant to write "dictionary-copy", but
accidentally appended the "!".


> 
>  - Maciej
> 
> 

	Jay Glascoe
	jglascoe@jay.giss.nasa.gov