MATLAB是否執行尾部呼叫優化？

我最近學會了Haskell，並試圖在可能的情況下將純粹的功能風格轉到我的其他代碼。其中一個重要方面是將所有變量視爲不可變的，即常量。爲了做到這一點，許多使用循環以命令式執行的計算必須使用遞歸來執行，這通常會由於爲每個函數調用分配一個新的棧幀而導致內存損失。但是，在尾部調用（即被調用函數的返回值立即返回給被調用者的調用者）的特殊情況下，該懲罰可以被稱爲尾部調用優化的過程繞過（在一種方法中，這可以通過基本上在正確設置堆棧後用jmp替換一個調用）。 MATLAB默認執行TCO，還是有辦法告訴它？MATLAB是否執行尾部呼叫優化？

來源

2011-03-16 Shea Levy

避免迭代只是它到底是不是一個好理念。使用任何更適合給定問題的方法（並且可行 - 當然迭代在純粹的函數式語言中是不實際的）。 – delnan 2011-03-16 14:33:17

通過適當的尾部呼叫優化，「避免迭代」成爲您如何思考問題的問題，而不是您的解決方案如何執行。如果MATLAB不提供TCO，那麼顯然我會在需要時使用迭代，但是如果這樣做，我將能夠在所有代碼中使用一致的範例。 – 2011-03-16 14:36:29

我不知道任何MATLAB，我一般來說都是。如果你編碼的是Python，Python有TCO，你仍然不應該在循環中使用遞歸，因爲它不是慣用的，語言和stdlib專注於充分利用迭代器等。關於「一致範例」：每個範式有它的弱點，所以用最好的辦法解決一個給定的問題（當然，「最好」的定義也包括它與其他方面一起工作的好壞程度）。 – delnan 2011-03-16 14:41:39

如果我定義了一個簡單的尾遞歸函數：

function tailtest(n) 
    if n==0; feature memstats; return; end 
    tailtest(n-1); 
end

，並調用它，這樣它會遞歸相當深刻：

set(0,'RecursionLimit',10000); 
tailtest(1000);

那麼它不看，如果堆棧幀吃了很多的記憶。但是，如果我讓遞歸深得多：

set(0,'RecursionLimit',10000); 
tailtest(5000);

然後（我的機器，今天）MATLAB簡單地崩潰了：過程毫不客氣地死去。

我不認爲這與MATLAB做任何TCO是一致的;一個函數只在一個地方調用自身，除了一個參數以外沒有局部變量，就像任何人所希望的那樣簡單。

所以：不，似乎MATLAB根本就沒有做TCO，至少默認情況下是這樣。我還沒有（到目前爲止）尋找可能啓用它的選項。如果有的話，我會很驚訝。

在我們沒有吹出堆棧的情況下，遞歸成本是多少？看看我對Bill Cheatham的回答的評論：看起來時間開銷不平凡但並非瘋狂。

......除了Bill Cheatham在我發表評論後刪除了他的回答。好。因此，我採用了Fibonacci函數的簡單迭代實現和一個簡單的尾遞歸函數，在兩者中進行基本相同的計算，並在fib(60)上對它們進行計時。遞歸實現比迭代實現花費的時間要長2.5倍。當然，對於每次迭代執行比一次加法和一次減法更多功能的函數，相對開銷將更小。

（我也同意delnan的情緒：在哈斯克爾感覺自然的那種高度遞歸的代碼通常可能是在MATLAB unidiomatic）

來源

2011-03-16 16:25:34

TCO在Matlab中可能很難，因爲從堆棧框架的工作空間中清除局部變量可能會對onCleanup產生副作用（）功能。 Matlab不是GCed的Java風格;它是確定性的，使用參考計數或類似的。支持RAII。要確定堆棧幀的安全性是否安全，它必須深入搜索所有未在尾部調用中傳遞的局部變量，以查看它們是否保留onCleanups。昂貴的測試。此外，在調用assignin（...，'caller'）或evalin（...，'caller'）的情況下，可能需要保留至少一個父堆棧幀。同意; unidiomatic。 – 2011-03-18 23:09:18

MATLAB是否執行尾部呼叫優化？

回答

相關問題