函數式編程的函數是如何實現的？

12-31

目的：在宿主語言（Host language）上運行目標語言（Target language）

目標語言：此例為「函數式語言」。過於寬泛，因此我們暫且忽略有否元編程特性、類型系統、IO、異常處理、primitive operator等問題，只考慮一個核心特性的實現：一等函數（First-class function）

宿主語言：可以是諸如JavaScript之類本身就有一等函數支持的語言，也可以是特定平台的機器碼。最偷懶的做法就是做代碼生成時直接用高級語言的一等函數來代表自己的一等函數，不過可能會受困於宿主語言缺乏尾遞歸等問題；改進的做法是先用高級語言實現目標語言，然後對實現進行幾次變換，逐步去掉對高級特性的依賴（最後可以連高級語言自己的調用棧都不需要了），最終實現底層語言中跑函數式語言。

實現方式：前面忽略了一大堆東西，但有一個沒法忽略：規約策略。至少要區分你要做strict的語言還是non-strict的。

non-strict函數式語言：這裡就不考慮call by name了，默認是有sharing的call by need策略。簡單的做法，graph rewriting，規約過程就是對AST進行重寫，這個過程當中產生的一等函數，都是一棵子樹，這棵子樹稱為一個thunk，代表一個也許已經規約到WHNF（Weak Head Normal Form）的表達式，同時可以有多個指針指向這個thunk。這個rewriting的過程是可以自動並行化的。更複雜一些的做法，就是編譯到G-machine或者TIM（Three Instruction Machine）等抽象機器。non-strict這部分一本不錯的參考是SPJ的《Implementing Functional Languages: A Tutorial》

strict函數式語言：最簡單的搞法是，首先用ML系的語言寫一個基於環境的解釋器（不介意的話可以看王垠博客那篇教寫解釋器的），然後一步一步地把解釋器進行變換，首先對解釋器做CPS變換，變換完了以後解釋器就不再依賴Host language里的general recursion，只依賴tail recursion了；接下來再做defunctionalization，把CPS變換里的continuation用簡單的數據類型表示，這樣一來解釋器就不再依賴Host language里的高階函數了。現在，解釋器已經低級到很容易重寫到C甚至彙編的地步了。欲知詳情可以看Andrew Appel的《Compiling with Continuations》。複雜的搞法，講不完了。。

加入類型：前面，我們的各種實現中，函數的參數都是某個可以代表基本類型數據或者又一個函數的東西，它們在內存中的表示都是（有gc兜著的）一些堆上的數據結構。當加入類型系統，可以去掉運行時的一些判斷（比如指針指向的堆上對象不是個函數，卻放在了函數應用式左邊，報錯）；留下來的指針標籤，只用來區分ADT的constructor，用於模式匹配。更複雜的情況，比如依賴類型之類需要運行時存留一些類型信息的場合，不講了。。

新手常見誤區：寫解釋器/編譯器，一上手就考慮「環境」和「閉包」等概念（它們並非必需品），而不知悉一些更基礎的概念，比如beta reduction。不看書的話至少把wikipedia過一遍，草稿紙上把常用的組合子都算一算，再想怎麼實現的事。。

題外話：這是我的知乎最後一貼。在這裡漲了姿勢，認識了菊苣，我玩得很開心！

雖然@邵成大大說得很全面了，但我猜大多數人還是懶得去看那兩本書，所以我來放個簡潔版的：《Definitional Interpreters for Higher-Order Programming Languages》。這篇paper 通過Meta-circular Interpreter 很好地回答了這個問題，不能找到更偷懶的資料了……

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

最近我的知乎的能量源們（R大，邵大，姚大等等）一個個都退出了（或者不活躍了），知乎乙烷。

最簡單的就是，通過給每一種函數類型定義一個interface，然後實現它的方法來實現。如C#的delegate。

編譯前：

int Fuck(int shit, int bitch) { return shit + bitch; }


Func& Screw(int dung)

{

    var fuck = bitch=&>Fuck(dung, bitch);

    dung++;

    return fuck;

}

void Main() { Console.WriteLine(Screw(1)(2)); // 4 }

編譯後：

interface IFuckable { int Invoke(int fuckee); }


class ScrewClosure

{

    public int dung;

}
int Fuck(int shit, int bitch)

{

    return shit + bitch;

}
class ScrewFuckable : IFuckable

{

    public ScrewClosure closure;
    int IFuckable.Invoke(int fuckee)

    {

        return Fuck(closure.dung, fuckee);

    }

}
IFuckable Screw(int dung)

{

    var closure = new ScrewClosure { dung = dung; };

    var fuck = new ScrewFuckable { closure = closure };

    closure.dung++;

    return fuck;

}

void Main() { Console.WriteLine(Screw(1).Invoke(2)); }

翻譯輪子哥 @vczh 的代碼=&> F#=&>反編譯

不邀自答，@邵成的答案非常全面，但是對新手而言，環境或者閉包的概念恰恰是理解first class的函數，與過程式語言的函數區別的關鍵。

函數式編程中函數有特色的一點就是可以curry化，設想一個有兩個分離參數的函數，當只用一個參數調用時，就得到了一個作為值返回的函數，輸入的參數作為自由變數被函數引用，所謂的代碼加自由變數表即得到閉包。

這個特性甚至可以使得函數式語言的函數閉包可以模擬對象。

所以通過程序變換，把高階函數轉化為閉包，對象，也就是代碼加上記錄自由變數的數據結構，這是一種函數語言的實現辦法。

單態函數超級簡單，兩個指針，一個表示代碼一個存 free variable，完事

多態函數就很麻煩了，一種可行的做法是顯式引入 System-F 的二階 $Lambda$ 進來，然後配合運行時類型系統去做。

比如我們可以把代碼：

let rec { even? = x. if (zero? x) true (odd? (- x 1)); odd? = x. if (zero? x) false (even? (- x 1)); id: = x. x; id_dyn = x : forall Q. (forall a. (box "a) -&> "Q) -&> "Q . unbox x } in let { strange = f : forall a. "a -&> "a . (f 1) (f (even? 5)) } in (strange id) (id_dyn (box_list 1))

決議成：

let rec { even?:int -&> boolean = x : int . &<"a-&>boolean&> if (zero? x) true (odd? (- x 1)); odd?:int -&> boolean = x : int . &<"a-&>boolean&> if (zero? x) false (even? (- x 1)); id:forall t1. "t1 -&> "t1 = (Λ{t1}. (x : "t1 . x)); id_dyn:(forall Q. (forall a. (box "a) -&> "Q) -&> "Q) -&> list int = x : forall Q. (forall a. (box "a) -&> "Q) -&> "Q . {"t-&>list int} unbox (Λ{"59a "47Q}. &<"a-&>"59a, "Q-&>"47Q&> x) } in let { strange:(forall a. "a -&> "a) -&> int * boolean = f : forall a. "a -&> "a . {"a-&>int, "b-&>boolean} (&<"a-&>int&> f 1) (&<"a-&>boolean&> f (even? 5)) } in &<"a-&>int * boolean, "b-&>list int&> (strange (Λ{"219a}. &<"t1-&>"219a&> id)) (id_dyn (Λ{"278a "263Q}. &<"a-&>list "278a, "Q-&>"263Q&> (&<"t-&>int&> box_list 1)))

上文中 Λ{"a "b ...}. e 為一個二階 Lambda 抽象（多態性定義），{"a-&>a, "b-&>b} e 為一個二階 Lambda 調用（多態對象的實例化）。

不妨就照著write you a scheme in 48 hours擼一遍，400行代碼實現的scheme，應該用來做SICP上的大部分習題不成問題了。

函數式語言中函數可以以以下三步進行解釋：

第一步把函數定義為一種值

作為值的函數包括三部分：

01 形式參數

02 函數體

03 函數定義時的環境（只需要包含函數體中的自由變數即可）

第二步在抽象語法樹中添加「函數定義」分支

對函數定義的求值結果是返回一個普通的函數（包含第一步所述的三個部分）

第三步在抽象語法樹中加入「函數調用」分支，這個分支通常包括兩部分表達式

exp1 exp2..expn

對第一部分表達式exp1求值得到一個函數，然後按你指定的順序對exp2..expn求值，得到的值和形式參數綁定在一塊，存入到函數值所自帶的環境中，然後在那個環境中對函數體求值（嚴格求值）

上面是解釋器的做法

如果是編譯的話，關鍵的一步是對函數自帶環境進行「閉包轉換」，即是把變數名替換成對應值的地址，值則放入內存某個位置

編譯還要解決活動記錄格式，調用約定……這些細節問題，一般用解釋的方法對理解原理也足夠了

面向對象的觀念是一切都對象，函數式的觀念是一切都函數。

那麼面向對象跟函數式是怎麼打通的呢，很簡單，函數即是對象。匿名函數即是個匿名對象。

至於語法上表現不同而已。

輪子哥所說的delegate是種相對重的函數，C#7會推出一種相對輕量級的。

有輸入，有輸出，即為函數。

先說普通函數。一種語言，定義了變數，值，表達式，就可以定義兩種規則，引入和消去。

引入是將表達式和變數名，組合得到一個lambda表達式（也就是函數）。

消去是把值綁定到變數名上，拆開表達式來計算，得到函數的值。

《計算機程序的構造與解釋》，就是講的這兩個過程。前面講如何引入函數（設計函數），後面講如何消解函數。定義函數，先要能定義表達式。所謂lisp七原語，就是配合數字字元字元串等值和若干運算符，定義表達式和函數。倒數第二章的解釋器，兩個過程eval和apply，分別來計算表達式和函數值。

然後是遞歸函數。遞歸函數有兩種定義方法，一種是帶名稱的也可能是letrec形式的，另一種是組合子。不管怎樣的形式，遞歸函數，同樣是apply+eval求值，不過需要運行時棧楨的配合。也有cps變換的解法，但是沒有本質區別。只是求值而已。

PS，邵成和彭飛推薦的兩書一文，非常好。

函數裡面表達式，只是會換到另外一個作用域執行代碼。int a，a+1。這裡的a在全局裡面(a=3)查詢。如果在函數裡面的話，在另外一個表裡(a=1，p=(a=3))面查詢a的值。和實現普通表達式沒有什麼區別，就是需要保存環境信息。