在尾递归函数中使用管道时发生堆栈溢出异常

Question

我有一个简单的游戏循环实现

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

此实现抛出一个 Whosebugexception。在我看来，这应该是尾递归。我可以像这样解决

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

所以我的问题是为什么第一个代码示例抛出 Whosebug 异常。

Answer 1

我认为这就是解释，尽管我鼓励 F# 编译器专家在我偏离基础时权衡一下：

第一个例子不是尾递归的，因为尾部的表达式是对 |> 的调用，而不是对 innerLoop.

的调用

回顾|>定义为

let (|>) x f = f x

如果我们稍微去除管道语法的糖分，当您调用

gamestate 
    |> readInput delta
    |> update delta
    |> render delta
    |> innerLoop delta

你实际上是在调用：

|> (innerLoop delta) (|> (render delta) (|> (update delta) (|> (readInput delta) gamestate)))

作为你在递归函数中的正文表达式。

中缀符号有点模糊了这一点，使它看起来像 innerLoop 在尾部位置。

Answer 2

我认为答案与线程 Vandroiy 链接中的答案相同：当你有

a
|> f b

然后在调试模式下，编译器可能会像对

的非常直白的解释一样编译它

(f b) a

并在第一步中显式计算 f b，然后在第二步中将其应用于 a。带参数 a 的调用仍然是尾调用，但如果编译器不发出 tail. 操作码前缀（因为尾调用已关闭，因为它们在调试模式下默认处于关闭状态），那么您将通过显式调用增加堆栈并最终导致堆栈溢出。

另一方面，如果你写

f b a

直接那么这不会发生：编译器不会部分应用 f，而是会识别这是一个直接的递归调用并将其优化为一个循环（即使在调试模式下）。

在尾递归函数中使用管道时发生堆栈溢出异常

Stack overflow exception when using pipes in tail-recursive function

f#

tail-recursion