将 "almost tail position" 中的递归调用移动到真正的尾部位置

Question

在阅读Guido's reasoning for not adding tail recursion elimination to Python时，我在Haskell中编造了这个几乎是尾递归的例子：

triangle :: Int -> Int
triangle 0 = 0
triangle x = x + triangle (x - 1)

这当然不是尾调用，因为尽管递归调用本身在 "return" 中，但 x + 阻止了当前堆栈被重新用于递归调用。

但是，可以将其转换为尾递归代码（尽管相当丑陋和冗长）：

triangle' :: Int -> Int
triangle' = innerTriangle 0
    where innerTriangle acc 0 = acc
          innerTriangle acc x = innerTriangle (acc + x) (x - 1)

这里 innerTriangle 是尾递归的，由 triangle' 启动。虽然微不足道，但似乎这样的转换也适用于其他任务，例如构建列表（这里 acc 可能只是正在构建的列表）。

当然，如果函数中没有递归调用return，这似乎是不可能的：

someRecusiveAction :: Int -> Bool
someRecursiveAction x = case (someRecursiveAction (x * 2)) of
    True -> someAction x
    False -> someOtherAction x

但我仅指的是 "almost tail" 调用，其中递归调用是 return 值的一部分，但由于另一个函数应用程序包装它（例如上面 triangle 示例中的 x +。

这在功能上下文中是否可以概括？强制性的呢？所有在 return 中具有递归调用的函数都可以转换为在尾部位置具有 return 的函数（即可以优化尾调用的函数）吗？

没关系，其中 none 是计算 Haskell 中三角形数的 "best" 方法，AFAIK 是 triangle x = sum [0..n] .该代码纯粹是这个问题的人为示例。

注意： 我已经阅读了 Are there problems that cannot be written using tail recursion?，所以我相当有信心我的问题的答案是肯定的。但是，答案提到了延续传球风格。除非我误解了 CPS，否则我转换后的 triangle' 似乎仍然是直接样式。在这种情况下，我很好奇能否以直接方式推广这种转换。

Answer 1

有一个有趣的 space 尾递归模运算符优化可以转换一些函数，使它们运行保持常量 space。可能最著名的是 tail-recursion-modulo-cons，其中 not quite tail call 是构造函数应用程序的参数。（这是一个古老的优化，可以追溯到 Prolog 编译器的早期——我认为 Warren Abstract Machine fame 的 David Warren 是第一个发现它的人）。

但是，请注意此类优化不太适合惰性语言。像 Haskell 这样的语言有非常不同的评估模型，其中尾调用并不那么重要。在 Haskell 中，包含递归调用的构造函数应用程序可能是可取的，因为它会阻止立即评估递归调用并允许延迟使用计算。请参阅 this HaskellWiki page 上的讨论。

这是一个用严格语言进行模优化的候选示例：

let rec map f = function
  | [] -> []
  | x::xs -> f x::map f xs

在这个 OCaml 函数中，对 map 的递归调用是尾部位置构造函数应用程序的参数，因此可以应用模优化。（OCaml 还没有做这个优化，尽管有一些实验性的补丁在浮动。）

转换后的函数可能类似于以下伪 OCaml。请注意，内部循环是尾递归的，并且通过改变先前的缺点来工作：

let rec map f = function
  | [] ->
  | x::xs ->
    let rec loop cons = function
      | [] -> cons.[1] <- []
      | y::ys ->
        let new_cons = f y::NULL in
        cons.[1] <- new_cons;
        loop new_cons ys in
    loop (f x::NULL) xs

（其中 NULL 是 GC 不会阻塞的一些内部值。）

通过不同的机制，尾部构造在 Lisp 中也很常见：突变往往被显式编程，而杂乱的细节隐藏在宏中，例如 loop.

如何推广这些方法是一个有趣的问题。

将 "almost tail position" 中的递归调用移动到真正的尾部位置

Moving recursive calls in "almost tail position" to true tail position

recursion

functional-programming

theory

tail-recursion

compiler-theory