协变与逆变

協變與逆變(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 中。通過函式類型的子類別規則，這個運算逆轉了第一參數上的≦順序而在第二參數上保持該順序，即它是一個在第一參數上逆變、而在第二參數上協變的函子。