非尾部递归函数不会在GHCi中爆炸。为什么？ [英] Non tail-recursive function not blowing up in GHCi. Why?

问题描述

  * Main>< p>让blowwss x = if x == 0 then 0 else（1 + blowwss（x-1））
 * Main> blowwss 1000000 
 1000000 
  

该函数似乎不是尾递归的，所以我想知道我可能会错过什么。 GHCi的堆栈比我想象的要大（我怎么能看到它的堆栈大小，顺便说一句？）。它是否使用某种蹦床来克服这个问题？是否足够聪明可以将函数转换为它的迭代对象？

谢谢

解决方案

GHCi，版本7.6.3：http://www.haskell.org/ghc/：？寻求帮助
加载包ghc-prim ...链接...完成。
加载包integer-gmp ...链接...完成。
加载程序包库...链接...完成。
前奏>让blowwss x = if x == 0 then 0 else（1 + blowwss（x-1））
Prelude> blowwss 1000000
***例外：堆栈溢出

请注意，GHC的堆栈大小限制纯粹是为了防止最可能发生编程错误的情况下的无限/意外深度循环。原则上，堆栈可以无限增长（当然，受系统内存限制）。即使您指定了较大的堆栈大小，堆栈实际上也会启动得更小，但可以增长到极限。目前有关于GHC未来版本可能完全取消限制的讨论。

I was expecting to see my stack blow with the following code.. yet it didn't:

*Main> let blowwss x = if x == 0 then 0 else (1 + blowwss (x-1))
*Main> blowwss 1000000
1000000

The function doesn't seem to be tail-recursive, so I'm wondering what may I be missing. Is GHCi's stack bigger than I thought (how can I see it's stack size, btw?). Is it using some kind of trampoline to get over this? Is it smart enough to convert the function to its iterative counterpart?

Thanks

解决方案

GHCi's stack is bigger than you think. IIRC, the default stack size is 500M for GHCi, whereas the default stack size for a compiled program is currently 8M. You can set a smaller limit yourself to see that you get a stack overflow (or you can increase your argument significantly).

$ ghci +RTS -K1M
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> let blowwss x = if x == 0 then 0 else (1 + blowwss (x-1))
Prelude> blowwss 1000000
*** Exception: stack overflow

Note that GHC has a stack size limit purely to prevent infinite / unexpectedly deep loops in situations that are most likely programming errors. In principle, the stack can grow indefinitely (constrained by the system memory, of course). Even if you specify a large stack size, the stack actually starts much smaller, but can grow up to the limit. There's currently discussion about possibly removing the limit completely in future versions of GHC.

这篇关于非尾部递归函数不会在GHCi中爆炸。为什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！