10

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

4

2 回答 2

7

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

所以这有两个部分：

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

将递归转换为尾递归

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

例如，计划人员描述：

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

将函数转换为尾调用

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

一个参考是在 GHC 中，它使用内联和一系列简化规则来折叠递归调用，直到它们的底层尾递归结构仍然存在。

尾声消除

一旦你有你的函数在一个尾递归的形式，你希望有效率地实现它。如果你可以生成一个循环，那就是一个好的开始。如果您的目标机器没有，那么尾调用消除“将需要一些技巧。引用下面引用的 Odersky 和 ​​Schinz，

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

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

... 一种流行的技术是使用蹦床。蹦床是重复调用内部函数的外部函数。每次内部函数希望尾调用另一个函数时，它不会直接调用它，而只是将其标识（例如作为闭包）返回给蹦床，然后蹦床自己进行调用。因此避免了无限的堆栈增长，但不可避免地会损失一些性能，主要是因为蹦床所做的所有调用都是对静态未知函数的调用。

另一种技术是Henry Baker 的“Cheney on the MTA” 使用他的技术，程序首先必须转换为连续传递样式（CPS），因此将所有调用转换为尾调用，然后可以像往常一样编译。在运行时，当堆栈即将溢出时，当前的延续被构建并返回（或 longjmped）到调用堆栈底部的蹦床“等待”。

  • Java 虚拟机上的尾调用消除，Michel Schinz Martin Odersky，2001

  • Henry G. Baker, Jr. CONS 不应该反对其论点，第二部分：切尼谈 MTA 草案版本，1994 年 1 月。

于 2012-05-22T11:57:18.573 回答
6

Mercury 包含一些自动使事物尾递归的优化。（Mercury是一种强制纯逻辑编程语言，因此它讨论的是谓词而不是函数，但是许多相同的想法适用于 Mercury 程序和 Haskell 程序。与逻辑而非函数相比，更大的区别在于它是严格而不是懒惰）

“累加器介绍”使用额外的累加器参数生成谓词的专用版本，以便允许在递归调用之前移动关联操作。显然，这种优化不一定会导致尾递归谓词本身，但通常会导致可以通过第二次优化优化的形式：

“Last call modulo constructors”本质上允许一个递归调用，该调用之后只有构造函数应用程序被重写，这样首先构造的值包含一个“洞”，然后递归调用将其输出直接返回到“洞”的内存地址" 而不是使用正常的返回值传递约定。然而，我相信 Haskell 会因为懒惰而免费获得这种优化。

这两种优化都在论文使 Mercury 程序尾递归中进行了描述。

于 2012-05-22T13:11:23.343 回答