Являются ли программы на функциональных языках более склонными к переполнению стека?

Question

Я начинаю изучать ocaml и действительно ценю возможности рекурсии в этом языке.Однако меня беспокоит одно — переполнение стека.

Если ocaml использует стек для вызовов функций, не переполнит ли он в конечном итоге стек?Например, если у меня есть следующая функция:

let rec sum x =
  if x > 1 then f(x - 1) + x
  else x;;

в конечном итоге это должно вызвать переполнение стека.Если бы мне пришлось сделать то же самое на C++ (используя рекурсию), я знаю, что это привело бы к переполнению.

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

Answer 1

Все (достойные реализации;-) функциональных языков оптимизируют хвостовую рекурсию, но это не то, что вы делаете здесь, поскольку рекурсивный вызов не является ПОСЛЕДНЕЙ операцией (за ней должно следовать сложение).

Итак, вскоре можно научиться использовать вспомогательную функцию, которая ЯВЛЯЕТСЯ хвостовой рекурсивной (и принимает в качестве аргумента текущую сумму накоплений), чтобы оптимизатор мог выполнять свою работу, то есть за вычетом возможного синтаксиса O'Caml, в котором я заржавел:

let sum x =
  aux(x)(0);;

let rec aux x accum =
  if x > 1 then aux(x - 1)(accum + x)
  else (accum + x);;

Здесь сумма возникает как АРГУМЕНТ рекурсивного вызова, т. е. ДО самой рекурсии, и поэтому может сработать хвостовая оптимизация (потому что рекурсия ЭТО последнее, что должно произойти!).

Answer 2

Функциональные языки обычно имеют НАМНОГО больший стек.Например, я написал функцию специально для проверки ограничений стека в OCaml, и она выполнила более 10 000 вызовов, прежде чем прекратилась.Однако ваша точка зрения имеет место быть.Переполнение стека по-прежнему является тем, на что следует обратить внимание в функциональных языках.

Одной из стратегий, которые функциональные языки используют для уменьшения зависимости от рекурсии, является использование оптимизация хвостового вызова.Если вызов следующей рекурсии текущей функции является последним оператором в функции, текущий вызов может быть удален из стека и на его месте будет создан новый вызов.Создаваемые ассемблерные инструкции будут в основном такими же, как и для циклов while в императивном стиле.

Ваша функция не подлежит оптимизации хвостовым вызовом, поскольку рекурсия не является последним шагом.Сначала ему нужно вернуться, а затем добавить x к результату.Обычно это легко обойти: вы просто создаете вспомогательную функцию, которая передает аккумулятор вместе с другими параметрами.

let rec sum x =
  let sum_aux accum x =
    if x > 1 then sum_aux (accum + x) (x - 1)
    else x
  in sum_aux 0 x;;

Answer 3

Некоторые функциональные языки, такие как Scheme, указывают, что хвостовая рекурсия должен быть оптимизированным, чтобы быть эквивалентным итерации;следовательно, функция хвостовой рекурсии в Scheme никогда не приведет к переполнению стека, независимо от того, сколько раз она повторяется (при условии, конечно, что она также не выполняет рекурсию и не участвует во взаимной рекурсии в других местах, кроме конца).

Большинство других функциональных языков не требуют эффективной реализации хвостовой рекурсии;некоторые предпочитают это делать, другие нет, но это относительно легко реализовать, поэтому я ожидаю, что большинство реализаций так и сделают.

Answer 4

Новичкам, конечно, легко написать глубокую рекурсию, которая взрывает стек.Objective Caml необычен тем, что библиотека List функции не являются стекобезопасными для длинных списков.Такие приложения, как Унисон фактически заменили стандарт Caml List библиотека со стекобезопасной версией.Большинство других реализаций лучше справляются со стеком.(Отказ от ответственности:моя информация описывает Objective Caml 3.08;текущая версия 3.11 может быть лучше.)

Стандартный ML Нью-Джерси необычен тем, что не использует стек, поэтому ваши глубокие рекурсии продолжаются до тех пор, пока у вас не закончится куча.Это описано в замечательной книге Эндрю Аппеля. Компиляция с продолжениями.

Я не думаю, что здесь есть серьезная проблема;это скорее «точка осознания», что если вы собираетесь писать много рекурсивного кода, что вы, скорее всего, будете делать на функциональном языке, вы должны знать о нехвостовых вызовах и размере стека, поскольку по сравнению с размером данных, которые вы будете обрабатывать.

Answer 5

Это сложно — в принципе да, но компиляторы и среды выполнения функциональных языков учитывают повышенную степень рекурсии в функциональных языках.Самый простой из них заключается в том, что большинство сред выполнения функциональных языков запрашивают гораздо больший стек, чем используют обычные итеративные программы.Но в дополнение к этому компилятор функционального языка гораздо лучше способен преобразовать рекурсивный код в нерекурсивный из-за гораздо более строгих ограничений языка.