Разве в OCaml нет проверки рекурсии?

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

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

let () =
    f 0;;

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

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


functional-programming ocaml tail-recursion
person Community    schedule 04.02.2011    source источник
comment
@Pascal Cuoq: Вы должны опубликовать это как ответ, чтобы я мог его принять ;-)   -  person    schedule 04.02.2011

Ответы (3)


arrow_upward
15
arrow_downward

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

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

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

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

person Pascal Cuoq    schedule 04.02.2011
comment
И если подумать об этом по-другому: поскольку рекурсия является стандартной конструкцией цикла в функциональных языках, предел рекурсии в OCaml будет эквивалентен ограничению на количество циклов, которое может выполняться в C или Python. - person Michael Ekstrand; 04.02.2011
comment
Только если функция является хвостовой рекурсией, иначе она переполнится стеком за исключением цикла - person 0xFF; 05.02.2011

arrow_upward
4
arrow_downward

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

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

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

а также

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

Оба они вычисляют одно и то же (и ни один из них не заканчивается). Однако первое вызовет переполнение стека, а второе — нет. Почему? Потому что foo выполняет вычисления с результатом вызова функции. Это означает, что значение, которое мне нужно хранить в стеке, пока не вернется foo (i - 1). С другой стороны, результат bar является результатом вызова 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)
person Steve Rowe    schedule 13.02.2011

arrow_upward
0
arrow_downward

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

person rlibby    schedule 04.02.2011