对 SICP Chapter 2 的一些理解

SICP 第二章的标题为 “Building Abstractions with Data”。与第一章标题“Building Abstractions with Procedures” 相比，这一章明显注重于在数据上的抽象。因此，在本章中所采用的例子中，会有多种数据类型被抽象出来，而每种数据类型又会对应着多种操作，那么随着代码量的增多，如何在不减少需求的情况下正确的对数据的抽象将直接影响开发者编码时的难度以及后期维护的成本。

在阅读和练习完 Chapter 2 之后，我想谈一下对我思维冲击比较大的几个点。

Data-Directed Programming

在 SICP 中，DDP 出现的一个背景是：存在多种数据类型，它们需要实现相同功能的操作，但对于不同的类型，具体的实现方式有存在不同。

拿书上的例子来说，对于有理数R1, R2, 它们的值分别为 3/4, 5/6。那么对于它们，可以构造一个方法叫做 add 用于计算 R1, R2 的值，比如 (add R1 R2)。

同样的，如果是在同一个系统里，再增加一种类型 ———— 无理数。对于 I1，I2, 它们的值分别是 1 + 2i, 3 + 4i。同样，可以构造一个方法叫 add, 同于计算 I1，I2 的值，比如 (add I1 I2)。

问题来了：这是在同一个系统当中，add 被定义了两次，后一次会覆盖前一次，那么在运算过无理数后再调用 add 计算 R1, R2 时，系统必然会报错。

解法一: 对于支持面向对象和方法重载的语言，比如 Java, C++，这个问题根本就不是问题。写两个 add 方法，但是参数类型不同。当你调用 add 的时候，系统会根据参数的类型用于决定调用哪一个 add 方法。

解法二：对于像 C 语言这种语言，还可以重新命名函数的方法，比如对于计算有理数加法的函数，可以叫做 add_rational；对于计算无理数加法的函数，可以叫做 add_irrational。但问题也很明显，如果在这个系统增加更多种需要进行加法运算的数据类型，那么对于每一种数据类型定义一种函数，而且名字还需要确保不同。假如在系统设计初期，设计者能想好这么多名字，比如 100 种，那勉强还算解决了。然而对于用户来说，这就很头疼了。如果我面对一个支持 100 种数据类型的系统，每操作一种数据类型，我就需要查查手册。如果有一个 add 函数能支持任意一种数据类型加法的运算，那么用户必然对这个系统的好感度必然直线上升。

解法三：那就定义一个 add 函数，当传入两个数据时，判断一下类型，在进行相应的操作就好了。
伪代码如下:

1
2
3
4
5
6
7
8
9
10
def add(x, y):
    if type(x) == "rational" and type(y) == "rational":
        pass # 对应有理数加法的代码
    elif type(x) == "irrational" and type(y) == "irrational":
        pass # 对应无理数加法的代码
    elif type(x) == "type-a" and type(y) == "type-a":
        pass # 对应type-a加法的代码
    elif type(x) == "type-b" and type(y) == "type-b":
        pass # 对应type-b加法的代码
    elif ... # 以此类推，每个elif 部分对应一种数据类型的加法运算

对于开发者实现来说，这个方法还算可以，虽然不算美观。
记得去年我在某公司实习的时候，我所在的那个项目中还真有这样的代码。一个文件中“挂”了至少上百个 else if。每个实习生一旦写好一个模块，就要在这个文件上加一个对应的 else if。然后因为多个实习生，每个实习生的工作台上都有整个项目的文件，最后提交的时候，负责管理实习生的员工还查看每个实习生增加了几个 else if，然后把它们一个一个汇总到一个文件上。
所以很明显，这个方法勉强可以，虽然对开发来说事实上会带来一点繁琐。

解法四: 在以上三种解法基础上，终于到了 DDP 登场。我认为 DDP 和解法三的一个重要区别就是，DDP 开发了一个表结构，帮助开发者分析类型并调用对应函数。同时在这时，系统还可以模块化，增加命名空间，避免设计者把过多时间花在起名字上。

DDP 中有两个重要的函数 put, get。

1
2
put(<操作>，<方法所需参数的各个类型>，方法名)
get(<操作>，<方法所需参数的各个类型>)

先不管具体是怎么实现的，先明白功能。put 的功能是往系统的一个特殊数据结构中存储一种方法，而这个方法对应的操作是 <操作>，对应参数的各个类型为<方法所需参数的各个类型>。
比如:

1
2
put("add", ["rational", "rational"], rational-add)
put("add", ["irrational", "irrational"], irrational-add)

而 put 的目的是为了 get，这个才是关键。通过 get 就可以实现取到对应数据类性的方法。

1
2
get("add", ["rational", "rational"]) # rational-add
get("add", ["irrational", "irrational"]) # irrational-add

这看上去似乎没什么用，但是如果在继续定义 add:

1
2
def add(x, y)
    return get("add", [type(x), type(x)])(x, y)

那么这个 add 就可以处理各种系统支持的类型了。
比如如果我用 add 计算有理数 R1, R2的和，那么 get 会返回 rational-add 方法计算R1， R2；如果再用 add 计算无理数 I1, I2的和，那么 get 会返回 irrational-add 方法计算I1， I2。

对于用户来说，每次计算调用的都是同一个方法 add，而对于系统，每次用于计算的则是不同的方法计算。那么如何解决命名空间呢？因为 put 方法已经在系统中实现，属于全局。那么put 也可以在任何地方使用，比如:

1
2
3
4
5
6
7
8
9
def install_rational():
    def _add(x, y):
        pass # 处理有理数加法
    put("add", ["rational", "rational"], _add)

def install_irrational():
    def _add(x, y):
        pass # 处理无理数加法
    put("add", ["irrational", "irrational"], _add)

这里事实上还涉及到了闭包。因为 _add 方法是在不同的函数中定义的，处于不同的命名空间。所以在这里，对于不同的数据类型的加法函数，可以采用同一个命名。另外，这种设计事实上也模块化了，因为当你需要用有理数时，只需执行 install_rational()。这样这个系统就支持有理数加法操作。

对比解法三，四可以发现，解法四更简洁化了，它开发了一个程序用于自动添加对应的方法。

因为 put 操作的作用是往表结构中存储数据，那么这个表结构可以采用类似 python 中的 dict 实现。

Message Passing

Message Passing 是本章另一个令我感觉十分新颖的点。在我看来，Message Passing 的特点在于它将一个数据，既可以看作函数操作，又可以看作对象操作。同时它又与 Object-oriented Programming (OOP) 又有些许相似之处。

同样，以有理数的实现为例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def make_rational(numer, denom):
    def add(y):
        pass

    def sub(y):
        pass

    def mul(y):
        return make_rational(numer * y("numer"), denom * y("denom"))

    def dispatch(msg):
        if msg == "add":
            return add
        elif msg == "sub":
            return sub
        elif msg == "mul":
            return mul
        elif msg == "numer":
            return numer
        elif msg == "denom":
            return denom
        ...
    return dispatch

可以看出，如果构造一个有理数对象，那么这个方法实际上返回的是 dispatch 的方法。而如果用调用 add 方法，或 获得 numer 属性，那么就要把构建出来的对象当作函数使用:

1
2
3
x, y = make_rational(2, 3), make_rational(4, 5)
x("add")(y)
x("numer")

这里是第一个有趣的地方，在第一行中，x, y 被看作是对象，而在第二、三行中，x, y 又被看作是方法 / 函数。这么一来 对象 和 函数 的界限似乎被打破了，或者说，对象 和 函数进行了自由的转换。

第二个有趣的地方在于这与 OOP 的关系，如果在一个支持 OOP 语言编写的系统中存在 Rational 这个类，那么 make_rational() 就类似与构造函数 Rational()；x("add")(y) 就类似于 OOP 中的 x.add(y)；x("numer") 类似于 OOP 中的 x.numer。也就是说，在一个不支持面向对象，但支持将函数看作对象操作的语言中，Message Passing 实现了类似于 OOP 的功能。

同样的，如果要定义一个通用的 add 操作，可以用以下方法实现:

1
2
3
4
def add(x, y):
    return x("add")(y)
x, y = make_rational(2, 3), make_rational(4, 5)
add(x, y)

那么用户就调用 add(x, y) 之时，又将 x，y 看作了对象而不是函数。倘若再增加一种无理数的数据类型，那也可以参照上文中有理数的实现方法实现，并且，如果无理数中的实现中，同样又对 “add” 的处理，那么无理数的相加也可以直接调用 add(x, y)。

Others

除了以上两点，在书中还有更多的讨论：其中一个常见的问题就是如果如何将add用于其他类型的相加，比如无理数和有理数的相加，无理数和自然数的相加。书中采用的方法很巧妙，它定义了一个升级的规则，如果两个相加的数不在一个等级，那么将其中一个等级较低的进行升级。比如，3 / 4 与 2 相加，2 先升级，成为有理数2 / 1，这是可以处在同一层级（都是有理数），所以可以相加；3 + 4i 与 2 相加，2 先升级，成为了 2 / 1，但仍不在同一个层级，因此再升级，成为2 / 1 + 0i，这时可以相加了（注意，实数部分的 3 + 2 / 1 计算过程中事实上也运用了升级的规则）。

总体来说，对于以上这几点，我只是做了比较基础的一些总结。如果对这方面感兴趣，建议阅读书籍，书中还有更多的内容值得阅读和思考。

References

  1. SICP
  2. SICP 解题参考
  3. DDP and Message Passing @ inst.eecs.berkeley.edu
  4. Data-Directed Programming @ berkeley-cs61as
  5. Message Passing @ berkeley-cs61as
LICENSED UNDER CC BY-NC-SA 4.0