Back to Questions
1.1k
views6
comments
Is structural comparison of recursive data types tail recursive ?
f#

Hi,

I'm playing with some fairly long and complex lambda expressions using the following recursive data type:

1
2
3
4
5
6

type exp =  | Var of Token

            | Lambda of Token * exp

            | Apply of exp * exp

and I run into the following StackOverflow.

I think it might be triggered by comparing two very deep tree instances of exp.

Is structural comparison of recursive data types tail recursive ?

Version: F# 1.9.6.16

StackOverflow StackTrace

FSharp.Core.dll!Microsoft.FSharp.Core.LanguagePrimitives.HashCompare.GenericHashWithComparerIntrinsic<char>(System.Collections.IEqualityComparer comp = {Microsoft.FSharp.Core.LanguagePrimitives.HashCompare.UnlimitedHasher}, char input = 'f') + 0x14 bytes

ConsoleApplication35.exe!Program.Token.GetHashCode(System.Collections.IEqualityComparer comp = {Microsoft.FSharp.Core.LanguagePrimitives.HashCompare.UnlimitedHasher}) Line 91 + 0xa3 bytes F#

ConsoleApplication35.exe!Program.exp.GetHashCode(System.Collections.IEqualityComparer comp = {Microsoft.FSharp.Core.LanguagePrimitives.HashCompare.UnlimitedHasher}) Line 126 + 0x8c bytes F#

ConsoleApplication35.exe!Program.exp.GetHashCode(System.Collections.IEqualityComparer comp = {Microsoft.FSharp.Core.LanguagePrimitives.HashCompare.UnlimitedHasher}) Line 126 + 0x1c5 bytes F#

ConsoleApplication35.exe!Program.exp.GetHashCode(System.Collections.IEqualityComparer comp = {Microsoft.FSharp.Core.LanguagePrimitives.HashCompare.UnlimitedHasher}) Line 126 + 0x193 bytes F#

ConsoleApplication35.exe!Program.exp.GetHashCode(System.Collections.IEqualityComparer comp = {Microsoft.FSharp.Core.LanguagePrimitives.HashCompare.UnlimitedHasher}) Line 126 + 0x193 bytes F#

ConsoleApplication35.exe!Program.exp.GetHashCode(System.Collections.IEqualityComparer comp = {Microsoft.FSharp.Core.LanguagePrimitives.HashCompare.UnlimitedHasher}) Line 126 + 0x193 bytes F#

ConsoleApplication35.exe!Program.exp.GetHashCode(System.Collections.IEqualityComparer comp = {Microsoft.FSharp.Core.LanguagePrimitives.HashCompare.UnlimitedHasher}) Line 126 + 0x193 bytes F#

ConsoleApplication35.exe!Program.exp.GetHashCode(System.Collections.IEqualityComparer comp = {Microsoft.FSharp.Core.LanguagePrimitives.HashCompare.UnlimitedHasher}) Line 126 + 0x193 bytes F#

ConsoleApplication35.exe!Program.exp.GetHashCode(System.Collections.IEqualityComparer comp = {Microsoft.FSharp.Core.LanguagePrimitives.HashCompare.UnlimitedHasher}) Line 126 + 0x193 bytes F#

ConsoleApplication35.exe!Program.exp.GetHashCode(System.Collections.IEqualityComparer comp = {Microsoft.FSharp.Core.LanguagePrimitives.HashCompare.UnlimitedHasher}) Line 126 + 0x193 bytes F#

ConsoleApplication35.exe!Program.exp.GetHashCode(System.Collections.IEqualityComparer comp = {Microsoft.FSharp.Core.LanguagePrimitives.HashCompare.UnlimitedHasher}) Line 126 + 0x193 bytes F#

ConsoleApplication35.exe!Program.exp.GetHashCode(System.Collections.IEqualityComparer comp = {Microsoft.FSharp.Core.LanguagePrimitives.HashCompare.UnlimitedHasher}) Line 126 + 0x193 bytes F#

ConsoleApplication35.exe!Program.exp.GetHashCode(System.Collections.IEqualityComparer comp = {Microsoft.FSharp.Core.LanguagePrimitives.HashCompare.UnlimitedHasher}) Line 126 + 0x193 bytes F#

ConsoleApplication35.exe!Program.exp.GetHashCode(System.Collections.IEqualityComparer comp = {Microsoft.FSharp.Core.LanguagePrimitives.HashCompare.UnlimitedHasher}) Line 126 + 0x193 bytes F#

ConsoleApplication35.exe!Program.exp.GetHashCode(System.Collections.IEqualityComparer comp = {Microsoft.FSharp.Core.LanguagePrimitives.HashCompare.UnlimitedHasher}) Line 126 + 0x193 bytes F#

ConsoleApplication35.exe!Program.exp.GetHashCode(System.Collections.IEqualityComparer comp = {Microsoft.FSharp.Core.LanguagePrimitives.HashCompare.UnlimitedHasher}) Line 126 + 0x193 bytes F#

ConsoleApplication35.exe!Program.exp.GetHashCode(System.Collections.IEqualityComparer comp = {Microsoft.FSharp.Core.LanguagePrimitives.HashCompare.UnlimitedHasher}) Line 126 + 0x193 bytes F#

ConsoleApplication35.exe!Program.exp.GetHashCode(System.Collections.IEqualityComparer comp = {Microsoft.FSharp.Core.LanguagePrimitives.HashCompare.UnlimitedHasher}) Line 126 + 0x193 bytes F#

.

Perchance did you compile in Debug mode (which doesn't do tail calls)? Try it in Release mode.

I have not tried Beta1, but in my internal bits, the program below works fine in Release mode.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

 

type Token = int
type exp =  | Var of Token
            | Lambda of Token * exp
            | Apply of exp * exp

let rec MakeLong n k =
    if n = 0 then
        k <| Var 0
    else
        MakeLong (n-1) (fun r ->
        k <| Lambda(0, r))

let rec MakeHuge leafVal n k =
    if n = 0 then
        k <| Var leafVal
    else
        MakeLong (n-1) (fun l ->
        MakeHuge leafVal (n-1) (fun r ->
        k <| Apply(l,r)))

let huge = MakeHuge 42 5000 (fun x -> x)
let huge2 = MakeHuge 99 5000 (fun x -> x)
printfn "made"

if huge = huge then
    printfn "no stackoverflow"        
if huge <> huge2 then
    printfn "no stackoverflow"
By on 9/2/2009 3:52 PM ()

I did compile in Debug mode but with the Generate Tail Calls CheckBox checked.

I'm pretty sure is generating tail calls because with the checkBox off it crashes well before that, inside one of my functions.

By on 9/2/2009 4:04 PM ()

Hm, if you could create a small repro of this (e.g. along the lines of mine), that would be great; I've not had success so far (but not yet taken time to look at the core library code).

By on 9/2/2009 8:51 PM ()

The following code exposes the same problem.

I believe now that my code crash was caused by storing the tree instance as a key in a dictionary (in an attempt to memoize a function).

Built on VS2008 F# 1.9.6.16 in Release mode.

It crashes, in the same place, with StackOverflow when evaluating the HashCode.

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

type exp = | Var of string

           | Lambda of string * exp

           | Apply of exp * exp

           

let createHugeLambda n = 

   List.fold (fun acc x -> Lambda("f", acc)) (Var "x") [1..n]

let sample = createHugeLambda 100000

let hashCode = sample.GetHashCode()

printf "%i" hashCode
By on 9/3/2009 1:27 AM ()

It seems to work fine on VS2010 Beta 1 (even in debug mode with tail calls turned off ??)

On VS2008 Microsoft F#, May 2009 Community Technology Preview F# Version 1.9.6.16:

It fails with StackOverflow exception both in Release and Debug mode.

By on 9/3/2009 10:40 AM ()

I talked to Don about this, it's By Design; briefly:

- Hashing recursive trees is, in general, hard to get right .

- The easiest thing is to avoid calling "node.GetHashCode()", and instead use "Operators.limitedHash node" or use "LanguagePrimitives.GenericLimitedHash". This will only go a fixed number of nodes 'deep'. If you're using the type in a keyed collection, just supply your own IEqualityComparer to the collection to use limited hashing.

- You can always apply "StructuralComparisonAttribute(false)", override Equals() and GetHashCode(), and take total control of your own destiny.

By on 9/3/2009 11:57 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