转换函数以使用尾递归 - 一个正式的研究

Question

有没有人写过一篇正式的论文,描述了一种(自动)将函数转换为尾递归的方法？我正在寻找大学级的正式治疗方法,包括限制(可以转换的功能类型),转换程序,以及可能的正确性证明？Haskell中的例子将是一个奖励.

Answer 1

(自动)将函数转换为尾递归的方法？

所以这有两个部分:

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

将递归转换为尾递归

在语法上识别尾递归定义似乎相对简单.毕竟,'tail recursive'只意味着调用在语法的尾部出现.

例如,方案人员描述:

仅仅编译适当的自调用,因为跳转不足以实现完整的尾递归.相反,我们在语法上将源语言中的所有子表达式位置划分为两个类:尾(或缩减)位置和子问题位置.在简单表达式中(如果是predicate后续替代方案),则predicate是子问题位置,而后续和替代都处于缩减位置.这种句法概念可以很容易地扩展到任意嵌套的子表达式.

• 将高阶语言编译成完全尾递归的便携式C语言

将函数转换为尾调用

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

GHC中有一个参考,它使用内联和大量简化规则来折叠递归调用,直到它们的底层尾递归结构保持不变.

• GHC内衬的秘密

尾巴呼叫消除

一旦你的函数以尾递归的形式出现,你就希望有效地实现它.如果你能产生一个循环,这是一个好的开始.如果您的目标机器没有,那么尾部调用消除 "将需要一些技巧.引用Odersky和Schinz,如下所述,

多年来已经提出了各种技术来消除一般(并且不仅仅是递归)尾部调用,主要用于针对C的编译器.

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

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

另一种技术是Henry Baker的"在MTA上的切尼"凭借他的技术,程序首先必须转换为延续传递方式(CPS),因此将所有调用转换为尾调用,然后可以像往常一样进行编译.在运行时,当堆栈即将溢出时,将构建当前延续并将其返回(或longjmped)到调用堆栈底部的"等待"蹦床.

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

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

Answer 2

Mercury包含一些优化功能,可以自动使尾部递归.(Mercury是一种强制纯度的逻辑编程语言,因此它讨论谓词而不是函数,但许多相同的思想适用于Mercury程序和Haskell程序.比逻辑而非功能更大的区别在于它是严格而不是懒惰)

"累加器简介"生成具有额外累加器参数的谓词的专用版本,以允许在递归调用之前移动关联操作.显然,这种优化不一定会导致尾递归谓词,但通常会产生一种可以通过第二次优化优化的形式:

"最后调用modulo构造函数"本质上允许递归调用,只有构造函数应用程序才能重写,以便首先构造包含"hole"的值,然后递归调用将其输出直接返回到"hole"的内存地址"而不是使用正常的返回值传递约定.不过,我相信Haskell会因为懒惰而免费获得这种优化.

这两个优化都在文章中提到了使Mercury程序拖尾递归.