转换函数以使用尾部递归-正式研究 [英] Converting a function to use tail recursion -- a formal study
问题描述
有人写过一篇正式论文，描述一种(自动)将函数转换为尾递归的方法吗?我正在寻找一种大学级的正式待遇，包括限制(可以转换的功能类型)，转换程序以及(如果可能)正确性证明?Haskell中的示例将是一个奖励.
Has anyone written a formal paper describing a method to (automatically) convert functions to be tail recursive? I am looking for a university-level formal treatment including the limitations (types of functions that can be converted), procedures for conversion, and, if possible, proofs of correctness? Examples in Haskell would be a bonus.
推荐答案
(自动)将函数转换为尾递归的方法?
a method to (automatically) convert functions to be tail recursive?
所以有两部分:
- 认识到可以将给定的递归函数转换为尾递归形式并进行转换
- 以高效的方式实现尾部调用，因此转换值得.
将递归转换为尾递归
在语法上识别尾递归定义似乎相对简单.毕竟，尾递归"只是意味着该调用在语法上出现在表达式的尾部.
It appears relatively straight forward to recognize tail recursive definitions syntactically. After all, 'tail recursive' just means that the call appears syntactically in the tail of the expression.
例如该计划的人们描述:
E.g. the Scheme folks describe:
仅编译适当的自我呼叫，因为跳跃并不足以实现完整的尾递归.相反，我们在语法上将所有源语言中的子表达式位置分为两类:tail(或归约)位置和子问题位置.在简单表达式(如果使用
predicate作为替代)，则predicate是子问题的位置，而结果和替代都在减少职位.这个句法概念可以很容易地扩展到任意嵌套的子表达式.
merely compiling appropriate self-calls as jumps is not suficient to achieve full tail-recursion. Instead, we syntactically divide all sub-expression positions in the source language into two classes: tail (or reduction) position and subproblem position. In the simple expression (if
predicateconsequent alternative), thepredicateis a subproblem position, while both consequent and alternative are in reduction positions. This syntactic notion can be easily extended to arbitrarily nested sub-expressions.
- 将高阶语言编译为完全尾递归便携式C
-
尾部Java虚拟机上的呼叫消除，Michel Schinz Martin Odersky，2001
Tail call elimination on the Java Virtual Machine, Michel Schinz Martin Odersky, 2001
小亨利·贝克(Henry G. Baker)，CONS不应该反对其论点，第二部分:切尼(Cheney)1994年1月的M. T. A.草案版本.
Henry G. Baker, Jr. CONS should not CONS its arguments, part II: Cheney on the M. T. A. Draft Version, January 1994.
这篇关于转换函数以使用尾部递归-正式研究的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
将函数转换为尾调用
问题的棘手部分是用于识别候选递归计算并将其转换为尾递归计算的优化.
The tricky part of your question is optimizations for identifying and transforming candidate recursive computations into tail recursive ones.
GHC中有一个参考文献，它使用内联法和各种简化规则来折叠递归调用，直到它们的底层尾部递归结构保持不变.
One reference is in GHC, which uses inlining and a wide array of simplification rules to collapse away recursive calls, until their underlying tail recursive structure remains.
消除尾声
一旦您以尾部递归形式使用函数，便希望高效地实现该功能.如果您可以生成一个循环，那将是一个很好的开始.如果您的目标计算机没有，那么尾叫消除"将需要一些技巧.引用下面引用的Odersky和Schinz，
Once you have your functions in a tail-recursive form, you'd like to have that implemented effiicently. If you can generate a loop, that's a good start. If your target machine doesn't, then the tail call elimination" will need a few tricks. To quote Odersky and Schinz, cited below,
多年来，人们提出了各种技术来消除一般的(不仅是递归的)尾调用，主要用于编译器定位C.
Various techniques have been proposed over the years to eliminate general (and not only recursive) tail calls, mostly for compilers targeting C.
...将整个程序放在一个大函数中并进行仿真该函数内部使用直接跳转或switch语句进行函数调用.
... put the whole program in a big function and to simulate function calls using direct jumps or switch statements inside this function.
...一种流行的技术是使用蹦床.蹦床是外在的重复调用内部函数的函数.每次内部功能希望尾部调用另一个函数，它不是直接调用它，而是简单地将其身份(例如作为封口)返回到蹦床，然后蹦床自称.这样可以避免无限的堆栈增长，但是可以提高一些性能不可避免地会丢失，主要是因为蹦床发出的所有电话都是电话静态未知功能.
... A popular technique is to use a trampoline. A trampoline is an outer function which repeatedly calls an inner function. Each time the inner function wishes to tail call another function, it does not call it directly but simply returns its identity (e.g. as a closure) to the trampoline, which then does the call itself. Unlimited stack growth is thus avoided, but some performance is inevitably lost, mostly because all the calls made by the trampoline are calls to statically unknown functions.
另一种技巧是亨利·贝克(Henry Baker)的"MT上的钱".用他的技术，程序首先必须转换为连续传递样式(CPS)，因此将所有通话变成尾部通话，然后可以像往常一样编译.在运行时，当堆栈即将溢出时，当前的延续被建立并返回(或加长)到蹦床等待"在调用堆栈的底部.
Another technique is Henry Baker’s "Cheney on the M.T.A." With his technique, the program first has to be converted to continuation passing style (CPS), therefore turning all calls into tail calls, and can then be compiled as usual. At run-time, when the stack is about to overflow, the current continuation is built and returned (or longjmped) to the trampoline "waiting" at the bottom of the call stack.
