协变和逆变(Type System)

Covariance & Contravariance

Feb 09, 2021

见习魔法师

在现代的大多数OOP语言中,继承关系为面向对象的核心,在这些语言的类型系统中,可能并没有提供自定义隐式转换规则的方法, 但是大多有这么一条隐式转换:如果AB的子类,即A<:B,则类型为A的变量可以被安全赋给类型为B的变量。 如果我们有这么一条Java代码:

Object str = "String";
这个语句是合法的,能通过编译,在这里,StringObject的子类,因此String可以被安全地隐式转换为Object,而不需要显式cast。可见即使是像Java这样的语言,在某种意义上也是有隐式转换的。

而协变,逆变和不变就是基于这个之上的,当然还得支持泛型。在构造泛型(接口)的时候,类型参数可以被标记为协变,逆变或不变。 这里想吐槽一句F#竟然不支持协变,逆变

协变

在OCaml和Scala这样的语言中,协变的类型参数用+标记,在C#中,用out标记。Java则不能在声明处声明泛型

Scala支持在traitclass标记,而C#只能在接口和委托中标记。Java则都不能标记

Scala:

trait F[+T]

C#:

interface F<out T> {}

这样说明,A <: B \to F[A] <: F[B],即如果A是B的子类,则F[A](或F<A>)是F[B](或F<B>)的子类,前者可以安全被转换为后者。

逆变

在Scala,OCaml里,逆变的类型参数用-标记,在C#中,用in标记。Java则还是不行

逆变则相反,A <: B \to F[A] >: F[B],即如果A是B的子类,则F[B](或F<B>)是F[A](或F<A>)的子类,前者可以安全被转换为后者。

不变

不变则是没有任何修饰符的泛型参数,表示以上两者均不适用。

协变和逆变的作用

首先,子类型的意义可以这么理解:但凡父类能做到的,子类也能做到。 $A <: B $ 说明,在任何需要B的环境中,都可以用A替换,在集合上则有 A \subset B

例如,我们想娱乐一下,现在提供了如下三种选择:

  • 问问神奇海螺,让他随便提供一种娱乐项目

  • 听听歌曲

  • 听听刚田武的个人演唱会

  1. 如果你是一个随意的人,无所谓干啥,则啥都能选。

  2. 如果你想要听听歌,那么你就不能问问神奇海螺了,因为他可能建议你去玩只狼双难。

  3. 如果你非刚田武的歌曲不听,那么你只能选第三项,因为第二项还可能给你听虹咲学园偶像同好会的歌曲。

这个娱乐的选择可以形式化为EntertainmentProvider[+Entertainment], 那么这个提供娱乐项目的接口肯定是协变的,因为刚田武演唱会,听音乐和问神奇海螺都是前者继承后者的关系。 任何想要父类的人都可以用任意子类的提供者来提供,即越是子类,能提供的情况就越多。

相应的,人类可以形式化为EntertainmentConsumer[-Entertainment], 人类是娱乐的消费者,这里娱乐是逆变的:任何需要父类的,都可以用子类替换, 越是父类,则选择越多,能接受的越多,可以做的的事情也越多,在这个意义上,父类的Consumer就是子类的Consumer的子类,这个和协变正好相反。所有需要使用子类Consumer的地方,都可以用父类的Consumer。

这个例子可以看出,协变通常用于可以提供物品的接口,而逆变则常用于可以使用物品的接口。

因此,可以如此理解语言中的标记, 在Scala,OCaml中,+-是从行为理解的,即标记了-的类型的子类型关系会颠倒。 而C#则是从用法来理解,协变用于输出,因此用out,逆变用于输入,因此用in

函数十分特殊,其参数是输入,返回值是输出,因此函数参数是逆变的,返回值是协变的。 Scala的函数的原型也可以看出来:

trait Function1[-T1, +R] extends AnyRef {
  def apply(v1: T1): R
}

容器的协变(抄作业引发的惨案)

那么Java有没有协变或逆变呢,当然有!那就是Java的数组,请看下面的著名代码:

Integer[] a = new Integer[] { 1, 1, 4 };
Object[] b = a;
b[1] = "114514";

这种看似愚蠢的行为是可以通过编译的,只是会在运行时报java.lang.ArrayStoreException, C#在一开始照抄Java,也抄错了。这个行为其实是在没有泛型时候的妥协,比如sort这样的函数其实根本不需要在乎数组里面存的什么具体类型,只需要能compare就行了,因此传Object[]简直是绝妙之选。这也是他们现在都用collection库里面的容器而不用array的的原因了。那么我们来看看为什么数组不能协变。

trait IArray[+T] {
  def apply(i: Int): T
  def set(i: Int, value: T): Unit
}

还是有A是B的子类,根据协变,IArray[A]IArray[B]的子类,这样会发生什么事情呢?

IArray[A].getIArray[B].get的子类,因为泛型参数在返回值,也处于协变点,不矛盾;同时想要B的地方也可以提供A,因此apply方法不存在问题。

而问题在于set,这个语句其实相当于arr[i] = value。而value作为参数,处于逆变点,因此,这里T必须是逆变的,与参数矛盾,因此这里的T只能是不变的。这也很好理解,一个只接受Integer的方法肯定不能强行塞入任意的Object,就像上面那个例子一样。

Scala的容器却支持协变,当然,这些容器都是不可变的。可以理解为,他们只能get,那么自然就能安全协变。

但是,有一个比较神奇的例子,就是Scala中的option:

trait Option[+T] {
  @inline final def getOrElse[U >: T](default: => U): U =
    if (isEmpty) default else this.get
}

比较奇怪的是泛型参数,为什么会多一个U,这里是因为default参数作为输入正好处于逆变点上,如果default的类型也是T的话, T处于逆变点上,整个容器应该不变。相反,如果添加了这个泛型,则U >: T说明U的范围就是Any - U, 如果 A \subset B,则Any \setminus B \subset Any \setminus A,可以看见这里的泛型U同时也满足了逆变,也处于逆变点上,因此编译通过。

同时,在只读容器中的新建容器修改后的副本操作基本都满足这样的泛型,那么可变容器能不能也这么设计呢? 如果这个子类可变容器可以安全塞进去父类的实例的话,也可以这么设计,但是实际上大多数都不能,尤其是Java中的基本数组。

在Scala/typescript的类型系统中,有一种bottom type,意味着该类是任何类型的子类,继承了任何类型。 这种类型在Scala中叫做Nothing,在typescript中叫做never。这种类型和Unit/void的区别是,后者代表这样的值存在,但没有意义,前者代表根本没有这样的值。作为函数的返回值代表了这种函数根本不会返回,因此可以被安全赋给任何变量。

这里就可以理解None作为Option的一种情况,究竟是什么的Option呢?自然是NothingOption,因此具体上的表现也是 None可以赋给任何类型的Option,而Option[Any]则是作为参数可以接受任何类型的Option。任何空容器都满足这种性质。 因此对于任何空的不可变容器,都可以指向同一个实例,比如List[+A],其空的实例就是Nil,可以被任意prepend任何类型的值。

如果像C#那样,类的静态类型也必须有泛型参数,而且没有bottom type就会导致所有的空实例的对象不一致, 每个实例化的不可变容器都是不同的对象。

public class C<T> {
  public static IEnumerable<T> Empty = new T[] {};
}

C<string>.Empty == C<object>.Empty // false

而Java就不会出现这种情况因为大家都擦成了Object

为什么定义变量是逆变的

为什么以下Scala代码是合法的呢?

val s: Any = "S"

似乎子类可以赋值给父类是一个oop语言的公理,但是实际上也能这么理解: 这个语句的作用是在上下文中引入一个绑定,直到当前作用域结束,则可以这么重写:

def bind[T, U](value: T, block: T => U): U = block(value)

val s: Any = "S"
println(s)
// <=>
bind[Any, Unit]("S", s => println(s))

那么就能得出结论:泛型T位于逆变点上,因此所有父类的形参都可以接收子类作为实参。

r{{ changeExtraDisplaySettings({blurMainImage: true}) }}