Stack overflow exception when using pipes in tail-recursive function

Question

I have a naive implementation of a gameloop

let gameLoop gamestate =     
    let rec innerLoop prev gamestate =
        let now = getTicks()
        let delta = now - prev
        gamestate 
        |> readInput delta
        |> update delta
        |> render delta
        |> innerLoop delta             

    innerLoop 0L gamestate

This implementation throws a stackoverflowexception. In my mind this should be tail recursive. I could make a work around like this

let gameLoop gamestate =     
    let rec innerLoop prev gamestate =
        let now = getTicks()
        let delta = now - prev
        let newState = gamestate 
            |> readInput delta
            |> update delta
            |> render delta

        innerLoop now newState

    innerLoop 0L gamestate

So my question is why the first code example throws a stackoverflow exception.

To clarify: does the work-around version you posted work OK? — Peter
@FyodorSoikin I am running on Windows 10 using fsi version 14.0.23413.0 — Xiol
This question might be of interest here. In any case, it may be interesting if the error happens on a debug or release compile, and whether it matters if a debugger is attached. — Vandroiy

kvb kvb · Accepted Answer · 2016-10-20T21:41:24

I think the answer is the same as in the thread Vandroiy links: when you have

a
|> f b

then in debug mode the compiler may compile this like a very literal interpretation of

(f b) a

and explicitly calculate f b in one step and apply it to a in a second step. The call with argument a is still a tail call, but if the compiler doesn't emit the tail. opcode prefix (because tailcalls are turned off, as they are by default in debug mode), then you'll grow the stack with the explicit call and eventually get a stack overflow.

On the other hand, if you write

f b a

directly then this doesn't happen: the compiler does not partially apply f, and instead will recognize that this is a direct recursive call and optimize it into a loop (even in debug mode).

Stack overflow exception when using pipes in tail-recursive function

2 Answers