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

Question

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

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

let () =
    f 0;;

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

и

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

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

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

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

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

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

Answer 3

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