面向对象语言导论(节选) 1(ZT)

（译自Martin Abadi, Luca Cardelli的对象理论一书的第一部分）
译者前言
这本书是我们上面向对象类型理论的教材。当时上这门课时，心里满不以为然，觉得自己的C++和OO已经颇有造纸，C++和Java的类型系统不说倒背如流，也是轻车熟路，上这么一门课不是白拿学分？哈哈!
但一上起来，才发现自己竟如井底之蛙一样。老天，原来就这么简单的面向对象竟有这么多说道！原来除了C++, Java, 面向对象还有这么多没见过甚至没想过的东西！
前几章概论，勉强还都搞定了。但后面上到类型系统的建模，subject reduction的证明，就发现自己就象回到了本科时代，这，这，这怎么都是数学啊！
这两天心血来潮。就想把它翻译一下。后面艰深的地方自觉功力太浅，就不不自量力了。不过，倒可以把前面几章的概论翻译一下，如果能起到帮助大家开阔眼界的作用，也就没白费劲。

第二章，基于类的面向对象语言
基于类的面向对象语言是面向对象世界里的主流。它包括：
Simula, 第一个面向对象语言
Smalltalk, 第一个支持动态类型的语言
C++, 它的大部分基于类的特性继承自Simula.
等等等等。
与基于类的语言相对应的是基于对象的面向对象语言。这里“基于对象”的概念和把Visual Basic叫做基于对象的概念是不同的。这里的“基于对象”是指一个只以对象为中心，没有类的概念的语言，类似Python之类的语言。

现在，我们来介绍一下基于类的面向对象语言的一些共同特征。

1．类和对象
让我们先看一个类的定义：
代码:

class cell is
var contents: Integer :=0;
method get(): Integer is
return self.contents;
end;
method set(n:Integer) is
self.contents := n;
end;
end;



一个类是用来描述所有属于这个类的对象的共同结构的。这个cell类表示的对象拥有一个叫做contents的整数属性(attribute)，这个属性被初始化成0。它还描述了两个操作contents的方法。Get和set. 这两个方法的内容都是很直观的。Self变量表示这个对象自己。

对象的动态语义可以这样理解：
一个对象在内部被表示为一个指向一组属性的指针。任何对这个对象的操作都会经过这个指针操作对象的属性和方法。而当对象被赋值或被当作参数传递的时候，所传递的只是指针，这样一来，同一组属性就可以被共享。
(注， 有些语言如C++, 明确区分指向属性组的指针和属性组本身，而一些其它的语言则隐藏了这种区别)

对象可以用new从一个类中实例化。准确地说，new C分配了一组属性，
并返回指向这组属性的指针。这组属性被赋予了初始值，并包括了类C所定义的方法的代码。

下面我们来考虑类型。对一个new C所生成的对象，我们把它的类型记为InstanceTypeOf(c). 一个例子是：

代码:
Code:var myCell:
InstanceTypeOf(cell) := new cell;




这里，通过引入InstanceTypeOf(cell), 我们开始把class和type区分开来了。我们也可以把cell本身当作是类型，但接下来，你就会发现，那样做会导致混淆的。



2．方法解析。(Method Lookup)
给出一个方法的调用o.m(……), 一个由各个语言自己实现的叫做方法解析的过程负责找到正确的方法的代码。（译者按：是不是想起了vtable了？）。
直观地看，方法的代码可以被嵌入各个单个对象中，而且，对于许多面向对象语言，对属性和方法的相似的语法，也确实给人这种印象。
不过，考虑到节省空间，很少有语言这样实现。比较普遍的方法是，语言会生成许多method suite, 而这些method suite可以被同一个类的对象们所共享。方法解析过程会延着对象内指向method suite的指针找到方法。
在考虑到继承的情况，方法解析会更加复杂化。Method suite也许会被组成一个树，而对一个方法的解析也许要查找一系列method suite. 而如果有多继承的话，method suite甚至可能组成有向图，或者是环。

方法解析可能发生在编译时，也可能发生在运行时。

在一些语言中，方法到底是嵌入对象中的，还是存在于method suite中这种细节，对程序员是无关紧要的。因为，所有能区分这两种模式的语言特性一般在基于类的面向对象语言中都不被支持。
比如说，方法并不能象属性一样从对象中取出来当作函数使用。方法也不能象属性一样在对象中被更新。(也就是说，你更新了一个对象的方法，而同一个类的其它对象的该方法保持不变。)

3. 子类和继承 （Subclassing and Inheritance）
子类和一般的类一样，也是用来描述对象的结构的。但是，它是通过继承其它类的结构来渐进式地实现这个目的。
父类的属性会被隐式地复制到子类，子类也可以添加新的属性。在一些语言中，子类甚至可以override父类的属性（通过更改属性的类型来实现）
父类中的方法可以被复制到子类，也可以被子类override.
一个子类的代码的示例如下：

Code:subclass reCell of cell is
var backup: Integer := 0;
override set(n: Integer) is
self.backup := self.contents;
super.set(n);
end;
method restore() is
self.contents := self.backup;
end;
end;


对有subclass的方法解析，根据语言是静态类型还是动态类型而有所不同。
在静态类型的语言（如C++, Java）里，父类，子类的method suite的拓扑结构在编译时就已经确定，所以可以把父类的method suite里的方法合并到子类的method suite中去，方法解析时就不用再搜索这个method suite的树或图了。（译者按：C++的vtable就是这种方法）
而对于动态类型的语言，（也就是说，父子类的关系是在运行时决定的），method suite就无法合并了。所以，方法解析时，就要沿着这个动态生成的树或有向图搜索直到找到合适的方法。而如果语言支持多继承，这个搜索就更复杂了。

4. Subsumption和Dynamic Dispatch (译者按：呵呵，黔驴技穷，找不到合适的翻译了)

从上述的几个例子来看，似乎子类只是用来从父类借用一些定义，以避免重复。但是，当我们考虑到subsumption, 事情就有些不同了。什么是Subsumption呢？请看下面这个例子：

代码:

Code:var myCell: InstanceTypeOf(cell) := new cell;
var myReCell: InstanceTypeOf(reCell) := new reCell;
procedure f(x: InstanceTypeOf(cell)) is … end;



再看下面这段代码：

代码:

Code:myCell := myReCell;
f(myReCell);



在这两行代码中，头一行把一个InstanceTypeOf(reCell)类型的变量赋值给一个InstanceTypeOf(cell)的变量。而第二行则用InstanceTypeOf(reCell)类型的变量作为参数传递给一个参数类型为InstanceTypeOf(cell)的函数。
这种用法在类似Pascal的语言中是不合法的。而在面向对象的语言中，依据以下的规则，它则是完全正确的用法。该规则通常被叫做subtype polimorphism, 即子类型多态（译者按：其实subtyping应该是OO语言最区别于其它语言的地方了）
如果c’是c的子类，并且o’是c’的一个实例，那么o’也是c的一个实例。

更严格地说：
如果c’是c的子类，并且o’: InstanceTypeOf(c’)，那么o’:
代码:

InstanceTypeOf( c ).



仔细分析上面这条规则，我们可以在InstanceTypeOf的类型之间引入一个满足自反和传递性的子类型关系， 我们用<:符号来表示。（译者按：自反就是说， 对任何a, a 关系 a都成立，比如说，数学里的相等关系就是自反的。而传递性是说，如果a 关系 b, b 关系c, 就能推出a 关系c。 大于，小于等关系都是具备传递性的）

那么上面这条规则可以被拆成两条规则：
1． 对任何a: A, 如果 A <: B, 那么 a: B.
2． InstanceTypeOf(c’) <: InstanceTypeOf(c) 当且仅当 c’是c的子类

第一条规则被叫做Subsumption. 它是判断子类型（注意，是subtype, 不是subclass）的唯一标准。
第二条规则可以叫做subclassing-is-subtyping (子类就是子类型，绕嘴吧？)
一般来说，继承都是和subclassing相关的，所以这条规则也可以叫做：inheritance-is-subtyping (继承就是子类型)

所有的面向对象语言都支持subsumption (可以说，没有subsumption, 就不成为面向对象)。
大部分的基于类的面向对象语言也并不区分subclassing和subtyping. 但是，一些最新的面向对象语言则采取了把subtyping和subclassing分开的方法。也就是说，A是B的子类，但A类的对象却不可以当作B类的对象来使用。（译者按：有点象C++里的私有继承，但内容比它丰富）
好吧，关于区分subclassing和subtyping, 我们后面会讲到。

下面，让我们重新回头来看看这个procedure f. 在subsumption的情况下，下面这个代码的动态语义是什么呢？
代码:

Code:Procedure f(x: InstanceTypeOf(cell)) is
x.set(3);
end;
f(myReCell);



当myReCell被当作InstanceTypeOf(cell)的对象传入f的时候，x.set(3)究竟是调用哪一个版本的set方法呢？是定义在cell中的那个set还是定义在reCell中的那个呢？
这时，我们有两种选择，
1． Static dispatch (按照编译时的类型来决定)
2． Dynamic dispatch (按照对象运行时真正类型来决定)
（译者按，熟悉C++的朋友们一定微笑了，这再简单不过了。）
static dispatch没什么可说的。
dynamic dispatch却有一个有趣的属性。那就是，subsumption一定不能影响对象的状态。如果你在subsumption的时候，改变了这个对象的状态，比如象C++中的对象切片，那么动态解析的方法就可能会失败。
好在，这个属性无论对语义，还是对效率，都是很有好处的。
（译者按，
C++中的object slicing会把新的对象的vptr初始化成它自己类型的vtable指针, 所以不存在动态解析的问题。但实际上，对象切片根本不能叫做subsumption。
具体语言实现中，如C++, 虽然subsumption不会改变对象内部的状态，但指针的值却是可能会变化的。这也是一个让人讨厌的东西，但 C++ vtable的方案却只能这样。有一种变种的vtable方法，可以避免指针的变化，也更高效。我们会在另外的文章中阐述这种方法。）


5． 赛翁失马 （关于类型信息）
虽然subsumption并不改变对象的状态，在一些语言里（如Java）, 它甚至没有任何运行时开销。但是，它却使我们丢掉了一些静态的类型信息。

比如说，我们有一个类型InstanceTypeOf(Object), 而Object类里没有定义任何属性和方法。我们又有一个类MyObject, 它继承自Object。那么当我们把MyObject的对象当作InstanceTypeOf(Object)类型来处理的时候，我们就得到了一个什么东西也没有的没用的空对象。

当然，如果我们考虑一个不那么极端的情况，比如说，Object类里面定义了一个方法f, 而MyObject对方法f做了重载，那么, 通过dynamic dispatch, 我们还是可以间接地操作MyObject中的属性和方法的。这也是面向对象设计和编程的典型方法。

从一个purist的角度看（译者按，很不幸，我就是一个purist）, dynamic dispatch是唯一你应该用来操作已经被subsumption忘掉的属性和方法的东西。它优雅，安全，所有的荣耀都归于dynamic dispatch！！！ (译者按，这句话是我说的)

不过，让purist们失望的是，大部分语言还是提供了一些在运行时检查对象类型，并从而操作被subsumption遗忘的属性和方法。这种方法一般被叫做RTTI（Run Time Type Identification）。如C++中的dynamic_cast, 或Java中的instanceof.

实事求是地说，RTTI是有用的。（译者按，典型的存在就是合理的强盗逻辑，气死我了！）。但因为一些理论上以及方法论上的原因，它被认为是破坏了面向对象的纯洁性。
首先，它破坏了抽象，使一些本来不应该被使用的方法和属性被不正确地使用。
其次，因为运行时类型的不确定性，它有效地把程序变得更脆弱。
第三点，也许是最重要的一点，它使你的程序缺乏扩展性。当你加入了一个新的类型时，你也许需要仔细阅读你的dynamic_cast或instanceof的代码，必要时改动它们，以保证这个新的类型的加入不会导致问题。而在这个过程中，编译器将不会给你任何帮助。
很多人一提到RTTI, 总是侧重于它的运行时的开销。但是，相比于方法论上的缺点，这点运行时的开销真是无足轻重的。

而在purist的框架中（译者按，吸一口气，目视远方，做深沉状），新的子类的加入并不需要改动已有的代码。
这是一个非常好的优点，尤其是当你并不拥有全部源代码时。

总的来说，虽然RTTI （也叫type case）似乎是不可避免的一种特性，但因为它的方法论上的一些缺点，它必须被非常谨慎的使用。今天面向对象语言的类型系统中的很多东西就是产生于避免RTTI的各种努力。
比如有些复杂的类型系统中可以在参数和返回值上使用Self类型来避免RTTI. 这点我们后面会介绍到。



6．协变，反协变和压根儿不变 （Covarance, Contravariance and Invariance）

在下面的几个小节里，我们来介绍一种避免RTTI的类型技术。在此之前，我们先来介绍“协变”，“反协变”和“压根儿不变”的概念。

协变
首先，让我们来看一个Pair类型： A*B
这个类型支持一个getA()的操作以返回这个Pair中的A元素。

给定一个A’ <: A, 那么，我们可以说A’*B <: A*B。


为什么呢？我们可以用Subsumption的属性加以证明:

假设我们有一个A’*B类型的对象a’*b, 这里，a’:A’, b:B, a’*b <: A’*B
那么，因为，A’ <: A， 从subsumption, 我们可以知道a’:A, getA():A 所以， a’*b<: A*B

这样，我们就定义A*B这个类型对于A是协变的。
同理，我们也可以证明A*B对于B也是协变的。


正规一点说，Covariance是这样定义的：

给定L(T), 这里，类型L是通过类型T组合成的。那么，
如果 T1 <: T2 能够推出 L(T1) <: L(T2), 那么我们就说L是对T协变的。


反协变

请看一个函数： A f(B b); (用functional language 的定义也许更简洁， 即f: B->A)

那么，给定一个B’ <: B, 在B->A 和 B’->A之间有什么样的subtype关系呢？

可以证明，B->A <: B’->A 。
基于篇幅，我们不再做推导。

所以，函数的参数类型是反协变的。
Contravariance的正规点的定义是这样的：
给定L(T), 这里，类型L是通过类型T组合成的。那么，
如果 T1 <: T2 能够推出 L(T2) <: L(T1), 那么我们就说L是对T反协变的。

同样，可以证明，函数的返回类型是协变的。

压根儿不变

那么我们再考虑函数g: A->A
这里，A既出现在参数的位置，又出现在返回的位置，可以证明，它既不是协变的，也不是反协变的。

对于这种既不是协变的，也不是反协变的情况，我们称之为Invariance (译者按：“压根儿不变”是我编的，这么老土的翻译，各位不必当真)

值得注意的是，对于第一个例子中的Pair类型，如果我们支持setA(A), 那么，Pair就变成Invariance了。


7．方法特化 （Method Specialization）
在我们前面对subclass的讨论中，我们采取了一种最简单的override的规则，那就是，overriding的方法必须和overriden的方法有相同的signature.
但是，从类型安全的角度来说，这并不是必须的。应用我们前面讨论的协变和反协变的知识，我们完全可以让方法的返回类型协变，让方法的参数类型反协变。
这样，只要A <: A’, B’ <: B, 下面的代码就是合法的：
代码:

Code:class c is
method m(x:A):B is … end;
method m1(x1:A1):B1 is … end;
end;
subclass c’ of c is
override m(x: A’):B’ is … end;
end;



我们暂时不允许属性的协变。因为只有immutable的属性才是协变的。允许对属性的修改使得属性都是invariant的。

特殊变量self这里有一个有趣的属性，它是一个参数，但它确是协变的。这种特殊特性是由于self变量只能隐式地由编译器传入，所以避免了协变参数的不安全性。

还有一点有趣的地方是，上面的协变发生在override的时候，也就是，子类要改写父类的方法的时候。但是，在继承时，参数和返回类型的变化规律就又是另一回事了。
比如说，下面这个例子：
代码:

Code:class c is
method m(x:A):B is … end;
method m1(x1:A1):B1 is … end;
end;
subclass c’ of c is
inherit m(x: A’):B’;
//这里，方法m的代码被继承，子类只是重定义方法m的接口signature
end;



那么，这里，参数就是协变的，而返回类型却是反协变的了。


这里，从另一个侧面，我们看到了subtyping (通过override), 和subclassing (通过inheritance) 的本质上的区别。

8. Self类型的特化 （Self Type Specialization）

方法特化允许你灵活地在子类中继承或改写父类的方法时改变类型。
除此之外，我们也许还需要另一种灵活性。考虑下面的代码：
代码:

Code:class c is
method getSelf(): InstanceTypeOf(c) is
return self;
end;
end;
subclass c’ of c is
var y: Integer := 0;
end;

InstanceTypeOf(c’) x := (new c’).getSelf();



这里，最后一句代码是非法的，因为getSelf()的返回类型是InstanceTypeOf(c), 而x的类型是InstanceTypeOf(c’).

当然，子类c’可以重载getSelf()方法， 返回类型InstanceTypeOf(c’)：
代码:

Code:subclass c’ of c is
var y: Integer := 0;
override getSelf(): InstanceTypeOf(c’) is
return self;
end;
end;


这样，因为方法的返回类型是协变的，并且特殊变量self (译者按，就是C++/Java中的this)不论是在继承还是重载中都是协变的, 所以以上的子类定义是可行的。
但是，这要求每个子类都要重载这个方法。而且，如果某些返回self的方法想要隐藏一些逻辑的话，这种重载也是不可能的。比如：
代码:

Code:class c is
method changeAndReturn(): InstanceTypeOf(c) is
…//做一些更新操作。并且对子类隐藏逻辑。
return self;
end;
end;

subclass c’ of c is
var y: Integer := 0;
override changeAndReturn (): InstanceTypeOf(c’) is
return super.changeAndReturn();
end;
end;


这里这个子类c’的定义就是不成立的， 因为super.changeAndReturn()返回的是InstanceTypeOf(c).

那么，有没有方法可以使子类c’继承的方法自然地返回InstanceTypeOf(c’)呢？这样一来，因为我们没有被迫丢失一些类型信息，RTTI就能够被避免。

这种考虑自然而然地引出了一种新的类型：Self类型。与self变量相似，Self类型代表的是这个对象的运行时真正类型。只有self变量是Self类型的。因为self变量的特殊协变特性，这样的类型是安全的。使用Self类型， 以上的例子可以被改写成：
代码:

Code:class c is
method getSelf(): Self is
return self;
end;
end;
subclass c’ of c is
var y: Integer := 0;
end;

InstanceTypeOf(c’) x := (new c’).getSelf();



这时，最后一句就合法了，因为现在(new c’).getSelf()的返回类型是InstanceTypeOf(c’)了。

除了方法的返回类型，我们也可以把属性定义为Self类型，为了保证类型的安全，这样的属性只能用self或其它Self类型的值进行初始化或更新。也就是说，如果在class c中定义了一个Self类型的属性，你不能用一个InstanceTypeOf(c)的变量来初始化或更新它。

对典型的基于类的面向对象语言做如上所述的扩展是可行的，而且是没有任何副作用的（除了会使类型检查系统稍微复杂一些）。它使强类型面向对象语言的表达能力大大增强。并且有效地防止了类型信息的不必要丢失。

很自然地，读者也许会想到把Self类型用于方法的参数。Eiffel就是这样做的。但不幸的是，参数对于重载来说却是contravariant的，就象我们前面所说明的那样。重载时，类型泛化是可以的，但特化却是不安全的。

不过，在基于类的面向对象领域里，对参数使用Self类型还是被广泛研究并使用的。我们会在后面在介绍相关的技术。

下章预告：
对象类型，泛型技术，分离subclassing和subtyping, 对象协议(object protocol).