This is the mail archive of the guile@cygnus.com mailing list for the guile project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: Scheme style auto-resizing hashtable (fwd)


I'm sure you're all anxious to hear about my hash table extension  ;)

front page news: my extension underwent the GREAT RENAMING:

$ for x in *.[ch] makefile; do
>     perl -ne '                                                          
>     s/hashtab/dictionary/g;
>     s/hash table/dictionary/g;
>     s/table/dictionary/g;
>     s/dictionarys/dictionaries/g;
>     print;
>     ' $x > foo
>     mv foo $x
> done

I decided to go with "dictionary" because

On Sat, 31 Oct 1998, Ian Bicking sagely murmured:

> A rich set of datatypes could also be a powerful addition.  Make
> dictionaries, not hash tables -- mostly that's just a matter of
> terminology, but I think it's important.  As a programmer, I don't
> care about the fact that hash tables use hashing, I care about the
> fact that hash tables are a collection of values indexed by keys.

and

On Sat, 31 Oct 1998, Maciej Stachowiak hummed this tune:

> ... Scheme has a tradition of using meaningful identifiers and uniform
> surface syntax ... 

<taken slightly out of context>

so what do I have here?  "dictionary" and "meaningful identifiers". hmm.
I also considered using "hash-table" (used by CL, so I just said "No."),
"assoc-array" (one letter longer than "dictionary", you lose), and even
"auto-hash" (where did that come from?).

Here's a list of utilities I'm planning on throwing into the extension:

constructors:

	make-dictionary
	make-dictionaryv
	make-dictionaryq

behavior modifiers:

	dictionary-enable! 
	dictionary-disable!
	dictionary-change-type!

the big three basic operations:

	dictionary-add!
	dictionary-lookup
	dictionary-remove!

the rest:

	dictionary-map
	dictionary-foreach
	dictionary-clear!
	dictionary-copy!
	dictionary-update!
	dictionary-make-iter
	call-with-dictionary-iterator
	dictionary->pairs
	dictionary->keys
	dictionary->values
	dictionary-stats
	dictionary-more-stats

all of these guys could (and perhaps should) be written in Scheme.  I'll
write both "dictionary-utils.[ch]" and "dictionary-utils.scm".  And then
we're off to the races.  Lots of timing tests to determine which benefit
from a C implementation and which don't (e.g.,
"call-with-dictionary-iterator"  would probably be most efficiently
implemented as a Scheme macro). 

any feedback: thoughts, ideas, suggestions, complaints, *flames*, etc. 
would be most appreciated. 

	tia,
	Jay
	jglascoe@jay.giss.nasa.gov