CMUCL and EQUAL hash tables 
Author Message
 CMUCL and EQUAL hash tables

I just noticed that I can't use arrays with fill-pointers as hash keys
in EQUAL hash tables. The following transcript should explain the
problem:

* (defvar *a-string* (make-array 20 :element-type 'character :fill-pointer 0))

*A-STRING*
* (vector-push #\A *a-string*)

0
* (vector-push #\B *a-string*)

1
* (vector-push #\C *a-string*)

2
* (defvar *a-htable* (make-hash-table :test 'equal))

*A-HTABLE*
* (setf (gethash "ABC" *a-htable*) 'foo)

FOO
* (gethash "ABC" *a-htable*)

FOO
T
* (equal *a-string* "ABC")

T
* (gethash *a-string* *a-htable*)

NIL
NIL

Of couse, I expect gethash to return FOO here, since *a-string* is EQUAL
to "ABC", but somehow the fill-pointer fools gethash. Is this a bug in
CMUCL or am I missing something? In CLISP it works as expected.

*--                                                                   --*

*-----         Computer Science at Abo Akademi University          -----*



Mon, 19 Nov 2001 03:00:00 GMT  
 CMUCL and EQUAL hash tables

| I just noticed that I can't use arrays with fill-pointers as hash keys in
| EQUAL hash tables.  The following transcript should explain the problem:

  and 18.1.2 Modifying Hash Table Keys in ANSI X3.226-1994 Common Lisp
  explains why.

  there never was a substitute for reading the specification.  go grab it
  from <URL:http://www.harlequin.com/education/books/HyperSpec/>.

| Of course, I expect ...

  well, there's your problem right there:  why did you expect this?

#:Erik



Tue, 20 Nov 2001 03:00:00 GMT  
 CMUCL and EQUAL hash tables

Quote:

>| I just noticed that I can't use arrays with fill-pointers as hash keys in
>| EQUAL hash tables.  The following transcript should explain the problem:

>  and 18.1.2 Modifying Hash Table Keys in ANSI X3.226-1994 Common Lisp
>  explains why.

>  there never was a substitute for reading the specification.  go grab it
>  from <URL:http://www.harlequin.com/education/books/HyperSpec/>.

>| Of course, I expect ...

>  well, there's your problem right there:  why did you expect this?

>#:Erik
>--


Me thinks Fredrik's got every right to expect this behaviour (which BTW
works in ACL as expected). The essential part of 18.1.2 reads:

 If an object O1 is used as a key in a hash table H and is THEN visibly modified with
 regard to the equivalence test of H, then the consequences are unspecified if O1,
 or any object O2 equivalent to O1 under the equivalence test (either before or after
 the modification), is used as a key in further operations on H.

At the point of using the key there was NO visible modification present
as also the successful (equal . ..) proved. So the hash-table lookup should
work as expected.

A totally different discussion would be the question of using modifyable keys
for storing stuff in hash-tables, which might easily lead to disaster.
But in the example given, the "storage key" was a simple string, whereas the
retrieval key was an array using a fill-pointer which happended to be EQUAL
at retrieval time. This seems like a totally reasonable usage pattern, e.g.
you have kind of symbol-table and parse some string collecting its characters
into an adjustable array and do some (hash-)table lookup after the token is
completed.

Bernhard
--
--------------------------------------------------------------------------
Bernhard Pfahringer
Austrian Research Institute for  http://www.ai.univie.ac.at/~bernhard/



Tue, 20 Nov 2001 03:00:00 GMT  
 CMUCL and EQUAL hash tables

Quote:


>| I just noticed that I can't use arrays with fill-pointers as hash keys in
>| EQUAL hash tables.  The following transcript should explain the problem:

>  and 18.1.2 Modifying Hash Table Keys in ANSI X3.226-1994 Common Lisp
>  explains why.

>  there never was a substitute for reading the specification.  go grab it
>  from <URL:http://www.harlequin.com/education/books/HyperSpec/>.

Umm, no, that section has nothing to do with what I was asking, I was not
modifying the hash key. There never was a substitute for understanding
the problem before trying to respond. ;-)  However, I notice that my
original sentence above is misleading -- I did not use an array with
a fill-pointer as a hash key, but I used one to do hash table lookup.
The transcript should have made this clear.

*--                                                                   --*

*-----         Computer Science at Abo Akademi University          -----*



Tue, 20 Nov 2001 03:00:00 GMT  
 CMUCL and EQUAL hash tables

| At the point of using the key there was NO visible modification present
| as also the successful (equal . ..) proved.  So the hash-table lookup
| should work as expected.

  ok, so you read 18.1.2 but not anything below 18.1.2 in the structure.
  that's not very smart.  please see 18.1.2.2.2 for further information
  about what "visible modification" means.

#:Erik



Tue, 20 Nov 2001 03:00:00 GMT  
 CMUCL and EQUAL hash tables

| There never was a substitute for understanding the problem before trying
| to respond. ;-)

  touch

| However, I notice that my original sentence above is misleading -- I did
| not use an array with a fill-pointer as a hash key, but I used one to do
| hash table lookup.  The transcript should have made this clear.

  ok, I tend to ignore examples when whatever they are intended to be
  examples of is sufficiently well explained.  that didn't work this time.
  looking at your transcript, I agree that GETHASH should work with any old
  string EQUAL to the key.

#:Erik



Tue, 20 Nov 2001 03:00:00 GMT  
 CMUCL and EQUAL hash tables

Quote:

>| At the point of using the key there was NO visible modification present
>| as also the successful (equal . ..) proved.  So the hash-table lookup
>| should work as expected.

>  ok, so you read 18.1.2 but not anything below 18.1.2 in the structure.
>  that's not very smart.  please see 18.1.2.2.2 for further information
>  about what "visible modification" means.

18.1.2 places restrictions on modifications after the object has been used
as a key in the hash table.  All of Bernhard's modifications to the object
were made *before* the (setf (gethash ...) ...).  So 18.1.2 is totally
irrelevant.

--

GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.



Tue, 20 Nov 2001 03:00:00 GMT  
 
 [ 7 post ] 

 Relevant Pages 

1. Generic Table -- Hash Table Implementation Module

2. Hash.new(Hash.new) doesn't use Hash.new as default value

3. Why can't a hash table be read/written as #S(HASH-TABLE ...)?

4. One and One doesn't equal two It equals 1 - The Who

5. One and One doesn't equal two It equals 1 - The Who

6. colon-equal vs equal

7. Open Source disk based hash tables

8. linked list hash table

9. public hash table full

10. Public hash table full

11. Hash table in Caml

12. hash table code in modula/oberon

 

 
Powered by phpBB® Forum Software