如何设计一门语言（七）——闭包、lambda和interface

如何设计一门语言（七）——闭包、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之间的关系了吧。我看了一下之前写过的六篇文章，加上今天这篇，内容已经覆盖了有：

1. 阅读C语言的复杂的声明语法
2. 什么是语法噪音
3. 什么是语法的一致性
4. C++的const的意思
5. C#的struct和property的问题
6. C++的多重继承
7. 封装到底意味着什么
8. 为什么exception要比error code写起来干净、容易维护而且不需要太多的沟通
9. 为什么C#的有些interface应该表达为concept
10. 模板和模板元编程
11. 协变和逆变
12. type rich programming
13. OO的消息发送的含义
14. 虚函数表是如何实现的
15. 什么是OO里面的类型扩展开放/封闭与逻辑扩展开放/封闭
16. visitor模式如何逆转类型和逻辑的扩展和封闭
17. CPS（continuation passing style）变换与异步调用的异常处理的关系
18. CPS如何让exception变成error code
19. argument passing和symbol resolving
20. 如何用lambda实现mutable struct和immutable struct
21. 如何用lambda实现interface

想了想，大概通俗易懂的可以自学成才的那些东西大概都讲完了。当然，系列是不会在这里就结束的，只是后面的东西，大概就需要大家多一点思考了。

写程序讲究行云流水。只有自己勤于思考，勤于做实验，勤于造轮子，才能让编程的学习事半功倍。