У OCaml нет рекурсивных проверок?

Недавно я играл с OCaml и быстро сделал свою любимую вещь, чтобы проверить, насколько хорошо разработан VM/Compiler, и написал рекурсивную программу:

let rec f i =
    Printf.eprintf "i = %d\n" i;
    f(i+1);;

let () =
    f 0;;

Программа работает так, как ожидалось, однако рекурсия НИКОГДА ломается, infact, у меня была эта программа, работающая несколько раз (примерно 30 минут), перенаправленная stderr в файл, чтобы избежать засорения моего Терминал. После проверки файла я был в недоумении, когда заметил, что файл был около 7 * ГБ * большой!

Как это может быть? Разве OCaml не имеет пределов рекурсии?

Ответы

Ответ 1

Вы должны искать информацию о оптимизации хвоста.

Чтобы ответить на ваш вопрос, существует ограничение на стек, которое было бы достигнуто вашей программой, если бы стек увеличивался.

Вы не должны ожидать, что достигнете его с помощью своей программы больше, чем вы ожидали бы деления на ноль в бесполезном выражении в программе на C, чтобы всегда производить деление на ноль после компиляции: компилятор может удалить бесполезное деление. В вашем примере компилятор удалил бесполезное переполнение стека.

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

Ответ 2

Паскаль правильный, но я думаю, что больше объяснений в порядке, потому что есть пределы.

OCaml реализует рекурсию хвостового вызова. Если возвращаемое значение функции полностью является результатом вызова функции, тогда вызов может быть оптимизирован. Рассмотрим эти два фрагмента кода:

let rec foo i = 
  i * foo(i-1)

let rec bar i j = 
  bar(i - 1, j * i)

Они оба вычисляют одно и то же (и ни один из них не заканчивается). Однако первый вызовет переполнение стека, а второй - нет. Зачем? Потому что foo выполняет вычисления с результатом вызова функции. Это означает, что значение, которое нужно сохранить в стеке, пока не вернется foo (i-1). С другой стороны, результат бара является результатом строки вызова (i-1, j * i) без изменений. Нет ничего, что должно быть сохранено в стеке.

Визуализируйте его таким образом. Пусть говорят, что мы начинаем с я = 3 (и j = 1). Foo будет выглядеть так:

foo(3)
  3 * foo (2)
    2 * foo (1)

и bar будет выглядеть так:

bar (3, 1)
bar (2, 3)
bar (1, 6)

Ответ 3

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