Arc Forum | Modifying hash table keys

Arc Forum

Modifying hash table keys

2 points by dido 4285 days ago | 3 comments

Been wondering at this. It seems that Arc allows one to use just about any object as a key in a hash table, but it seems that the semantics are all messed up. For instance, I have the following:

  arc> (= h (table))
  #hash()
  arc> (= h2 (table))
  #hash()
  arc> (= (h h2) 1)
  1
  arc> (h h2)
  1
  arc> (h (table))
  1

So far, this seems to indicate that the value of the empty table is being used as the key, and not the specific instance of the empty table h2 that had been created. But then, when we modify h2:

  arc> (= (h2 1) 2)
  2
  arc> h2
  #hash((1 . 2))
  arc> (h h2)
  nil
  arc> h
  #hash((#hash((1 . 2)) . 1))
  arc> (h (table))
  nil

What just happened here? In contrast, when we try to use conses as keys it seems to do something more reasonable but still strange:

  arc> (= h (table))
  #hash()
  arc> (= c '(1 2))
  (1 2)
  arc> (= (h c) 3)
  3
  arc> (h c)
  3
  arc> (h '(1 2))
  3
  arc> (scar c 3)
  3
  arc> c
  (3 2)
  arc> h
  #hash(((3 2) . 3))
  arc> (h '(3 2))
  3
  arc> (h '(1 2))
  nil

I don't know how this can be done efficiently. Modifying any reference possibly requires a hash table to re-key? Seems like a bloody piece of work to implement.

3 points by rocketnia 4285 days ago | link

Arc just uses Racket's hash tables, which come with this disclaimer:

"Caveat concerning mutable keys: If a key in an equal?-based hash table is mutated (e.g., a key string is modified with string-set!), then the hash table’s behavior for insertion and lookup operations becomes unpredictable." - http://docs.racket-lang.org/reference/hashtables.html

If you're just interested in what's happening in the current implementation, I have a guess for your table-in-table example: When you initially put h2 in the table, its hash is calculated, and it's filed in a bin of entries that have that hash. Then when you look up h2 again, it calculates a different hash, so it searches the wrong bin and doesn't find the entry. When you look up (table), it finds the right bin, but the only key in that bin is h2. Since h2 is not currently equal? to (table), the search fails again.

I can't reproduce your second example, but what I get is consistent with this explanation:

  arc> h
  #hash(((3 2 . nil) . 3))
  arc> (h '(3 2))
  nil
  arc> (h '(1 2))
  nil

That was Arc 3.1. Anarki is different, but not by much:

  arc> h
  #hash(((3 2) . 3))
  arc> (h '(3 2))
  nil
  arc> (h '(1 2))
  nil

I used Racket 5.2 for these, and then I upgraded to Racket 5.3.3 and got the same results. What version are you using?

-----

3 points by dido 4285 days ago | link

Been using Racket 5.1.1. That's a bit reassuring then. I guess that means I shouldn't be worrying too much about the behaviour of mutating keys in the implementation of Arcueid. If Racket says that the insertion and lookup operations of its hash tables become unpredictable then the same is true for reference Arc as well, and it doesn't matter if Arcueid does something completely different as well.

-----

1 point by rocketnia 4285 days ago | link

I agree. ^_^

-----