Re: Scheme style auto-resizing hashtable (fwd)

[Maciej Stachowiak <mstachow@mit.edu>]

hjstein@bfr.co.il writes:

> This whole hash table / dictionary issue says to me that one really
> wants an object structure with dictionary as a virtual class at the
> top & hash-table, avl tree, red/black tree, gdbm file, etc, as
> subclass implementations.  They all have the same interface, namely
> make, put, get, delete, map, for-each, next, previous, first and last.  The
> only difference btw the tree ones & the hash based ones is that the
> tree ones need a comparison fcn in the make call & that next, prev,
> first & last have meanings relative to the given comparison fcn.
> 

I couldn't have put it better. An important consideration for Guile's
future object system is to make it possible to handle native Scheme
types within the object system so we can have properly generic
operations. A possible fragment of a class hierarchy: (multiple
inheritance is not drawn very well)


collection -+
            |
            +- finite-collection -+
            |                     |
            |                     +-
            |

            +- set -+
            |       |
            |       +- ordered-set
            |
            +- sequence -+
            |            |
            |            +- stream (in the SICP sense, not the CL sense)
            |            |
            |            +- finite-sequence -+
            |                                |
            |                                +- array -+
            |                                |         |
            |                                |         +- vector
            |                                |         |
            |                                |         +- string
            |                                |
            |                                +- list -+
            |                                |        |
            |                                |        +- alist
            |                                |          [ordered-mapping]
            |                                |
            |                                +- ordered-mapping (see below)
            |                                   [sequence]
            |
            +- mapping -+
                        |
                        +- finite-mapping -+
                        [finite-collection]|
                                           +- hash-table
                                           |
                                           +- database-hash
                                           |
                                           +- ordered-mapping -+
                                              [sequence]       |
                                                               +- alist
                                                               |  [list]
                                                               |
                                                               +- tree -+
                                                                        |
                                                                        +- avl-tree
                                                                        |
                                                                        +- red-black-tree


In case it is unclear, the distinctions some of the top-level classes
make in terms of most important operations available at each level
are:

collection: member?, insert, delete

finite-collection: size, for-each (unordered), map

set: union, intersection, set-difference (a generic collection is not
a set because elements may appear more than once).

seqence: set/reference by numerical index, map, filter, first, subsequence

finite-sequence: reverse, for-each (ordered), last

mapping: set/reference by key

tree: implies that the ordering is by a sorting of the keys, not
arbitrary; prev, next


The fact that map appears in several places might imply that there
should be a `mappable' class in there somewhere. Also, I have totally
ignored the issue when inserts and deletes should be destructive and
when they shouldn't - obviously they should be for most mappings but
can't be for vectors.


Of course, this whole message is really gratuitous - scant little of
the infrastructure to implement this exists yet. But it would be cool
if we could get there. Also, it's not as gratuitous as it could be - I
managed to stop myself before adding groups, fields and other such
things only likely to be interesting to math nerds.

 - Maciej