From: Peter Seibel
Subject: User-defined equality/hashing functions in hash tables?
Date:
Message-ID: <m3k75ea2zw.fsf@javamonkey.com>
What implementations support user-defined equality/hashing functions
for built-in hash tables? Here are the ones I know of:
Allegro - :hash-function argument to MAKE-HASH-TABLE
CMUCL - DEFINE-HASH-TABLE-TEST function in EXT package
SBCL - DEFINE-HASH-TABLE-TEST function in SB-INT package
CLISP - DEFINE-HASH-TABLE-TEST macro in EXT package
any others?
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Peter Seibel <·····@javamonkey.com> writes:
> What implementations support user-defined equality/hashing functions
> for built-in hash tables? Here are the ones I know of:
>
> Allegro - :hash-function argument to MAKE-HASH-TABLE
> CMUCL - DEFINE-HASH-TABLE-TEST function in EXT package
> SBCL - DEFINE-HASH-TABLE-TEST function in SB-INT package
> CLISP - DEFINE-HASH-TABLE-TEST macro in EXT package
I don't think you're considering the same thing, here. I don't
know what the define-hash-table-test operators in other languages
do (hopefully they create functionality which only do a single
thing). But as you allude to by your "equality/hashing" pair, there
are actually two things which must be considered in any hash table
setup: How to generate hash codes for an object, and how to test
for equality. The :hash-function argument that Allegro CL provides
doesn't make any assumptions about the test you want to provide, and
so, in CL tradition, it defaults the test to EQL. We do, however,
extend the :test option as well to accept the name of any
previously-defined function to do the testing. We even have the
print-object method for hash tables describe what is going on:
CL-USER(1): (setq x (make-hash-table :hash-function 'my-hash-fcn))
#<MY-HASH-FCN/EQL hash-table with 0 entries @ #x717c089a>
CL-USER(2): (setq y (make-hash-table :hash-function 'my-hash-fcn
:test 'simple-string=))
#<MY-HASH-FCN/SIMPLE-STRING= hash-table with 0 entries @ #x717c10ca>
CL-USER(3):
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
[responding to unfortunate wording by myself]
Duane Rettig <·····@franz.com> writes:
> Peter Seibel <·····@javamonkey.com> writes:
>
> > What implementations support user-defined equality/hashing functions
> > for built-in hash tables? Here are the ones I know of:
> >
> > Allegro - :hash-function argument to MAKE-HASH-TABLE
> > CMUCL - DEFINE-HASH-TABLE-TEST function in EXT package
> > SBCL - DEFINE-HASH-TABLE-TEST function in SB-INT package
> > CLISP - DEFINE-HASH-TABLE-TEST macro in EXT package
>
> I don't think you're considering the same thing, here. I don't
> know what the define-hash-table-test operators in other languages
=================================================^^^^^^^^^^^^^^^^^^
Here I should have said "the other vendors' products". I suppose
one could argue that since these are all Common Lisp extensions, they
are "other languages", but that's not the emphasis I had intended.
> do (hopefully they create functionality which only do a single
> thing). But as you allude to by your "equality/hashing" pair, there
> are actually two things which must be considered in any hash table
> setup: How to generate hash codes for an object, and how to test
> for equality. The :hash-function argument that Allegro CL provides
> doesn't make any assumptions about the test you want to provide, and
> so, in CL tradition, it defaults the test to EQL. We do, however,
> extend the :test option as well to accept the name of any
> previously-defined function to do the testing. We even have the
> print-object method for hash tables describe what is going on:
>
> CL-USER(1): (setq x (make-hash-table :hash-function 'my-hash-fcn))
> #<MY-HASH-FCN/EQL hash-table with 0 entries @ #x717c089a>
> CL-USER(2): (setq y (make-hash-table :hash-function 'my-hash-fcn
> :test 'simple-string=))
> #<MY-HASH-FCN/SIMPLE-STRING= hash-table with 0 entries @ #x717c10ca>
> CL-USER(3):
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
From: Peter Seibel
Subject: Re: User-defined equality/hashing functions in hash tables?
Date:
Message-ID: <m3u14h8z24.fsf@javamonkey.com>
Duane Rettig <·····@franz.com> writes:
> Peter Seibel <·····@javamonkey.com> writes:
>
> > What implementations support user-defined equality/hashing functions
> > for built-in hash tables? Here are the ones I know of:
> >
> > Allegro - :hash-function argument to MAKE-HASH-TABLE
> > CMUCL - DEFINE-HASH-TABLE-TEST function in EXT package
> > SBCL - DEFINE-HASH-TABLE-TEST function in SB-INT package
> > CLISP - DEFINE-HASH-TABLE-TEST macro in EXT package
>
> I don't think you're considering the same thing, here.
Why not. These all seem like solutions to the problem "I want to store
objects in a hash table that uses an arbitrary equivalence predicate
with a corresponding hash function." Sure the mechanism is different
but they are all solutions to that problem. The DEFINE-HASH-TABLE-TEST
functons and macros basically let you define a pair of functions with
a particular name:
(define-hash-table-test 'foo #'my-equal #'my-hash)
which can then be used as an argument to MAKE-HASH-TABLE:
(make-hash-table :test 'foo)
This is more or less equivalent--as I understand it--to saying, in
Allegro:
(make-hash-table :test #'my-equal :hash-function #'my-hash)
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Peter Seibel <·····@javamonkey.com> writes:
> Duane Rettig <·····@franz.com> writes:
>
> > Peter Seibel <·····@javamonkey.com> writes:
> >
> > > What implementations support user-defined equality/hashing functions
> > > for built-in hash tables? Here are the ones I know of:
> > >
> > > Allegro - :hash-function argument to MAKE-HASH-TABLE
> > > CMUCL - DEFINE-HASH-TABLE-TEST function in EXT package
> > > SBCL - DEFINE-HASH-TABLE-TEST function in SB-INT package
> > > CLISP - DEFINE-HASH-TABLE-TEST macro in EXT package
> >
> > I don't think you're considering the same thing, here.
>
> Why not. These all seem like solutions to the problem "I want to store
> objects in a hash table that uses an arbitrary equivalence predicate
> with a corresponding hash function." Sure the mechanism is different
> but they are all solutions to that problem. The DEFINE-HASH-TABLE-TEST
> functons and macros basically let you define a pair of functions with
> a particular name:
>
> (define-hash-table-test 'foo #'my-equal #'my-hash)
>
> which can then be used as an argument to MAKE-HASH-TABLE:
>
> (make-hash-table :test 'foo)
>
> This is more or less equivalent--as I understand it--to saying, in
> Allegro:
>
> (make-hash-table :test #'my-equal :hash-function #'my-hash)
This is fine. So in order to be accurate, your table would be
Allegro - :hash-function and :test arguments to MAKE-HASH-TABLE
CMUCL - DEFINE-HASH-TABLE-TEST function in EXT package
SBCL - DEFINE-HASH-TABLE-TEST function in SB-INT package
CLISP - DEFINE-HASH-TABLE-TEST macro in EXT package
(others ...)
The point is that the other vendors' define-hash-table-test functionality
seems to define a hash-code-gen/equality-test pair, whereas we separate
the hash-code-generation from the test. The reason why I mention this
is that we used to do a similar thing in earlier versions (I think it was
circa Allegro CL 4.3) but we found that adding a keyword was a cleaner
way to specify a hash-code-generator. Someone mentioned Lispworks
adding a keyword similar to ours; it would be interesting to see if they
have a similar interface as well (i.e. extension of the :test keyword
and use of one keyword used per functionality rather than one operator
defining two separate tasks).
[*] For an argument as to why it is cleaner to separate the two
functionalities, consider first that both styles are ex-CL in the
sense that they each extend the spec in some way. Then, consider
the distance between the actual spec (and its spirit) and the new
functionalities. Allegro's style of extension adds two things:
it adds one keyword to make-hash-table, and it extends the list
of operators that can be specified by the :test keyword. The other
method doesn't add a new keyword, but it does add to what the :test
keyword does and _additionally_ it adds semantics to the test keyword
as well (i.e. the :test keyword no longer simply specifies a function
which is used to compare entries with a key for same-ness, it now
might cause hash-codes to be generated as well). I consider this
less clean. Our style allows you to separate the two specifications,
also - if you specify only a :test option that is not one of the options
allowed by the spec, then make-hash-table will give you a hash-function
which has defaulted to sxhash:
CL-USER(3): (setq y (make-hash-table :test 'simple-string=))
#<SXHASH/SIMPLE-STRING= hash-table with 0 entries @ #x717c1562>
CL-USER(4):
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182