原作者：Guido
原文地址
我最近在 Python 之歷史博客中發(fā)布了一篇關(guān)于 Python “函數(shù)式” 起源 的文章?！安恢С治策f歸消除（TRE）”這一句話帶來了類似 “很遺憾 Python 不會這么做” 的評論，以及嘗試 “證明” TRE 可以容易地添加到 Python 中的博客。那么讓我捍衛(wèi)自己的立場：我不希望 Python 有 TRE。一個簡短的答案就是 TRE 一點也不 Pythonic。 下面是長答案：
首先，正如一位評論者所言，TRE 與優(yōu)雅的棧跟蹤信息是不相容的：尾部遞歸被消除后，若出現(xiàn)錯誤，沒有任何堆?？蚣芸捎糜诖蛴』厮荨＿@會混淆那些無意中使用遞歸的用戶（遞歸在打印的棧跟蹤中不明顯），并且使調(diào)試變得困難。提供一個禁用 TRE 的選項對我來說是錯誤的：Python 的默認值應(yīng)該總是對調(diào)試最有幫助。這也讓我能提出接下的事情。
其次，TRE 僅僅是一種優(yōu)化，每個 Python 實現(xiàn)都可以選擇實現(xiàn)或不實現(xiàn)的想法是錯誤的。一旦存在尾遞歸消除，開發(fā)人員將開始編寫依賴于它的代碼，并且他們的代碼將無法在沒有提供 TRE 的實現(xiàn)上運行：典型的 Python 實現(xiàn)允許 1000 次遞歸，這對于非遞歸或用于遞歸遍歷的代碼是足夠的，例如，一個經(jīng)典的解析樹，但不足以用于遞歸遍歷一個大的列表。
第三，我不相信遞歸是所有編程的基礎(chǔ)。這是某些計算機科學(xué)家的基本信念，特別是那些熱愛 Scheme 并喜歡以 cons 單元和遞歸作為編程教程開頭的人。但對我而言，將遞歸看作是所有其他事物的基礎(chǔ)只是一個很好的理論方法，而不是日常的工具。
出于實際的目的，對于剛開始探索編程世界來說，Python 風(fēng)格的列表（它們是靈活的數(shù)組，而不是鏈表），以及一般的序列，比遞歸更有用。對于有經(jīng)驗的 Python 程序員來說，它們也是最重要的工具。使用鏈表來表示序列顯然是不夠 Pythonic，同時在大多數(shù)情況下效率非常低。 Python 的大部分庫都是用序列和迭代器作為基本構(gòu)建塊（當(dāng)然還有詞典）編寫的，而不是鏈表，所以不使用列表或序列你將無法享受許多預(yù)定義的實用功能。
最后，讓我們看看如何實現(xiàn)尾遞歸消除。第一個值得注意的是你不能在編譯時這么做。我已經(jīng)看到至少有一個博客利用字節(jié)碼在 RETURN 操作之前替換 CALL操作，改為跳轉(zhuǎn)到函數(shù)體的頂部。這可能是一個很好的演示，但不幸的是，Python 的編譯器不能可靠地確定任何特定的調(diào)用是否實際上引用了當(dāng)前函數(shù)，即使它看起來具有相同的名稱?？紤]這個簡單的例子：
def f(x):
if x > 0:
return f(x-1)
return 0
看起來你可以用這樣的東西替換函數(shù)體：
if x > 0:
x = x-1
# <跳轉(zhuǎn)到頂部>
return 0
這似乎很簡單，但現(xiàn)在添加：
g = f
def f(x):
return x
g(5)
調(diào)用 g(5) 時用到了前一個f，但“遞歸”調(diào)用不再遞歸！在運行時，名字 f 被再綁定到后面的非遞歸定義的版本，所以返回的值是 4，而不是 0。雖然我同意這個例子是不好的風(fēng)格，但它是 Python 明確定義的語義，具有大量合法用途。一個編譯器如果樂觀地認為 f 的定義保持不變，會因這種替換在現(xiàn)實世界的代碼中導(dǎo)致令人發(fā)指的錯誤。
另一篇博客展示了可用于使用神奇異常或返回值實現(xiàn)尾遞歸的裝飾器。這些可以用普通的 Python 編寫（盡管這篇文章展示了一個優(yōu)化的 Cython 版本，聲稱它“速度只慢了10％”，盡管它似乎不是線程安全的）。如果這讓你想去使用，我不會試圖阻止你，但我強烈反對在核心發(fā)行版中包含這樣的內(nèi)容：使用這樣的裝飾器有許多警告，因為它必須假定任何遞歸調(diào)用（在裝飾函數(shù)中）是尾遞歸的并且可以被消除。在經(jīng)驗不足的用戶手中，這很容易導(dǎo)致災(zāi)難。例如，階乘的通用遞歸定義不是尾遞歸的：
def fact(n):
if n > 1:
return n * fact(n-1)
return 1
還有有很多函數(shù)包含一個尾遞歸調(diào)用和另一個不是尾遞歸的遞歸調(diào)用，裝飾器不處理這種情況。這些裝飾器無法處理的另一個微妙之處是在 try 塊內(nèi)部進行尾遞歸調(diào)用：這些調(diào)用塊可能看起來像可以被刪除，但它們不能，因為 TRE 可以刪除由語言保證的異常處理。由于所有這些原因，我認為這個方法是糟糕的，至少對于一般的用戶來說。
但是，如果有人決定將 TRE 添加到 CPython，他們可以大致如下修改編譯器。首先，確定“安全”尾遞歸呼叫站點。這就像是一個 CALL 操作碼，緊跟著一個 RETURN 操作碼，并且完全在任何 try 塊之外。（注意：我忽略了不同的 CALL_ *操作碼，這應(yīng)該很容易使用相同的方法處理。）接下來，用一個 CALL_RETURN 操作碼替換每個這樣的 CALL - RETURN 操作碼對。編譯器不需要嘗試檢查被調(diào)用函數(shù)的名稱是否與當(dāng)前函數(shù)相同：只需通過節(jié)省解碼第二個操作碼的時間，新操作碼就可以節(jié)省所有 CALL + RETURN 組合的成本。如果在運行時確定此特定調(diào)用不適用于 TRE，則執(zhí)行 CALL 和 RETURN 操作碼之后的通常操作。（我想你可以添加一些對調(diào)用位點索引過緩存機制來加速運行時間的決定。）
在確定可以優(yōu)化時，可以設(shè)置幾種優(yōu)化級別。如果被調(diào)用的對象是已經(jīng)在當(dāng)前棧幀中運行的函數(shù)，那么最不積極的 vanilla 方法將只優(yōu)化調(diào)用。我們現(xiàn)在要做的就是清除當(dāng)前堆?？蚣苤械木植浚ㄒ约捌渌[藏狀態(tài)，例如活動循環(huán)），設(shè)置賦值棧中的參數(shù)并跳轉(zhuǎn)到函數(shù)頂部。 （微妙地，根據(jù)定義，新的參數(shù)在當(dāng)前的堆棧中。可能只是需要先復(fù)制它們，更微妙的是關(guān)鍵字參數(shù)，可變長度參數(shù)列表和默認參數(shù)值的存在。雖然這只是一個簡單的編程問題。）
一個更激進的版本也將識別出一種方法是尾遞歸的情況（即被調(diào)用的對象是一個方法，其底層函數(shù)與當(dāng)前棧幀中的函數(shù)相同）。這只需要更多的編程；CPython 解釋器代碼（ceval.c）已經(jīng)對方法調(diào)用進行了優(yōu)化。（我不知道這將是多么有用：我期望尾部遞歸風(fēng)格受到喜歡使用函數(shù)式編程風(fēng)格的程序員的歡迎，并且可能不會使用太多的類。)
從理論上講，只要新調(diào)用所需的局部變量的數(shù)量可以在當(dāng)前堆?？蚣軐ο笾姓{(diào)節(jié)，就可以優(yōu)化所有被調(diào)用的對象是用 Python 編寫的函數(shù)或方法的情況。（CPython中的Frame對象被分配到堆上，并且具有基于本地所需空間的變量分配大小;已經(jīng)有用于重用框架對象的機器）。這將優(yōu)化相互的尾遞歸函數(shù)，否則將不會是優(yōu)化。唉，它也會在大多數(shù)情況下禁用堆棧跟蹤，所以它可能不是一個好主意。
一個更好的變體是像以前一樣創(chuàng)建 Python 級別的堆棧對象，但重用 C 堆?？蚣堋＿@將創(chuàng)建一個近似無棧的 Python，盡管遞歸內(nèi)置的函數(shù)或方法，仍然可以很容易地耗盡 C 的堆棧。
當(dāng)然，這些都不能解決我的前三個問題。重寫你的函數(shù)來使用循環(huán)是否真的是一件大事？（畢竟 TRE 只處理可以很容易被循環(huán)替換的遞歸）
