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

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

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

let () =
    f 0;;

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

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

Источник

3 ответа

Решение

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

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

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

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

Источник

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

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(3)
  3 * foo (2)
    2 * foo (1)

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

bar (3, 1)
bar (2, 3)
bar (1, 6)
Источник

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

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