Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Stack overflow exception when using pipes in tail-recursive function

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.

like image 967
Xiol Avatar asked Oct 20 '16 20:10

Xiol


1 Answers

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).

like image 116
kvb Avatar answered Nov 16 '22 04:11

kvb