函数式编程语言中的相互递归函数

Question

单个递归函数可以应用尾部递归优化，以防止堆栈溢出，但相互递归的函数呢？

这个答案展示了如何在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中，任何类型的值都可以递归定义。