[racket-dev] Output value of program changes depending on whether I pretty-print an opaque struct value

I determined this morning that the cause was a bad hash code for my generic hashes/sets. I use an injection from the value space into the natural numbers by assigning atoms prime numbers (thanks math/number-theory for next-prime!), and I multiply them together to produce the encoding of sets (I check divisibility before multiplying, so I always have a <=1 multiplicity). I use Cantor's injection for producing the number of pairs, so I can make a set of pairs encode finite functions (hashes). The result should be that equal numbers imply equal values, so I hashed on the numbers for hash-proc and hash2-proc instead of the values. I still compare equality only using the numbers since it's 3 orders of magnitude faster. I changed the hash-proc to hash on the values instead and got consistent results for the analysis. I'm perplexed by this, so I'm trying to write a smaller example that demonstrates the problem.

I only use hasheq for seen checks when traversing through a hash that has circular references, and I never change the hash during these traversals, and the result is a set. The order doesn't matter. I also changed all hasheqs in my code to hashes to see if that was a problem. It wasn't.

-Ian
----- Original Message -----
From: "Carl Eastlund" <cce at ccs.neu.edu>
To: "J. Ian Johnson" <ianj at ccs.neu.edu>
Cc: "Matthew Flatt" <mflatt at cs.utah.edu>, "dev" <dev at racket-lang.org>
Sent: Wednesday, August 28, 2013 12:34:08 PM GMT -05:00 US/Canada Eastern
Subject: Re: [racket-dev] Output value of program changes depending on whether I pretty-print an opaque struct value


Is it possible your analysis is depending on the order of graph traversal? That is, do you ever use in-hash on the hasheq, and if so is it possible the results of your analysis would change if in-hash produced hash table entries in a different order? Same for in-hash-keys or in-hash-values, obviously. 



Carl Eastlund 


On Tue, Aug 27, 2013 at 6:58 PM, J. Ian Johnson < ianj at ccs.neu.edu > wrote: 


Weird you can't repro. 
I only use hasheq when I know the keys are symbols, or the table is local and only used for a graph traversal (where the graph is not changing during traversal). 
-Ian 


----- Original Message ----- 
From: "Matthew Flatt" < mflatt at cs.utah.edu > 
To: "J. Ian Johnson" < ianj at ccs.neu.edu > 
Cc: "dev" < dev at racket-lang.org > 
Sent: Tuesday, August 27, 2013 6:33:02 PM GMT -05:00 US/Canada Eastern 
Subject: Re: [racket-dev] Output value of program changes depending on whether I pretty-print an opaque struct value 

I haven't been able to get a different result by changing printing. 

One thing that printing might do, however, is assign `eq?`-based hash 
codes to objects that did not already have them. That assignment, in 
turn, could affect the order in which objects appear later in a hash 
table. 

I hacked Racket to make the internal hash-code generator count down 
instead of up, and I was able to get a different result that way. 

Are you using `eq?`-based hashing at all? Could there be some 
dependency on the order of values within a hash table (or hash set)? 

At Tue, 27 Aug 2013 14:02:50 -0400 (EDT), "J. Ian Johnson" wrote: 
> This is mostly an mflatt-only problem. 
> 
> My analysis framework is now using a generic dictionary for its abstract heap, 
> and depending on whether or not I pretty-print this heap before continuing on 
> analyzing, the result of the analysis changes (sound versus unsound). I found 
> the problem doing some printf debugging, and when fixed, I tried removing the 
> print statements. The answer changed. There must be some problem in the C code 
> somewhere, because this is just bonkers. 
> 
> (Note: I've had previous bugs where rewriting a (begin (void) e) => e caused a 
> similar value-changing bug. Updating the compiler to head fixed it at that 
> point. I'm running yesterday's HEAD now, though.) 
> 
> https://github.com/dvanhorn/oaam/tree/thocon 
> 
> See the ;; mflatt: comment in code/kcfa.rkt 
> 
> To see the problem, 
> racket code/run-benchmark.rkt --lcg benchmarks/temp-c/sort2.sch 
> 
> Thanks, 
> -Ian 
> _________________________ 
> Racket Developers list: 
> http://lists.racket-lang.org/dev 
_________________________ 
Racket Developers list: 
http://lists.racket-lang.org/dev