Функция без хвостовой рекурсии не взрывается в GHCi. Почему?

Я ожидал, что мой стек взорвется со следующим кодом... но этого не произошло:

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

Функция не кажется хвостовой рекурсией, поэтому мне интересно, что я могу упустить. Стек GHCi больше, чем я думал (кстати, как я могу увидеть его размер стека?). Он использует какой-то батут, чтобы преодолеть это? Достаточно ли он умен, чтобы преобразовать функцию в ее итеративный аналог?

Спасибо


functional-programming haskell ghci tail-recursion
person devoured elysium    schedule 01.12.2013    source источник
comment
попробуй blowwss 99999999999999999999999999999999999999   -  person Ingo    schedule 01.12.2013
comment
Обратите внимание, что вам обычно не нужна хвостовая рекурсия в Haskell для достижения пространственной сложности O (1). Например. бесконечный ленивый список может быть использован прямо на месте, и на каждый созданный преобразователь один удаляется сборщиком мусора. И наоборот, функции хвостовой рекурсии также могут взорвать стек, если они недостаточно строгие, потому что сам хвостовой вызов просто помещается в стек. — Лучший способ справиться с такими проблемами — не вообще писать явную рекурсию, а полагаться, например, на складок с известными свойствами строгости.   -  person leftaroundabout    schedule 01.12.2013
comment
Я не понял. функции хвостовой рекурсии также могут взорвать стек, если они недостаточно строгие, потому что сам хвостовой вызов просто помещается в стек. Я думал, что компилятор перепишет функцию хвостового вызова как ее итеративный аналог?   -  person devoured elysium    schedule 01.12.2013
comment
@devouredelysium проверьте haskell.org/haskellwiki/Tail_recursion и blog.sigfpe.com/2007/07/data-and-codata.html.   -  person jberryman    schedule 01.12.2013

Ответы (2)


arrow_upward
8
arrow_downward

Стек GHCI больше, чем вы думаете. IIRC, размер стека по умолчанию составляет 500 МБ для GHCi, тогда как размер стека по умолчанию для скомпилированной программы в настоящее время составляет 8 МБ. Вы можете установить меньший предел самостоятельно, чтобы увидеть, что вы получаете переполнение стека (или вы можете значительно увеличить свой аргумент).

$ 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

Обратите внимание, что GHC имеет ограничение на размер стека исключительно для предотвращения бесконечных/неожиданно глубоких циклов в ситуациях, которые, скорее всего, являются ошибками программирования. В принципе, стек может расти бесконечно (разумеется, ограниченный системной памятью). Даже если вы укажете большой размер стека, на самом деле стек будет намного меньше, но может вырасти до предела. В настоящее время обсуждается возможность полного снятия ограничения в будущих версиях GHC.

person kosmikus    schedule 01.12.2013
comment
Вы случайно не знаете, почему размер стека GHCi больше, чем у скомпилированных по умолчанию программ? - person Thomas Eding; 03.12.2013
comment
@ThomasEding Нет, я действительно не знаю. Но кажется, что между GHC/GHCi и программами, которые он интерпретирует, нет разделения по размеру стека, и, по крайней мере, его трудно изменить изнутри GHCi во время сеанса, поэтому высокое значение по умолчанию кажется разумным. - person kosmikus; 03.12.2013

arrow_upward
1
arrow_downward

Вы использовали слишком маленькое значение для этого. Я перенес вашу функцию в отдельный файл

blowwss x = if x == 0 then 0 else (1 + blowwss (x-1))

main = do
  print $ blowwss 10000000000
  print $ blowwss 10000000000000

а затем скомпилировать и запустить

[mihai@esgaroth tmp]$ ghc --make 1.hs
[1 of 1] Compiling Main             ( 1.hs, 1.o )
Linking 1 ...
[mihai@esgaroth tmp]$ ./1
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

Запустив это в GHCI, я получаю высокую нагрузку, а затем переполнение стека. Это потому, что стек GHCi выше, я думаю, где-то около 512M.

person Mihai Maruseac    schedule 01.12.2013