Re: hash tables

[Thomas Bushnell, BSG]

Alex Shinn <address@hidden> writes:

[snip]

> fails when someone simply wants an array of alists, and is not
> considering them a hash.

Exactly.

> One approach to solving this is that unlike most Unix scripting
> languages, Scheme distinguishes between vectors and lists.  So in your
> Python translator, you're probably representing tuples and (Python)
> lists as one of these, leaving the other type free to uniquely
> identify hashes.  

Well, right now I'm identifying Python lists and Scheme lists.  I want
to identify Python tuples and Scheme vectors.

Python does not have improper lists.  So I'm going to use pairs like
('hash . the-table-itself)
to represent Python objects that don't have easy Scheme counterparts.
That works as long as the cdr of these pairs is never itself a pair;
then it's easy and quick to distinguish these from Python lists.

> Unfortunately this leaves out potential optimizations for knowing when
> a Python tuple/list would be better implemented as a vector or list
> (an approach which could in many cases make the Guile translation run
> much faster than the original Python).

::grin::  Note that the tagging method makes this easy.  Now we have

(define (python:hash? obj)
  (and (pair? obj) (eq? (car obj?) 'hash)))

> Another approach, which more closely matches Python's dictionaries, is
> to define a hash record (or class), and give it some meta-information.
> Such as the ahash (automatically-resizing hash):
> 
> (make-record-type "ahash" ' (table size elements))
> 
> which could keep track of the current size and number of elements in
> the table and perform a re-hash when the ratio reaches a certain
> limit.  The Perl version of this might also include a next slot,
> holding a continuation referencing a hash-fold loop for use in Perl's
> each.

So far I've been avoiding records as being non-standard Scheme.  Is
that foolishness?