CS143 Chapter 10

10-01 Static vs. Dynamic Typing

正如前面所说，类型检查可以采用 Static Typing 或 Dynamic Typing。Static Type System 能够在编译阶段提前发现很多常见错误，但由于编译器只能利用静态信息进行判断，因此也可能拒绝一些实际上能够正确运行的程序。

解决这种问题可以有两个方向：

使用 Dynamic Type Checking
→ 将更多判断留到 Runtime

或者

设计更加 Expressive 的 Static Type System
→ 在编译阶段保留更多类型信息

但更加 Expressive 的 Type System 往往也会更加复杂。

这里还需要区分 Static Type 和 Dynamic Type。

Dynamic Type 是一个 Runtime 概念，表示一个对象在实际运行时真正是什么 Class。例如一个对象由：

new B

创建，那么它的 Dynamic Type 就是 B。

而 Static Type 是 Compile Time 概念，是编译器在不实际运行程序的情况下，为一个 Expression 推导出来的 Type。它需要概括这个 Expression 在运行时所有可能出现的 Dynamic Types。

例如：

class A { ... }

class B inherits A { ... }

x : A ← new A

x ← new B

变量 x 的 Static Type 始终是：

A

但是它运行时保存的对象可能分别具有：

Dynamic Type = A

或者：

Dynamic Type = B

因为：

B ≤ A

所以 B 类型的对象可以被 A 类型的变量保存。

因此，在 COOL 中 Static Type 和 Dynamic Type 并不要求完全相同，而是满足：

dynamic_type(E) ≤ static_type(E)

也就是说：

Expression 实际运行得到的 Dynamic Type，可以比编译器推导出的 Static Type 更具体，但不能超出 Static Type 所允许的范围。

例如：

Static Type  = Animal
Dynamic Type = Dog

只要：

Dog ≤ Animal

就是合法的。

之所以这样仍然是 Sound 的，是因为一个 Subtype 至少支持其父类型允许的操作，因此按照 Static Type 进行 Type Checking 后，即使 Runtime 得到的是更加具体的 Subtype，也不会破坏原来的类型安全。

所以可以简单理解为：

Static Type 是编译器在编译阶段能够保证的类型范围，而 Dynamic Type 是程序真正运行时对象实际具有的类型。Static Type 负责提供安全保证，Dynamic Type 则可以在这个范围内更加具体。

10-02 Self Type

SELF_TYPE 解决的是类继承过程中，父类方法被子类继承后，返回类型过于宽泛而导致类型信息丢失的问题。

例如父类 Count 中存在方法：

inc() : Count

并且该方法最终返回 self。

如果子类：

Stock inherits Count

继承了 inc()，那么：

(new Stock).inc()

实际运行时返回的仍然是一个 Stock 对象，但是按照原来的 Type Rule，它的 Static Type 会被判断为 Count。这样就会导致：

Stock a ← (new Stock).inc()

在类型检查时出现错误。

问题的关键在于：

inc() 返回的是 self，因此返回值的 Type 实际上应该和调用这个方法的对象 Type 保持一致，而不是永远固定为父类 Count。

因此可以将方法定义修改为：

inc() : SELF_TYPE

此时 Type Checker 就可以得到：

(new Count).inc() : Count

(new Stock).inc() : Stock

也就是说，SELF_TYPE 会随着当前调用对象的 Type 变化，从而避免父类方法在继承后丢失具体的子类类型信息。

需要注意的是：

SELF_TYPE 本身仍然是一种 Static Type，而不是 Dynamic Type。

它的作用是让 Static Type System 能够更加准确地记录对象可能具有的类型，因此可以接受更多原本正确、但由于类型信息丢失而无法通过检查的程序，也就是提高 Type System 的 Expressiveness。

所以可以简单理解为：

SELF_TYPE 表示“当前 self 所具有的 Type”，使继承的方法能够根据实际调用它的 Class 保留更加具体的返回类型。

---

10-03 SELF_TYPE Operation

SELF_TYPE 可以近似理解为当前 Class Type 的一个更具体子集，用来保留继承过程中更加精确的子类类型信息。后续的 ≤ 和 lub 只是对原有类型运算增加 SELF_TYPE 的处理规则。

SELF_TYPE_C 表示出现在 Class C 中的 SELF_TYPE，可以直观理解为：

C 或 C 的某个 Subtype

因此：

SELF_TYPE_C ≤ C

成立。

为了支持 SELF_TYPE，需要在原本的 Type Operation 上补充对应规则，主要包括 ≤ 和 lub。

对于 Subtyping：

SELF_TYPE_C ≤ SELF_TYPE_C

SELF_TYPE_C ≤ T
if C ≤ T

T ≤ SELF_TYPE_C
通常不成立

对于 lub：

lub(SELF_TYPE_C, SELF_TYPE_C)
= SELF_TYPE_C

lub(SELF_TYPE_C, T)
= lub(C, T)

因此可以简单理解为：

SELF_TYPE 表示当前 Class 或其更具体的 Subtype，而 SELF_TYPE Operation 就是在原来的 Subtyping 和 lub 规则上补充对这种特殊 Type 的处理。

10-04 SELF_TYPE Usage

SELF_TYPE 并不是在所有可以写 Type 的地方都能使用。Parser 只负责检查它是否出现在 Type 应该出现的位置，而 Type Checker 还需要进一步限制它具体能出现在哪里。

可以简单整理成：

class T inherits T'
→ T、T' 都不能是 SELF_TYPE

x : T
→ T 可以是 SELF_TYPE

let x : T in E
→ T 可以是 SELF_TYPE

new T
→ T 可以是 SELF_TYPE
   表示创建一个与 self 相同类型的对象

e@T.f(...)
→ T 不能是 SELF_TYPE

对于 Method：

m(x : T) : T' { ... }

规则是：

Parameter Type T
→ 不能是 SELF_TYPE

Return Type T'
→ 可以是 SELF_TYPE

原因是 Method Parameter 如果使用 SELF_TYPE，继承之后参数要求会随着子类发生变化，可能破坏原本父类方法允许的调用方式。

课件中的例子：

class A {
    foo(x : SELF_TYPE) : Bool { ... }
}

class B inherits A {
    b : Int

    foo(x : SELF_TYPE) : Bool {
        ... x.b ...
    }
}

如果允许这种写法，那么通过 A 类型对象调用 foo(new A) 原本应该合法，但对象实际可能是 B，此时 B.foo() 会把参数当成 B 使用并访问 x.b，而传入的却可能只是 A，因此会产生类型安全问题。

所以这一节可以直接记成：

SELF_TYPE 主要允许用于 Object / Attribute、Let、new 和 Method Return Type；不能用于 Class 继承、Static Dispatch 指定 Type 和 Method Parameter Type。

10-04 SELF_TYPE Checking

对应 PPT 24-34

由于 SELF_TYPE 的具体含义取决于它出现在哪个 Class 中，因此进行 Type Checking 时，除了原来的 Object Environment O 和 Method Environment M，还必须知道当前所在的 Class C。

因此完整的 Type Checking 形式为：

O, M, C ⊢ e : T

表示：

在 Object Environment O、Method Environment M 和当前 Class C 下，Expression e 的 Static Type 为 T。

加入 SELF_TYPE 后，大多数原来的 Type Rules 不需要改变，只需要使用上一节扩展后的：

≤

lub

来处理 SELF_TYPE 即可。

真正需要特殊处理的主要是 Method Dispatch。

对于普通方法：

e0.f(e1, ..., en)

如果方法 f 的 Return Type 是普通 Type：

M(T0, f) = (T'1, ..., T'n, T'n+1)

那么仍然按照原来的规则：

e0 : T0
ei : Ti

Ti ≤ T'i

最终：
e0.f(e1, ..., en) : T'n+1

也就是 Method Call 的 Type 就是方法声明的 Return Type。

但是如果方法声明：

M(T0, f) = (T'1, ..., T'n, SELF_TYPE)

那么 Method Call 的结果 Type 不再直接写成 SELF_TYPE，而是：

e0.f(e1, ..., en) : T0

即：

如果方法返回 SELF_TYPE，那么整个 Dispatch Expression 的 Type 就是调用对象 e0 的 Static Type。

例如：

(new Stock).inc() : Stock

而如果：

x : Count ← new Stock

那么：

x.inc() : Count

因为 Type Checker 看的是 receiver x 的 Static Type Count。

需要注意：

Formal Parameter
→ 不能声明为 SELF_TYPE

Actual Argument
→ 可以是 SELF_TYPE

Actual Argument 是否合法，可以直接交给扩展后的 ≤ 规则判断。 lecture10

如果 receiver e0 本身的 Type 就是 SELF_TYPE，那么查找方法 f 时，可以使用当前所在的 Class C。这也是为什么完整的 Type Checking Environment 中必须保存 Current Class。

对于 Static Dispatch：

e0@T.f(e1, ..., en)

基本规则与普通 Dispatch 相同，并且仍然需要：

T0 ≤ T

如果 f 返回普通 Type，则整个表达式返回该 Type；如果 f 返回：

SELF_TYPE

那么整个 Static Dispatch 的 Type 仍然是：

T0

而不是 T。

原因是 SELF_TYPE 表示的是 self 对应的类型，即使方法是在 T 中找到的，实际调用这个方法的对象仍然是 e0，它的 Type 可能是 T 的某个 Subtype。

最后还需要加入两个新的 Type Rule：

self : SELF_TYPE_C

new SELF_TYPE : SELF_TYPE_C

也就是说：

self
→ 当前对象自身的类型

new SELF_TYPE
→ 创建一个与当前 self 相同类型的对象

所以这一节最核心的内容可以直接记成：

SELF_TYPE Checking

1. Type Checking 需要 O, M, C
2. 大多数规则直接使用扩展后的 ≤ 和 lub
3. Method 返回 SELF_TYPE 时：
      e0.f(...) 的 Type = e0 的 Static Type
4. Static Dispatch 返回 SELF_TYPE 时也是如此
5. self 和 new SELF_TYPE 的 Type 都是 SELF_TYPE_C

本质上，SELF_TYPE 的作用就是让 Type Checker 不要过早把子类信息丢成父类 Type，从而提高 Static Type System 的表达能力；代价是类型规则也会变得更加复杂。

10-06 error recovering

对于类型错误和类型检查的错误，需要做一套合理的处理方案。

在分析过程中，树的分支向上进行传递会导致错误不断累积。为了解决这个问题，我们曾考虑将一个特殊的类型设置为 no type（也就是所有 any type 的子类型 subtype）。这样的话，编译器可以用这个特殊类型去标识错误并继续进行后续任务，同时也不会让错误不断累积上去。

然而，这个解决方案的设计存在缺陷： 原本的代码分析是一个自顶向下的顺序，从 object 到下面的 subtype，再到更下面的 subtype。引入 no type 之后，最后一层都会归约到 no type 上，导致算法无法完美运行，还需要额外创建数据结构。

在这里，其实没有必要搞这样一个 no type，它会让整个设计变得非常复杂。所以我们不用它去替换 object。虽然当前的实现仍有错误，但这是我们最初的实现，改动反而会让编程变得更加困难