walker...to the next step

SICP第二章提到了data-directed programming和message passing，及它们的关系。正好最近客户那边重构代码天天提data driven，而且message passing这个词一下让我想到了Smalltalk和OO，所以就把头绪理一下。

考虑一个非常常见的场景：你有两个不同的数据结构，它们其上各自有一组类似但不相同的操作。显然这些操作是针对于各自的具体数据类型的。现在的要求是：

1. 提供一组通用操作作为这两个数据结构的外部接口。
2. 要考虑将来加入新的具体数据类型对系统的影响。
3. 要考虑将来加入新的操作对系统的影响。（感觉OO老是故意回避这个问题。事实上接口变动是很正常很频繁的。当然我设计模式学艺不精，请指正。）

按照OO和设计模式的思路，我们应该使用adapter设计模式。Adapter要实现某抽象数据类型，而这个抽象数据类型就是外部接口。client code仅使用此抽象数据类型，这样第一个要求就满足了。至于新加入的具体数据类型，大不了再加adapter就是，对现有代码无需做改动。不过加入新的操作就很麻烦了，每个具体数据类型都要改，抽象数据类型也要改。当然如果新加入的操作对每个具体类型都一样，可以放进抽象数据类型里。

在语言的实现方面，这需要是一个dynamic dispatch/binding的机制。Java和C++都采用了虚函数表，将对于抽象数据类型的操作在运行时映射到具体数据类型。Smalltalk和Python则采用了完全的动态也就是运行时查找，基本就是大查哈希表。

好吧现在我们剥掉OO那个外壳，回到Scheme的朴素思路。还是得有个抽象数据放在这儿当接口，在Scheme中没有object这个把数据和操作绑一起的东西，这个抽象数据其实就是一组通用操作。但现在语言不再自觉地替我们做这些dispatch，或者说将抽象映射到具体的工作了，我们得自己动手了。所以首先最弱智的我们可以用那一手generic operations with explicit dispatch：我们定义通用操作，然后在在其中显式的判断具体数据类型，再调用具体的操作。这一手确实把client code隔离开了，也就是满足了第一条，但显然每加一个具体数据类型都得在每个通用操作里加一个判断分支，没有满足第二条。这就是书中说的not additive。不过如果加一个操作的话还是挺方便的哈，老代码基本不用改。

第二手是用data-directed。其实质就是把那些判断也就是dispatch拿出来放一表或者说registry里。此表以同一具体数据类型的不同操作为列，以不同具体类型的相同操作为行（看SICP 181页或者自己画一个）。表中放的是某一具体数据类型的具体操作。通用操作不再充斥着写死的判断语句，而是接受操作名称作为参数，并从具体数据中获得类型信息，然后查表取得针对具体数据类型的操作并执行之。这样dispatch就成隐式的了，就是一个查表的过程。

所谓的data driven跟这个差不多就一个意思：把代码和数据严格分开，用数据驱动程序，新具体数据类型加进来的时候代码就不用改了。这样的代码就是additive的。详见ESR的Unix编程艺术和Wikipedia。

最后说message passing。它与generic operations with explicit dispatch是相对的。GOED是在operations里包含dispatch，其实质是，每一个operation其实就是data-directed里面的那个表里的一行，根据传入的数据类型自行解决dispatch问题。MP则是，把这个表分割成列，每个data type根据传入的operation自行解决dispatch问题。

在Scheme里表现出来就是，将数据表示为过程（带状态的过程，也就是闭包），其参数是operation。过程内部显式判断operation名称，再做或者调用具体操作。这其实已经是典型的OO特征了。显式判断operation名称就相当于调用实例方法啊！！！相比data-directed，显然是写死了。像Java这种OO语言呢里那些方法名不就是写死的么？当然动态语言除外。Python有个dict大家都知道。所以Scheme这里(object 'method)就相当于Java里object.method()啊！只不过这里dispatch是我们自己写的！而且这个dispatch不是动态的。

哈，object果然就是闭包！

然后SICP里为了提供Scheme风格的数据抽象，对MP也写了个apply-generic函数。据此我们可以再把那些通用操作写出来。比如

(define (real-part z) (apply-generic 'real-part z))

当新的具体数据类型加入时，我们需要写新的过程即可。但加入新操作就费劲了。注意MP和上面OO的局限多么的一致！其实它们的内在就是一样的！

基本思想是，如果我们把数据（具体数据类型）和代码（操作）视作正交，那么GOED和MP各自按住了一个，或者说基于其中一个做模块化，针对另一个做dispatch。所以遇到它们dispatch的那个东西要增加或者减少时，它们划分好的模块就被切了，怎么整都不爽。（想想那个表在按列切的时候多了一行，或按行切的时候多了一列，等于跨了已划分好的模块。）data-directed则是按照这两个维度做模块化，切得更细，需要两个坐标（具体数据类型，操作）才能找到目标。用这个思想看2.76那道题，一目了然。

私以为经验的重要性大致等同于知识，但二者皆低于思想。

继承和多重继承（http://en.wikipedia.org/wiki/Multiple_inheritance）是language features，是面向对象技术为了使程序向现实贴近的一个手段。不过在面向对象理论中多重继承也不是必须的，基本上所有可以用多重继承实现的，都可以通过单继承来work around。这句话更多来自于实践而不是严格的理论。

从继承的实现角度来说，当子类对象被初始化时，实际上有一个父类对象也被初始化并且组合到子类对象中。这种来自继承的组合和普通的组合的不同之处主要在于，我们是仅仅需要使用父类提供的功能，还是说也需要使用父类提供的接口。

有继承就有多态。C++为了实现多态引入了late/dynamic/runtime binding（Connecting a function call to a function body is called binding）：编译时，编译器不知道通过一个基类引用调用的某函数，具体调用的到底是那段代码。所以传统的非OOP编译器的early/static binding机制就行不通了。C++中实现late binding的手段是虚函数。Python和Java中所有的函数/方法实际上都是虚的。所以说虚函数只是实现多态的一个（并不唯一的）技术手段。

具体的实现机制是，编译器为每一个包含虚函数的类（包括通过继承得来虚函数的类）都生成一段分配空间并初始化VTABLE（就是所谓的虚函数表）的代码。于是在运行的时候内存中就会有这样的VTABLE，它们包含了该类中所有虚函数的实现代码的地址。这是非常合乎逻辑的，因为同一个具体类的所有对象，其虚函数实现都是一样的，所以一个类只需要一个虚函数表。

接下来，每当编译器在源代码中看到new一个对象的时候，都会做一些小偷小摸的事：它会生成一些额外的代码，在对象中在分配空间给一个指针成员变量VPTR（对程序员是不可见的！！！），通常被放在对象内存布局最开始的地方，也就是this指针指向的地址。这个VPTR指向本对象的类所属的VTABLE。这部分代码被十分自然的放在构造器中，所以运行时new一个对象出来，对象被初始化后，这个VPTR就已经ready好了。明白了吧！这就是为什么如果程序员不写构造器，编译器会搞个默认构造器出来。Java中也是这样。

但是VTABLE的地址是在运行时才available的。初始化VPTR这段代码必须在运行时获得本对象的类型信息才能知道正确的VTABLE是哪个！所以编译器确实是插入了类型信息到对象中的。在运行时的时候可以获得。题外话：这也是RTTI的本质。

前面的说法有一个hole，就是如果一个对象多重继承怎么办？这样对于同一个对象就会有多个VTABLE。最直觉也是最家常的做法，就是搞多个VPTR出来，也是都放在对象头部。但这时就需要pointer fixups即thunks(http://en.wikipedia.org/wiki/Virtual_table)，即当用不同的类型去引用该对象时，使用不同的VTABLE。

接下来的事情就简单了：当通过一个基类指针调用虚函数时，不管对象的具体类型是啥，总能找到正确的VTABLE，通过其找到被调用函数的正确地址，并调用之。

从语言使用者的角度来看，virtual只是一个关键字。使用者实际上不需要知道虚函数是怎么实现的。但由于虚函数调用会有额外的开销，有心的程序员会去研究它的实现并且在适当的时候才使用。

所谓纯虚函数，就是只有声明没有实现的函数。包含至少一个纯虚函数的类就是抽象类。

多重继承引入了二义性问题。最典型的菱形问题http://en.wikipedia.org/wiki/Diamond_problem。

C++使用虚函数来解决多态调用，使用了虚基类来解决菱形问题。

Python则规定了一个特别的method resolution order来摒除二义性：http://en.wikipedia.org/wiki/Diamond_problem。

Python中的super http://fuhm.net/super-harmful/ 

类型系统的本质是，赋予计算机中那些莫名二进制数据一些意义。它定义了这些东西代表了啥，并且规定了在特定类型上能做哪些操作。编译器/解释器可以检查对象的类型，也可以不检查；可以在编译时检查，也可以在运行时检查。

1. object/value 对象/值
   • a. 程序员在程序空间中可操纵的东西
   • b. 对应一些内存空间
   • c. 下文中的“对象”和“值”可互换。一般我会用“对象”
2. class 类
   • a. 类只不过是用户定义类型罢了
   • b. 实例的类型就是对应的类
   • c. OO中的继承经常基于类。但Self和JavaScript则是基于prototype，比较另类
   • d. 用户定义类型是一个语言feature。要提供这个feature，不一定非得提供类机制。比如JavaScript就是用函数定义不同的对象，用prototype实现继承（代码重用）。
3. type 类型
   • a. 每一个对象都有一个或多个类型（面向对象语言一般都支持一个对象有多个类型，尤其是用户定义类型即class）
   • b. 类型这个东西在某些语言中，程序员可以操纵，即它们也是对象。在另一些语言中则不是
   • c. 前一种情况的例子包括Python, Java。不过Java只为操纵类型提供了很弱的支持，并且primitive类型无法操纵（虽然有wrapper class）。我勉强把Java归为这一类。Python中的类型则是第一级（first-class）公民。你可以写return int这样的语句
   • d. C属于后一种情况。你可以传递一个类型为某struct的值，而不是这个struct本身。
   • e. 当类型也是对象的时候，会引发一个新的问题：由于对象必有类型，所以类型对象（包括类）也有类型，对吧？（Java里的类不是对象，但可以用对象表示）
   • f. 那么类型的类型是什么呢？？？Python里有个type类，可谓是元类型。事实上Python允许你通过创建type类的instance创建新类型。哦my god。使用这种方式创建出的类型和用户定义类型class应该是没啥区别。所有类型对象，包括class，都是type class的实例。实例的类型当然就是对应的class了，所以Python中，类型的类型就是这个type class。
   • g. 接着说Python。type class也是个class啊，class在Python里也是第一级公民，也是对象。（咱就说new-style class吧，不要讨论old-style的了。）那type class的类型是什么呢？所有的class的类型都是type class，所以它自己也不例外。。。我们会在Java中看到类似的情况。
   • h. Java里面的类不是对象，本质上是不可操纵的。Java使用java.lang.Class的实例来表示class。你可以通过这些实例获得一些类型信息，还可以用它们创建出对应它们所表示class的实例。对应每一个类，都可以获得对应的java.lang.Class实例。当然对于java.lang.Class这个类本身，也可以获得其对应的java.lang.Class实例。

赋值

函数

高阶函数

工作在更高层次（概念）上 and/or generalize and/or 隐藏细节

A tail call is a subroutine call just before the end of a subroutine.

If a subroutine performs a tail call on itself, this is called tail recursion. This can be optimized to a form of iteration, an optimization which is almost always done in functional programming languages.

今天看书，里面讲静态作用域（词法作用域）和动态作用域。想起大概一年多以前用过一点Common Lisp，里面就可以声明动态作用域的变量。基本上就是说，遇到一个符号的时候，不是根据源代码（静态，词法，写程序时）的结构来bind，而是在运行时根据函数调用栈（动态）来bind。举个例子，你在一个函数f里引用了变量v，但是函数f里并没定义这个变量，也不存在这个全局变量，但是，调用f的函数（注意是调用f而不是定义f的函数）g定义了这个变量，那就成了，就是它。真变态。

支持这个特性的语言一定是解释执行的。因为编译的时候你根本就不知道这个变量是什么，既没有这个变量的地址，也不知道它的大小，没法分配空间。实现起来并不困难，只要顺着运行栈往调用者方向一路查去就成了。实现上的方便一般都不会带来好结果。。。动态作用域是难以理解并容易出错的，所以现在很少见了。