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

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

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

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

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

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

Источник

5 ответов

Решение

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

Итак, вскоре вы научитесь использовать вспомогательную функцию, которая является хвостовой рекурсивной (и принимает текущую сумму, накапливаемую в качестве аргумента), чтобы оптимизатор мог выполнять свою работу, т. Е. За исключением возможного синтаксиса 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);;

Здесь сумма происходит в качестве аргумента для рекурсивного вызова, т. Е. ДО самой рекурсии, и поэтому может включиться оптимизация хвоста (потому что рекурсия - это последнее, что должно произойти!).

Источник

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

Одной из стратегий, которые функциональные языки используют для уменьшения зависимости от рекурсии, является использование оптимизации хвостового вызова. Если вызов следующей рекурсии текущей функции является последним оператором в функции, текущий вызов может быть отброшен из стека, а новый вызов создан на его месте. Сгенерированные инструкции по сборке будут в основном такими же, как и для циклов 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;;
Источник

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

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

Источник

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

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

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

Источник

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

Источник
Другие вопросы по тегам