协变与逆变

协变与逆变(Covariance and contravariance )是在计算机科学中，描述具有父/子型别关系的多个型别通过型别构造器、构造出的多个复杂型别之间是否有父/子型别关系的用语。

Java与C#中的协变量组

早期版本的Java与C#不包含泛型（generics，即参数化多态）。在这样的设置下，使数组为“不变”将导致许多有用的多态程序被排除。 
例如，考虑一个用于重排（shuffle）数组的函数，或者测试两个数组相等的函数，使用Object与equals方法. 函数的实现并不依赖于数组元素的确切类型，因此可以写一个单独的实现而适用于所有的数组：
    boolean equalArrays (Object[] a1, Object[] a2);
    void shuffleArray(Object[] a);
然而，如果数组类型被处理为“不变”，那么它仅能用于确切为Object[]类型的数组。对于字符串数组等就不能做重排操作了。 
所以，Java与C#把数组类型处理为协变。在C#中，string[]是object[]的子类型，在Java中，String[]是Object[]的子类型。
如前文所述，协变数组在写入数组的操作时会出问题。Java与C#为此把每个数组对象在创建时附标一个类型。 每当向数组存入一个值，编译器插入一段代码来检查该值的运行时类型是否等于数组的运行时类型。如果不匹配，会抛出一个ArrayStoreException（在C#中是ArrayTypeMismatchException）：
    // a 是单元素的String 数组
    String[] a = new String[1];

    // b 是 Object 的数组
    Object[] b = a;

    // 向 b 中赋一个整数。如果 b 确实是Object 的数组，这是可能的；然而它其实是个String 的数组，因此会发生java.lang.ArrayStoreException
    b[0] = 1;
在上例中，可以从b中安全地读。仅在写入数组时可能会遇到麻烦。 
这个方法的缺点是留下了运行时错误的可能，而一个更严格的类型系统本可以在编译时识别出该错误。这个方法还有损性能，因为在运行时要运行额外的类型检查。 

Java与C#有了泛型后，有了类型安全的编写这种多态函数。数组比较与重排可以给定参数类型
    <T> boolean equalArrays (T[] a1, T[] a2);
    <T> void shuffleArray(T[] a);
也可以强制C#方法只读方式访问一个集合，可以用界面IEnumerable<object>代替作为数组object[]。

函数类型

支持一等函数的语言具有函数类型，比如“一个函数期望输入一只Cat 并返回一只Animal（写为OCaml 的 Cat -> Animal 或 C# 的Func<Cat,Animal>）。
这些语言需要指明什么时候一个函数类型是另一个函数类型的子类型—也就是说，在一个期望某个函数类型的上下文中，什么时候可以安全地使用另一个函数类型。 
可以说，函数f可以安全替换函数g，如果与函数g相比，函数f接受更一般的参数类型，返回更特化的结果类型。 
例如，函数类型Cat->Cat可安全用于期望Cat->Animal的地方；类似地，函数类型Animal->Animal可用于期望Cat->Animal的地方——典型地，在 Animal a=Fn(Cat(...)) 这种语境下进行调用，由于 Cat 是 Animal 的子类所以即使Fn 接受一只Animal 也同样是安全的。一般规则是：
S₁ → S₂ ≦ T₁ → T₂  当T₁ ≦ S₁且S₂ ≦ T₂.
换句话说，类型构造符→对输入类型是逆变的而对输出类型是协变的。这一规则首先被Luca Cardelli正式提出。
在处理高端函数时，这一规则可以应用多次。例如，可以应用这一规则两次，得到(A'→B)→B ≦ (A→B)→B 当 A'≦A。即，类型(A→B)→B在A位置是协变的。在跟踪判断为何某一类型特化不是类型安全的可能令人困扰，但是比较容易计算哪个位置是协变或逆变：一个位置是协变当且仅当在偶数个箭头的左边。
例如，在Visual Basic中，允许把lambda表达式（匿名函数）赋值给委托（delegate）类型的实例，如果参数是widen，返回值是narrowen：
' 定义委托Del1Delegate Function Del1(ByVal arg As Integer) As Integer' 合法的lambda 表达式赋值，不论 Option Strict 是开是关：' 整数匹配于整数Dim d1 As Del1 = Function(m As Integer) As Integer' 整数扩展到长整数Dim d2 As Del1 = Function(m As Long) As Integer' 整数扩展到双精度浮点Dim d3 As Del1 = Function(m As Double) As Integer' 合法的返回值赋值（Option Strict 打开）：' 整数匹配于整数Dim d6 As Del1 = Function(m As Integer) As Integer' 短整数扩展到整数Dim d7 As Del1 = Function(m As Long) As Short' 字节扩展到整数Dim d8 As Del1 = Function(m As Double) As Byte

面向对象语言中的继承

当一个子类重写一个超类的方法时，编译器必须检查重写方法是否具有正确的类型。虽然一些语言要求类型必须与超类相同，但允许重写方法有一个“更好的”类型也是类型安全的。对于大部分的方法子类化规则来说，这要求返回值的类型必须更具体，也就是协变，而且接受更宽泛的参数类型，也就是逆变。
对于一下示例,假设Cat 是 Animal 的子类,而且我们以及拥有了这两个类(使用Java语法)
class AnimalShelter {
    Animal getAnimalForAdoption() {
      ...
    }

    void putAnimal(Animal animal) {
      ...
    }}
问题是:如果我们子类化AnimalShelter, 我们可以让getAnimalForAdoption 和 putAnimal具有什么类型？

返回值的协变

在允许协变返回值的语言中, 子类可以重写getAnimalForAdoption 方法来返回一个更窄的类型：
class CatShelter extends AnimalShelter {
    Cat getAnimalForAdoption() {
        return new Cat();
    }}
主流的面向对象语言中, Java和C++允许返回值协变，C#不支持。添加返回值协变是1998年C++标准委员会最先允许的对C++语言核心的修改之一。 Scala和D语言也支持返回值协变。

方法参数的逆变

类似地，子类重写的方法接受更宽的类型也是类型安全（type safe）的：
class CatShelter extends AnimalShelter {
    void putAnimal(Object animal) {
       ...
    }}
允许参数逆变的面向对象语言并不多——C++和Java会把它当成一个函数重载。
然而，Sather既支持协变，也支持逆变。对于重写的方法，出参数和返回值是协变的，而常规的参数是逆变的。

协变的方法参数类型

在主流的语言中，Eiffel 允许一个重写的方法参数比起父类中的那一个有更加具体的类型，即参数类型协变。因此，Eiffel 版本的putAnimal 会如下所示：
    class CatShelter extends AnimalShelter {
        void putAnimal(Cat animal) {
           ...
        }
    }
这并不是类型安全的。通过把CatShelter 转换为AnimalShelter，程序员可以把“狗”放进猫庇护所里。这种类型安全性的缺失（在 Eiffel 社区里称为“猫调用问题”）由来已久。许多年以来，人们组合使用各种全局/ 局部静态分析以及新的语言特性来进行补救，有些已被写进了一些Eiffel 编译器。
抛开类型安全问题不谈，Eiffel 的设计者认为在对现实世界建模这一点上，协变的参数类型是不可或缺的。猫庇护所问题演示了一种常见现象：它是一种动物庇护所，但有着额外的限制；而用继承和受限参数类型又似无不可。通过提出继承的这种应用方式，Eiffel 设计者们拒绝了Liskov 代换原则（即子类对象受的限制一定比它们父类对象少）。
另一个参数类型协变可能有益的例子是所谓二元方法，即其参数与方法所在对象的类型相同。例如 compareTo 方法：a.compareTo(b) 检查 a 和 b 在某种排序下的先后关系，但比较不同类型对象——比如，比较两个有理数以及比较两个字符串——的方式可以大相径庭。其它的常见二元方法例子还有相等性比较、算术运算、以及诸如求交集 / 并集的集合运算。
在旧一点的Java 版本中，比较方法是以接口Comparable 的方式指定的：
interface Comparable {
    int compareTo(Object o);}
这种方式的缺点是方法参数类型指定为Object。一个典型的实现可能是先把这个参数向下强制转换——如果不是期望的类型，那么报错：
class RationalNumber implements Comparable {
    int numerator;
    int denominator;

    ...
    
    public int compareTo(Object other) {
        RationalNumber otherNum = (RationalNumber)other;
        return Integer.compare(numerator*otherNum.denominator,
                               otherNum.numerator*denominator);
    }}
在有参数协变的语言中，compareTo 的参数可以直接定为希望的类型（RationalNumber），从而把类型转换消除掉。（当然，该报运行时错误的时候还是会报错的，比如对一个String 调用 compareTo）。

去除对参数类型协变的依赖

其它语言特性可能用来弥补缺乏参数类型协变的缺乏。
在有泛型（即参数化多态及受限量词）的语言中，前面的例子可用更类型安全的方式重写
：不定义AnimalShelter，改为定义一个参数化的类Shelter<T>。（这种方法的缺点之一是基类实现者需要预料到哪些类型要在子类中特化）
class Shelter<T extends Animal> {
    T getAnimalForAdoption() {
        ...
    }

    void putAnimal(T animal) {
        ...
    }}class CatShelter extends Shelter<Cat> {
    Cat getAnimalForAdoption() {
        ...
    }

    void putAnimal(Cat animal) {
        ...
    }}
相似地，在新版本的Java 中 Comparable 接口也被参数化了，从而允许以一种类型安全的方式省去向下类型转换：
class RationalNumber implements Comparable<RationalNumber> {
    int numerator;
    int denominator;
  
    ...
     
    public int compareTo(RationalNumber otherNum) {
        return Integer.compare(numerator*otherNum.denominator, 
                               otherNum.numerator*denominator);
    }}
另一个有助的语言特性是多分派。二元方法难写的一个原因就是在类似于a.compareTo(b) 的调用中，对 compareTo 的正确选择其实依赖于a 和 b 两者的类型，但在经典的面向对象语言中只有a 的类型被纳入考虑。在有CLOS 样式多分派特性的语言中，比较方法可以写成一个泛型方法，其两个参数类型都在方法选择中被考虑。
Giuseppe Castagna 观察到在一个有类型而且有多分派的语言中，泛型函数的各个参数有些控制分派而余下那些则否。因为方法选择的规则是在可用方法中选择特化程度最高的，如果一个方法重写了另一个方法那么，它（前者）就会在那些控制性的参数上有更特化的类型。而另一方面，为了保证类型安全，语言又得要求剩下的参数越泛化越好。用上面的术语来说，运行时方法选择中使用的类型是协变的，而没用到的类型则是逆变的。常规的单分派语言，例如 Java，也遵循这种规则：只有在其上调用方法的对象（this）类型才用来选择方法，而在子类方法里的this 的类型也确实要比在父类那里更特化。
Castagna 提议在需要参数类型协变的地方——尤其是二元方法——改用多分派，它本性就是协变的。然而不幸的是，大多数编程语言都不支持多分派。

泛型类型

在支持泛型（即参数化多态）的语言中，程序员可以用新的构造器扩展类型系统。例如，C# 的泛型接口IList<T> 可以构造IList<Animal> 和 IList<Cat> 这样的新类型。那么接下来的问题就是这些类型构造器应具有何种变型性质。
有两种主要的处理方式。在有着声明点变型标记法（如 C#）的语言中，程序员在泛型类型处标注其类型参数的预想变型方式；而在使用点变型标记法（如 Java）的语言中，程序员改在泛型类型实例化的位置标注。

声明点变型标记法

具有这种记法的最流行语言包括C#（使用关键字in 和 out）、Scala 以及 OCaml（这两者使用加号减号）。其中，C# 只允许在接口类型上标记变型，而 Scala 和 OCaml 既允许在接口类型上标记、也允许在具体的数据类型上标记变型。

数据

C# 允许在接口的类型参数上标注变型，但不能在类上应用。由于 C# 的成员变量永远是可变的，类型参数可变型的类在C# 中并没有多大用途。不过强调不可变量据的语言就可以利用协变量据类型，例如在Scala 和 OCaml 中不可变列表类型是协变的：List[Cat] 是 List[Animal] 的子类型。
Scala 的变型类型检查规则基本上跟C# 相同。然而，有一些习惯用法会被套用到不可变量据结构上，如下从List[A] 类中摘抄的代码所示：
sealed abstract class List[+A] extends AbstractSeq[A] {
  def head: A
  def tail: List[A]

  /** 向列表头添加元素*/
  def ::[B >: A] (x: B): List[B] =
    new scala.collection.immutable.::(x, this)

  ...}
首先，具有变型类型的类成员必须是不可变的。在这里，head 成员具有类型A，其声明为协变（+），而且 head 成员确实被声明为函数（def）。试图将其声明为可变成员变量（var）将会得到一个类型错误。
其次，即使数据结构是不可变的，它也经常会有返回值类型逆变的函数。例如，考虑向列表头添加元素的函数::。（这个实现创建一个同名类 ::——即非空列表的类——的新对象。）这个函数最显然的类型莫过于
  def :: (x: A): List[A]
然而这是个类型错误，因为协变的参数A（作为函数参数而）出现在了逆变位置。不过也有绕过这个问题的方法：给 :: 一个更泛化的类型，使其能添加具有任何A 的超类型B 的元素。注意这依赖于List 是协变的，因为 this 具有类型List[A]、而我们要把它作为List[B] 对待。乍看之下这个泛化的类型似乎不那么可靠，但如果程序员真拿那个简单的声明出来的话、类型错误会指出需要泛化的地方的。

变型的推断

设计一个让编译器能在所有类型参数上自动推断出尽量好的变型的类型系统是可能的。然而，分析过程可能由于许多原因而变得复杂：其一，分析过程不是局部的，因为一个接口的变型性质取决于其所有使用到的接口；其二，为了得到最优解，类型系统必须允许双向变型——既是协变、同时也是逆变——的类型参数；其三，类型参数的变型性质应当是接口设计者深思熟虑的结果，而不是随机发生的事情。
因此，许多语言都几乎对变型不做干预。C# 和 Scala 完全不推断任何变型注；而 Ocaml 虽然可以推断具体数据类型的变型，程序员还是需要显式指定抽象类型（接口）的变型。
例如，考虑一个OCaml 的数据类型T，其包装了一个函数：
type ('a, 'b) t = T of ('a -> 'b)
编译器会推断出第一参数是逆变、第二参数是协变的。程序员也可以显式提供标注、让编译器检查是否满足，因此下面的声明等价于上面：
type (-'a, +'b) t = T of ('a -> 'b)
当定义接口时，OCaml 中的显式标注就有用了。例如，标准库给关联表的接口Map.S 包括一个标注，指明类型构造器map 的返回类型是协变的：
module type S =
  sig
    type key
    type (+'a) t
    val empty: 'a t
    val mem: key -> 'a t -> bool
    ...
  end
这保证了IntMap.t cat 是 IntMap.t animal 的子类型。

使用点变型标记法（通配符）

声明点标记法的一个缺点是许多接口类型必须是不变的。例如，前面的IList<T> 需要是不变的，因为其中既有协变的函数也有逆变的函数。为了暴露更多的变型性，API 设计者可以提供附加的接口以提供可用方法的子集——例如，一个只提供Insert 函数的“只写列表”。然而这太笨拙了。
使用点标记法试图给某个类的用户以更多的机会去继承，而不要求该类的设计者分开定义具有不同变型性质的若干接口。当某个类或接口被应用于类型声明中时，程序员可以指明用到的只有成员函数的一个子集。就效果而言，类的定义同时也给出了相当于该类的协变和逆变的“部分”的接口。因此，类的设计者不再需要把变型纳入考虑，从而提高了可重用性，
Java 通过通配符提供使用点变型标记，这是一种有界的约束存在量化形式。一个参数化类型可以通过通配符? 加上上下界的形式实例化，例如 List<? extends Animal> 或者 List<? super Animal>。（诸如 List<?> 这样不加约束的通配符等价于List<? extends Object>，因为 Java 的所有类型都派生自Object）。List<X> 这样的类型表明了未知类型X 满足约束这件事。例如，如果变量l 是 List<? extends Animal> 类型，那么类型检查器会接受
Animal a = l.get(3);
因为已知类型X 是 Animal 的子类，相反
l.add(new Animal())
将会导致类型错误，因为一个Animal 并不一定是个X。一般而论，给定某个接口I<T>，一个 I<? extends A> 的记法禁止使用需要T 逆变的函数；反之，如果 l 的类型是List<? super Animal>，我们可以调用l.add 但不能调用l.get。
虽然 Java 中的普通泛型类型是不变的（即在List<Cat> 和 List<Animal> 之间没有子类关系），通配符类型仍可以通过指定一个更严格的界来变得更加特化。例如，List<? extends Cat> 是 List<? extends Animal> 的子类型。这显示了通配符类型是在上界协变（以及在下界逆变）的。总而言之，给定一个诸如C<? extends T> 的通配符类型，有三种方式可以形成子类：特化类C、指定更加严格的约束T、或者把通配符? 替换成一个更特化的类型（见图）。
通过把子类化的两个步骤合并，我们就可以做到诸如给期望List<? extends Animal> 类型参数的函数传递一个List<Cat> 参数这样的事。这正是协变接口类型所允许的程序。List<? extends Animal> 类型就像一个只包含List<T> 的那些协变的函数的接口，然而 List<T> 的实现者并不需要预先作出定义。这就是使用点变型。
在 IList<T> 这种常见的泛型数据结构中，协变参数用于从结构中读出数据，而逆变参数用于写入数据。Joshua Bloch 所著《Effective Java》中提出的助记短语PECS（Producer Extends, Consumer Super）提供了一个合适使用协变/ 逆变的好记方法。
通配符很灵活，但也有个缺点。虽然使用点变型意味着API 设计者不需要考虑接口的类型参数的变型性质，他们却经常需要使用更复杂的函数签名。一个常见例子涉及到Java 中的Comparable 接口。假设我们要写一个查找集合中最大元素的函数，这些元素需要实现compareTo 函数，所以首先我们可能会做如下尝试：
<T extends Comparable<T>>  T max(Collection<T> coll);
然而这并不够泛型——我们会发现能够找到一个Collection<Calendar> 集合中的最大值，但对Collection<GregorianCalendar> 而言则否。问题在于GregorianCalendar 并不实现Comparable<GregorianCalendar> 接口，而是实现了（更好的）Comparable<Calendar>。不像C#，在 Java 中 Comparable<Calendar> 并不被认为是Comparable<GregorianCalendar> 的子类。因此 max 的类型要改成这样：
<T extends Comparable<? super T>>  T max(Collection<T> coll);
有界通配符? super T 用来表明max 只调用Comparable 接口的逆变函数。这个示例令人沮丧的原因是Comparable 接口中的所有函数都是逆变的，因此条件是平凡真、所有用到这个接口的函数都要这样。声明点变型的系统就可以让这个例子不那么啰嗦：只需要在Comparable 接口上标注即可。

比较声明点与使用点变型

使用点变型提供了额外的灵活性，允许更多程序得以通过类型检查。然而，它们因为给语言带来的复杂性、以及所引发的复杂类型签名和错误消息而饱受批评。
一个评判这种额外灵活性是否有用的方法是看它能否应用在现存程序里。一个对大量Java 库的调查发现 39% 的通配符标记本可以用一个声明点标记直接换掉，也即那剩下的61% 是 Java 受益于有这么个使用点变型系统的地方。
在声明点变型语言中，库必须要么更少地暴露变型、要么定义更多的接口。例如，Scala 集合库给每个接口都定义了三个分开的版本：基本版本是不变型的、也不提供任何写操作，有带副作用函数的可写版本，还有不可写但把类型参数（通常）标为协变的版本。这种设计跟声明点标注配合得很好，但大量的接口给库的用户带来了复杂性开销。并且，修改库接口可能不是一个可行选项——具体来说，Java 泛型的一个目标就是要维持二进制向后兼容性。
另一方面，Java 的通配符本身就有够复杂。在一场会议讲演，Joshua Bloch 就批评它们太过难懂难用，声称当添加闭包支持时“再来一个通配符简直就是不能承受之重”。早期版本的Scala 使用使用点标注，然而程序员觉得它们难于实际应用，而声明点标注就在设计类时有大用。后期版本的Scala 添加了Java 样式的存在类型和通配符；然而据Martin Odersky 所说，假如没有跟Java 的互操作性需求的话，这些根本都不会被加进来。
Ross Tate 争辩说 Java 通配符的复杂性有一部分是因为决定了要用存在类型的记法来标记使用点变型。原本的提案是使用专门用途的语法来标记变型，写作 List<+Animal> 而不是Java 这么啰嗦的List<? extends Animal>。
既然通配符是存在类型的一种形式，它们就不仅可以用来做变型这一种事。一个诸如List<?>（某种列表）的类型允许对象不必指定类型参数就能被传递给函数或者放进变量里。这对于像Class 这样的类而言尤其有用，因为其中的大多数函数都根本不管类型参数是什么。
然而，对于存在类型的类型推导是一个难点。对于编译器实现者来说，Java 的通配符提出了类型检查器终结、类型参数推导、以及歧义程序的问题。对程序员来说，它则带来了复杂的类型错误消息。Java 通过把通配符换成新类型变量的方式进行类型检查（所谓捕获检查），这会让错误信息更难读，因为它们现在指向了程序员根本没直接写出的类型变量。例如，试图将一个Cat 加到List<? extends Animal> 会得到类似这样的错误：
 函数 List.add(capture#1) 不能应用（实参Cat 不能被函数调用转换成capture#1）
 其中 capture#1 是新类型变量：
   capture#1 extends Animal，由于捕获了? extends Animal
由于声明点变型和使用点变型都有各自的用处，有些类型系统干脆两者都提供了。

Dart 中的协变泛型

Dart 语言并不跟踪变型，而是把所有参数化类型都当作协变对待。语言规约是这么说的：
由于泛型类型的协变性，类型系统并不稳健。这是故意为之（当然也无疑会引起争论）。经验表明稳健的泛型类型规则在程序员的直觉面前如同废纸。如果想的话，工具仍可简单地提供稳健的类型分析，这可能对诸如重构之类的任务有所帮助。

“协变”一词的来源

这些术语来源于范畴论中函子的记法。考虑范畴C，其中的对象是类型、其态射代表了子类关系≦（这是一个任何偏序集合可被看成范畴的例子）；那么诸如函数的类型构造器接受两个类型p 和 r 并创建一个新类型p→r，即它把C² 中的对象映射到C 中。通过函数类型的子类规则，这个运算逆转了第一参数上的≦顺序而在第二参数上保持该顺序，即它是一个在第一参数上逆变、而在第二参数上协变的函子。