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

Question

Одна рекурсивная функция может использовать оптимизацию хвостовой рекурсии для предотвращения переполнения стека, но как насчет взаимно-рекурсивных функций?

Это answer показывает, как определить взаимно рекурсивные функции в F #:

let rec F() = 
    G() 
and G() = 
    F() 

Это определено таким образом, чтобы генерируемый родной машинный код или байт-код будет состоять в конечном счете, только одна функция с оптимизацией хвостовой рекурсии применяется как для F, так и для G? Это предотвратит переполнение стека?

Как работает алгоритм работы с хвостом для взаимно рекурсивных функций?

С другой стороны, Haskell не нуждается в таком синтаксисе. Это из-за ленивой оценки Хаскелла? Или, как предлагает @augustss, компиляторы Haskell также выполняют те же действия, что и выше?

Answer 1

Функциональные языки обычно выполняют так называемую оптимальную оптимизацию хвостовых вызовов, которая полностью не зависит от рекурсии. Любой вызов оптимизирован в прыжок, будь то рекурсивный вызов, вызов ранее определенной функции, частично примененная функция или даже вызов функции первого класса. Например:

g x = let y = 2*x in abs x -- tail call 
add x = (+) x -- tail call 
apply f x = f x -- tail call 

F # должен быть в состоянии сделать все, что, так как CLR имеет инструкцию хвостовая (несмотря на то, что было известно, медленно).

Answer 2

Поскольку F # находится в семействе ML, я предполагаю, что это довольно простой вопрос: простое let просто не является рекурсивным, а взаимно рекурсивные функции должны быть связаны вместе let rec. Это упрощает анализ компилятора в определенной степени. В Haskell компилятор заканчивает разбиение кода на аналогичные блоки, как для поддержки вывода типа, так и для выполнения оптимизации. Способ ML, возможно, более предсказуем. Я не думаю, что любой подход по своей сути лучше.

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