Arc Forum | Bug in hash tables ?

Arc Forum

Bug in hash tables ?

1 point by sacado 6283 days ago | 6 comments

Hey every one. I hope my question is not too stupid...

  (= buggy (table))  ==> #hash()
   (= (buggy 'buggy) t)  ==> t
  (buggy 'buggy)   ==> t  ; works ok
  (buggy buggy) ==> nil ; still ok

  (= (buggy buggy) t) ==> t
  (buggy buggy) ; loops forever

Am I missing something ? or is it really broken ? Yeah, I know, it might seem a strange idea, but I actually used such features in Python a few years ago...

1 point by pg 6283 days ago | link

It's not a bug. It's displaying the table that loops forever, because it is a circular structure. It should work fine otherwise.

-----

5 points by sacado 6283 days ago | link

Thanks for your answer Paul ! However I think I'm still missing something because display seems to work fine :

buggy ==> #0=#hash((#0# . t) (buggy . t))

(ok, we can see it is circular here, but no infinite loop)

However,

(if (buggy 'buggy) 'yes) ==> yes ; ok...

(if (buggy buggy) 'yes) ==> infinite loop...

Here, no display of the table seems to be involved ?

-----

5 points by pg 6282 days ago | link

Oops, that does look like a bug. Will investigate. Sorry for not actually testing it before.

-----

4 points by nex3 6282 days ago | link

It looks like an issue with Scheme, rather than Arc. Check out the following Scheme session:

  > (define t (make-hash-table 'equal))
  > (hash-table-put! t t 'foo)
  > t
  #0=#hash((#0# . foo))
  > (hash-table-get t t)
  ; Loops forever

-----

3 points by soegaard 6282 days ago | link

"Issue". It behaves as specified. From R5RS:

Equal? recursively compares the contents of pairs, vectors, and strings, applying eqv? on other objects such as numbers and symbols. A rule of thumb is that objects are generally equal? if they print the same. Equal? may fail to terminate if its arguments are circular data structures.

There is a silver lining though. In R6RS the following was added:

  Note: The equal? procedure must always terminate, even if its arguments contain cycles.

That is, there is a good chance that the behaviour of equal? changes, when the PLT Scheme team begins implementing the R6RS language.

-----

1 point by sacado 6282 days ago | link

I submitted a bug report to PLT Scheme about that. Here's their answer :

"The process for generating an `equal?' hash key is defined to not terminate on circular objects, such as a hash table that contains itself. So `(hash-table-get <any-table> t)' loops trying to generate a key for `t'.

The specification of hashing has changed for the next release to deal gracefully with cyclic data, just as `equal?' has changed so that it can compare cyclic data. In the current pre-release version, v3.99.0.10, your example returns immediately.

(It returns with a "key not found" error. That's because the process of installing a hash table into itself changes the table's own `equal?' hash key.)"

-----