第4章：子类型（类型的层次）Subtyping — The Hierarchy of Types

一、导读

1.1 学习目标

本章深入探讨子类型关系，这是面向对象编程和现代类型系统中的核心概念。通过本章的学习，读者将达成以下目标：

掌握子类型的形式化定义和基本性质（自反性、传递性）
理解 Top 类型和 Bottom 类型的特殊地位与作用
掌握记录类型的子类型规则（宽度子类型与深度子类型）
理解子类型与参数多态的交互问题（协变、逆变、不变）
认识子类型在面向对象语言中的实际应用和设计指导意义

1.2 重要性

子类型是现代编程语言中最普遍的类型关系之一。在 Java 中，ArrayList 是 List 的子类型；在 TypeScript 中，具有更多属性的对象类型是具有较少属性对象类型的子类型；在 Scala 中，Nothing 是所有类型的子类型。子类型关系使得类型系统更加灵活，允许在需要通用类型的地方使用更具体的类型，实现了代码的多态性和可扩展性。

子类型的理论基础对于理解面向对象编程至关重要。Liskov 替换原则（Liskov Substitution Principle, LSP）——"子类型对象应该能替代超类型对象而不破坏程序的正确性"——本质上就是子类型的语义要求。理解子类型的形式化规则有助于我们设计正确的类层次结构，避免常见的继承陷阱。

1.3 核心问题

子类型和类型等价有什么区别？为什么需要两种不同的类型关系？
为什么函数类型的参数位置是逆变的，而返回值位置是协变的？
数组为什么在 Java 中是协变的？这个设计决策带来了什么问题？
子类型和多态类型（泛型）如何交互？为什么 List<Dog> 不是 List<Animal> 的子类型？

二、核心概念详解

2.1 子类型的基本定义

子类型关系 S <: T（读作"S 是 T 的子类型"）表示 S 类型的值可以安全地用于需要 T 类型值的上下文。这个定义的核心是"安全替换"——子类型的值具有超类型的所有能力，可能还有额外的能力。

子类型关系必须满足以下基本性质：

自反性（Reflexivity）：T <: T。任何类型都是自身的子类型。

传递性（Transitivity）：如果 S <: T 且 T <: U，则 S <: U。子类型关系可以传递。

反对称性（Anti-symmetry）：如果 S <: T 且 T <: S，则 S 和 T 是等价的类型。这保证了子类型关系的层次结构不会出现循环。

子类型化的核心规则是替换规则（Subsumption）：

Γ ⊢ e : S    S <: T
----------------------
Γ ⊢ e : T

如果 e 具有类型 S，且 S 是 T 的子类型，则 e 也可以被视为具有类型 T。这条规则允许在类型检查时自动将子类型值提升为超类型值。

2.2 Top 类型与 Bottom 类型

Top 类型（记为 Top 或 ⊤）是所有类型的超类型：对任何类型 T，都有 T <: Top。Top 类型的变量可以接受任何类型的值，但它不提供任何特定的操作。Top 类型类似于 Java 中的 Object（在纯子类型系统中）或 TypeScript 中的 unknown。

Bottom 类型（记为 Bottom 或 ⊥）是所有类型的子类型：对任何类型 T，都有 Bottom <: T。Bottom 类型没有实际的值（它是空类型），但它在类型系统中扮演重要角色。一个返回 Bottom 类型的函数永远不会正常返回——它要么抛出异常，要么进入无限循环。在 TypeScript 中，never 类型就是 Bottom 类型。

Top 和 Bottom 类型为类型系统提供了完整的边界。任何类型都在 Top 和 Bottom 之间形成一个偏序结构（格结构）。这个格结构在类型推断和类型检查中起着重要作用——类型推断的结果通常是满足约束的最小类型或最大类型。

2.3 记录类型的子类型

记录类型（Record Type）是由命名字段组成的复合类型，如 {name: String, age: Nat}。记录类型的子类型规则是子类型理论中最重要也最微妙的部分。

宽度子类型（Width Subtyping）：具有更多字段的记录是具有较少字段记录的子类型。

{name: String, age: Nat, email: String} <: {name: String, age: Nat}

直觉：一个拥有 name、age 和 email 的对象完全可以用于只需要 name 和 age 的上下文——它拥有所有需要的字段，还多了一个不影响的额外字段。

深度子类型（Depth Subtyping）：如果记录的对应字段之间存在子类型关系，则记录之间也存在子类型关系。

{name: String, addr: {city: String, zip: String, country: String}}
  <:
{name: String, addr: {city: String, zip: String}}

直觉：嵌套字段也遵循宽度子类型规则。

注意：深度子类型要求字段类型之间是协变关系。如果字段是可变（mutable）的，则深度子类型可能不安全——这是 Java 数组协变问题的根源。

2.4 函数类型的子类型

函数类型的子类型规则是最反直觉但最重要的规则之一。函数类型 S1 → S2 是 T1 → T2 的子类型，当且仅当：

T1 <: S1（参数类型逆变，contravariant）
S2 <: T2（返回值类型协变，covariant）

形式化规则：

T1 <: S1    S2 <: T2
-----------------------------
S1 → S2 <: T1 → T2

为什么参数是逆变的？ 考虑一个接受 Animal 参数的函数 f: Animal → String。它可以安全地用于需要 Dog → String 函数的上下文吗？可以！因为任何传入的 Dog 都可以当作 Animal 处理（Dog <: Animal）。所以 Animal → String <: Dog → String，参数位置发生了逆转。

为什么返回值是协变的？ 一个返回 Dog 的函数 f: String → Dog 可以安全地用于需要 String → Animal 函数的上下文吗？可以！因为返回的 Dog 可以当作 Animal 使用。所以 String → Dog <: String → Animal，返回值位置保持同向。

2.5 方差注解

在实际编程语言中，泛型类型的方差（variance）是一个关键的设计问题：

协变（Covariant）：如果 A <: B，则 F<A> <: F<B>。类型参数的子类型关系保持同向。适用于只读容器（如 producer）。Java 中用 ? extends T 表示上界通配符。

逆变（Contravariant）：如果 A <: B，则 F<B> <: F<A>。类型参数的子类型关系逆转。适用于只写容器（如 consumer）。Java 中用 ? super T 表示下界通配符。

不变（Invariant）：F<A> 和 F<B> 之间没有子类型关系。适用于既可读又可写的容器。Java 的 List<T> 是不变的——List<Dog> 不是 List<Animal> 的子类型，因为你可以向 List<Animal> 中插入 Cat，但如果实际是 List<Dog> 就会破坏类型安全。

PECS 原则（Producer Extends, Consumer Super）总结了泛型方差的实践指导：如果泛型容器只用于产出（producer），使用协变（extends）；如果只用于消费（consumer），使用逆变（super）。

三、深入分析

3.1 子类型与多态的交互

子类型和多态是类型系统中两个独立但经常交互的概念。子类型多态（subtype polymorphism）允许通过子类型关系实现多态，是面向对象编程的基础。参数多态（parametric polymorphism）通过类型参数实现多态，是泛型编程的基础。

两者的交互产生了微妙的问题。在 Java 中，数组是协变的（Dog[] <: Animal[]），这在早期设计中被认为是方便的，但实际上是不安全的：

java

Dog[] dogs = new Dog[10];
Animal[] animals = dogs;  // 合法，因为 Dog[] <: Animal[]
animals[0] = new Cat();   // 运行时 ArrayStoreException！

Java 通过运行时检查来弥补这个设计缺陷，但这违反了类型安全应在编译期保证的原则。相比之下，C# 的数组是不变的，避免了这个问题。

对于泛型，Java 采用了更安全的方案：List<Dog> 不是 List<Animal> 的子类型（不变），但可以通过通配符实现受控的方差：List<? extends Animal> 是只读的协变容器，List<? super Dog> 是只写的逆变容器。

3.2 Liskov 替换原则的形式化

Liskov 替换原则（LSP）是面向对象设计的核心原则之一，它要求子类型的行为必须与超类型兼容。形式化地说，如果 S 是 T 的子类型，则对于任何使用 T 类型值的程序 P，将 P 中的 T 值替换为 S 值后，P 的行为不变。

LSP 对子类的设计提出了严格的约束：

前置条件不能增强：子类方法不能比超类方法要求更多的输入条件
后置条件不能减弱：子类方法不能比超类方法保证更少的输出条件
不变量必须保持：子类必须保持超类定义的所有不变量

违反 LSP 的经典例子是"正方形是矩形吗？"。从数学上看，正方形是特殊的矩形。但在程序设计中，如果矩形支持独立设置宽度和高度（setWidth、setHeight），则正方形不能安全地替代矩形——设置宽度时正方形也会改变高度，违反了矩形的后置条件。

3.3 子类型判定算法

子类型判定算法用于确定两个类型之间是否存在子类型关系。对于简单的类型系统，这是一个直接的递归过程：

function isSubtype(S, T):
  if S == T: return true            // 自反性
  if T == Top: return true           // Top 是超类型
  if S == Bottom: return true        // Bottom 是子类型
  
  match (S, T):
    case (S1 → S2, T1 → T2):        // 函数类型
      return isSubtype(T1, S1)       // 参数逆变
          && isSubtype(S2, T2)       // 返回值协变
    case ({fields_S}, {fields_T}):   // 记录类型
      for each field f in fields_T:
        if f not in fields_S: return false   // 宽度
        if not isSubtype(fields_S[f], fields_T[f]): return false  // 深度
      return true
    case (S1 × S2, T1 × T2):        // 积类型
      return isSubtype(S1, T1) && isSubtype(S2, T2)
    case (S1 + S2, T1 + T2):        // 和类型
      return isSubtype(S1, T1) && isSubtype(S2, T2)

对于包含递归类型或存在类型的系统，子类型判定变得更加复杂，可能需要不动点计算。对于包含通用量词（如 F-bounded 多态）的系统，子类型判定可能变得不可判定。

四、实践案例

4.1 案例一：TypeScript 的结构化子类型

TypeScript 采用结构化子类型（Structural Subtyping），也称为"鸭子类型"（Duck Typing）的形式化版本。在 TypeScript 中，类型兼容性由类型的结构决定，而非由类型的名称决定。

typescript

interface Named {
  name: string;
}

class Person {
  name: string;
  age: number;
}

let n: Named;
let p: Person = { name: "Alice", age: 30 };
n = p;  // 合法！Person 的结构包含 name: string，满足 Named 的要求

TypeScript 的子类型规则还包含了函数参数双变的实用主义妥协：在函数赋值时，参数类型允许双变（bivariant），即既不要求协变也不要求逆变。这在严格意义上是不安全的，但在实践中避免了大量不必要的类型标注负担。TypeScript 提供了 --strictFunctionTypes 编译选项来启用严格的函数参数逆变检查。

4.2 案例二：Java 的泛型方差设计

Java 的泛型方差设计是一个从错误中学习的经典案例。早期 Java 数组的协变设计带来了运行时类型安全问题。在引入泛型时（Java 5），设计者采用了更安全的不变策略，并通过通配符提供了受控方差。

java

// 不变：List<Dog> 不是 List<Animal> 的子类型
List<Dog> dogs = new ArrayList<>();
// List<Animal> animals = dogs;  // 编译错误

// 协变上界：只读访问
List<? extends Animal> animals = dogs;  // 合法
Animal a = animals.get(0);  // 合法：可以读取为 Animal
// animals.add(new Cat());  // 编译错误：不能写入

// 逆变下界：只写访问
List<? super Dog> animalList = new ArrayList<Animal>();
animalList.add(new Dog());  // 合法：可以写入 Dog
// Dog d = animalList.get(0);  // 编译错误：只能读取为 Object

这个设计体现了 PECS 原则：Producer Extends（协变用于读取），Consumer Super（逆变用于写入）。

五、常见误区

5.1 误区一："is-a" 关系等同于子类型

许多教科书用 "is-a" 关系来解释继承和子类型，但这是不精确的。正方形在数学上"是一个"矩形，但在程序设计中可能不是矩形的子类型（违反 LSP）。子类型的关键不是语义上的 "is-a"，而是行为上的"可替换性"——子类型必须能安全地替代超类型。

5.2 误区二：子类型就是继承

在面向对象语言中，继承是实现子类型的一种机制，但两者不是同一概念。子类型是类型之间的外部关系（关于值的可替换性），继承是类之间的内部关系（关于代码的复用和扩展）。在结构化子类型系统（如 TypeScript）中，两个完全无关的类之间也可能存在子类型关系，只要它们的结构兼容。

5.3 误区三：协变总是安全的

协变在只读场景下是安全的，但在可写场景下可能不安全。Java 数组的协变设计就是一个反例。对于泛型容器，必须根据使用方式（只读/只写/读写）选择合适的方差。记住 PECS 原则：Producer Extends, Consumer Super。

5.4 误区四：名义类型比结构类型更优越

名义类型系统（如 Java）通过名称判断子类型关系，结构类型系统（如 TypeScript）通过结构判断。名义类型更明确但更僵硬，结构类型更灵活但可能产生意外的兼容关系。两种类型系统各有优劣，选择取决于具体的设计需求。

六、本章小结

本章系统讲解了子类型的基本概念、规则和实际应用。子类型关系通过替换原则实现了类型的多态性，使得更具体的类型可以安全地用于需要更通用类型的上下文。Top 和 Bottom 类型为类型系统提供了完整的边界。

记录类型的子类型规则（宽度和深度子类型）支持了灵活的字段扩展模式。函数类型的子类型规则揭示了参数逆变和返回值协变的原则，这是类型系统中最反直觉但最重要的规则之一。方差注解（协变、逆变、不变）为泛型类型的安全使用提供了指导。

子类型与多态的交互产生了丰富的设计问题。Java 数组的协变设计教训和泛型通配符的解决方案展示了子类型理论在实践中的重要性。Liskov 替换原则为面向对象设计提供了形式化的指导。

理解子类型理论有助于我们设计更灵活、更安全的类型层次结构，避免常见的继承和设计陷阱。这些知识为后续学习多态类型和存在类型奠定了重要基础。

七、思考题

请证明函数类型的子类型规则：为什么参数必须逆变而返回值必须协变？构造一个具体例子说明违反这两条规则会导致什么类型安全问题。

考虑以下类型层次：Circle <: Shape，List<T> 是不变的。请问 List<Circle> 和 List<Shape> 之间是什么关系？如何安全地向 List<Shape> 中添加 Circle 元素？

在 TypeScript 中，{a: string, b: number} 和 {a: string} 之间是什么子类型关系？如果 b 是可选的（b?: number），关系会改变吗？

设计一个场景说明"正方形不是矩形的子类型"。用代码展示违反 LSP 的具体后果。

研究一下你常用的编程语言中子类型的实现方式。它是名义类型还是结构类型？函数类型的参数是协变、逆变还是双变的？