将函数转换为使用尾递归——一项正式研究

有没有人写过一篇正式论文描述一种（自动）将函数转换为尾递归的方法？我正在寻找大学级别的正式处理，包括限制（可以转换的函数类型）、转换程序，以及（如果可能）正确性证明？ Haskell 中的例子将是一个额外的好处。

一种（自动）将函数转换为尾递归的方法？

所以这有两个部分：

• 认识到给定的递归函数可以转换为尾递归形式并进行该转换
• 以有效的方式实现尾部调用，因此这种转变是值得的。

将递归转化为尾递归

从语法上识别尾递归定义似乎相对简单。毕竟，“尾部递归”仅意味着调用在语法上出现在表达式的尾部。

例如。计划人员描述：

仅仅编译适当的自调用作为跳转并不足以 实现完全尾递归。相反，我们在语法上划分所有 子表达式在源语言中的位置分为两类：tail （或减少）位置和子问题位置。在简单的 表达式（如果predicate随后的替代方案），predicate是一个 子问题的位置，而结果和替代都在 减仓。这个句法概念可以很容易地扩展到 任意嵌套的子表达式。

• 将高阶语言编译为完全尾递归可移植 C

将函数转换为尾调用

您的问题的棘手部分是识别候选递归计算并将其转换为尾递归计算的优化。

其中一个参考是 GHC，它使用内联和一系列广泛的简化规则来折叠递归调用，直到保留其底层尾递归结构。

• GHC 内衬的秘密

尾部调用消除

一旦您的函数采用尾递归形式，您就希望能够有效地实现它。如果您可以生成一个循环，那就是一个好的开始。如果您的目标机器没有，那么尾调用消除“需要一些技巧。引用下面引用的奥德斯基和辛茨的话：

多年来已经提出了各种技术来消除 一般（不仅是递归）尾部调用，主要用于编译器 瞄准C.

...将整个程序放在一个大函数中并进行模拟 在该函数内使用直接跳转或 switch 语句进行函数调用。

...一种流行的技术是使用蹦床。蹦床是一个外 重复调用内部函数的函数。每次内部函数 希望尾部调用另一个函数，它不会直接调用它，而是简单地调用它 将其身份（例如作为闭包）返回给蹦床，然后蹦床执行 调用自己。因此可以避免无限的堆栈增长，但会降低一些性能 不可避免地会丢失，主要是因为蹦床发出的所有调用都是调用 静态未知函数。

另一种技巧是亨利·贝克（Henry Baker）的“切尼谈 M.T.A.”​​。 使用他的技术，程序首先必须转换为连续传递 风格（CPS），因此将所有调用变成尾调用，然后可以 像往常一样编译。在运行时，当堆栈即将溢出时， 当前的延续被构建并返回（或 longjmped）到蹦床 在调用堆栈的底部“等待”。

• Java 虚拟机上的尾调用消除，米歇尔·辛茨·马丁·奥德斯基，2001

• 小亨利·G·贝克 (Henry G. Baker, Jr.) 反对者不应反对其论点，第二部分：切尼 关于 M.T.A. 草案版本，1994 年 1 月。