Programming Language Generics

泛型的协变与逆变

深入理解协变与逆变

Posted by John Mactavish on July 26, 2020

Definition

首先是泛型的定义，懒得复读没意义的内容了，直接上 Google 到的 第一项：

A generic type is a type with formal type parameters. A parameterized type is an instantiation of a generic type with actual type arguments. A generic type is a reference type that has one or more type parameters. These type parameters are later replaced by type arguments when the generic type is instantiated (or declared ).

Example (of a generic type): 

interface Collection<E>  { 
  public void add (E x); 
  public Iterator<E> iterator();
}

The interface Collection has one type parameter E.
The type parameter E is a place holder that will later be replaced by a type argument when the generic type is instantiated and used. The instantiation of a generic type with actual type arguments is called a parameterized type.

Example (of a parameterized type): 

Collection<String> coll = new LinkedList<String>();

The declaration Collection<String> denotes a parameterized type, which is an instantiation of the generic type Collection, where the place holder E has been replaced by the concrete type String.

一句话概括就是 A parameterized type (such as Collection<String>) is an instantiation of the generic type (such as Collection<E>). 至于泛型(Generics)嘛，就是 refers to the technique of writing the code for a class without specifying the data type(s) that the class works on.

Covariance and Contravariance

对于一个 generic type，比如 List[T]，如果对 A 及其子类型 B，满足 List[B] 也是 List[A] 的子类型， 那么就称这一现象为 covariance(协变)；如果 List[A] 是 List[B] 的子类型，即与原来的父子关系刚好相反， 则称为 contravariance(逆变)。如果一个类型 T 支持协变或逆变，则称这个类型为 variance(可型变)， 否则称为 invariant(不可型变的)。

那么协变与逆变有什么讲究吗？看下面这个摘自深入理解 TypeScript的例子：

先约定如下的标记：

  • A ≼ B 意味着 A 是 B 的子类型。
  • A → B 指的是以 A 为参数类型，以 B 为返回值类型的函数类型。
  • x : A 意味着 x 的类型为 A。

假设我有如下三种类型：

Greyhound ≼ Dog ≼ Animal

Greyhound （灰狗）是 Dog （狗）的子类，而 Dog 则是 Animal （动物）的子类。 由于子类型通常是可传递的，因此我们也称 Greyhound 是 Animal 的子类。

问题：以下哪种类型是 Dog → Dog 的子类呢？

  • Greyhound → Greyhound
  • Greyhound → Animal
  • Animal → Animal
  • Animal → Greyhound

让我们来思考一下如何解答这个问题。首先我们假设 f 是一个以 Dog → Dog 为参数的函数。 它的返回值并不重要，为了具体描述问题，我们假设函数结构体是这样的： f : (Dog → Dog) → String。

现在我想给函数 f 传入某个函数 g 来调用。我们来瞧瞧当 g 为以上四种类型时，会发生什么情况。

  1. 我们假设 g : Greyhound → Greyhound， f(g) 的类型是否安全？ 不安全，因为在 f 函数体内调用它的参数(g 函数)时，提供给 g 的可能是一个不同于灰狗但又是狗的子类，例如 GermanShepherd （牧羊犬）；
  2. 我们假设 g : Greyhound → Animal， f(g) 的类型是否安全？ 不安全。理由同(1)；
  3. 我们假设 g : Animal → Animal， f(g) 的类型是否安全？ 不安全。因为 f 有可能在调用完 g 之后，让 g 的返回值，也就是 Animal （动物）狗叫，但是并非所有动物都会狗叫；
  4. 我们假设 g : Animal → Greyhound， f(g) 的类型是否安全？ 是的，它的类型是安全的。首先，f 可能会以任何狗的品种来作为参数调用，而所有的狗都是动物。其次，它可能会假设结果是一条狗，而所有的灰狗都是狗。

如上所述，我们得出结论：

(Animal → Greyhound) ≼ (Dog → Dog)

返回值类型很容易理解：灰狗是狗的子类。但参数类型则是相反的：动物是狗的父类！

用合适的术语来描述这个奇怪的表现，可以说我们要求一个函数类型满足，返回值类型是协变的， 而参数类型是逆变的。返回值类型是协变的，意思是 A ≼ B 就意味着 (T → A) ≼ (T → B) ； 参数类型是逆变的，意思是 A ≼ B 就意味着 (B → T) ≼ (A → T) （ A 和 B 的位置颠倒过来了）。

你也许会好奇，上面节选的部分讨论的是函数类型，那对于我们一开始讨论的 List[T] 又如何呢。 换句话说，List[Dog] 能否为 List[Animal] 的子类？这个问题比函数类型的稍微复杂一点。

前面我们设想情景用的是这样的：

f : (Dog → Dog) → String

现在我们则是要考虑

f : List[Dog] → String

对于不支持高阶函数的面向对象语言，f 的参数不是一个函数，不可以调用， 但是它是一个对象，拥有可以调用的方法，我们因此转而考虑 List[Dog] 的方法的类型签名。 假如 List[T] 拥有方法 g : T → T，记作 List[T]{g : T → T}， 那么对于具体类型(parameterized type) Dog 则有

f : List[Dog]{g : Dog → Dog} → String

问题转化为了上面的函数类型问题，讨论结果与 f : (Dog → Dog) → String 一致。 即 List[Animal]{g : Animal → Animal} 和 List[Greyhound]{g : Greyhound → Greyhound}， 都不可以作为 f 的参数，T 应为不可型变的。

但是考虑另一个情景：

f : List[Dog]{g : () → Dog} → String

即假如 List[T] 拥有方法 g : () → T， 显然此时 List[Greyhound]{g : () → Greyhound} 可以代替 List[Dog]{g : () → Dog} 作为 f 的输入参数， f 调用参数的 g 方法，把实际返回值 Greyhound 当作 Dog 来对待是没有问题的。事实上， 不变的列表（immutable List[T]）确实有这样的方法 g，它就是 get(获取List[T]中的元素)。 此时，List[T] 中的 T 可以支持协变。同理可得，List[Animal]{h : Animal → Unit} 可以代替 List[Dog]{h : Dog → Unit}。但是如果 List[T] 同时有方法 g 和 h 就会出大问题。因为我们无法确定 函数 f 会怎样使用输入参数的 g 和 h 方法。可变列表就是这样一个例子， 假设有

generic type MutableList[T]{get : E → T, add : T → R}

(E,R 为其他类型，按理说应该写作 MutableList[T,E,R]，这里省略了)

和情景

f : MutableList[Dog]{get : Int → Dog, add : Dog → Bool} → String

那么当输入参数为 MutableList[Animal]{get : Int → Animal, add : Animal → Bool} 时，f 使用 参数的方法 get 的返回值会出错(f 按照自己的类型签名期待一个 Dog 的返回值，实际 get 只保证返回 Animal)； 当输入参数为 MutableList[Greyhound]{get : Int → Greyhound, add : Greyhound → Bool} 时，f 调用 参数的方法 add 时会出错(add 使用 Greyhound 类型的参数，但 f 按照自己的类型签名只保证传给 add 的是 Dog)。

不难发现，上面的这个例子之所以出问题是因为 MutableList[T] 的 get 和 add 方法同时使用一个类型参数 T， 从而可以在群内定义新方法

add_and_get = add compose get :: T → T (假设 R==E 或者丢弃 R 再随便传入一个 E)

这就回到了一开始讨论的 List[T]{g : T → T} 中 T 不可型变的问题上去了。我们可能会灵机一动，那提供两个类型 参数又怎么样呢?定义

Fun[T1,T2]{g : E → T1, h : T2 → R}

那么试一试就会发现这里 T1 是协变的， 同时 T2 是逆变的。

顺带一提，我们在这里借助泛型的函数类型(generic function type)来讨论泛型类(generic class)， 而在一些融合了 OOP 与 FP 的语言(如 Scala)中函数(function)与类(class)之间确实有着微妙的关系。 Scala 中的函数类型表示为 (T1,T2…) => R，小括号里的是入参类型(最多可以有22个，最少为0)， 右箭头右边的是返回结果类型；它背后其实等价于 trait FunctionN[T1,T2…, R] (N 对应 0~22)； 入参类型 T1,T2… 都是逆变的，而结果类型 R 是协变的。而 trait FunctionN 其实定义了一个方法 apply：

trait Function2[-T1,-T2,+R] {
  def apply (v1: T1, v2: T2) : R
}

那么一个满足该 trait 的对象其实就是一个函数，函数调用就是对象的 apply 方法调用， 函数的类型就是 trait 中 apply 方法的类型。OOP 与 FP 的语法设计就在这里交汇。

Real World Cases

最后介绍一下几个实际语言中的实现吧。

我们上面的这个就是 Scala 中的实现了，再拿下来看看。

trait Function2[-T1,-T2,+R] {
  def apply (v1: T1, v2: T2) : R
}

类型参数的型变特性在 generic type 定义时给出了，类型参数前的负号(-T1)表示它(T1)逆变， 正号(+R)则表示协变。

再来看看 C# 与 Kotlin 中的实现(以 Kotlin 为例,例子来自 官方文档)：

interface Source<out T> {
    fun nextT(): T
}

fun demo(strs: Source<String>) {
    val objects: Source<Any> = strs // This is OK, since T is an out-parameter
    // ...
}

interface Comparable<in T> {
    operator fun compareTo(other: T): Int
}

fun demo(x: Comparable<Number>) {
    x.compareTo(1.0) // 1.0 has type Double, which is a subtype of Number
    // Thus, we can assign x to a variable of type Comparable<Double>
    val y: Comparable<Double> = x // OK!
}

协变用 out 表示，逆变用 in 表示；初看有点特别，细想也很合理：协变和逆变两词没能表现它们之间的不同， 但是 out 和 in 却很直白,方便编程。

out: 输出(作为结果) in: 输入(作为参数)

所以如果有一个泛型参数标记为 out,则代表它是用来输出的，只能作为结果返回， 而如果有一个泛型参数标记为 in,则代表它是用来输入的，也就是它只能作为参数。

Java 的设计就差多了。首先数组与泛型容器在语法上是不统一的两部分；其次 Java 并不支持声明点型变(declaration-site variance，即在定义一个类型时声明它是 variance， 也称 definition-site)，但是它支持使用点型变(use-site variance)，即：

List<? extends Object> list = new ArrayList<String>();

static void getUperNumber(List<? extends Number> data) {
    System.out.println("data :" + data.get(0));
}

最后，数组既是可变的(mutable)，又是协变的。记得前面的 MutableList[T] 的例子吗，这当然不安全。 不过，数组记得它内部元素的具体类型，并且会在运行时(Runtime)做类型检查。所以不安全的代码 虽然能通过编译(静态类型检查)， 但运行时会报错，确切的说是插入不兼容元素时报错，因为它不支持逆变。既然一开始就插不进去， 也就用不着考虑取出时的情况了，插入时报错也算满足 LET IT CRASH 原则，还是有点安全保证的。

Number[] num = new Integer[20]; 
num[0] = 5.6;     //Error

另外讲一个有趣的事，Java 中不支持泛型数组。这是因为泛型是用擦除（Erasure）实现的， 运行时类型参数会被擦掉。无论你声明的的是 List<String>，还是 List<Integer> 或者原生类 List， 容器实际类型都是 List<Object>,这样一来数组就无法记得它内部元素的具体类型，这就会导致

public static void main(String[] args) {
    Box<Dog>[] dogBoxes = new Box<Dog>[3]; // 装着狗的箱子
    Object[] boxes = dogBoxes; // 数组协变，这样声明是可以的
    boxes[0] = new Box<Cat>(); // 运行时数组看来都是 Box<Object>, 禁止逆变的检查在此失效
    Dog dog = boxes[0].get(); // 报错被延迟到取出元素时，不合理的设计
}

因此，Java 干脆不支持泛型数组，上面的代码便被编译器禁止了。

最后附上GitHub：https://github.com/gonearewe

CATALOG
    FEATURED TAGS
    SSH Windows Subsystem Linux (wsl) IPv6 校园网 树莓派 VS Code Go 匿名函数 转载 golang gradle CSS Java git beego jQuery 算法 数据结构 设计模式 并发 随感 Programming Language 常用算法与数据结构模板系列 二叉树 马克思 论文 读书笔记 软件设计 Scala Redis Java 并发原理系列 分布式 JavaFX Spring Boot 一个视频播放器的设计与实现系列 缓存系统学习系列 性能测试
    FRIENDS