compiler-construction - 转换函数以使用尾递归-正式研究

Question

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

Answer 1

a method to (automatically) convert functions to be tail recursive?

因此，这包括两个部分:

认识到可以将给定的递归函数转换为尾递归形式，然后进行转换

以有效的方式实现尾部调用，因此转换值得。

将递归转换为尾递归

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

例如。该计划的人们描述:

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 predicate consequent alternative), the predicate is a subproblem position, while both consequent and alternative are in reduction positions. This syntactic notion can be easily extended to arbitrarily nested sub-expressions.

Compiling Higher-Order Languages into Fully Tail-Recursive Portable C

将函数转换为尾调用

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

一个引用是在GHC中，它使用内联和各种各样的简化规则来折叠递归调用，直到它们的基本尾部递归结构保留下来。

Secrets of the GHC inliner

消除尾叫

一旦您以尾递归形式使用函数，便希望有效地实现该功能。如果您可以生成一个循环，那将是一个很好的开始。如果您的目标机器不需要，那么tail call elimination“将需要一些技巧。下面引用Odersky和Schinz，

Various techniques have been proposed over the years to eliminate general (and not only recursive) tail calls, mostly for compilers targeting C.

... 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.

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.

Tail call elimination on the Java Virtual Machine，Michel Schinz Martin Odersky，2001

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