[pro] "fhash"

[Alessio Stalla]

On Tue, Jun 14, 2011 at 9:37 AM, Marco Antoniotti
<antoniotti.marco at disco.unimib.it> wrote:
>
> On Jun 13, 2011, at 21:18 , Daniel Weinreb wrote:
>
>> Friends,
>>
>> I wrote a little package for "fash hash tables", which provide an
>> abstraction that is analogous to that of Common Lisp hash tables, but
>> is faster for tables with few elements, and only slightly inferior for
>> tables with many elements.
>>
>> I did this because performance analysis showed that our system was
>> spending too much time in hash table operations, and using the new
>> package helped.
>>
>> I have recently been cleaning this up, one reason being that I'd like
>> to open source it.  The function names used to be things like getfhash
>> and mapfhash.  Now they are like fhash:get and fhash:map-elements and
>> so on.
>>
>> However, before I open-source it, I was to make sure it's "right".  It
>> recently occurred to me that the package name "fhash" has problems.
>>
>> Here are pros and cons of changing it that I can see.
>>
>> Pro: I's not a hash table in the small-cardinality case; it's a linear
>> lookup.  So the name is not actually accurate.
>>
>> Pro: Calling such a data structure a "hash table", even as Common Lisp
>> does, is an abstraction violation.  Whether it works by hashing is an
>> implementation detail.  The Java collection library calls this a Map.
>> Python calls it a dictionary.  Clojure calls it a map.  Those are both
>> better names.
>
> Actually, in Java the naming reflects the separation between abstraction and implementation.  AFAIU, clojure does not quite do this and neither does Python.
>
> I would advocate settling down on a Java-esque nomenclature with MAP or DICTIONARY as "names" for the abstraction and with different names for the implementations; e.g.,  DICTIONARY-TREE, DICTIONARY-FHASH, DICTIONARY-HASH-TABLE, you name it....

AFAIK, Java started just like Lisp with the Hashtable class
(implementation without interface) which later was deprecated in favor
of Map (interface) + HashMap, TreeMap, ... (implementations).
There is already a somewhat official API for extensible sequences,
designed by Christophe Rhodes and implemented in SBCL and ABCL (and
maybe others, I don't know). We could similarly have extensible maps,
even though "sequence" is an already recognized abstraction in CL,
while "map" is not.

Alessio