为什么你需要 Subtyping

2025年3月26日

自从 Stephen Dolan 2016 年的论文 Algebraic Subtyping 展示了如何结合类型推断和子类型以来，我一直在开发基于这些思想的日益复杂的编程语言，首先是 2019 年的 IntercalScript，然后是 2020 年的 CubiML，2025 年的 PolySubML，并且我的下一种语言已经在规划阶段。

我一直认为子类型是编程语言设计的下一次重大演进，并且它是新型编程语言的关键特性。 然而，现有的编程语言几乎没有子类型，并且编程社区普遍缺乏对子类型的认识。 因此，在这篇文章中，我将解释什么是子类型以及为什么它如此重要。

什么是 Subtyping？

如果你还记得面向对象编程的潮流，“子类型”可能会让你想起类和继承层次结构。 然而，子类型是一个比这更基本和更一般的概念。

我们说类型 X 是语言中类型 Y 的子类型，如果类型 X 的值可以在任何需要类型 Y 的地方使用。 请注意，这与类或继承无关。 在一个微不足道的意义上，子类型存在于每种语言中，因为根据这个定义，类型始终是其自身的子类型。 然而，语言设计中重要的问题是编译器允许非平凡子类型关系的程度如何。

子类型可能是什么样的？ 首先，让我们考虑一种具有 boxed records 的高级语言，例如 JavaScript 或 Python：

// r: {x: int, y: int}
function foo(r) {
  console.log(r.x + r.y);
}
foo({x: 42, y: 21, z:18});

foo 仅读取其参数的 x 和 y 属性，但你可以传入任何具有这些属性的值，即使它也具有 foo 不查看的其他属性。 JavaScript 实际上没有类型注释，但如果有，它可能看起来像“foo 需要类型为 {x: int, y: int} 的值，而传递的参数的类型为 {x: int, y: int, z: int}”。 在这种情况下，{x: int, y: int, z: int} 是 {x: int, y: int} 的子类型。

是的，即使对于底层语言，你也需要 Subtyping

对像这样的示例的常见反应是“嗯，这对于所有值都被 boxed 的高级语言来说可能还可以，但是如果你关心性能，你需要使用固定的类型相关的内存表示来编译事物，因此你不能在不同宽度的 records 之间存在子类型关系。 因此，对于大多数语言来说，不需要子类型。”

然而，这种反应是错误的。 虽然前一节中的具体示例是你在未优化的语言中才会看到的东西，但即使是优化的语言仍然需要子类型。 它们将具有更少的子类型关系，但不是零子类型。

内存布局优化意味着你不能在具有不同内存布局的类型之间存在任何子类型关系。 如果你的类型系统足够稀疏，以至于每个内存布局只有一个类型，那么你确实不会有任何非平凡的子类型关系。 然而，如此稀疏的类型系统并不是很有用。

随着计算机变得越来越快，利用它们来帮助程序员通过在编译时自动捕获错误来更快地开发软件的趋势越来越强。 这意味着类型系统自然会发展为捕获越来越多值得检查的代码属性，包括与内存布局没有 1:1 映射的属性。 反过来，这意味着你有子类型！

Null 检查

考虑一下空值检查的问题，Tony Hoare 臭名昭著的 Billion Dollar Mistake。 空指针错误是编程中如此常见的问题，以至于大多数现代语言都以某种方式在类型系统中检查可空性，以静态地防止错误。

例如，在 Kotlin 中，String? 是可空字符串的类型，它可以是正常的 String 值或 null。 同时，String 是不可空字符串的类型，它在静态上保证不是 null：

val not_null: String = "Hello";
val maybe_null: String? = "World";
fun takes_nonnull(x: String) {}
fun takes_nullable(x: String?) {}
// 可以将 String 传递给 String
takes_nonnull(not_null);
// 可以将 String? 传递给 String?
takes_nullable(maybe_null);
// *也可以*将 String 传递给 String?
takes_nullable(not_null);

这个系统可用性的关键在于，即使在需要可空值的地方，你也可以自由地传递不可空值。 如果一个函数接受一个可以是 String 或 null 的值，那么传递给它一个保证是 String 而不是 null 的值是可以的。 换句话说，String 是 String? 的子类型！

String 和 String? 是两种不同的类型，它们具有相同的内存布局，因此即使使用特定于类型的内存布局，我们仍然具有非平凡的子类型关系。 为了静态地检查诸如不影响内存布局的可空性之类的属性，编译器需要支持子类型。

别名检查

在空值检查的情况下，你的类型格相当简单 - 你只有 String 和 String?。 每个类型要么是可空的，要么是不可空的。 然而，这仅仅是类型检查器现在和将来将被要求执行的分析类型的冰山一角。

例如，静态类型检查的下一个伟大前沿是别名分析。 别名相关的问题是错误的常见来源，为了静态地防止它们，你需要一个 borrow checker。 这将每个指针与权限相关联，每个权限在特定的生命周期内有效。

每个指针都具有相同的运行时表示（它们都只是内存中的指针）。 然而，静态类型是完全不同的。 指针的权限仅在编译时存在，并且对代码的运行时行为没有影响，但它们对于在编译期间捕获别名错误仍然至关重要。

与空值检查一样，“额外”信息自然会产生子类型关系。 如果你有一个具有更多权限的指针，它仍然应该可以在只需要具有较少权限的指针的地方使用。 如果你有一个从两个可能的值派生的条件值（例如 if foo {p} else {q}），那么新指针应该具有两个可能的源指针共享的权限。 等等。

与空值检查不同，在空值检查中，你只有与每个类型关联的一位“额外”信息（值可以为空吗？），而使用 borrow checker，你可以将无限量可能的信息与每个类型相关联。 这意味着拥有一种从一开始就设计成可以很好地使用子类型的类型系统和编译器比以往任何时候都更加重要。

结论

正如空值检查示例所示，几乎每种语言都具有某种子类型。 然而，类型系统和编译器通常在设计时没有考虑到子类型，导致许多可预防的粗糙边缘。 类型系统越复杂，在设计中不认真对待子类型的代价就越大。 为了设计未来的编程语言，受 Algebraic Subtyping 启发的设计将变得更加重要。

请参见 此处 以获取有关如何使用类型推断实现子类型的基本教程。