移動在「近尾部位置」遞歸調用真正的末尾位置

在閱讀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

但我只提到「幾乎尾巴」呼籲，那些在遞歸調用是返回值的一部分，但由於其他函數應用程序包裝它而不在尾部位置（例如上面triangle示例中的x +）。

這是泛化的功能上下文嗎？那麼一個必要的呢？所有在遞歸調用中的函數都可以被轉換成尾部位置返回的函數（即可以調用尾部優化的函數）？

不要緊，這些都不是計算Haskell中三角形數的「最佳」方法，AFAIK是triangle x = sum [0..n]。該代碼純粹是這個問題的一個人爲的例子。

注：我讀過Are there problems that cannot be written using tail recursion?，所以我相當有信心我的問題的答案是肯定的。但是，答案提到了延續傳球的風格。除非我誤解CPS，否則我的轉換triangle'仍然是直接風格。在這種情況下，我很好奇這種轉換是直接式的。

來源

2016-03-09 Bailey Parker

是不是所有的函數都能被轉換，使得它們只有帶CPS轉換的尾調用？ – Claudiu

有一個有趣的尾遞歸模運算符優化空間，它可以轉換某些函數，使它們在恆定空間中運行。可能最爲人熟知的是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中函數的遞歸調用圖是一個參數，在尾部位置的構造應用程序，所以模-cons優化可能適用。（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通過不同的機制：那裏的突變往往是明確編程和雜亂的細節隱藏在一個宏如loop。

這些方法如何被推廣是一個有趣的問題。

來源

2016-03-09 08:28:48 gsg

移動在「近尾部位置」遞歸調用真正的末尾位置

回答

相關問題