為什麼說「函數式語言是沒有調用棧」的，所謂「函數式語言的思維」又是指什麼呢？

01-27

我最近再看一篇想尾遞歸跟CPS的blog（尾遞歸與Continuation）的時候對下面的一則評論感覺很困惑
按理說，函數式語言應該是沒有調用棧的，函數式語言的函數可以按某個規則展開和歸約。所以尾遞歸就可以和命令式語言的循環一樣進行。
我之前對函數式語言的尾遞歸的理解如下：
無非是棧上現在不再需要存儲臨時數據，但是FP啊之類功能性的欄位都還是會有的，要不然函數執行結束返回到哪兒呢。。。也就是說「尾遞歸能大大減少對堆棧的消耗」至於說「保證不會堆棧溢出」我認為這是編譯器做的優化了。。而非尾遞歸自己的特性
但是看到這則評論之後感覺非常困惑，但有隱隱覺得似乎自己一直以來都混淆了「函數式編程」的思維跟「命令式編程」的思維。。。但其實又不是很清楚具體應該如何思考。。。

懇請各位前輩能否給與指點。。。解釋。。。？謝謝！

謝謝邀請。

函數式語言是有調用棧的，但並不是所有函數式語言都有。

題目說明裡的那篇文章說了尾遞歸。這裡需要注意兩點：一，我們可以從數學上證明，尾遞歸能夠以成熟的演算法形式快速轉換為等價的循環形式；二，實踐上，尾遞歸同樣有可能出現棧溢出，但需要視解釋器而定。如果具體到 Scheme，那麼我們可以肯定地說，符合標準的 Scheme 實現在執行尾遞歸代碼時肯定不會出現棧溢出。因為這是 RxRS 規範很早以前就已經規定，符合 Scheme 規範的解釋器或編譯器必須將尾遞歸優化為循環形式。有興趣者可參見 R6RS 5.11 節，Proper Tail Recursion。

所謂「函數式語言沒有調用棧」的說法，據我所知，廣為人知的語言中唯一大概能讓這一條成立的，是 Haskell。無論是否使用尾遞歸，Haskell 確實不會產生棧溢出，但理由絕對不是某些不學無術的 Haskell 社區吹鼓手所謂的「因為 Haskell 是純函數式語言」的奇談怪論。真正的原因是 Haskell 本身以圖歸約的方式組織函數調用鏈，而非棧。Haskell 能這麼做的本錢，在於其惰性求值的語言特性。而惰性求值，本質上是用堆上的內存保存所有計算的中間結果，雖然去掉了棧，但是以堆上內存消耗加大為代價的——實際上是用了一個厚厚的運行時管理整個中間結果。目前實現惰性求值的語言並不多，Haskell 是比較有代表性的。而活性求值語言則受限於活性求值的特徵，很少能見到使用圖規約構造運行時的例子。

順便說一句：@vczh 說的「因為 Haskell 編譯成 x86 所以肯定有棧」的觀點，雖然糾起來也沒錯，但我不是很認同。在我看來，這實際上是混淆了運行時系統的棧和上層語言的棧兩個概念。

最後，我不評價所謂「函數式語言的思維」。在我眼裡，編程語言即工具，屬於形而下的範疇。工具面前，盲目追求所謂「思維」這種形而上的東西，百害而無一利。但是函數式語言確實有一些通用的編程思路和規則，一般來說：

避免賦值的概念。利用參數和返回值構造數據變化的流向。
利用遞歸表示循環。事實上如果不使用賦值，那麼遞歸在很多情況下是唯一可行的循環手段。
執行代碼和數據總是合併。因此函數式語言中的函數本身攜帶自身的環境，可以構造閉包結構。
避免定義執行次序。比如 Scheme 的 begin 語句，並不是常用結構。
利用 continuation 進行程序執行流跳轉，即所謂 CPS。不過請允許我說句犯禁的話：Continuation 與其說是函數式設計的優點，倒不如說是因為其強硬地拒絕存儲和執行流的概念而不得不生造出來的機制。違反多數人的直覺，晦澀且難懂，並不是程序設計的正面範例。

補充說明：不熟悉 Haskell 的程序愛好者可能不理解所謂惰性求值的含義。在此做一些簡要的說明。惰性求值區別於多數語言所謂「活性求值」的特點，大概可以通俗地用 Python 代碼做如下的描述：

def fibonacci(n): if n &<= 0: return 0 elif n == 1: return 1 else: return fibonacci(n - 2) + fibonacci(n - 1)

現在假設求 fibonacci(4)，我們顯然需要先求解 fibonacci(3) 和 fibonacci(2)，而當求解 fibonacci(3) 時，活性求值語言會先求解 fibonacci(2)，並將其結果保存在棧里，而後在 fibonacci(3) 已知時，再將之前的結果彈棧。所以隨著迭代次數的增長，棧的內容也會增加；而惰性求值語言則不然，它會先將整個表達式的求解過程展開成一張有向無環圖，每個圖節點實際上是 fibonacci + 參數的組合。所謂求解，就是從最後一個可以直接求解的節點（fibonacci(0) 和 fibonacci(1)）開始，依次向上逆推，直到所有的節點對應的值都可知為止，圖的頂點即表達式的結果。

參考：

Proper Tail Recursion：Revised^6 Report on the Algorithmic Language Scheme

Wikipedia: Tail call

Wikipedia: CPS = Continuation-passing style

尾遞歸，可以從邏輯上被轉化成循環。

因此編譯器做優化時，直接將尾遞歸優化為循環結構，執行，不需要你說的反覆堆棧調用過程。

這不是一種編譯器私下小動作的過程。

==============

對於函數式語言來說，邏輯上的函數調用完全就不是什麼「堆棧調用」，而就是「規則展開」。

甚至而言，函數式語言的「循環」功能實現，就跟尾遞歸是一回事兒。

純看函數式語言的教程恐怕稍難理解，可以研究一下函數式語言的基礎——Lambda演算，裡面從數字、四則運算開始就是用表達式來表現的。

就算是Haskell最終也要編譯成x86的代碼的，所以必須要有調用堆棧。有些人說Haskell沒有調用堆棧，估計是看太多論文了，我姑且就來猜一下：假設我們要計算一個數組的長度，然後你寫了下面的代碼：

length_ [] x = x
length_ (x:xs) = length_ xs (x+1)
length = flip length_ 0

好了，那麼我們來看length [1,2]會發生什麼事情

length [1,2]
length_ [1,2] 0
length_ [2] (0+1)

length_ [] (0+1+1)
0+1+1
2

那個沒有調用堆棧說的大概就是這個意思吧。因為你每一次調用函數都等價於把代碼apply上context之後inline進來，所以留在內存中的永遠是一段代碼，你在裡面也看不出堆棧的結構，當然就沒有調用堆棧了。當然實際情況不可能是這樣的，不然慢爆了呀。所以說鼓吹這個事情的肯定是論文看太多了。補充一點，之所以能這麼做，就像@陳甫鵃說的，有lazy evaluation的成分。不過之所以Haskell會選擇lazy evaluation，最大的原因就是他那個沒有副作用的設計了。當然用Haskell寫過代碼的都知道，很多種類的程序，都是用副作用來建模的，這個時候用Haskell來寫你就得上monad，monad寫複雜了就得學會monad transformation/lifting，到後來你都不知道自己在幹什麼了……

不過Haskell都編譯成x86了，怎麼可能會真的沒有調用堆棧呢，啊哈哈哈哈。

=================================

關於函數式語言的思維的問題，其實說白了就是要你把程序看成是函數的組合而不是對數據的操作吧。舉個例子，譬如說我們要求(x-1)2的這個事情：

非函數式語言思維：

y = x - 1
result = y * y

函數式語言的思維：（用haskell）

TASK = square . (-1)
result = TASK x

第一個明顯是操作數據，第二個明顯是先用函數組合出你想要的運算規則，最後才把參數喂進去。這種事情就像你在C#裡面用Linq，在C++裡面用#include &裡面的東西一樣，其實並不是什麼神奇的事情。只要你這兩者用多了，或者你乾脆用Haskell寫多幾個程序，你自然就會有體會了。

貌似是裝配腦袋說的，要不叫Vczh大來回答一下好了XD

我對那句話的理解是這樣子的。純函數式語言，沒有副作用可言，因此所有的表達式都可以做代數替換，因此你可以把最頂層的函數調用用定義來進行代換，一直替換到沒用自定義的函數，全部都是操作符為止，這時候你做操作就不需要棧了，因為沒有函數調用。

``函數式編程的思維——思維這詞太空洞了，回答不上來。題主不妨想想自己在哪裡看到這個名詞的，然後去問一下寫下這個詞的原作者XD

這個估計是指棧幀框架吧。

函數執行返回的問題，這只不過是需要實現先進後出而已，又不是非得用棧不可。

實際上為了實現靜態詞法域，調用棧不可能真的實現成一個棧，數據都必須放堆上，所以用棧幀框架實現的調用棧對函數式語言來說是不可能直接用在函數調用中的。

----------------

嗯，談談函數式語言的思維。

函數式語言的思維就是脫離圖靈機式的思維，語言中的基礎設施成了一種純粹的構造，而不需要再去考慮計算機是怎麼實現的。

函數式語言的思維就是見到全局變數，類成員變數，類靜態變數，各種IO的時候都會心裡一緊，小心把他們與運算隔離開。函數式語言的思維就是盡量用無副作用的純函數去構建系統的核心部分，盡量用純函數組合生成純函數，如此反覆擴大純函數的覆蓋範圍。