Back to Questions
1.2k
views4
comments
stackoverflow in GetHashCode
f#compiler

Hi,

I'm building a tiny compiler for a Java-like language. Part of the AST for the language is shown below:

type memb =

Field of string * decl option ref

type decl =

Class of string * memb

The last parameter of memb is a pointer to its parent (the class defining the field) which should be filled in during type checking.

Ever since I added the parent pointer, my application throws a StackOverFlow where it constantly switches between GetHashCode on memb and decl. Do you see any way to fix this problem?

Thanks for your help!

J

.

Hi,

You've got a stack overflow because of structural comparison (the hash code of your ref depends on its content).

The following trick seems to remove the stack overflow:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

[<StructuralEquality(false)>]


[<StructuralComparison(false)>]


type memb =
  

    Field of string * decl option ref
with
    override x.GetHashCode() =
     // define your own method
    override x.Equals(y) = // ...

Another way is simply to change the behaviour of the ref type, so that comparison and hash code don't depend on the reference content:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

[<StructuralEquality(false)>]


[<StructuralComparison(false)>]


type 'a pref = {mutable contents: 'a}


let (:=) x y = x.contents <- y


let (!) x = x.contents


let ref x = {contents=x}

Laurent.

By on 10/19/2009 2:02 AM ()

Thx, Laurent! I definitely have to look into the attributes more!

I solved it by passing an IEqualityComparer to the dictionary.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

let f_comp() =

  { 

    new System.Collections.Generic.IEqualityComparer<memb> with

      member x.Equals(a, b) =

        System.Object.ReferenceEquals(a, b)

      member x.GetHashCode(b) =

        System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(b)

  }

let dictionary = new System.Collections.Generic.Dictionary<memb, FuncDecl>(f_comp());
By on 10/19/2009 2:49 AM ()

Note also there is e.g.

GenericLimitedHash

in the LanguagePrimitives module, which is just for this purpose (only hash to a certain fixed depth); good to use as part of an IEqualityComparer implementation for structural types.

[link:research.microsoft.com]

By on 10/19/2009 7:30 AM ()

Hi,

The problem seems to be that I use members as keys in a system.collections.generic.Dictionary.

I see two solutions:

a) use ref comparison instead of .Equals

b) switch to an F# map

If anyone knows a better solution, feel free to post it here! :-)

By on 10/19/2009 1:50 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper