为什么年份=年+ 1因堆栈溢出而失败？

Question

year.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检测到无限循环,并决定抱怨它.