在函数式语言中，编译器如何将非尾递归转换为循环以避免堆栈溢出（如果有的话）？

Question

我最近一直在学习函数式语言以及有多少不包含 for 循环。虽然我个人并不认为递归比 for 循环更难（而且通常更容易推理），但我意识到许多递归示例不是尾递归，因此不能使用简单的尾递归优化来避免堆栈溢出。 According to this question, all iterative loops can be translated into recursion, and those iterative loops can be transformed into tail recursion, so it confuses me when the answers on a question like this 建议如果您想避免堆栈溢出，您必须自己明确管理递归到尾递归的转换。似乎编译器应该可以完成从递归到尾递归的所有转换，或者从递归直接到迭代循环的所有转换，而不会出现堆栈溢出。

函数式编译器是否能够在更一般的递归情况下避免堆栈溢出？您是否真的被迫自己转换递归代码以避免堆栈溢出？如果他们不能执行一般的递归堆栈安全编译，他们为什么不能？

Answer 1

According to this question, all iterative loops can be translated into recursion

"Translated" 可能有点牵强。如果你理解图灵完备性，证明每个迭代循环都有一个等效的递归程序是微不足道的：因为图灵机可以使用严格的迭代结构和严格的递归结构来实现，所以每个可以用迭代语言表达的程序都可以表达在递归语言中，vice-versa。这意味着对于每个迭代循环，是一个等效的递归结构（反之亦然）。然而，这并不意味着我们有一些自动的方法将一个转换成另一个。

and those iterative loops can be transformed into tail recursion

尾递归也许可以很容易地转化为迭代循环，反之亦然。但并不是所有的递归都是尾递归。这是一个例子。假设我们有一些二叉树。它由 node 组成。每个 node 可以有一个 left 和一个 right child 和一个 value。如果一个节点没有 children，则 isLeaf returns 为真。我们假设有一些函数 max 是 returns 两个值的最大值，如果其中一个值是 null 它 returns 另一个。现在我们要定义一个函数来查找所有叶节点中的最大值。这是我做的pseudo-code

findmax(node) {
    if (node == null) {
        return null
    }
    if (node.isLeaf) {
        return node.value
    } else {
        return max(findmax(node.left), findmax(node.right))
    }
}

max 函数中有两次递归调用，所以我们无法针对尾递归进行优化。在将它们提供给 max 函数并确定当前节点的调用结果之前，我们需要两者的结果。

现在，可能有一种方法可以获得相同的结果，即使用递归且仅调用一次 tail-recursive。它在功能上是等效的，但它是一种不同的算法。编译器可以做很多转换来创建功能等效的程序并进行大量优化，但它们还不够聪明，无法创建功能等效的算法。

即使将仅递归调用一次自身的函数转换为 tail-recursive 版本也绝非易事。这种改编通常使用一些参数传递给递归调用，用作当前结果的 "accumulator"。

查看下一个计算数字阶乘的简单实现（例如 fact(5) = 5*4*3*2*1）：

fact(number) {
    if (number == 1) {
        return 1
    } else {
        return number * fact(number - 1)
    }
}

不是tail-recursive。但是可以这样制作：

fact(number, acc) {
    if (number == 1) {
        return acc
    } else {
        return fact(number - 1, number * acc)
    }
}
// Helper function
fact(number) {
    return fact(number, 1)
}

这需要对正在做的事情进行解释。识别这种情况很容易，但是如果您调用函数而不是乘法怎么办？编译器如何知道对于初始调用，累加器必须为 1 而不是 0？你如何翻译这个程序？

recsub(number) {
    if (number == 1) {
        return 1
    } else {
        return number - recsub(number - 1)
    }
}

到目前为止，这超出了我们现在拥有的那种编译器的范围，事实上可能永远都是。

也许在 computer science Stack Exchange 上问这个问题会很有趣，看看他们是否知道一些对此进行更多研究的论文或证明 in-depth。

Answer 2

尾调用优化：

进行参数和调用的自然方式是在退出或返回时整理清理。

要使尾调用起作用，您需要对其进行更改，以便尾调用继承当前帧。因此，它不会创建一个新框架，而是对框架进行按摩，以便下一次调用 returns 到当前函数调用者而不是这个函数，如果它是尾调用，它实际上只会清理和 returns。

因此 TCO 就是最后一次调用之前的清理。

Continuation Passing Style - 对所有内容进行尾调用

编译器可以更改代码，使其仅执行原始操作并将其传递给延续。因此，由于要继续的计算成为一个函数，因此堆栈使用被移到堆上。

一个例子是：

function hypotenuse(k1, k2) {
  return sqrt(add(square(k1), square(k2)))
}

变成

function hypotenuse(k, k1, k2) {
  (function (sk1) {
    (function (sk2) {
      (function (ar) {
         k(sqrt(ar));
      }(add(sk1,sk2));
    }(square(k2));
  }(square(k1));
}

注意现在每个函数只有一次调用并且评估顺序已设置。

Answer 3

任何递归函数都可以转换为尾递归函数。例如，考虑图灵机的转换函数，即是从一个配置到下一个配置的映射。模拟图灵机你只需要迭代转换函数直到你达到了最终状态，这很容易用尾递归表示形式。同样，编译器通常将递归程序翻译成一个迭代的，只是添加一堆激活记录。

你也可以使用continuation 翻译成尾递归形式传球风格（CPS）。举一个经典的例子，考虑斐波那契功能。这可以通过以下方式用 CPS 样式表示，其中第二个参数是延续（本质上是一个回调函数）：

def fibc(n, cont):
    if n <= 1:
        return cont(n)
    return fibc(n - 1, lambda a: fibc(n - 2, lambda b: cont(a + b)))

同样，您正在使用动态数据结构模拟递归堆栈：在这种情况下，lambda 抽象。

在所有以前的动态结构（列表、堆栈、函数等）中的使用例子是必不可少的。也就是说，为了模拟一个泛型递归函数迭代，你无法避免动态内存分配，因此，您通常无法避免堆栈溢出。

因此，内存消耗不仅与iterative/recursive有关程序的性质。另一方面，如果你阻止动态内存分配，你的程序本质上是有限状态机，具有有限的计算能力功能（更有趣的是根据输入的维度）。

一般来说，就像你无法预测终止一样，你也不能预测程序的未绑定内存消耗：使用编译时的图灵完备语言发散无法避免，栈溢出也无法避免

在函数式语言中，编译器如何将非尾递归转换为循环以避免堆栈溢出（如果有的话）？

In functional languages, how is the compiler able to translate non-tail recursion into loops to avoid stack overflows (if at all)?

recursion

functional-programming

compiler-construction

compiler-optimization

tail-recursion

尾调用优化：

Continuation Passing Style - 对所有内容进行尾调用