Re: Scheme style auto-resizing hashtable (fwd)

[Maciej Stachowiak <mstachow@mit.edu>]

jglascoe@jay.giss.nasa.gov writes:
> 
> > > 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?
> 

* `ref' is short for `reference' or `dereference'. 

* `vector-set!' is entirely different from plain old `set!' because it
modifies a vector, not a variable, and I don't see why this is
confusing at all. You may as well ask "a[x] = y;" is completely
different from "a = y;" in C.

* It's not clear to me why your criticism of "delete!" does not apply
equally to "remove!". However, in general the reason it is obvious it
does not mean "delete the whole data structure" is because there are
no such operations in Scheme.


The reason these are preferable to insert!/lookup/remove! is because
they are parallel with the operations on Scheme basic types, as
defined in R5RS, a standards document that is a lot harder to change
than random data structure implementations. For that matter, one could
make up similar arguments against insert!/lookup/remove!, e.g.:

* insert! implies adding a new element, but it might in fact be
changing an existing element. set! expresses this much better


Really, the choices between these are close to arbitrary, hence
consistency with existing practice should be the deciding factor.

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

IMO, it makes a lot more sense to make adding a single key-value pair
a primitive rather than to make adding a whole list of them a
primitive.

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

As I said in another message, dropping all references to the alist
(e.g. set!'ing the variable that refers to it to '(), or better yet
not storing it in a lasting variable at all) achieves the same effect
much more efficiently.


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

It can only possibly reuse the cons cells that represent the
associations, not the ones that form the list structure, which will
become garbage. Sharing the association cells does not require
destroying the alist.

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

Then make dictionary-stats do what dictionary-more-stats would do.

 - Maciej