將函數轉換爲使用尾遞歸 - 正式研究

Question

有沒有人寫過一篇描述方法（自動）將函數轉換爲尾遞歸的正式論文？我正在尋找一種包括限制（可轉換功能的類型），轉換程序以及可能的話證明正確性的大學級正式治療方法？ Haskell的例子將是一個獎金。

Answer 1

（自動）將函數轉換爲尾遞歸的方法？

因此，有兩個部分，以這樣的：

• 認識到給定的遞歸函數可以被轉換爲一個尾遞歸形式和製備轉化
• 實施尾巴以有效的方式調用，所以轉型是值得的。

轉化成遞歸尾遞歸

看起來比較直截了當地承認語法尾遞歸定義。畢竟，「尾遞歸」意味着調用在語句的尾部出現。

E.g.該方案的人描述：

只編譯適當的自我調用，因爲跳轉不夠 實現完全尾遞歸。相反，我們在源語言中將所有 子表達式位置語法分爲兩類：尾部 （或縮小）位置和子問題位置。在簡單的 表達式中（如果是predicate後續備選），predicate是子問題的位置，而後續和替代方案都在 減少位置。這個句法概念可以很容易地擴展到 任意嵌套的子表達式。

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

轉變職能爲尾調用

你的問題的最棘手的部分是識別和轉化候選人循環的計算到尾遞歸那些優化。

GHC中引用了一個參考，它使用內聯和各種簡化規則來收回遞歸調用，直到它們的底層尾遞歸結構保持爲止。

• Secrets of the GHC inliner

尾調用消除

一旦你有一個尾遞歸形式的功能，你想有effiicently實現。如果你能產生一個循環，這是一個好的開始。如果你的目標機沒有，那麼tail call elimination「將需要一些技巧。引述Odersky的和Schinz，下面引用，

各種技術已經被提出，多年來，以消除 一般（不僅是遞歸）尾調用，多爲編譯器 目標C.

...把​​整個節目的一大功能，並使用直接跳轉或切換這個功能裏面語句調用模擬 功能。

...一個流行的技術是使用蹦牀。蹦牀是一個外部的 函數，它重複調用一個內部函數。每次內部功能 希望尾調用另一個功能時，它不直接調用它，但簡單地 將其身份（例如作爲閉包）返回給蹦牀，然後 自己調用它。因此避免了無限的堆棧增長，但有些性能不可避免地會丟失，主要是因爲蹦牀所做的所有呼叫都是對靜態未知函數的調用 。

另一種技術是亨利·貝克的「切尼在MTA」 憑藉他的技術，程序首先必須被轉換爲延續傳遞 風格（CPS），因此轉所有呼叫到尾調用，然後可以 編譯照常。在運行時，當堆棧即將溢出時，將建立並返回（或長時間跳轉）到call孔 「等待」在調用堆棧底部的當前延續。

• Tail call elimination on the Java Virtual Machine，米歇爾Schinz馬丁·奧德斯基，2001年

• 亨利G.貝克，小缺點不應該缺點它的參數，第二部分：在MTA草案版本，1994年1月，切尼 。

Answer 2

水星包含一些自動使事情尾遞歸的優化。 （Mercury是一種強制純度的邏輯編程語言，所以它討論的是謂詞而不是函數，但許多相同的思想適用於Mercury程序，與Haskell程序相比，更大的區別在於它是邏輯的而非功能的。嚴格而不是懶惰）

「累加器引入」使用額外的累加器參數生成謂詞的專用版本，以便允許在遞歸調用之前移動關聯操作。很明顯，這種優化不一定會自己產生尾遞歸謂詞，但通常會導致可以通過第二次優化優化的表單：

「最後調用模數構造函數」實質上允許執行後續遞歸調用只有通過構造函數應用程序才能被重寫，以便首先構造包含「孔」的值，然後遞歸調用將其輸出直接返回到「孔」的內存地址，而不是使用正常的返回值傳遞約定。但是，我相信Haskell會因爲懶惰而免費獲得這個優化。

這兩種優化在論文Making Mercury programs tail recursive中描述。