Re: Scheme style auto-resizing hashtable (fwd)

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

On Wed, 18 Nov 1998, Maciej Stachowiak wrote:

> jglascoe@jay.giss.nasa.gov writes:
> > 
> > 	*** translators: ***
> > 
> > list->hash-table list [wrapper]
> > list->hash-tablev list [wrapper]
> > list->hash-tableq list [wrapper]
> > list->hash-tablex list user-equal? user-hasher [wrapper]
> 
> Can you change these to alist->hash-table*, since they conver
> association lists?

with appropriate "wrapper"s, these functions will work on any list. 

(list->hash-table el (lambda (x) (cons x '())))

> > list->hash-table! list [wrapper]
> > list->hash-tablev! list [wrapper]
> > list->hash-tableq! list [wrapper]
> > list->hash-tablex! list user-equal? user-hasher [wrapper]
> >     Similar to the non-destructive procedures above.
> >     Magically turn list "list" into a hash-table.  Return value
> >     is unspecified.  Note: "list" must be nonempty.
> > 
> 
> Destructive conversion functions are a bad idea and cannot
> generalize. Taking advantage of the fact that a hash table is
> fundamentally a cons cell will make things lose big if you ever change
> your underlying implementation, for instance.

hmm.  I could make them destructive as well as functional.  I mean, "list"
will still be destroyed -- it's finally reduced to (()) -- but rather than
directly converting "list" to a hash-table, the new hash-table will be the
return value of the function.  Would this be preferable to in-place
transformation?  I like the idea, now they'll work fine with empty lists.

Presumably the same comments apply to "hash-table->list!".  If I make that
guy functional (but still destructive) then he'll be able to handle
"empty" hash-tables.

As far as losing big if hash-table objects are not pairs, that's easily
solved with a macro:

(define-syntax imperative-list->hash-table!
  (syntax-rules ()
    ((_ el)
     (set! el (functional-list->hash-table! el)))))

in-place transformation or functional return value... I don't know which
is best.  An *unspecified* return value reminds the user that something
destructive just happened, but then OTOH the "!" at the end of the
procedure also hints at the same thing.

> > hash-table-consume-list! hash-table list [wrapper]
> >     Similar to the non-destructive "hash-table-add-list!" above.
> >     Delete list "list" while inserting (wrapper list-element)
> >     into hash-table "hash-table" for all of "list"'s elements.
> >     Return value is unspecified.
> > 
> 
> I still argue this is useless, especially since Guile is getting a
> generational GC.  Bloating the API unnecessarily is a bad thing.

I don't see how this depends upon the type of GC in use.  Let's say that
"list" has millions of elements.  Surely *any* GC will free much of the
unreferenced cons cells before the procedure is complete.

I agree that the API is a bit big, but all eight of the
"list->hash-table[vqx]?!?" procedures and the
"hash-table-(add|consume)-list!" duo directly call:

static void
basic_hash_table_add_list_x(SCM hash_table, SCM list,
			    SCM user_wrapper, short consume_flag);

And both of "hash-table->list!?" use:

static SCM
basic_hash_table2list(SCM hash_table, SCM user_unwrapper,
                      short consume_flag);

Throwing in the "consume_flag" argument was, I think, both natural and
trivial for both of these basic functions.

In addition to the space-saving virtues of the destructive functions, they
also ensure that the new hash-table or list is the sole owner of the pairs
contained in the old list or hash-table. (assuming nobody else is holding
onto the pairs).


	Jay Glascoe
	jglascoe@jay.giss.nasa.gov