haskell - 为什么 year=year+1 不会因堆栈溢出而失败？

Question

年.hs:

year = year + 1

main = print year

这不是尾递归调用:

year = year + 1
year = (year + 1) + 1
year = ((year + 1) + 1) + 1
...

然而 runhaskell year.hs不输出任何东西，这表明它进入了无限循环。

Haskell 编译器是否对非尾递归调用进行优化？

Answer 1

因为懒惰(加上单态限制†)。基本上当你说

year = year + 1

然后评估 year , Haskell 为结果节省空间，然后当它看到 year它试图重用相同的结果。所以当 year + 1试图评估 year , year 的代码实际上并没有进入。

在 GHC 中，为了实现多线程‡，它实际上所做的是在当前线程尝试获取已经被评估的变量的值时阻塞当前线程。然后，当评估完成时，它会继续执行被阻塞的线程。在这种情况下，线程在它自己正在执行的评估中被阻塞，这就是你得到死锁的原因。

如果你改为说

year () = year () + 1

然后运行 ​​ year ()确实给我一个堆栈溢出。

† 单态限制开始发挥作用，因为如果你添加一个类型签名

year :: Num a => a
year = year + 1

编译器完全可以自由处理 Num a像 () 这样的字典参数，产生堆栈溢出。在这种情况下，这并不是真正的问题，但不缓存中间结果是实际计算中的一个大问题。在这种情况下，看起来 GHC 实际上是将递归放入字典的抽象中，生成的代码更像

year () = let y = y + 1 in y

这也不会产生堆栈溢出。

‡ 在单线程模式下编译代码(使用 GHC)产生

<<loop>>

这意味着 GHC 检测到无限循环并决定提示它。