如何設計一門語言（七）——閉包、lambda和interface

人們都很喜歡討論閉包這個概念。其實這個概念對于寫代碼來講一點用都沒有，寫代碼只需要掌握好lambda表達式和class+interface的語義就行了。基本上只有在寫編譯器和虛擬機的時候才需要管什么是閉包。不過因為系列文章主題的緣故，在這里我就跟大家講一下閉包是什么東西。在理解閉包之前，我們得先理解一些常見的argument passing和symbol resolving的規則。

首先第一個就是call by value了。這個規則我們大家都很熟悉，因為流行的語言都是這么做的。大家還記得剛開始學編程的時候，書上總是有一道題目，說的是：

void Swap(int a, int b)
{
    int t = a;
    a = b;
    b = t;
}

int main()
{
    int a=0;
    int b=1;
    Swap(a, b);
    printf("%d, %d", a, b);
}

然后問程序會輸出什么。當然我們現在都知道，a和b仍然是0和1，沒有受到變化。這就是call by value。如果我們修改一下規則，讓參數總是通過引用傳遞進來，因此Swap會導致main函數最后會輸出1和0的話，那這個就是call by reference了。

除此之外，一個不太常見的例子就是call by need了。call by need這個東西在某些著名的實用的函數式語言（譬如Haskell）是一個重要的規則，說的就是如果一個參數沒被用上，那傳進去的時候就不會執行。聽起來好像有點玄，我仍然用C語言來舉個例子。

int Add(int a, int b)
{
    return a + b;
}

int Choose(bool first, int a, int b)
{
    return first ? a : b;
}

int main()
{
    int r = Choose(false, Add(1, 2), Add(3, 4));
    printf("%d", r);
}

這個程序Add會被調用多少次呢？大家都知道是兩次。但是在Haskell里面這么寫的話，就只會被調用一次。為什么呢？因為Choose的第一個參數是false，所以函數的返回值只依賴與b，而不依賴與a。所以在main函數里面它感覺到了這一點，于是只算Add(3, 4)，不算Add(1, 2)。不過大家別以為這是因為編譯器優化的時候內聯了這個函數才這么干的，Haskell的這個機制是在運行時起作用的。所以如果我們寫了個快速排序的算法，然后把一個數組排序后只輸出第一個數字，那么整個程序是O(n)時間復雜度的。因為快速排序的average case在把第一個元素確定下來的時候，只花了O(n)的時間。再加上整個程序只輸出第一個數字，所以后面的他就不算了，于是整個程序也是O(n)。

于是大家知道call by name、call by reference和call by need了。現在來給大家講一個call by name的神奇的規則。這個規則神奇到，我覺得根本沒辦法駕馭它來寫出一個正確的程序。我來舉個例子：

int Set(int a, int b, int c, int d)
{
    a += b;
    a += c;
    a += d;
}

int main()
{
    int i = 0;
    int x[3] = {1, 2, 3};
    Set(x[i++], 10, 100, 1000);
    printf("%d, %d, %d, %d", x[0], x[1], x[2], i);
}

學過C語言的都知道這個程序其實什么都沒做。如果把C語言的call by value改成了call by reference的話，那么x和i的值分別是{1111, 2, 3}和1。但是我們知道，人類的想象力是很豐富的，于是發明了一種叫做call by name的規則。call by name也是call by reference的，但是區別在于你每一次使用一個參數的時候，程序都會把計算這個參數的表達式執行一遍。因此，如果把C語言的call by value換成call by name，那么上面的程序做的事情實際上就是：

x[i++] += 10;
x[i++] += 100;
x[i++] += 1000;

程序執行完之后x和i的值就是{11, 102, 1003}和3了。

很神奇對吧，稍微不注意就會中招，是個大坑，基本沒法用對吧。那你們還整天用C語言的宏來代替函數干什么呢。我依稀記得Ada（有網友指出這是Algol 60）還是什么語言就是用這個規則的，印象比較模糊。

講完了argument passing的事情，在理解lambda表達式之前，我們還需要知道兩個流行的symbol resolving的規則。所謂的symbol resolving講的就是解決程序在看到一個名字的時候，如何知道這個名字到底指向的是誰的問題。于是我又可以舉一個簡單粗暴的例子了：

Action<int> SetX()
{
    int x = 0;
    return (int n)=>
    {
        x = n;
    };
}

void Main()
{
    int x = 10;
    var setX = SetX();
    setX(20);
    Console.WriteLine(x);
}

弱智都知道這個程序其實什么都沒做，就輸出10。這是因為C#用的symbol resolving地方法是lexical scoping。對于SetX里面那個lambda表達式來講，那個x是SetX的x而不是Main的x，因為lexical scoping的含義就是，在定義的地方向上查找名字。那為什么不能在運行的時候向上查找名字從而讓SetX里面的lambda表達式實際上訪問的是Main函數里面的x呢？其實是有人這么干的。這種做法叫dynamic scoping。我們知道，著名的javascript語言的eval函數，字符串參數里面的所有名字就是在運行的時候查找的。

=======================我是背景知識的分割線=======================

想必大家都覺得，如果一個語言的lambda表達式在定義和執行的時候采用的是lexical scoping和call by value那該有多好呀。流行的語言都是這么做的。就算規定到這么細，那還是有一個分歧。到底一個lambda表達式抓下來的外面的符號是只讀的還是可讀寫的呢？python告訴我們，這是只讀的。C#和javascript告訴我們，這是可讀寫的。C++告訴我們，你們自己來決定每一個符號的規則。作為一個對語言了解得很深刻，知道自己每一行代碼到底在做什么，而且還很有自制力的程序員來說，我還是比較喜歡C#那種做法。因為其實C++就算你把一個值抓了下來，大部分情況下還是不能優化的，那何苦每個變量都要我自己說明我到底是想只讀呢，還是要讀寫都可以呢？函數體我怎么用這個變量不是已經很清楚的表達出來了嘛。

那說到底閉包是什么呢？閉包其實就是那個被lambda表達式抓下來的“上下文”加上函數本身了。像上面的SetX函數里面的lambda表達式的閉包，就是x變量。一個語言有了帶閉包的lambda表達式，意味著什么呢？我下面給大家展示一小段代碼。現在要從動態類型的的lambda表達式開始講，就湊合著用那個無聊的javascript吧：

function pair(a, b) {
    return function(c) {
        return c(a, b);
    };
}

function first(a, b) {
    return a;
}

function second(a, b) {
    return b;
}

var p = pair(1, pair(2, 3));
var a = p(first);
var b = p(second)(first);
var c = p(second)(second);
print(a, b, c);

這個程序的a、b和c到底是什么值呢？當然就算看不懂這個程序的人也可以很快猜出來他們是1、2和3了，因為變量名實在是定義的太清楚了。那么程序的運行過程到底是怎么樣的呢？大家可以看到這個程序的任何一個值在創建之后都沒有被第二次賦值過，于是這種程序就是沒有副作用的，那就代表其實在這里call by value和call by need是沒有區別的。call by need意味著函數的參數的求值順序也是無所謂的。在這種情況下，程序就變得跟數學公式一樣，可以推導了。那我們現在就來推導一下：

var p = pair(1, pair(2, 3));
var a = p(first);

// ↓↓↓↓↓

var p = function(c) {
    return c(1, pair(2, 3));
};
var a = p(first);

// ↓↓↓↓↓

var a = first(1, pair(2, 3));

// ↓↓↓↓↓

var a = 1;

這也算是個老掉牙的例子了啊。閉包在這里體現了他強大的作用，把參數保留了起來，我們可以在這之后進行訪問。仿佛我們寫的就是下面這樣的代碼：

var p = {
    first : 1,
    second : {
        first : 1,
        second : 2,
    }
};

var a = p.first;
var b = p.second.first;
var c = p.second.second;

于是我們得到了一個結論，（帶閉包的）lambda表達式可以代替一個成員為只讀的struct了。那么，成員可以讀寫的struct要怎么做呢？做法當然跟上面的不一樣。究其原因，就是因為javascript使用了call by value的規則，使得pair里面的return c(a, b);沒辦法將a和b的引用傳遞給c，這樣就沒有人可以修改a和b的值了。雖然a和b在那些c里面是改不了的，但是pair函數內部是可以修改的。如果我們要堅持只是用lambda表達式的話，就得要求c把修改后的所有“這個struct的成員變量”都拿出來。于是就有了下面的代碼：

// 在這里我們繼續使用上面的pair、first和second函數

function mutable_pair(a, b) {
    return function(c) {
        var x = c(a, b);
        // 這里我們把pair當鏈表用，一個(1, 2, 3)的鏈表會被儲存為pair(1, pair(2, pair(3, null)))
        a = x(second)(first);
        b = x(second)(second)(first);
        return x(first);
    };
}

function get_first(a, b) {
    return pair(a, pair(a, pair(b, null)));
}

function get_second(a, b) {
    return pair(b, pair(a, pair(b, null)));
}

function set_first(value) {
    return function(a, b) {
        return pair(undefined, pair(value, pair(b, null)));
    };
}

function set_second(value) {
    return function(a, b) {
        return pair(undefined, pair(a, pair(value, null)));
    };
}

var p = mutable_pair(1, 2);
var a = p(get_first);
var b = p(get_second);
print(a, b);
p(set_first(3));
p(set_second(4));
var c = p(get_first);
var d = p(get_second);
print(c, d);

我們可以看到，因為get_first和get_second做了一個只讀的事情，所以返回的鏈表的第二個值（代表新的a）和第三個值（代表新的b）都是舊的a和b。但是set_first和set_second就不一樣了。因此在執行到第二個print的時候，我們可以看到p的兩個值已經被更改成了3和4。

雖然這里已經涉及到了“綁定過的變量重新賦值”的事情，不過我們還是可以嘗試推導一下，究竟p(set_first(3));的時候究竟干了什么事情：

var p = mutable_pair(1, 2);
p(set_first(3));

// ↓↓↓↓↓

p = return function(c) {
    var x = c(1, 2);
    a = x(second)(first);
    b = x(second)(second)(first);
    return x(first);
};
p(set_first(3));

// ↓↓↓↓↓

var x = set_first(3)(1, 2);
p.a = x(second)(first); // 這里的a和b是p的閉包內包含的上下文的變量了，所以這么寫會清楚一點
p.b = x(second)(second)(first);
// return x(first);出來的值沒人要，所以省略掉。

// ↓↓↓↓↓

var x = (function(a, b) {
    return pair(undefined, pair(3, pair(b, null)));
})(1, 2);
p.a = x(second)(first);
p.b = x(second)(second)(first);// ↓↓↓↓↓

x = pair(undefined, pair(3, pair(2, null)));
p.a = x(second)(first);
p.b = x(second)(second)(first);// ↓↓↓↓↓

p.a = 3;
p.b = 2;

由于涉及到了上下文的修改，這個推導嚴格上來說已經不能叫推導了，只能叫解說了。不過我們可以發現，僅僅使用可以捕捉可讀寫的上下文的lambda表達式，已經可以實現可讀寫的struct的效果了。而且這個struct的讀寫是通過getter和setter來實現的，于是只要我們寫的復雜一點，我們就得到了一個interface。于是那個mutable_pair，就可以看成是一個構造函數了。

大括號不能換行的代碼真他媽的難讀啊，遠遠望去就像一坨屎！go語言還把javascript自動補全分號的算法給抄去了，真是沒品位。

所以，interface其實跟lambda表達是一樣，也可以看成是一個閉包。只是interface的入口比較多，lambda表達式的入口只有一個（類似于C++的operator()）。大家可能會問，class是什么呢？class當然是interface內部不可告人的實現細節的。我們知道，依賴實現細節來編程是不對的，所以我們要依賴接口編程。

當然，即使是倉促設計出javascript的那個人，大概也是知道構造函數也是一個函數的，而且類的成員跟函數的上下文鏈表的節點對象其實沒什么區別。于是我們會看到，javascript里面是這么做面向對象的事情的：

function rectangle(a, b) {
    this.width = a;
    this.height = height;
}

rectangle.prototype.get_area = function() {
    return this.width * this.height;
};

var r = new rectangle(3, 4);
print(r.get_area());

然后我們就拿到了一個3×4的長方形的面積12了。不過javascript給我們帶來的一點點小困惑是，函數的this參數其實是dynamic scoping的，也就是說，這個this到底是什么，要看你在哪如何調用這個函數。于是其實

obj.method(args)

整個東西是一個語法，它代表method的this參數是obj，剩下的參數是args。可惜的是，這個語法并不是由“obj.member”和“func(args)”組成的。那么在上面的例子中，如果我們把代碼改為：

var x = r.get_area;
print(x());

結果是什么呢？反正不是12。如果你在C#里面做這個事情，效果就跟javascript不一樣了。如果我們有下面的代碼：

class Rectangle
{
    public int width;
    public int height;

    public int GetArea()
    {
        return width * height;
    }
};

那么下面兩段代碼的意思是一樣的：

var r = new Rectangle
{
    width = 3;
    height = 4;
};

// 第一段代碼
Console.WriteLine(r.GetArea());

// 第二段代碼
Func<int> x = r.GetArea;
Console.WriteLine(x());

究其原因，是因為javascript把obj.method(a, b)解釋成了GetMember(obj, “method”).Invoke(a, b, this = r);了。所以你做r.get_area的時候，你拿到的其實是定義在rectangle.prototype里面的那個東西。但是C#做的事情不一樣，C#的第二段代碼其實相當于：

Func<int> x = ()=>
{
    return r.GetArea();
};
Console.WriteLine(x());

所以說C#這個做法比較符合直覺啊，為什么dynamic scoping（譬如javascript的this參數）和call by name（譬如C語言的宏）看起來都那么屌絲，總是讓人掉坑里，就是因為違反了直覺。不過javascript那么做還是情有可原的。估計第一次設計這個東西的時候，收到了靜態類型語言太多的影響，于是把obj.method(args)整個當成了一個整體來看。因為在C++里面，this的確就是一個參數，只是她不能讓你obj.method，得寫&TObj::method，然后還有一個專門填this參數的語法——沒錯，就是.*和->*操作符了。

假如說，javascript的this參數要做成lexical scoping，而不是dynamic scoping，那么能不能用lambda表達式來模擬interface呢？這當然是可以，只是如果不用prototype的話，那我們就會喪失javascript愛好者們千方百計絞盡腦汁用盡奇技淫巧鎖模擬出來的“繼承”效果了：

function mutable_pair(a, b) {
    _this = {
        get_first = function() { return a; },
        get_second = function() { return b; },
        set_first = function(value) { a = value; },
        set_second = function(value) { b = value; }
    };
    return _this; 
}

var p = new mutable_pair(1, 2);
var a = p.get_first();
var b = p.get_second();
print(a, b);
var c = p.set_first(3);
var d = p.set_second(4);
print(c, d);

這個時候，即使你寫

var x = p.set_first;
var y = p.set_second;
x(3);
y(4);

代碼也會跟我們所期望的一樣正常工作了。而且創造出來的r，所有的成員變量都屏蔽掉了，只留下了幾個函數給你。與此同時，函數里面訪問_this也會得到創建出來的那個interface了。

大家到這里大概已經明白閉包、lambda表達式和interface之間的關系了吧。我看了一下之前寫過的六篇文章，加上今天這篇，內容已經覆蓋了有：

閱讀C語言的復雜的聲明語法
什么是語法噪音
什么是語法的一致性
C++的const的意思
C#的struct和property的問題
C++的多重繼承
封裝到底意味著什么
為什么exception要比error code寫起來干凈、容易維護而且不需要太多的溝通
為什么C#的有些interface應該表達為concept
模板和模板元編程
協變和逆變
type rich programming
OO的消息發送的含義
虛函數表是如何實現的
什么是OO里面的類型擴展開放/封閉與邏輯擴展開放/封閉
visitor模式如何逆轉類型和邏輯的擴展和封閉
CPS（continuation passing style）變換與異步調用的異常處理的關系
CPS如何讓exception變成error code
argument passing和symbol resolving
如何用lambda實現mutable struct和immutable struct
如何用lambda實現interface

想了想，大概通俗易懂的可以自學成才的那些東西大概都講完了。當然，系列是不會在這里就結束的，只是后面的東西，大概就需要大家多一點思考了。

寫程序講究行云流水。只有自己勤于思考，勤于做實驗，勤于造輪子，才能讓編程的學習事半功倍。

posted on 2013-07-05 22:32 陳梓瀚(vczh) 閱讀(11756) 評論(18) 收藏舉報