Stack overflow despite tail call position but only in 64-bit

Question

Originated from this question, I have this little F# code (github) to generate random values according to a normal distribution:

// val nextSingle : (unit -> float32)
let nextSingle =
    let r = System.Random()
    r.NextDouble >> float32

// val gauss : (float32 -> float32 -> seq<float32>)
let gauss mean stdDev =
    let rec gauss ready = seq {
        match ready with
        | Some spare ->
            yield spare * stdDev + mean
            yield! gauss None
        | _ ->
            let rec loop () =
                let u = nextSingle() * 2.f - 1.f
                let v = nextSingle() * 2.f - 1.f
                let s = pown u 2 + pown v 2
                if s >= 1.f || s = 0.f then loop() else
                u, v, s
            let u, v, s = loop()
            let mul = (*)(sqrt(-2.f * log s / s))
            yield mul u * stdDev + mean
            yield! mul v |> Some |> gauss
    }
    gauss None

To me it seems that this should only call itself in tail call position, ergo never cause a StackOverflowException when TCO is enabled. But it does when running 64-bit. It does not when running 32-bit (i.e. “Prefer 32-bit” checkbox in project settings).

I'm using .NET Framework 4.5.2 and F# 4.4.0.0.

Can somebody explain what is causing the problem?

Mcniel

Which .NET version are you using? – Matri

I found these articles talking about tail call optimization using .NET 2.0 vs using .NET 4.0, maybe they can help. – Matri

Also what version of F# are you using? I use F#4 and when debugging I don't see stack growing at all. I disassembled the IL code and it looks like the code F#4 generate shouldn't stackoverflow. – Niccolo

Please include a full repro. What does the calling code look like? "Tail recursion" in a sequence expression can be confusing, because the sequence does not actually advance itself, some other code does. – Beta

Answer 1

Looks like a bug in the compiler's sequence expression compilation mechanism. Here's a simplified repro:

let rec loop r = seq {
    if r > 0 then
        let rec unused() = unused()
        yield r
        yield! loop r
}

printfn "%i" (Seq.nth 10000000 (loop 1))

Obviously the presence of the unused recursive definition shouldn't affect whether this generates a stack overflow, but it does.

Beta

I've filed this as an issue on GitHub. – Beta

Was it intuitive or unintuitive reasoning that lead to the problem? I am interested to know if it was just basic problem solving using IL inspection combined with factoring down to the minimal which I can do using VS community edition, or did you make use of something more? I am trying to improve my ability to resolve TCO problems. If you want this as a separate SO question I will be happy make it such. Also which version of the code did you start from, the GitHub full, GitHub minimal, or the example in the question, as I want to figure it out independently. – Stokowski

@GuyCoder - My reasoning was something like this: Talking about "tail calls" when looking at a computation expression can be misleading - there really isn't such a thing (see e.g. https://mcmap.net/q/829802/-why-is-this-f-sequence-function-not-tail-recursive for one related discussion, though not related to sequence expressions). So something like gauss will not itself ever overflow the stack, only the code calling it could make it overflow. – Beta

@GuyCoder - But once I saw that the calling code was just something like Seq.nth, that meant that there was almost certainly a compiler bug, because the pattern of "tail yield!ing" in a sequence expression is supposed to get optimized (not sure if this is part of the spec, but I think it's fairly well known). So then it was just a case of seeing what parts of the initial repro were necessary. Replacing loop in the original code with a non-recursive definition made the repro stop failing, as did removing the pattern match. – Beta

@GuyCoder - I didn't find looking at the IL helpful (there's so much compiler-generated machinery involved in the compilation of sequence expressions), I just tried minimizing the repro at the source level and empirically testing the behavior. – Beta

Thanks. If I make this a separate SO question can you post this as the answer. I think it worth sharing as comments do not show up in searches. – Stokowski

Sure, I'd be happy to. – Beta

I posted the question as What reasoning lead to the answer for Sequence expression containing recursive definition is compiled incorrectly but feel free to edit the title, question and tags, I view it all as CC. – Stokowski