recursion - 将 "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)

这当然不是尾调用，因为虽然递归调用本身位于“返回”中，但 x + 阻止当前堆栈被重用于递归调用。

但是，我们可以将其转换为尾递归代码(尽管相当丑陋且冗长):

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

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

当然，如果函数返回中没有递归调用，这似乎不可能:

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

但我仅指“几乎尾部”调用，其中递归调用是返回值的一部分，但由于另一个函数应用程序包装了它而不位于尾部位置(例如上面 x + 示例中的 triangle )。

这可以在函数上下文中推广吗？如果是命令式的呢？所有返回值中包含递归调用的函数都可以转换为返回值位于尾部位置的函数(即可以进行尾部调用优化的函数)吗？

没关系，这些都不是在 Haskell 中计算三角形数的“最佳”方法，据我所知是 triangle x = sum [0..n] 。该代码纯粹是针对此问题的人为示例。

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

Answer 1

有一个有趣的尾递归模运算符优化空间，可以转换某些函数，使其在恒定空间中运行。可能最知名的是 tail-recursion-modulo-cons ，其中不完全尾部调用是构造函数应用程序的参数。 (这是一个古老的优化，可以追溯到 Prolog 编译器的早期 - 我认为 Warren Abstract Machine 名声大噪的 David Warren 是第一个发现它的人)。

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

以下是严格语言中模数优化的候选示例:

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

在此 OCaml 函数中，对 map 的递归调用是尾部位置的构造函数应用程序的参数，因此可以应用模数优化。 (OCaml 尚未进行此优化，尽管有一些实验性补丁。)

转换后的函数可能类似于以下 psuedo-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 不会阻塞的一些内部值。)

尾部consing通过不同的机制在Lisp中也很常见:突变往往是显式编程的，而困惑的细节隐藏在宏中，例如循环。

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