Почему Перл так боится "глубокой рекурсии"?

Недавно я наткнулся на книгу Perl более высокого порядка, которая в основном предлагает способы сделать что-то в Perl функциональным способом. Автор объясняет, что Perl имеет 6 из 7 основных функций Lisp, а C не имеет.

У меня была проблема, которая выглядела как хороший кандидат для рекурсивного решения, и я закодировал ее таким образом. Но Перл жаловался на "глубокую рекурсию". Я немного погуглил и нашел монаха Perl, объяснив, что "Perl не Haskell". По-видимому, вы получаете жалобу по умолчанию, когда глубина рекурсии превышает 100 уровней.

Есть способы расширить этот предел или полностью отключить его, но мой вопрос:

Есть ли причина, по которой Perl настолько возмущен рекурсией, в то время как Haskell не является вообще?

Ответ 1

Потому что в Haskell у нас есть лень и охраняемая рекурсия и оптимизация хвостовых вызовов, и у Perl нет ни одного.

Это по существу означает, что каждый вызов функции выделяет заданный объем памяти, называемый "стек", пока функция не вернется. Когда вы пишете рекурсивный код, вы создаете огромный объем памяти из-за этих вложенных вызовов функций и в конечном итоге можете переполнять стек. TCO позволяет оптимизировать неиспользуемые куски.

Без этого не стоит полагаться на рекурсию. Например, скажем, вы написали рекурсивную версию map, она бы разбилась с любым приличным размером списка. В Haskell охраняемая рекурсия означает, что с большими списками рекурсивное решение намного быстрее, чем функция типа "loop".

TL;DR: реализация Haskell предназначена для обработки функционального/рекурсивного стиля, а реализация perl не верна и в старые добрые времена, 100 уровней вызовов функций были разумным пределом.

Ответ 2

Предупреждение о "глубокой рекурсии" является необязательным и индикатором того, что что-то пошло не так: большую часть времени функция, вызывающая себя снова и снова, не предназначена (Perl - это язык с несколькими парадигмами, и многие люди не используют функциональные идиомы). И даже если сознательно использовать рекурсию, слишком легко забыть базовый случай.

Легко отключить предупреждение "глубокой рекурсии":

use warnings;
no warnings 'recursion';

sub recurse {
  my $n = shift;
  if ($n) {
    recurse($n - 1);
  }
  else {
    print "look, no warnings\n";
  }
}

recurse(200);

Вывод:

look, no warnings

Верно, что Perl не выполняет оптимизацию хвостовой рекурсии, потому что это испортит вывод caller (что жизненно важно для некоторых вещей, таких как прагмы или Carp). Если вы хотите вручную выполнить хвостовой вызов, то

return foo(@args);

становится

@_ = @args; # or something like `*_ = \@args`
goto &foo;

хотя плохие вещи могут произойти, если вы неразумно local ized @_.

Ответ 3

Ограничение по умолчанию слишком низкое, но оно подходит для небольших машин, на которых первоначально выполнялся Perl. Теперь 100 смешно, если вы делаете серьезную рекурсивную работу, но, как вы говорите, ее можно настроить. Я предполагаю, что у Haskell есть еще один способ поймать бесконечную рекурсию?