对交类型和子类型的一些思考

December 26, 2022 · 12 min read

网易·杭州研究院·编程语言实验室

今天感觉允许多继承、允许实现多接口的子类型系统其实天然就是部分支持交类型（intersection types）的类型系统，只不过交类型的类型规则与学界不同且不是一等公民（first-class citizen），以及大多数 OO 语言没提供交类型成员的即时（on the fly）构造机制罢了。

交类型、子类型

交类型，莫不是一个 value（expression 或 term）同时有两种类型罢了？

例如：

let x : Int & Bool = ...

func f(_ param : Int) { print("Int received") } // _ 表示没有外部形参名，可忽略
func g(_ param : Bool) { print("Bool received") }

f(x) // 打印 Int received
g(x) // 打印 Bool received

x 同时是 Int 和 Bool 类型，具有两种类型的特质，因此既可以被 f 调用也可以被 g 调用。

虽然上面不是合法的 Swift 代码，但经过一些改动，我们依然能实现相似的效果：

protocol IntLike { } // protocol 类似常见的 interface
protocol BoolLike { }

extension String : IntLike {} // 实现“接口”
extension String : BoolLike {}

let x = "0"

func f(_ param : IntLike) { print("Act like an Int") }
func g(_ param : BoolLike) { print("Act like a Bool") }

f(x) // 打印 Act like an Int
g(x) // 打印 Act like a Bool

x 的类型是 String，但不也是 IntLike & BoolLike 吗？ x 实实在在地具有多个类型的能力，它应当是交类型！

（Java、Kotlin 等也可以模拟，除了它们不能给语言内置的基础类型（如这里的 String）添加父接口。）

再看另一个例子：

protocol IntLike { func actLikeInt() }
protocol BoolLike { func actLikeBool() }

extension String : IntLike {
    func actLikeInt() {
        print("Act like an Int")
    }
}

extension String : BoolLike {
    func actLikeBool() {
        print("Act like a Bool")
    }
}

let x = "0"

func f<T>(_ param : T) where T : IntLike & BoolLike { // 使用 & 记号描述约束的上界是有原因的吧
    param.actLikeInt()
    param.actLikeBool()
}

f(x) // 打印 Act like an Int 和 Act like a Bool

上述代码中，T : IntLike & BoolLike 表示 T 的泛型约束上界是 IntLike & BoolLike，即 T 既要是 IntLike 的子类型又要是 BoolLike 的子类型。它为什么不能称为交类型呢？我今天觉得是了。它应当是交类型！

学术界的交类型

除了上面说的“一个 value（expression 或 term）同时有两种类型”，学术界的交类型（例如 Pierce 在 1990 年代研究的交类型 [1]）通常还具有下面这个特性（类型规则），以区别于上一章的例子。

// 注意：下面的代码只用来示意，并不合法
let ib : A & B

let twoFuncs : (A) -> Int & (B) -> Bool

protocol A {}
protocol B {}

let ib2 = twoFuncs(ib) // ib2 : Int & Bool

函数调用的结果 ib2 的依然是一个交类型。

上面最后一行发生的事情：

twoFuncs 是两个函数类型 (A) -> Int 和 (B) -> Bool 的交类型。
实参 ib 也是个交类型 A & B。
(A) -> Int & (B) -> Bool 和 A & B 做了 2 * 2 = 4 次尝试（即 & 的左右类型俩俩尝试）
只有两组类型符合函数调用的类型检查规则（即实参、形参类型匹配）：(A) -> Int 和 A，以及 (B) - > Bool 和 B。
两组“符合规则”的调用分别产生了 Int 和 Bool 两个结果类型。
两个结果类型再次组成交类型 Int & Bool。

我如何造出同时具有两个函数类型——(A) -> Int & (B) -> Bool——的东西？我可以用函数重载吗？

protocol A {}
protocol B {}

func twoFuncs(_ param : A) -> Int { }  // twoFuncs 会有 A -> Int &
func twoFuncs(_ param : B) -> Bool { } //   B -> Bool 类型吗？

func test<T>(_ param : T) where T : A & B {
  twoFuncs(param) // Error: ambiguous use of 'twoFuncs'
}

编译器会告诉我们上面的第 8 行有错误。

因此，与学术界的交类型的规则不同，重载的函数在调用处会有一个叫重载决议（overload resolution）的算法来择优，而非保留所有结果。

那如果我不做重载决议而是保留所有结果，是不是就成了学术界的那个交类型了？

不做重载决议，问题可就又多了去了……例如

protocol A {}
class B : A {}

let x = B()

func g(_ param : A) -> Int { return 0; }
func g(_ param : B) -> Int { return 1; }

g(x)

这里假设 g : (A) -> Int & (B) -> Int，第 9 行的函数调用结果的类型应该是 Int & Int，值是 0 & 1……？——

Int & Int 应该与 Int 一样吧，否则不就成元组类型 (Int, Int) 了？
那我们是保留 0 作为结果，还是保留 1 作为结果呢？

为了避免上述问题，大部分对交类型的研究都限缩在 disjoint intersection type 上，即只研究“不相交交类型”，或者也许应该叫做“互斥交类型”。

在不相交交类型的系统里，g : (A) -> Int & (B) -> Int 会被拒绝——因为 (A & B) -> Int 是 (A) -> Int 和 (B) -> Int 的一个公共父类型 [2]，因此 (A) -> Int 和 (B) -> Int 并非“不相交”，因此 (A) -> Int & (B) -> Int 本身就是非法类型，也就不用关心它的调用问题了。

工业语言欠缺的

很多人认为工业语言没有交类型这一特性，我想，应该是因为开头说的：它们“缺少了一个交类型成员的即时（on the fly）构造机制”。

Pierce 的论文 [1] 中提供的构造机制为

for α in T0..Tn . e

例如 for α in Int, Real. λ x : α. x + x ，它的类型是 Int -> Int & Real -> Real。

我们“熟悉”的

func f<T>(...) where T : U0 & ... & Un { ... }

可以说是在结构上很相似，但它只能构造出泛型函数类型。（注意，论文中的那个构造，构造出的不是泛型类型，也不一定必须是函数类型。）

Bruno 的论文 [2] 中提供的构造机制为

e0 ,, e1

例如 1 ,, true 即为一个 Int & Bool（交）类型的成员。

C++ 的启发

C++ 有很多为人（学术界）诟病的特性，例如多继承问题（diamond problem，或 Deadly Diamond of Death）。借用维基百科的例子 [3]

class Animal {
  public:
  virtual void eat() { cout << "Animal eat." << endl; };
};

class Mammal : public Animal {
  public:
  virtual void eat() { cout << "Mammal eat." << endl; };
};

class WingedAnimal : public Animal {
  public:
  virtual void eat() { cout << "WingedAnimal eat." << endl; };
};

// A bat is a winged mammal
class Bat : public Mammal, public WingedAnimal { };

Bat bat;
bat.eat();

由于多继承，最后一行（第 20 行）的 bat.eat() 会被编译器抱怨 “error: request for member ‘eat’ is ambiguous”，这是因为 Bat 自己没有重新实现 eat 方法，而其直接继承的 Mammal 和 WingedAnima 却有不同的 eat 方法，因此编译器不知道要调用哪一个父类中的 eat 方法。

针对此类问题，其实 C++ 给出了自己的解决方案（而不是像有些语言一样束手无策）：我们可以使用语法 [4] bat.Mammal::eat() 或 bat.WingedAnimal::eat() 来指定无歧义的（父类）调用，前者输出 Mammal eat. 而后者输出 WingedAnimal eat.。

我猜测，对于多继承，C++ 给出的语法消歧义方案和整套的实现方案——即使有成员数量爆炸问题——应当可以指导我们实现出 fully intersection types（而非上面所提到的 disjoint intersection types）。例如对于

class A { }
class B : A { }

let x : A & B = A() ,, B() // 借用一下构造交类型的符号

func f(_ param : A) -> Int { return 0; }
func g(_ param : B) -> Int { return 1; }

f(x)
g(x)

我们可以把 x 的两份数据都记录下来，在后续调用 f(x) 和 g(x) 中：

函数 f 要求实参是 A 的子类型，
- 那么这里可以像 C++ 一样报错 ambigous argument ...，
- 也可以选择 “x 中的 A 成分”——它最接近形参类型，
- 也可以选择 “x 中的 B 成分”——在所有可用的“成分”中，它在子类型关系上最优，
- 也可以按学术界的思路，两个成分都选择，f 被调用两次，两次调用的结果再次组成交类型……
函数 g 要求实参是 B 的子类型，
- 那么这里必然只能选择 “x 中的 B 成分”。