12 Object-Oriented Languages¶
面向对象语言 (Object-Oriented Languages) 的编译器需要将类、继承、方法重写等高层抽象高效地映射到机器代码和数据布局上。核心挑战是：如何在运行时以最低开销实现动态方法分派、字段访问和类型检测。
12.1 Core Concepts¶
基于类的面向对象语言有三个基本特征：
- 继承 (Inheritance)：类可以扩展另一个类，子类自动拥有父类的所有字段和方法，并可重写方法以精化行为。
- 封装 (Encapsulation)：对象的内部状态隐藏在公共接口之后，外部代码只能通过暴露的方法访问。私有性检查在编译时完成，不影响运行时性能。
- 多态 (Polymorphism)：同一方法调用可根据对象的运行时实际类型执行不同代码。典型实现机制为虚函数表 (VTable)。
Object-Tiger 语法：在标准 Tiger 基础上增加了类声明、继承、对象创建和方法调用。
// 类声明
dec → classdec
classdec → class id extends id { classfield* }
classfield → vardec
| method
method → method id ( tyfields ) = exp
| method id ( tyfields ) : type-id = exp
// 对象表达式
exp → new id // 创建对象
| lvalue . id ( ) // 无参方法调用
| lvalue . id ( exp {, exp} ) // 带参方法调用
继承规则：
- 父类的所有字段和方法隐式属于子类，无需重复声明。
- 方法可以重写 (Override)，子类用同签名方法覆盖父类实现。
- 字段不可以重写——子类不能声明与父类同名字段。
- 重写方法必须保持与父类相同的参数类型和返回类型（签名一致）。
Self 参数：每个方法隐式携带一个 self 参数，运行时自动绑定到接收者对象（即方法调用中 . 左侧的对象）。self 不是关键字——它只是一个约定名称的隐式形参，在方法体中引用当前对象。
编译 Object-Tiger 程序需要解决三个核心问题：
- 字段布局 (Field Layout)：如何将对象的字段排布在内存中，使得字段访问高效。
- 方法分派 (Method Dispatch)：如何找到某个方法调用对应的具体实现。
- 成员测试 (Membership Test)：如何在运行时判断对象是否属于某类型（如
instanceof）。
后续章节依次展开这三方面的实现技术。
12.2 Single Inheritance¶
单继承是最简单的继承模型——每个类最多有一个父类，形成一棵类继承树。
12.2.1 Field Layout: Prefix Method¶
前缀法 (Prefix Method) 是单继承下字段布局的标准策略：子类对象的内存布局是父类布局的前缀——先按父类顺序排放字段，再追加子类新增字段。
优势：父类字段在所有子类中的偏移量完全一致。无论对象实际是 A、B 还是 C，字段 a 始终在偏移量 4 处，编译器可以直接用 [obj + 4] 生成访问指令，无需任何运行时查表。
12.2.2 Method Dispatch¶
编译器按方法调用是否允许多态分为两种分派方式：
静态方法 (Static Dispatch)：编译时根据变量声明类型确定调用目标，直接跳转到固定标签。
在语义分析阶段，编译器为每个变量建立指向其类描述符 (Class Descriptor) 的环境条目。类描述符中包含父类指针和方法实例列表，每个方法实例关联一个机器代码标签。
调用 c.f() 时：
1. 从变量 c 的声明类 C 开始查找方法 f
2. 若 C 中未找到，沿继承链向上查找父类 → 祖父类 → ...
3. 在祖先类 A 中找到后，直接生成 call A_f 指令
整个过程在编译时完成，不涉及运行时查表——调用的目标取决于变量的声明类型而非对象的实际类型。因此静态方法无多态、无运行时开销，等同于普通函数调用。
动态方法 (Dynamic Dispatch)：运行时根据对象实际类型解析调用目标。核心机制是 VTable（虚函数表）。
12.2.3 VTable¶
每个类的类描述符 (Class Descriptor) 中嵌入一个 VTable——一个按固定顺序排列的方法指针数组。
每个对象在头部存储一个指向其类 VTable 的指针。动态方法调用的机器代码序列：
// 调用 obj.m3() 的底层实现:
r1 ← obj->vtable_ptr // ① 加载 VTable 地址 (1次 mem load)
r2 ← r1[m3_offset] // ② 加载方法指针 (1次 mem load)
call r2 // ③ 间接跳转
开销：2 次内存加载 + 1 次间接跳转。相比于静态调用（1 次直接跳转），额外开销可接受，且换来了多态的灵活性。
12.3 Multiple Inheritance¶
多继承下，一个类有多个父类。简单的前缀法失效——无法同时将所有父类的字段都放在子类开头。
12.3.1 Graph Coloring¶
将字段偏移量分配建模为图着色问题：
- 节点：字段名（如
a,b,c） - 边：两个字段共存于同一个类中（它们需要不同的偏移量）
- 颜色：内存偏移量
着色算法为每个字段分配一个不冲突的颜色（偏移量），保证任何类中共存的字段使用不同的偏移。
12.3.2* Hash Table (Dynamic Loading)¶
对于支持动态类加载的语言（如 Java），无法在编译时完成全程序分析。此时类描述符中存储键值对表：
- Ktab (Key Table)：字段名 / 方法名的哈希键
- Ftab (Field/Function Table)：对应的字段偏移或方法指针
访问字段时通过哈希查找获取偏移量。开销较大但支持运行时的类动态链接和反射。
12.4* Class Membership Testing¶
instanceof 和类型强制转换需要在运行时判断"对象是否是某类的实例"。
12.4.1 Linear Search¶
从对象的类描述符开始，沿 super 指针逐级向上查找目标类：
function instanceof(obj, targetClass):
cls = obj->class_desc
while cls != null:
if cls == targetClass: return true
cls = cls->super // 沿继承链向上
return false
缺点：时间复杂度 \(O(d)\)（\(d\) 为继承深度），每次 instanceof 都要沿链查找，长继承链下性能差。
12.4.2 Display Array¶
预计算每个类的祖先数组 (Display Array)，记录各深度的祖先类：
class A (depth 0): Display = [A, null, null, ...]
class B extends A (depth 1): Display = [A, B, null, ...]
class C extends B (depth 2): Display = [A, B, C, null, ...]
判断算法：
function instanceof(obj, targetClass):
d = targetClass->depth
return obj->class_desc->display[d] == targetClass
只需一次数组索引 + 一次指针比较——时间复杂度 \(O(1)\)。每个类的 display 数组在类加载时通过拷贝父类 display 并追加自身即可完成。
12.5 Private Members¶
私有性（private）纯粹是编译时概念：
- 编译器在类型检查阶段验证访问权限——检查当前代码是否有权访问目标字段/方法。
- 一旦类型检查通过，生成的代码与公有成员完全相同——无任何运行时检查开销。
- 私有字段在内存布局中依然遵循继承规则：子类对象包含父类的私有字段（占用空间），只是子类代码无法直接通过名字访问它们。
class A {
private field secret: int
public method get(): int = self.secret
}
class B extends A {
method get(): int = self.secret // ★ 编译错误! 子类不能访问 A 的 private
}
这意味着封装是纯粹的编译期安全机制，不付出额外的运行时代价。
Comparison¶
| 静态方法 | 动态方法 | 字段访问 | |
|---|---|---|---|
| 解析时机 | 编译时 (声明类型) | 运行时 (实际类型) | 编译时 (固定偏移) |
| 实现机制 | 直接跳转 | VTable + 间接跳转 | [obj + offset] 直接寻址 |
| 运行时开销 | 1 次 jump | 2×load + 1×indirect call | 1×load |
| 多态支持 | 否 | 是 | — |
| 单继承 | 多继承 | |
|---|---|---|
| 字段布局 | 前缀法 — 简单高效 | 图着色 / 哈希表 — 复杂 |
| 方法分派 | VTable 前缀继承 | VTable 需额外调整 this 指针 |
| 成员测试 | Display Array — O(1) | 同样适用 |
| 工程语言 | C#, Swift | C++, Python |
评论区
对你有帮助的话请给我个赞和 star =>
欢迎跟我探讨！！！