9 对象和类
在许多编程工作中，程序都要用接口管理某些状态。例如，文件系统内部状态的访问和修改 只能通过系统的接口。状态常常涉及多个变量，为了维护状态的一致性，必须协同修改那些 变量。因此，我们需要某种技术，确保组成状态的多个变量能协同更新。 面向对象编程 (Object-oriented programming) 技术正是为了完成这一任务。
在面向对象编程中，每个受管理的状态称为一个对象 (object)。一个对象中存有 多个量，称为字段 (field)；有多个相关过程，称为方法 (method)，方 法能够访问字段。调用方法常被视为将方法名和参数当作消息传给对象；有时，又说这是 从消息传递 (message-psasing) 的视角看待面向对象编程。
在状态那样的有状态语言中，过程也能体现用对象编程的优势。过程是一种对象， 其状态包含于自由变量之中。闭包只有一种行为：拿参数调用它。例如， g-counter的 g 控制计数器的状态，此状态的唯一操作就是递增。但更常 见的是，一个对象具有多种行为。面向对象的编程语言具有这种能力。
一个方法通常需要管理多重状态，例如多个文件系统或程序中的多个队列。为便于方法共享， 面向对象编程系统通常提供名为类 (class) 的结构，用来指定某种对象的字段及 方法。每个对象都创建为类的实例 (instance)。
类似地，多个类可能有相似而不相同的字段和方法。为便于共享实现，面向对象编程语言通 常支持继承 (inheritance)，允许程序员增改某些方法的行为，添加字段，对现有 类小做修改，就能定义新类。这时，由于新类的其他行为从原类继承而得，我们说 新类继承于 (inherit from) 或扩展 (extend) 旧类。
不论是用代码建模真实世界中的对象还是人工层面的系统状态，一旦程序能由结合行为和状 态的对象组成，其结构通常都清晰明了。将行为类似的对象与同一个类关联起来，也是自然 而然的。
真实世界中的对象通常兼具状态和行为，后者要么控制前者，要么受前者控 制。例如，猫能吃，打呼噜，跳，躺下，这些活动都由猫当前的状态控制，包括有多饿，有 多累。
对象和模块既相似，又不同。模块和类都提供了定义模糊类型的机制，但对象是一种具有行 为的数据结构，模块只是一组绑定。同一个类可以有很多个对象；大多数模块系统没有提供 相仿的能力。但 PROC-MODULES 这样的模块系统提供了更为灵活的方式来控制名字的可见性。 模块和类能够相得益彰。
9.1 面向对象编程
本章，我们研究一种简单的面向对象语言，名为 CLASSES。CLASSES 程序包含一些类声明， 然后是一个可能用到那些类的表达式。
展示了用这种语言写成的简单程序。它定义了继承于 object 的类 c1。类 c1 的每个对象都包含两个字段，名为 i 和 j。 字段叫做成员 (member) 或实例变量 (instance variable)。类 c1 支持三个方法或成员函数 (member function)，名为 initialize、 countup 和 getstate。每个方法包含方法名 (method name)， 若干方法变量 (method var)（又称方法参数 (method parameters)）， 以及方法主体 (method body)。方法名对应 c1 实例能够响应的消息种类。有时，我们称之为 “c1 的方法 countup”。
[!ht]
class c1 extends object
field i
field j
method initialize (x)
begin
set i = x;
set j = -(0,x)
end
method countup (d)
begin
set i = +(i,d);
set j = -(j,d)
end
method getstate () list(i,j)
let t1 = 0
t2 = 0
o1 = new c1(3)
in begin
set t1 = send o1 getstate();
send o1 countup(2);
set t2 = send o1 getstate();
list(t1,t2)
end
本例中，类的每个方法都维护完整性约束或不变式 i = -j。当然，真实程序的 完整性约束可能复杂得多。
中的程序首先初始化三个变量。t1 和 t2 初始化为 0。 o1 初始化为类 c1 的一个对象。我们说这个对象是类 c1 的一个实 例。对象通过 new 操作创建。它会触发调用类的方法 initialize，在本例中， 是将对象的字段 i 设置为 3，字段 j 设置为 -3。然后，程序调用 o1 的 方法 getstate，返回列表 (3 -3)。接着，它调用 o1 的方法 countup，将两个字段的值改为 5 和 -5，然后再次调用 getstate，返回 (5 -5)。最后，值 list(t1,t2)，即 ((3 -3) (5 -5))，成为整段程序的 返回值。
[!ht]
class interior-node extends object
field left
field right
method initialize (l, r)
begin
set left = l;
set right = r
end
method sum () +(send left sum(),send right sum())
class leaf-node extends object
field value
method initialize (v) set value = v
method sum () value
let o1 = new interior-node(
new interior-node(
new leaf-node(3),
new leaf-node(4)),
new leaf-node(5))
in send o1 sum()
解释了面向对象编程中的关键思想：动态分发 (dynamic dispatch)。在这段程序中，树有两种节点，interior-node 和 leaf-node。通常，我们不知道是在给哪种节点发送消息。相反，每个节点接收 sum 消息，并用自身的 sum 方法做适当操作。这叫做动态分发。这里， 表达式生成一棵树，有两个内部节点，三个叶节点。它将 sum 消息发给节点 o1； o1 将 sum 消息发给子树，依此类推，最终返回 12。这段程序也表明：所有方 法都是互递归的。
方法主体可通过标识符 self（有时叫做 this）调用同一对象的其他方法， self 总是绑定于方法调用时的对象。例如，在
class oddeven extends object
method initialize () 1
method even (n)
if zero?(n) then 1 else send self odd(-(n,1))
method odd (n)
if zero?(n) then 0 else send self even(-(n,1))
let o1 = new oddeven()
in send o1 odd(13)
中，方法 even 和 odd 递归调用彼此，因为它们执行时，self 绑定到包 含二者的对象。这就像 中，用动态绑定实现递归。
9.2 继承
通过继承，程序员能够渐进地修改旧类，得到新类。在实践中，这十分有用。 例如 中的经典例子：有色点与点类似，但多了处理颜色的方法。
[!ht]
class point extends object
field x
field y
method initialize (initx, inity)
begin
set x = initx;
set y = inity
end
method move (dx, dy)
begin
set x = +(x,dx);
set y = +(y,dy)
end
method get-location () list(x,y)
class colorpoint extends point
field color
method set-color (c) set color = c
method get-color () color
let p = new point(3,4)
cp = new colorpoint(10, 20)
in begin
send p move(3,4);
send cp set-color(87);
send cp move(10,20);
list(send p get-location(), % 返回 (6 8)
send cp get-location(), % 返回 (20 40)
send cp get-color()) % 返回 87
end
如果类 c_2 扩展类 c_1，我们说 c_1 是 c_2 的父类 (parent) 或超类 (superclass)，c_2 是 c_1 的子类 (child)。在继承中， 由于 c_2 定义为 c_1 的扩展，所以 c_1 必须在 c_2 之前定义。作为起始， 语言还包含一个预先定义的类，名为 object，它没有任何方法或字段。由于类 object 没有 initialize 方法，因此无法用它创建对象。除 object 之外 的所有类都有唯一父类，但可以有多个子类。因此，由 extends 得出的关系在类与类 之间产生了树状结构，根为 object。因为每个类至多只有一个直接超类，这是一种 单继承 (single-inheritance) 语言。有些语言允许类继承自多个 超类。多继承 (multiple inheritance) 虽然强大，却不无问题。在练习中，我们 会看到一些不便之处。
[!t]
field x
field y
method initialize () 1
method setx1 (v) set x = v
method sety1 (v) set y = v
method getx1 () x
method gety1 () y
class c2 extends c1
field y
method sety2 (v) set y = v
method getx2 () x
method gety2 () y
let o2 = new c2()
in begin
send o2 setx1(101);
send o2 sety1(102);
send o2 sety2(999);
list(send o2 getx1(), % 返回 101
send o2 gety1(), % 返回 102
send o2 getx2(), % 返回 101
send o2 gety2()) % 返回 999
end
术语继承源于宗谱的类比。我们常常引申这一类比，说类的祖 先 (ancestor)（从类的父类到根类 object） 和后代 (descendant)。如果 c_2 是 c_1 的后代，可以说 c_2 是 c_1 的子类 (subclass)，写作 c_2 < c_1。
如果类 c_2 继承自 c_1，除非在 c_2 中重新声明，c_1 的所有字段和方 法都对 c_2 的方法可见。由于一个类继承了父类的所有方法和字段，任何能够使用父 类实例的地方都可以使用子类实例。类似地，任何能够使用类实例的地方都可以使用其后代 的实例。有时，这叫做子类多态 (subclass polymorphism)。我们的语言选择这种 设计，其他面向对象语言可能选择不同的可见性规则。
接下来，我们考虑重新声明类的字段或方法时会发生什么。如果 c_1 的某个字段在某 个子类 c_2 中重新声明，新的声明遮蔽 (shadow) 旧的，就像词法定界一样。 例如。类 c2 的对象有两个名为 y 的字段：c1 中 声明的和 c2 中声明的。c1 中声明的方法能看到 c1 的字段 x 和 y。在 c2 中，getx2 中的 x 指代 c1 的字段 x，但 gety2 中的 y 指代 c2 的字段 y。
如果类 c_1 的方法 m 在某个子类 c_2 中重新声明，我们说新的 方法覆盖 (override) 旧的方法。我们将方法声明所在的类称为方法 的持有类 (host class)。 类似地，我们将表达式的持有类定义为表达式所在方法（如果有的话）的持有类。我们还将 方法或表达式的超类定义为持有类的父类。
如果给类 c_2 的对象发送消息 m，应使用新的方法。这条规则很简单，结果却不 简单。考虑下面的例子：
class c1 extends object
method initialize () 1
method m1 () 11
method m2 () send self m1()
class c2 extends c1
method m1 () 22
let o1 = new c1() o2 = new c2()
in list(send o1 m1(), send o2 m1(), send o2 m2())
我们希望 send o1 m1() 返回 11，因为 o1 是 c1 的实例。同样地，我们 希望 send o2 m1() 返回 22，因为 o2 是 c2 的实例。那么 send o2 m2() 呢？方法 m2 直接调用方法 m1，但它调用的是哪个 m1？
动态分发告诉我们，应查看绑定到 self 的对象属于哪个类。self 的值是 o2，属于类 c2。因此，调用 send self m1() 应返回 22。
[!t]
class point extends object
field x
field y
method initialize (initx, inity)
begin
set x = initx;
set y = inity
end
method move (dx, dy)
begin
set x = +(x,dx);
set y = +(y,dy)
end
method get-location () list(x,y)
class colorpoint extends point
field color
method initialize (initx, inity, initcolor)
begin
set x = initx;
set y = inity;
set color = initcolor
end
method set-color (c) set color = c
method get-color () color
let o1 = new colorpoint(3,4,172)
in send o1 get-color()
我们的语言还有一个重要特性：超类调用 (super call)。 考虑 中的程序。我们在类 colorpoint 中重写了 initialize 方法，同时设置字段 x、y 和 color。但是，新方法的 主体复制了原方法的代码。在我们的小例子中，这尚可接受，但在大型例子中，这显然是一 种坏的做法（为什么？）。而且，如果 colorpoint 声明了字段 x，就没法初始 化 point 的字段 x，正如field-shadowing的例子中，没法初始化第 一个 y 一样。
解决方案是，把 colorpoint 的 initialize 方法主体中的重复代码替换 为超类调用，形如 super initialize()。那么 colorpoint 中的 initialize 方法写作：
method initialize (initx, inity, initcolor)
begin
super initialize(initx, inity);
set color = initcolor
end
方法 m 主体中的超类调用 super n(...) 使用的是 m 持有类父类的方 法 n。这不一定是 self 所指类的父类。self 所指类总是 m 持有类的 子类，但不一定是同一个，任何类都是自身的子类，故有此说。——译注因为 m 可能在目标对象的某个祖先中声明。
要解释这种区别，考虑。给类 c3 的对象 o3 发送消息 m3，找到的是 c2 的方法 m3，它执行 super m1()。o3 的类是 c3，其父类是 c2，但方法的持有类是 c2，c2 的超类是 c1。 所以，执行的是 c1 的方法 m1。这是静态 方法分发 (static method dispatch) 的例子。虽然进行超类方法调用的对 象是 self，方法分发却是静态的，因为要调用的方法可以从程序文本中推断出来，与 self 所指类无关。
本例中，c1 的方法 m1 调用 o3 的方法 m2。这是普通方法调用，所 以使用动态分发，找出的是 c3 的方法 m2，返回 33。
[!t]
class c1 extends object
method initialize () 1
method m1 () send self m2()
method m2 () 13
class c2 extends c1
method m1 () 22
method m2 () 23
method m3 () super m1()
class c3 extends c2
method m1 () 32
method m2 () 33
let o3 = new c3()
in send o3 m3()
9.3 语言
我们的语言 CLASSES 由 IMPLICIT-REFS 扩展而得，新增生成式如 所示。 程序开头是一些类声明，然后是一个待执行的表达式。类声明有名字，最相近的超类名，0 或多个字段声明，以及 0 或多个方法声明。方法声明类似 letrec 中的过程声明， 有名字、形参列表以及主体。同时我们扩展语言，支持多参数过程、多声明 let 和多 声明 letrec 表达式，还有些其他操作，如加法和 list。 列表操作同。最后，我们增加 begin 表达式， 同，它从左到右求出子表达式的值，返回最后一个表达式的值。
\begin{align*}\mathit{ExpVal} &= \mathit{Int} + \mathit{Bool} + \mathit{Proc} + \mathit{Listof(ExpVal)} + \mathit{Obj}\\ \mathit{DenVal} &= \mathit{Ref(ExpVal)}\end{align*}
我们写 \mathit{Listof(ExpVal)}，表示列表可以包含任何表达值。
我们将在对象考察 \mathit{Obj}。在我们的语言中，类既不是指代值，也 不是表达值：它们能作为对象的一部分，但不能绑定到变量或是成为表达式的值（但要 看看）。
[!ht] \begin{align*} \mathit{Program} &::= \{\mathit{ClassDecl}\}^{*} \phantom{x} \mathit{Expression} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{a-program (class-decls body)} \\[5pt] \mathit{ClassDecl} &::= class \mathit{Identifier} extends \mathit{Identifier} \\[-3pt] &\mathrel{\phantom{::=}} \phantom{x}\{field \mathit{Identifier}\}^{*}\phantom{x}\{\mathit{MethodDecl}\}^{*} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{\begin{math}\begin{alignedat}{-1} &a-class-decl \\ &\phantom{x}(class-name super-name \\ &\phantom{xx}field-names method-decls) \end{alignedat}\end{math}} \\[5pt] \mathit{MethodDecl} &::= method \mathit{Identifier} (\{\mathit{Identifier}\}^{*(,)}) \mathit{Expression} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{a-method-decl (method-name vars body)} \\[5pt] \mathit{Expression} &::= new \mathit{Identifier} (\{\mathit{Expression}\}^{*(,)}) \\[-3pt] &\mathrel{\phantom{::=}} \fbox{new-object-exp (class-name rands)} \\[5pt] \mathit{Expression} &::= send \mathit{Expression} \mathit{Identifier} (\{\mathit{Expression}\}^{*(,)}) \\[-3pt] &\mathrel{\phantom{::=}} \fbox{method-call-exp (obj-exp method-name rands)} \\[5pt] \mathit{Expression} &::= super \mathit{Identifier} (\{\mathit{Expression}\}^{*(,)}) \\[-3pt] &\mathrel{\phantom{::=}} \fbox{super-call-exp (method-name rands)} \\[5pt] \mathit{Expression} &::= self \\[-3pt] &\mathrel{\phantom{::=}} \fbox{self-exp}\end{align*}
我们新增了四种表达式。new 表达式创建指定类的对象，然后调用 initialize 方法初始化对象的字段。rands 求值后，传给 initialize 方法。这个方法调用 的返回值被直接抛弃，新对象则作为 new 表达式的值返回。
send 表达式包含一个值为对象的表达式，一个方法名，以及 0 或多个操作数。它从 对象的类中找出指定的方法，然后求操作数的值，将得到的实参传给该方法。就像 IMPLICIT-REFS 那样，它要为每个实参分配一个新位置，然后将方法的形参与对应位置的引 用绑定起来，并在这个词法绑定作用域内求方法主体的值。
super-call 表达式包含一个方法名和 0 或多个参数。它从表达式持有类的超类开始， 找出指定的方法，然后以当前对象为 self，求出方法主体的值。
9.4 解释器
我们求程序的值时，首先用 initialize-class-env! 处理所有类声明，然后求表达式 的值。过程 initialize-class-env! 创建一个全局类 环境 (class environment)，将各个类名映射到类的方法。因为这个环境是全局的，我们用一个 Scheme 变量表示 它。在类和类环境我们再详细讨论类环境。
value-of-program : \mathit{Program} \to \mathit{ExpVal} (define value-of-program (lambda (pgm) (initialize-store!) (cases program pgm (a-program (class-decls body) (initialize-class-env! class-decls) (value-of body (init-env))))))
像之前那样，语言中的各种表达式——包括四种新生成式——在过程 value-of 里都有对 应的语句。
我们依次考虑各个新增的表达式。
表达式需要求值，通常是因为它是操作某个对象的方法的一部分。在当前环境中，这个对象 绑定到伪变量 %self。我们称之为伪变量 (pseudo-variable) 是因为它虽然 像普通变量那样遵循词法绑定，但却像下面将要探讨的那样，具有一些独特性质。类似地， 当前方法持有类的超类名字绑定到伪变量 %super。
求 self 表达式的值时，返回的是 %self 的值。这对应 value-of 中的语 句
(self-exp () (apply-env env '%self))
求 send 表达式的值时，操作数和对象表达式都需要求值。我们从对象中找出它的类 名，然后用 find-method 找出方法。find-method 取一个类名和一个方法名， 返回一个方法。接着，我们用当前对象和方法的参数调用这个方法。
(method-call-exp (obj-exp method-name rands) (let ((args (values-of-exps rands env)) (obj (value-of obj-exp env))) (apply-method (find-method (object->class-name obj) method-name) obj args)))
超类调用与普通方法调用类似，不同之处是，要在表达式持有类的超类中查找方法。 它在 value-of 中的对应语句是：
(super-call-exp (method-name rands) (let ((args (values-of-exps rands env)) (obj (apply-env env '%self))) (apply-method (find-method (apply-env env '%super) method-name) obj args)))
最后一项工作是创建对象。求 new 表达式的值时，我们需要求操作数的值，并根据类 名创建一个新对象。然后我们调用对象的初始化函数，但忽略这个函数的值。最后，返回 该对象。
(new-object-exp (class-name rands) (let ((args (values-of-exps rands env)) (obj (new-object class-name))) (apply-method (find-method class-name 'initialize) obj args) obj))
接下来，我们确定如何表示对象、方法和类。我们通过一个示例解释这种表示， 如 所示。
class c1 extends object
field x
field y
method initialize ()
begin
set x = 11;
set y = 12
end
method m1 () ... x ... y ...
method m2 () ... send self m3() ...
class c2 extends c1
field y
method initialize ()
begin
super initialize();
set y = 22
end
method m1 (u,v) ... x ... y ...
method m3 () ...
class c3 extends c2
field x
field z
method initialize ()
begin
super initialize();
set x = 31;
set z = 32
end
method m3 () ... x ... y ... z ...
let o3 = new c3()
in send o3 m1(7,8)
9.4.1 对象
(define-datatype object object? (an-object (class-name identifier?) (fields (list-of reference?))))
在列表中，我们把“最年长”类的字段排在前面。这样， 在 中，类 c1 对象的字段排列为 (x y)；类 c2 对 象的字段排列为 (x y y)，其中，第二个 y 是 c2 中的；类 c3 对 象的字段排列为 (x y y x z)。 中对象 o3 的表示 如 所示。当然，我们想让类 c3 中的方法使用 c3 中声 明的字段 x，而不是 c1 中声明的。在建立方法主体的求值环境时，我们要处理 这一点。
这种方法有个好处：对 c3 的任何子类，列表中的相同位置具有相同字段，因为后添 加的任何字段都会出现在这些字段的右边。在 c3 任一子类定义的某个方法中， x 在什么位置呢？我们知道，如果没有重定义，x 在所有这些方法中的位置一定 是 3。这样，在声明字段变量时，变量对应值的位置保持不变。这一特点使字段引用的位置 能够静态地确定，就像我们在消除变量名中处理变量那样。
创建新对象很容易。我们只需创建 an-object，它有一个新引用列表，列表长度与对 象的字段数目相等。要确定其数目，我们从对象所属类中取出字段变量列表。我们用不合法 的值初始化所有位置，以便探知程序是否使用了未初始化的位置。
\mathit{ClassName} = \mathit{Sym} new-object : \mathit{ClassName} \to \mathit{Obj} (define new-object (lambda (class-name) (an-object class-name (map (lambda (field-name) (newref (list 'uninitialized-field field-name))) (class->field-names (lookup-class class-name))))))
9.4.2 方法
接下来我们处理方法。方法就像过程，但是它们不保存环境，而是记录所引用的字段名。方 法调用在如下环境中执行其主体：
-
方法的形参绑定到新引用，引用初始化为实参的值。这与 IMPLICIT-REFS 中的 apply-procedure 行为类似。
-
可见字段名绑定到当前对象的字段。要实现这点，我们定义
(define-datatype method method? (a-method (vars (list-of identifier?)) (body expression?) (super-name identifier?) (field-names (list-of identifier?)))) apply-method : \mathit{Method} \times \mathit{Obj} \times \mathit{Listof(ExpVal)} \to \mathit{ExpVal} (define apply-method (lambda (m self args) (cases method m (a-method (vars body super-name field-names) (value-of body (extend-env* vars (map newref args) (extend-env-with-self-and-super self super-name (extend-env* field-names (object->fields self) (empty-env)))))))))
这里，我们使用 中的 extend-env*。它在扩展环境时，把变 量列表绑定到指代值的列表。我们还给环境接口新增过程 extend-env-with-self-and-super，分别将 %self 和 %super 绑定到对象 和类名。
要确保各方法看到正确的字段，我们在构建 field-names 列表时需要小心。各方法只 应见到最后一个声明的同名字段，其他同名字段应被遮蔽。所以，我们构建 field-names 列表时，把最右边之外的出现的每个重复名字替换为新名。 中的程序对应的 field-names 如下
类
定义的字段
字段
field-names
c1
x, y
(x y)
(x\phantom{xxx}y)
c2
y
(x y y)
(x\phantom{xxx}y%1 y)
c3
x, z
(x y y x z)
(x%1\phantom{x}y%1 y x z)
由于方法主体无从得知 x%1 和 y%1，所以它们只能见到各字段变量在最右边的 声明，正合期望。
展示的环境，是求 中 send o3 m1(7,8) 内方 法主体的值时创建的。这张图表明，引用列表可能比变量列表长：变量列表只是 (x y%1 y)，因为 c2 的方法 m1 只能见到这些字段变量，但 (object->fields self) 的值是对象中所有字段的列表。不过，由于三个可见字段变 量的值是列表中的头三个元素，而且我们把第一个 y 重命名为 y%1（该方法对 此一无所知），方法 m1 将把变量 y 与 c2 中声明的 y 关联起来， 正合期望。
[!t]
当 self 的持有类和所属类相同时，变量列表的长度通常与字段引用列表相同。如果 持有类位于类链的上端，那么位置数可能多于字段变量数目，但对应于字段变量的值位于列 表开头，其余值则不可见。
9.4.3 类和类环境
迄今为止，我们的实现都依赖从类名获取与类相关的信息。所以，我们需要 一个类环境 (class environment) 完成这一工作。类环境将每个类名与描述类的 数据结构关联起来。
类环境是全局的：在我们的语言中，类声明聚集于程序开头，且对整个程序生效。所以，我 们用名为 the-class-env 的全局变量表示类环境，它包含列表 (类名,类) 的列 表，但我们用过程 add-to-class-env! 和 lookup-class 隐藏这一表示。
\mathit{ClassEnv} = \mathit{Listof(List(ClassName, Class))} the-class-env : \mathit{ClassEnv} (define the-class-env '()) add-to-class-env! : \mathit{ClassName} \times \mathit{Class} \to \mathit{Unspecified} (define add-to-class-env! (lambda (class-name class) (set! the-class-env (cons (list class-name class) the-class-env)))) lookup-class : \mathit{ClassName} \to \mathit{Class} (define lookup-class (lambda (name) (let ((maybe-pair (assq name the-class-env))) (if maybe-pair (cadr maybe-pair) (report-unknown-class name)))))
对每个类，我们记录三样东西：超类的名字，字段变量的列表，以及将方法名映射到方法的 环境。
(define-datatype class class? (a-class (super-name (maybe identifier?)) (field-names (list-of identifier?)) (method-env method-environment?))) 这里，我们用谓词 (maybe identifier?) 判断值是否为符号或 #f。后一种情况 对是必须的，因为类 object 没有超类。filed-names 是类的方法能见到的字段， method-env 是一环境，给出了类中每个方法名的定义。
我们初始化类环境时，为类 object 添加一个绑定。对每个声明，我们向类环境添加 一个新绑定，将类名绑定到一个 class，它包含超类名、类中方法的 field-names 以及类中方法的环境。
过程 append-field-names 用来给当前类创建 field-names。它将新类声明的字 段添加到超类字段之后，同时将超类中被新字段遮蔽的字段替换为新名字， 就像field-renaming的示例那样。
append-field-names :
\phantom{xx}\mathit{Listof(FieldName)} \times \mathit{Listof(FieldName)} \to \mathit{Listof(FieldName)}(define append-field-names (lambda (super-fields new-fields) (cond ((null? super-fields) new-fields) (else (cons (if (memq (car super-fields) new-fields) (fresh-identifier (car super-fields)) (car super-fields)) (append-field-names (cdr super-fields) new-fields))))))
9.4.4 方法环境
剩下的只有 find-method 和 merge-method-envs 了。
像处理类那样，我们用列表 (方法名,方法) 的列表表示方法环境，用 find-method 查找方法。
\mathit{MethodEnv} = \mathit{Listof(List(MethodName, Method))} find-method : \mathit{Sym} \times \mathit{Sym} \to \mathit{Method} (define find-method (lambda (c-name name) (let ((m-env (class->method-env (lookup-class c-name)))) (let ((maybe-pair (assq name m-env))) (if (pair? maybe-pair) (cadr maybe-pair) (report-method-not-found name))))))
用这一信息，我们可以写出 method-decls->method-env。它取一个类的方法声明，创 建一个方法环境，记录每个方法的绑定变量、主体、持有类的超类名，以及持有类的 field-names。
method-decls->method-env :
\phantom{xx}\mathit{Listof(MethodDecl)} \times \mathit{ClassName} \times \mathit{Listof(FieldName)} \to \mathit{MethodEnv}(define method-decls->method-env (lambda (m-decls super-name field-names) (map (lambda (m-decl) (cases method-decl m-decl (a-method-decl (method-name vars body) (list method-name (a-method vars body super-name field-names))))) m-decls)))
最后，我们写出 merge-method-envs。由于新类中的方法覆盖了旧类的同名方法，我 们可以直接扩展环境，将新方法添加到前面。
merge-method-envs : \mathit{MethodEnv} \times \mathit{MethodEnv} \to \mathit{MethodEnv} (define merge-method-envs (lambda (super-m-env new-m-env) (append new-m-env super-m-env))) 构建方法环境还有其他一些方式，它们在方法查询时更高效（）。
((c3 #(struct:a-class c2 (x%2 y%1 y x z) ((initialize #(struct:a-method () #(struct:begin-exp ...) c2 (x%2 y%1 y x z))) (m3 #(struct:a-method () #(struct:diff-exp ...)) c2 (x%2 y%1 y x z)) (initialize #(struct:a-method ...)) (m1 #(struct:a-method (u v) #(struct:diff-exp ...) c1 (x y%1 y))) (m3 #(struct:a-method ...)) (initialize #(struct:a-method ...)) (m1 #(struct:a-method ...)) (m2 #(struct:a-method () #(struct:method-call-exp #(struct:self-exp) m3 ()) object (x y)))))) (c2 #(struct:a-class c1 (x y%1 y) ((initialize #(struct:a-method () #(struct:begin-exp ...) c1 (x y%1 y))) (m1 #(struct:a-method (u v) #(struct:diff-exp ...) c1 (x y%1 y))) (m3 #(struct:a-method () #(struct:const-exp 23) c1 (x y%1 y))) (initialize #(struct:a-method ...)) (m1 #(struct:a-method ...)) (m2 #(struct:a-method () #(struct:method-call-exp #(struct:self-exp) m3 ()) object (x y)))))) (c1 #(struct:a-class object (x y) ((initialize #(struct:a-method () #(struct:begin-exp ...) object (x y))) (m1 #(struct:a-method () #(struct:diff-exp ...) object (x y))) (m2 #(struct:a-method () #(struct:method-call-exp #(struct:self-exp) m3 ()) object (x y)))))) (object #(struct:a-class #f () ())))
9.4.5 练习
\textnormal{[}{\star}\textnormal{]} 用本节的语言实现以下各项：
队列类 (queue)，包含方法 empty?、enqueue 和 dequeue。
扩展队列类，添加计数器，记录当前队列已进行的操作数。
扩展队列类，添加计数器，记录本类所有队列已进行的操作总数。提示：你可以在 对象初始化时传递共享计数器。
\textnormal{[}{\star}\textnormal{]} 继承可能很危险，因为子类可以覆盖任意方法，改变其行为。定义继承自 oddeven 的 类 bogus-oddeven，覆盖方法 even，从而导致 let o1 = new bogus-oddeven() in send o1 odd (13) 给出错误的答案。
\textnormal{[}{\star}{\star}\textnormal{]} 在 中，哪里是共享的方法环境？哪里是共享的 field-names 列表？
\textnormal{[}{\star}\textnormal{]} 修改对象的表示，让 \mathit{Obj} 包含对象所属的类，而非其名字。跟文中的方式相 比，这种表示有何优劣？
\textnormal{[}{\star}\textnormal{]} 解释器中的解释器在词法环境中存储方法持有类的超类名。修改实现，让方法存储 持有类的名字，然后用持有类的名字查找超类名。
\textnormal{[}{\star}\textnormal{]} 给我们的语言添加表达式 instanceof exp class\mbox{-}name。当且仅当表 达式 exp 的值为对象，且为 class\mbox{-}name 或其子类的实例时，这一表达式 的值为真。
\textnormal{[}{\star}\textnormal{]} 在我们的语言中，方法环境包含持有类和超类声明的字段变量的绑定。将其限制为 持有类的字段变量绑定。
\textnormal{[}{\star}\textnormal{]} 给我们的语言添加新表达式：
fieldref obj field\mbox{-}name
取出指定对象指定字段的内容。再添加：
fieldset obj field\mbox{-}name = exp
将指定字段设置为 exp 的值。
\textnormal{[}{\star}\textnormal{]} 添加 superfieldref field\mbox{-}name 和 superfieldset field\mbox{-}name = exp 表达式，处理 self 中原本被遮蔽的字段。 记住：super 是静态的，总是指持有类的超类。
\textnormal{[}{\star}{\star}\textnormal{]} 有些面向对象编程语言支持指定类名的方法调用和字段引用。在指定类名的方法调用中，可 以写 named-send c1 o m1()。只要 o 是 c1 或其子类的实例，即使 o 所属类覆盖了 m1，这也会对 o 调用 c1 的方法 m1。这是一 种静态方法分发。指定类名的字段与之类似。给本节的语言添加指定类名的方法调用、字段 引用和字段赋值。
\textnormal{[}{\star}{\star}\textnormal{]} 允许 CLASSES 指定每个方法是私有的 (private)，只能在持有类内访问； 或受保护的 (protected)，只能在持有类及其后代中访问；或公 有的 (public)，在所有位置都能访问。许多面向对象编程语言都包含了这一特性的某种版本。
\textnormal{[}{\star}{\star}\textnormal{]} 像 那样，允许 CLASSES 指定每个字段是私有的、受保护的、或 公有的。
\textnormal{[}{\star}{\star}\textnormal{]} 为了防止 那样的恶意子类，许多面向对象编程语言都能指定无法覆 盖的 final 方法。给 CLASSES 添加这样的组件，那么我们就能写：
class oddeven extends object
method initialize () 1
final method even (n)
if zero?(n) then 1 else send self odd(-(n,1))
final method odd (n)
if zero?(n) then 0 else send self even(-(n,1))
\textnormal{[}{\star}{\star}\textnormal{]} 另一种防止恶意子类的方法是使用某种形式的静态分发。修改 CLASSES，使通过 self 调用的总是持有类的方法，而不是目标对象所属类的方法。
\textnormal{[}{\star}{\star}\textnormal{]} 很多面向对象编程语言都提供静态变量或者类变量。静态变量与类的某些状 态相关联；类的所有实例共享这一状态。例如，我们可以写：
class c1 extends object
static next-serial-number = 1
field my-serial-number
method get-serial-number () my-serial-number
method initialize ()
begin
set my-serial-number = next-serial-number;
set next-serial-number = +(next-serial-number,1)
end
let o1 = new c1()
o2 = new c1()
in list(send o1 get-serial-number(),
send o2 get-serial-number())
类 c1 的每个新对象具有连续的序列号。
给我们的语言添加静态变量。由于静态变量可以在方法主体中出现，apply-method 必 须在它构建的环境中添加额外的绑定。求静态变量初始化表达式（上例中的 1）的值 时，应使用什么环境？
\textnormal{[}{\star}{\star}\textnormal{]} 面向对象编程语言常允许重载 (overloading) 方法。这一特性允许类有多个同名 方法，只要它们有不同的签名 (signature)。方法签名通常是方法名加上参数类型。 由于 CLASSES 中没有类型，我们只能依靠方法名和参数个数重载方法。例如，某个类可能 有两个 initialize 方法，一个没有参数，用它来初始化时，需要给字段默认值；另 一个有一个参数，用它来初始化时，需要给字段特定值。扩展我们的解释器，允许通过方法 的参数个数重载方法。
\textnormal{[}{\star}{\star}\textnormal{]} 显而易见，我们语言中的类定义是全局的。给 CALSSES 添加局部类，可写成 letclass c = ... in e。提示：考虑给解释器添加一个类环境参数。
\textnormal{[}{\star}{\star}\textnormal{]} merge-method-envs 产生的方法环境可能很长。再写出一版 merge- method-envs，保证每个方法名只出现一次，而且总是出现在最先声明的位置。例如，在 中，在 c1、c2、c3，以及 c3 任意后代的方 法环境中，方法 m2 应出现在同样的位置。
\textnormal{[}{\star}{\star}\textnormal{]} 为 CLASSES 实现词法寻址。首先，为本节语言写出类似实现词法地址的词法地址计算器。 然后修改环境的实现，去掉其中的名字。接着修改 value-of 和 apply-env，不 再取符号，而是像无名解释器那样取一词法地址。
\textnormal{[}{\star}{\star}{\star}\textnormal{]} 方法调用也能够用类似 那样的方式优化吗？讨论为什么能，或为什 么不能。
\textnormal{[}{\star}{\star}\textnormal{]} 如果类中有很多方法，从头线性搜索方法列表会很耗时。将其修改为更快的实现。你的实现 能改进多少？不论优劣，解释你的结果。
\textnormal{[}{\star}{\star}\textnormal{]} 在 中，我们扩展解释器，给语言添加了重载。另一种支持重载的方 式不需修改解释器，而是用语法预处理器。写一个预处理器，将每个方法 m 重命名为 m:@n 的形式，其中，n 是方法声明中参数的数量。同时，它还必须根据操作数 的数量改变每个方法调用的名字。我们假定程序员在方法名中不使用 :@，但解释器 接受使用 :@ 的方法名。编译器经常使用这种技术实现方法重载。这是一种通用技巧 的例子，名为名称混淆 (name mangling)。
\textnormal{[}{\star}{\star}{\star}\textnormal{]} 我们以词法绑定的方式看待超类调用。但我们还可以做得更好：我们可以静态地确 定 super 调用。由于超类调用指向类的父类的方法，且父类与其方法在执行之前已知， 我们可以在进行词法寻址和其他分析的同时确定超类调用究竟指的是哪个方法。写一个翻译 器，将每个超类调用替换为一个抽象语法树节点，节点中包含实际要调用的方法。
\textnormal{[}{\star}{\star}{\star}\textnormal{]} 写一个翻译器，把 中指定类调用的方法名替换为数字，该数字表示 运行期间，指定方法在指定类的方法表中的偏移。为翻译后的代码实现一个解释器，在常数 时间内访问指定的方法。
\textnormal{[}{\star}{\star}{\star}\textnormal{]} 我们给 第一个继承例子中的类 point 添加一个方法，判断两 个点是否具有相同的横纵坐标。我们照下面这样给类 point 添加方法 similarpoints：
method similarpoints (pt)
if equal?(send pt getx(), x)
then equal?(send pt gety(), y)
else zero?(1)
这对所有类型的点都有效。因为 getx、gety 和 similarpoints 都在类 point 中定义，通过继承，它们在 colorpoint 中也有定义。测试 similarpoints，比较点和点、点和有色点、有色点和点，以及有色点和有色点。
接下来考虑一个小扩展。我们给类 colorpoint 添加新方法 similarpoints。我 们希望两个点横纵坐标相同、都是有色点且颜色相同时，它返回真；否则返回假。这里是一 种错误做法。
method similarpoints (pt)
if super similarpoints(pt)
then equal?(send pt getcolor(),color)
else zero?(1)
测试这一扩展。说明它为何不适用于任意情况。修复它，让所有测试都返回正确的值。
过程依赖多个对象造成的困难称为二元方法问题 (binary method problem)。它表 明，本章探讨的以类为中心的面向对象编程模型在处理多个对象时有其不足。这叫做 二元方法问题，因为两个对象就能引起这一问题，但当对象数目增加时，它会愈发 严重。
\textnormal{[}{\star}{\star}{\star}\textnormal{]} 多继承允许一个类有多个父类，这虽然有用，但可能带来过度的复杂性。如果两个被继承的 类具有同名方法呢？可以禁止这种情况；也可以按照某种规则遍历方法，比如深度优先或从 左到右；还可以要求在调用时消除这种歧义。字段的情况就更糟了。考虑下面的情形，类 c4 继承自 c2 和 c3，二者均继承自 c1：
class c1 extends object
field x
class c2 extends c1
class c3 extends c1
class c4 extends c2, c3
c4 的实例中，是有一个由 c2 和 c3 共享的字段 x 实例呢，还是有 两个分别继承自 c2 和 c3 的字段 x 呢？有些语言选择共享，有些不，还 有一些（至少在某些条件下）任选。这问题的复杂性致使人们在设计时，更偏爱类的单继承， 而多继承只用于接口（带有类型的语言），以尽量避免这些困难。
给 CLASSES 添加多继承。对语法做必要扩展。指出解决方法名和字段名冲突时面临什么问 题。描述共性问题及其解决方法。
\textnormal{[}{\star}{\star}{\star}\textnormal{]} 实现下面设计的无类有对象语言。对象是一组闭包，各闭包共享一个环境（亦即某种状态）， 环境以方法名为索引。类则由返回对象的过程替代。所以，我们不用写 send o1 m1(11,22,33)，而是写普通的过程调用 (getmethod(o1,m2) 11 22 33)；不用写
class oddeven extends object
method initialize () 1
method even (n)
if zero?(n) then 1 else send self odd(-(n,1))
method odd (n)
if zero?(n) then 0 else send self even(-(n,1))
let o1 = new oddeven()
in send o1 odd(13)
而是写
let make-oddeven
= proc ()
newobject
even = proc (n) if zero?(n) then 1
else (getmethod(self,odd) -(n,1))
odd = proc (n) if zero?(n) then 0
else (getmethod(self,even) -(n,1))
endnewobject
in let o1 = (make-oddeven) in (getmethod(o1,odd) 13)
\textnormal{[}{\star}{\star}{\star}\textnormal{]} 给 的语言添加继承。
\textnormal{[}{\star}{\star}{\star}\textnormal{]} 设计和实现不需写明类的面向对象语言，让每个对象包含自身的方法环境。这种对象 叫做原型 (prototype)。把类 object 替换为没有方法和字段的原型对象。 扩展类时，给其原型添加方法和字段，得到新的原型。这样，我们就能用 let c2 = extend c1 ... 替代 class c2 extends c1 ...。把操作 new 替换为 clone，它取一对象，直接复制对象的方法和字段。这种语言中的方法出现于一个词法 作用域中，所以应该能像通常那样访问词法上可见的变量以及字段变量。 当超型 (superprototype) 的字段变量与当前所在词法作用域的变量同名时，遮蔽 关系是怎样的？
9.5 带有类型的语言
在类型，我们展示了如何用类型系统检查程序，保证程序执行时不会进行不当操 作。通过检查器的程序不会调用非过程处理实参，调用过程或其他操作符时，也不会使用错 误数量或类型的实参。
本节，我们将这种技术应用于名为 TYPED-OO 的面向对象语言。这种语言具有上述所有安全 性质，此外，通过我们检查器的程序不会给没有对应方法的对象发送消息，也不会给对象发 送实参数量或类型错误的消息。
TYPED-OO 的示例程序如 所示。这段程序定义了一个类 tree， 其方法 sum 像 那样求出树叶之和，方法 equal 取另一 棵树，递归向下处理树，判断二者是否相等。
这种语言的主要新特性有：
-
字段和方法需要用和类型类似的语法指定类型。
-
在面向对象设值中，引入接口 (interface) 的概念。
-
语言中引入了子类型多态 (subtype polymorphism) 的概念。
-
语言中引入了强制转换 (casting) 的概念，同时也 包含 中的 instanceof 判断。
我们依次考虑这些特性。
TYPED-OO 中的新生成式如 所示。我们添加一种类型 void， 作为 set 操作的类型，然后添加 中的列表类型； 像 那样，我们要求调用 list 时至少给出一个实参。我们给类 型表达式的集合添加标识符，但在本章，用作类型的标识符与同名的类或接口相关联。稍后 我们仔细考虑这种对应关系。方法需要指明结果类型和参数类型，其语法 与类型中的 letrec 类似。最后是两种新增的表达式 cast 和 instanceof。
要理解这种语言的新特性，我们必须像 那样，定义语言的类型。
对象只能是一个类的实例，但可以有很多类型。
-
创建对象时的类是其类型。
-
该类的超类以及继承关系上方的所有类是其类型。特别地，每个对象都是 object 类型。
-
对象所属类实现的任意接口均是其类型。
第二条性质叫做子类多态 (subclass polymorphism)。第三条性质 叫做接口多态 (interface polymorphism)。
接口表示实现某些方法的所有对象集合，而不论这些对象如何生成。仅当类 c 按照约 定的类型实现了接口 I 要求的所有方法时，我们的判类系统才允许 c 声称实现了 I。虽然我们的例子中只用了一个接口，但一个类可以实现多个不同接口。
interface tree
method int sum ()
method bool equal (t : tree)
class interior-node extends object implements tree
field tree left
field tree right
method void initialize(l : tree, r : tree)
begin
set left = l; set right = r
end
method tree getleft () left
method tree getright () right
method int sum () +(send left sum(), send right sum())
method bool equal (t : tree)
if instanceof t interior-node
then if send left equal(send
cast t interior-node
getleft())
then send right equal(send
cast t interior-node
getright())
else zero?(1)
else zero?(1)
class leaf-node extends object implements tree
field int value
method void initialize (v : int) set value = v
method int sum () value
method int getvalue () value
method bool equal (t : tree)
if instanceof t leaf-node
then zero?(-(value, send cast t leaf-node getvalue()))
else zero?(1)
let o1 = new interior-node (
new interior-node (
new leaf-node(3),
new leaf-node(4)),
new leaf-node(5))
in list(send o1 sum(),
if send o1 equal(o1) then 100 else 200)
\begin{align*} \mathit{ClassDecl} &::= class \mathit{Identifier} extends \mathit{Identifier} \\ &\mathrel{\phantom{::=}} \phantom{x}\{implements \mathit{Identifier}\}^{*} \\ &\mathrel{\phantom{::=}} \phantom{x}\{field \mathit{Type} \mathit{Identifier}\}^{*} \\ &\mathrel{\phantom{::=}} \phantom{x}\{\mathit{MethodDecl}\}^{*} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{\begin{math}\begin{alignedat}{-1} &a-class-decl(c-name s-name i-names \\ &\phantom{xxxxxxxxxxxx}f-types f-names m-decls) \end{alignedat}\end{math}} \\[5pt] \mathit{ClassDecl} &::= interface \mathit{Identifier} \{\mathit{AbstractMethodDecl}\}^{*} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{an-interface-decl (i-name abs-m-decls)} \\[5pt] \mathit{MethodDecl} &::= method \mathit{Type} \mathit{Identifier} (\{\mathit{Identifier} \ : \mathit{Type}\}^{*(,)}) \mathit{Expression} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{{\begin{math}\begin{alignedat}{-1} &a-method-decl \\ &\phantom{x}(res-type m-name vars var-types body) \end{alignedat}\end{math}}} \\[5pt] \mathit{AbstractMethodDecl} &::= method \mathit{Type} \mathit{Identifier} (\{\mathit{Identifier} \ : \mathit{Type}\}^{*(,)}) \\[-3pt] &\mathrel{\phantom{::=}} \fbox{{\begin{math}\begin{alignedat}{-1} &a-method-decl \\ &\phantom{x}(res-type m-name m-vars m-var-types) \end{alignedat}\end{math}}} \\[5pt] \mathit{Expression} &::= cast \mathit{Expression} \mathit{Identifier} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{cast-exp (exp c-name)} \\[5pt] \mathit{Expression} &::= instanceof \mathit{Expression} \mathit{Identifier} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{instanceof-exp (exp name)} \\[5pt] \mathit{Type} &::= void \\[-3pt] &\mathrel{\phantom{::=}} \fbox{void-type ()} \\[5pt] \mathit{Type} &::= \mathit{Identifier} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{class-type (class-name)} \\[5pt] \mathit{Type} &::= listof \mathit{Type} \\[-3pt] &\mathrel{\phantom{::=}} \fbox{list-type (type1)}\end{align*}
在 中，类 interior-node 和 leaf-node 都实现了接口 tree。类型检查器允许这样，因为它们都实现了 tree 所要求的 sum 和 equal 方法。
当 e 的值是一个对象，且是类 c 或其后代的实例时，表达式 instanceof e c 返回真。强制转换是 instanceof 的补充。当 e 的值是一对象， 且是类 c 或其后代的实例时，cast 表达式 cast e c 的值与 e 的值相同；否则 cast 表达式报错。cast e c 的类型总是c， 因为只要返回值，它的类型就一定是 c。
例如，我们的示例程序包含如下方法
method bool equal(t : tree)
if instanceof t interior-node
then if send left
equal(send cast t interior-node getleft())
then send right
equal(send cast t interior-node getright())
else false
else false
表达式 cast t interior-node 检查 t 的值是否为 interior-node（或其 后代，如果有的话）的实例。如果是，则返回 t 的值；否则报错。当且仅当对应的 cast 成功时，instanceof 表达式返回真值。因此，本例中的 instanceof 确保强制转换一定成功。而强制转换又确保 send ... getleft() 能够使用。强制转 换表达式返回值的类型一定为类 interior-node，因此，给这个值发送消息 getleft 是安全的。
我们的实现从对象中的解释器开始。我们给 value-of 添加两条语句，求 instanceof 和 cast 表达式的值：
(cast-exp (exp c-name) (let ((obj (value-of exp env))) (if (is-subclass? (object->class-name obj) c-name) obj (report-cast-error c-name obj)))) (instanceof-exp (exp c-name) (let ((obj (value-of exp env))) (if (is-subclass? (object->class-name obj) c-name) (bool-val #t) (bool-val #f))))
过程 is-subclass? 沿着第一个类结构的父系而上，直到找出第二个类，或在父系为 #f 时停止。由于接口只用作类型，这个过程忽略它们。
is-subclass? : \mathit{ClassName} \times \mathit{ClassName} \to \mathit{Bool} (define is-subclass? (lambda (c-name1 c-name2) (cond ((eqv? c-name1 c-name2) #t) (else (let ((s-name (class->super-name (lookup-class c-name1)))) (if s-name (is-subclass? s-name c-name2) #f))))))
\textnormal{[}{\star}\textnormal{]} 创建接口 summable：
interface summable
method int sum ()
为可求和列表、可求和二叉树（如）和可求和的广义树（每个节点 包含一个可求和的子节点列表）定义类。
然后为接口
interface stringable
method string to-string ()
做同样的操作。
\textnormal{[}{\star}\textnormal{]} 在 中，把 tree 定义为类，然后让两个节点类继承 tree 可行吗？在什么情况下这种方法比使用 summable 之类的接口更好？在什 么情况下更糟？
\textnormal{[}{\star}{\star}\textnormal{]} 不使用 instanceof 和 cast，给类 tree 写一个等值判断谓词。这里需要 用双派发 (double dispatch) 替代通常方法使用的单派发。可做如下模拟：不用 instanceof 找出实参 t 的类，而是让当前的树给 t 返回一条消息，这条 消息编码了当前树的所属类，其参数则包含适当字段的值。
9.6 类型检查器
现在我们来看这种语言的检查器。检查器的目标是确保一些安全性质。对我们的语言来说， 这些性质包括原有过程式语言的那部分和之后面向对象语言增加的那部分：通过我们类型检 查器的程序不会
我们无意验证 initialize 方法确实初始化了所有字段，所以程序仍可能引用未初始 化的字段。同样地，由于 initialize 方法的类型通常难以预测，我们的检查器未防 止以错误数量或类型的参数显式调用 initialize 方法，但通过 new 间接调用 initialize 方法一定是正确的。
检查器首先实现 type-of-program。由于所有类的所有方法都是互递归的，我们的处 理方式类似 letrec。对 letrec，我们首先收集过程声明的类型，生成 tenv-for-letrec-body（）。然后，我们根据声明类型检查每 个过程主体。最后，我们在 tenv-for-letrec-body 中检查 letrec 的主体。
这里，我们首先调用 initialize-static-class-env!，遍历类声明，将所有类型收集 到一个静态类环境中。由于这个环境是全局的，且不会改变，我们不是将其作参数传递，而 是把它存储在一个 Scheme 变量中。然后，我们用 check-class-decl! 检查每个类声 明。最后，我们找出程序主体的类型。
type-of-program : \mathit{Program} \to \mathit{Type} (define type-of-program (lambda (pgm) (cases program pgm (a-program (class-decls exp1) (initialize-static-class-env! class-decls) (for-each check-class-decl! class-decls) (type-of exp1 (init-tenv))))))
静态类环境将每个类名映射到一个静态类，这个类包含父类的名字、字段的名字和类型，以 及方法的名字和类型。在我们的语言中，接口既没有父类，也没有字段，所以我们用只含所 需方法名字和类型的数据结构表示它们（但是，看看）。
(define-datatype static-class static-class? (a-static-class (super-name (maybe identifier?)) (interface-names (list-of identifier?)) (field-names (list-of identifier?)) (field-types (list-of type?)) (method-tenv method-tenv?)) (an-interface (method-tenv method-tenv?)))
在思考如何生成静态环境之前，我们先思考如何扩展 type-of，检查六种面向对象表 达式的类型：self、instanceof、cast、方法调用、超类调用，以及 new。
对 self 表达式，我们用伪变量 %self 查询其类型。就像在解释器中， %self 绑定到当前持有对象一样，在检查器中，该变量一定绑定到当前持有类的类型。
instanceof 表达式如果返回，一定返回 bool 值。若 e 的值是一个对象， 且是 c 或它的某个后代的实例，则表达式 cast e c 返回 e 的值。 因此，cast e c 如果返回值，值的类型是 c。所以我们总能将 cast e c 的类型视为 c。对 instanceof 和 cast 表达式， 解释器求出参数的值，并用它执行 object->class-name，所以我们也必须确保操作数 类型正常，且返回值是一个对象。这三种情况的代码如 所示。
[!t]
(self-exp () (apply-tenv tenv '%self)) (instanceof-exp (exp class-name) (let ((obj-type (type-of exp tenv))) (if (class-type? obj-type) (bool-type) (report-bad-type-to-instanceof obj-type exp)))) (cast-exp (exp class-name) (let ((obj-type (type-of exp tenv))) (if (class-type? obj-type) (class-type class-name) (report-bad-type-to-cast obj-type exp))))
接下来我们考虑方法调用。现在，我们的语言中有三种调用：过程调用、方法调用和超类调 用。我们抽象出一个过程来检查它们。
type-of-call : \mathit{Type} \times \mathit{Listof(Type)} \times \mathit{Listof(Exp)} \times \mathit{Exp} \to \mathit{Type} (define type-of-call (lambda (rator-type rand-types rands exp) (cases type rator-type (proc-type (arg-types result-type) (if (not (= (length arg-types) (length rand-types))) (report-wrong-number-of-arguments (map type-to-external-form arg-types) (map type-to-external-form rand-types) exp)) (for-each check-is-subtype! rand-types arg-types rands) result-type) (else (report-rator-not-of-proc-type (type-to-external-form rator-type) exp)))))
这个过程等价于 CHECKED 中 call-exp 对应的那一行（），但 多了两处明显区别。首先，由于我们的过程现在取多个参数，我们要确保调用时的实参数目 正确。在 for-each 这行，我们逐一对照每个操作数的类型和过程类型中相应参数的 类型。更有意思的是第二点，我们把 中的 check-equal-type! 换成了 check-is-subtype!。
为什么必须这样？子类多态原则是说，如果类 c_2 扩展了 c_1，那么类 c_2 的对象可在类 c_1 对象能够出现的任何地方使用。如果我们写出了过程 proc (o : c_1) ...，那么该过程应该能取类型为 c_2 的实参。
子类多态的概念可以大体上推广到子类型多态，就像模块中的 <:< /span> 那样。我们说 t_1 是 t_2 的子类型，当且仅当：
-
t_1 和 t_2 是类，且 t_1 是 t_2 的子类，或
-
t_1 是类，t_2 是接口，且 t_1 或其某个超类实现了 t_2，或
-
t_1 和 t_2 是过程类型，且 t_2 参数类型是 t_1 参数类型的子 类型，t_1 结果类型是 t_2 结果类型的子类型。
[!th]
要理解最后一条规则，令 t_1 为 (c1 -> d1)，t_2 为 (c2 -> d2)， 且 c2 < c1，d1 < d2。令 f 为一过程，类型为 t_1。我们说 f 类型也为 t_2。为什么？假设我们给 f 传递了类型为 c2 的参数。由于 c2 < c1，参数类型也是 c1，所以 f 可以接受这个参数。然后，f返 回值类型为 d1。但由于 d1 < d2，这个结果类型也是 d2。所以，如果给 f 一个类型为 c2 的参数，其返回值类型为 d2。因此，f 类型为 (c2 -> d2)。我们说结果类型的子类型判定是协变的 (covariant)，参数类 型的子类型判定是逆变的 (contravariant)。见。这与 实现中 <:-iface< /span> 的定义类似。
这部分代码如 所示。代码使用every2?， 它扩展 中的过程 every?，取一个双参数谓词和两个列表，当 列表长度相同且对应元素满足谓词时，返回 #t，否则返回 #f。
check-is-subtype! : \mathit{Type} \times \mathit{Type} \times \mathit{Exp} \to \mathit{Unspecified} (define check-is-subtype! (lambda (ty1 ty2 exp) (if (is-subtype? ty1 ty2) #t (report-subtype-failure (type-to-external-form ty1) (type-to-external-form ty2) exp)))) is-subtype? : \mathit{Type} \times \mathit{Type} \to \mathit{Bool} (define is-subtype? (lambda (ty1 ty2) (cases type ty1 (class-type (name1) (cases type ty2 (class-type (name2) (statically-is-subclass? name1 name2)) (else #f))) (proc-type (args1 res1) (cases type ty2 (proc-type (args2 res2) (and (every2? is-subtype? args2 args1) (is-subtype? res1 res2))) (else #f))) (else (equal? ty1 ty2))))) statically-is-subclass? : \mathit{ClassName} \times \mathit{ClassName} \to \mathit{Bool} (define statically-is-subclass? (lambda (name1 name2) (or (eqv? name1 name2) (let ((super-name (static-class->super-name (lookup-static-class name1)))) (if super-name (statically-is-subclass? super-name name2) #f)) (let ((interface-names (static-class->interface-names (lookup-static-class name1)))) (memv name2 interface-names)))))
现在可以逐一考虑三种调用（）。对方法调用，我们首先像通常那 样，找出目标对象和操作数的类型。我们用类似 find-method 的 find-method-type 找出方法的类型。如果目标类型不是类或接口，那么 type->class-name 报错。如果没有对应方法，那么 find-method-type 报错。 然后，我们调用 type-of-call 验证操作数的类型与方法的期望是否相符，并返回结 果的类型。
(method-call-exp (obj-exp method-name rands) (let ((arg-types (types-of-exps rands tenv)) (obj-type (type-of obj-exp tenv))) (type-of-call (find-method-type (type->class-name obj-type) method-name) arg-types rands exp))) (super-call-exp (method-name rands) (let ((arg-types (types-of-exps rands tenv)) (obj-type (apply-tenv tenv '%self))) (type-of-call (find-method-type (apply-tenv tenv '%super) method-name) arg-types rands exp))) (new-object-exp (class-name rands) (let ((arg-types (types-of-exps rands tenv)) (c (lookup-static-class class-name))) (cases static-class c (an-interface (method-tenv) (report-cant-instantiate-interface class-name)) (a-static-class (super-name i-names field-names field-types method-tenv) (type-of-call (find-method-type class-name 'initialize) arg-types rands exp) (class-type class-name)))))
对 new 表达式，我们首先取出类名对应的类信息。如果没有类与名字相关联，那就报 错。之后，用操作数的类型调用 type-of-call，检查调用 initialize 是否安 全。如果检查通过，那么执行表达式就是安全的。由于 new 表达式返回指定类的新对 象，结果类型就是对应类的类型。
TYPED-OO 中表达式的检查讨论完了，我们接着来构建静态类环境。
要构建静态类环境，initialize-static-class-env! 首先将其设置为空，然后为类 object 添加绑定。接着，它遍历各个类和接口声明，给静态类环境添加适当的内容。
initialize-static-class-env! : \mathit{Listof(ClassDecl)} \to \mathit{Unspecified} (define initialize-static-class-env! (lambda (c-decls) (empty-the-static-class-env!) (add-static-class-binding! 'object (a-static-class #f '() '() '() '())) (for-each add-class-decl-to-static-class-env! c-decls)))
add-class-decl-to-static-class-env! : \mathit{ClassDecl} \to \mathit{Unspecified} (define add-class-decl-to-static-class-env! (lambda (c-decl) (cases class-decl c-decl (an-interface-decl (i-name abs-m-decls) (let ((m-tenv (abs-method-decls->method-tenv abs-m-decls))) (check-no-dups! (map car m-tenv) i-name) (add-static-class-binding! i-name (an-interface m-tenv)))) (a-class-decl (c-name s-name i-names f-types f-names m-decls) (let ((i-names (append (static-class->interface-names (lookup-static-class s-name)) i-names)) (f-names (append-field-names (static-class->field-names (lookup-static-class s-name)) f-names)) (f-types (append (static-class->field-types (lookup-static-class s-name)) f-types)) (method-tenv (let ((local-method-tenv (method-decls->method-tenv m-decls))) (check-no-dups! (map car local-method-tenv) c-name) (merge-method-tenvs (static-class->method-tenv (lookup-static-class s-name)) local-method-tenv)))) (check-no-dups! i-names c-name) (check-no-dups! f-names c-name) (check-for-initialize! method-tenv c-name) (add-static-class-binding! c-name (a-static-class s-name i-names f-names f-types method-tenv)))))))
过程 add-class-decl-to-static-class-env!（）承担创建静 态类的艰巨工作。对每个类，我们必须收集其接口、字段和方法：
-
类实现父类实现的任何接口，以及自身声称实现的接口。
-
类具有父类的所有字段，以及自身的字段，但是父类字段被当前声明的字段遮蔽。 所以，field-names 由 append-field-names 计算而得，就像 initialize-class-env! 那样（initialize-class-env!）。
-
类字段的类型包括父类字段的类型，以及自身声明字段的类型。
-
类的方法包括父类的和自身的，方法带有声明类型。我们用 proc-type 记录方法的类型。我们把当前声明的方法放在前面， 因为它们覆盖父类的方法。
-
我们确保当前类中声明的方法名、接口名和字段名不重复。我们还确保类中一定有 initialize 方法。
一旦建立了静态类环境，我们可以检查每个类声明。这由 check-class-decl!（）完成。对接口，什么都不必检查。对 类声明，我们传递从静态类环境收集到的信息，检查每个方法。最后，我们检查类是否实现 了它声称实现的每个接口。
[!t]
check-class-decl! : \mathit{ClassDecl} \to \mathit{Unspecified} (define check-class-decl! (lambda (c-decl) (cases class-decl c-decl (an-interface-decl (i-name abs-method-decls) #t) (a-class-decl (class-name super-name i-names field-types field-names method-decls) (let ((sc (lookup-static-class class-name))) (for-each (lambda (method-decl) (check-method-decl! method-decl class-name super-name (static-class->field-names sc) (static-class->field-types sc))) method-decls)) (for-each (lambda (i-name) (check-if-implements! class-name i-name)) i-names)))))
要检查方法声明，我们首先检查其主体是否符合声明类型。要这样做，我们建立一个类型环 境，该环境与主体求值时的环境相符。然后我们检查主体的结果类型是否为声明中结果类型 的子类型。
[!ht]
check-method-decl! :
\phantom{x}\mathit{MethodDecl} \times \mathit{ClassName} \times \mathit{ClassName} \times \mathit{Listof(FieldName)} \times \mathit{Listof(Type)} \\ \phantom{xxxx}\to \mathit{Unspecified}(define check-method-decl! (lambda (m-decl self-name s-name f-names f-types) (cases method-decl m-decl (a-method-decl (res-type m-name vars var-types body) (let ((tenv (extend-tenv vars var-types (extend-tenv-with-self-and-super (class-type self-name) s-name (extend-tenv f-names f-types (init-tenv)))))) (let ((body-type (type-of body tenv))) (check-is-subtype! body-type res-type m-decl) (if (eqv? m-name 'initialize) #t (let ((maybe-super-type (maybe-find-method-type (static-class->method-tenv (lookup-static-class s-name)) m-name))) (if maybe-super-type (check-is-subtype! (proc-type var-types res-type) maybe-super-type body) #t)))))))))
但还没完：如果这个方法覆盖了超类中的某个方法，我们要确保它的类型兼容超类中的方法 类型。之所以如此，是因为这个方法可能由另一方法调用，而另一方法只知道超类方法的类 型。这条规则的唯一例外是 initialize，它只在当前类中调用，且随继承改变类型 （见）。要这样做，它调用 maybe-find-method-type，后者 返回已绑定方法的类型，或者 #f。见。
如，过程 check-if-implements? 取两个符号，分别为类名和 接口名。它首先检查两个符号确实为类名和接口名。然后，它遍历接口中的每个方法，检查 类是否提供了同名且类型兼容的方法。
为 中示例程序生成的静态类环境如 所示。 静态类是逆序的，这反映了生成类环境的顺序。三个类中的方法顺序相同，且类型相同，符 合期望。
[!t]
check-if-implements! : \mathit{ClassName} \times \mathit{InterfaceName} \to \mathit{Bool} (define check-if-implements! (lambda (c-name i-name) (cases static-class (lookup-static-class i-name) (a-static-class (s-name i-names f-names f-types m-tenv) (report-cant-implement-non-interface c-name i-name)) (an-interface (method-tenv) (let ((class-method-tenv (static-class->method-tenv (lookup-static-class c-name)))) (for-each (lambda (method-binding) (let ((m-name (car method-binding)) (m-type (cadr method-binding))) (let ((c-method-type (maybe-find-method-type class-method-tenv m-name))) (if c-method-type (check-is-subtype! c-method-type m-type c-name) (report-missing-method c-name i-name m-name))))) method-tenv))))))
((leaf-node #(struct:a-static-class object (tree) (value) (#(struct:int-type)) ((initialize #(struct:proc-type (#(struct:int-type)) #(struct:void-type))) (sum #(struct:proc-type () #(struct:int-type))) (getvalue #(struct:proc-type () #(struct:int-type))) (equal #(struct:proc-type (#(struct:class-type tree)) #(struct:bool-type)))))) (interior-node #(struct:a-static-class object (tree) (left right) (#(struct:class-type tree) #(struct:class-type tree)) ((initialize #(struct:proc-type (#(struct:class-type tree) #(struct:class-type tree)) #(struct:void-type))) (getleft #(struct:proc-type () #(struct:class-type tree))) (getright #(struct:proc-type () #(struct:class-type tree))) (sum #(struct:proc-type () #(struct:int-type))) (equal #(struct:proc-type (#(struct:class-type tree)) #(struct:bool-type)))))) (tree #(struct:an-interface ((sum #(struct:proc-type () #(struct:int-type))) (equal #(struct:proc-type (#(struct:class-type tree)) #(struct:bool-type)))))) (object #(struct:a-static-class #f () () () ())))
\textnormal{[}{\star}\textnormal{]} 扩展类型检查器，确保安全性质：instanceof 和 cast 不会处理非对象值或非 类类型。
\textnormal{[}{\star}\textnormal{]} 若 e 的类型不是 c 的后代或者祖先，则表达式 cast e c 不会成 功（为什么？）。扩展类型检查器，确保程序只对满足这条性质的 cast 表达式求值。 再对 instanceof 的检查做相应扩展。
\textnormal{[}{\star}\textnormal{]} 扩展类型检查器，确保 initialize 方法只从 new-object-exp 内部调用，从而 加强安全性。
\textnormal{[}{\star}\textnormal{]} 扩展语言，允许接口继承自其他接口。接口应要求实现父类要求实现的所有方法。
\textnormal{[}{\star}{\star}\textnormal{]} 我们的 TYPED-OO 语言使用动态分发。另一种方式是静态分发。在静态分发中，方 法的选择依赖于对象的类型，而不是所属类。考虑例子
class c1 extends object
method int initialize () 1
method int m1 () 11
staticmethod int m2 () 21
class c2 extends c1
method void m1 () 12
staticmethod int m2 () 22
let f = proc (x : c1) send x m1()
g = proc (x : c1) send x m2()
o = new c2()
in list((f o), (g o))
调用 f 和 g 时，x 类型为 c1，但绑定到类 c2 的对象。方法 m1 使用动态分发，所以调用的是 c2 的方法 m1，返回 12。方法 m2 使用静态分发，所以给 x 发送消息 m2 时，调用的是与 x 类型（即本例 中的 c1）对应的方法，所以返回 21。
修改带有类型的语言中的解释器，处理静态分发。提示：考虑在环境中记录类型信息，那么 解释器就能在 send 中找出目标表达式的类型。
\textnormal{[}{\star}{\star}\textnormal{]} 为什么类的信息必须在检查方法之前加入到静态类环境中？提示：思考一下，某个方法主体 通过 self 调用方法时会发生什么？
\textnormal{[}{\star}{\star}\textnormal{]} 除了在 new 内隐式调用 initialize 之外，让类型检查器禁止调用 initialize。
\textnormal{[}{\star}\textnormal{]} 修改语言的设计，让每个字段声明包含一个用于初始化字段的表达式。这种设计的优势是， 通过检查的程序不会使用未初始化的值。
\textnormal{[}{\star}{\star}\textnormal{]} 扩展类型检查器，像 那样，处理 fieldref 和 fieldset。
\textnormal{[}{\star}{\star}\textnormal{]} 在类型检查器中，静态方法与普通方法处理方式相同，只是静态方法不能覆盖动态方法，反 之亦然。扩展检查器，处理静态方法。