跳至內容

協變與逆變

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

協變與逆變(Covariance and contravariance)是在電腦科學中,描述具有父/子型別關係的多個型別通過型別構造器、構造出的多個複雜型別之間是否有父/子型別關係的用語。

概述

[編輯]

許多程式設計語言型別系統支援子型別。例如,如果CatAnimal的子型別,那麼Cat型別的表達式可用於任何出現Animal型別表達式的地方。所謂的變型(variance)是指如何根據組成型別之間的子型別關係,來確定更複雜的型別之間(例如Cat列表之於Animal列表,回傳Cat的函數之於回傳Animal的函數...等等)的子型別關係。當我們用型別構造出更複雜的型別,原本型別的子型別性質可能被保持、反轉、或忽略───取決於型別構造器的變型性質。例如在C#中:

  • IEnumerable<Cat>IEnumerable<Animal>的子型別,因為型別構造器IEnumerable<T>是協變的(covariant)。注意到複雜型別IEnumerable的子型別關係和其介面中的參數型別是一致的,亦即,參數型別之間的子型別關係被保持住了。
  • Action<Animal>Action<Cat>的子型別,因為型別構造器Action<T>是逆變的(contravariant)。(在此,Action<T>被用來表示一個參數型別為Tsub-T一級函數)。注意到T的子型別關係在複雜型別Action的封裝下是反轉的,但是當它被視為函數的參數時其子型別關係是被保持的。
  • IList<Cat>IList<Animal>彼此之間沒有子型別關係。因為IList<T>型別構造器是不變的(invariant),所以參數型別之間的子型別關係被忽略了。

程式語言的設計者在制定陣列、繼承、泛型數據類別等的型別規則時,必須將「變型」列入考量。將型別構造器設計成是協變、逆變而非不變的,可以讓更多的程式俱備良好的型別。另一方面,程式員經常覺得逆變是不直觀的;如果為了避免執行時期錯誤而精確追蹤變型,可能導致複雜的型別規則。為了保持型別系統簡單同時允許有用的編程,一個程式語言可能把型別構造器視為不變的,即使它被視為可變也是安全的;或是把型別構造器視為協變的,即使這樣可能會違反型別安全。

形式定義

[編輯]

在一門程式設計語言的型別系統中,一個型別規則或者型別構造器是:

  • 協變(covariant),如果它保持了子型別序關係≦。該序關係是:子型別≦基型別。
  • 逆變(contravariant),如果它逆轉了子型別序關係。
  • 不變(invariant),如果上述兩種均不適用。

下文中將敘述這些概念如何適用於常見的型別構造器。

陣列

[編輯]

首先考慮陣列類型構造器: 從Animal類型,可以得到Animal[](「animal陣列」)。 是否可以把它當作

  • 協變:一個Cat[]也是一個Animal[]
  • 逆變:一個Animal[]也是一個Cat[]
  • 以上二者均不是則為不變

如果要避免類型錯誤,且陣列支援對其元素的讀、寫操作,那麼只有第3個選擇是安全的。Animal[]並不是總能當作Cat[],因為當一個客戶讀取陣列並期望得到一個Cat,但Animal[]中包含的可能是個Dog。所以逆變規則是不安全的。

反之,一個Cat[]也不能被當作一個Animal[]。因為總是可以把一個Dog放到Animal[]中。在協變陣列,這就不能保證是安全的,因為背後的儲存可以實際是Cat[]。因此協變規則也不是安全的—陣列構造器應該是不變。注意,這僅是可寫(mutable)陣列的問題;對於不可寫(只讀)陣列,協變規則是安全的。

這範例了一般現像。只讀數據型別(源)是協變的;只寫數據型別(彙/sink)是逆變的。可讀可寫型別應是「不變」的。

Java與C#中的協變陣列

[編輯]

早期版本的Java與C#不包含泛型(generics,即參數化多態)。在這樣的設置下,使陣列為「不變」將導致許多有用的多態程式被排除。

例如,考慮一個用於重排(shuffle)陣列的函數,或者測試兩個陣列相等的函數,使用Objectequals方法. 函數的實現並不依賴於陣列元素的確切型別,因此可以寫一個單獨的實現而適用於所有的陣列:

    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(寫為 OCamlCat -> AnimalC#Func<Cat,Animal>)。

這些語言需要指明什麼時候一個函數型別是另一個函數型別的子型別—也就是說,在一個期望某個函數型別的上下文中,什麼時候可以安全地使用另一個函數型別。

可以說,函數f可以安全替換函數g,如果與函數g相比,函數f接受更一般的參數類型,返回更特化的結果類型。

例如,函數型別Cat->Cat可安全用於期望Cat->Animal的地方;類似地,函數型別Animal->Animal可用於期望Cat->Animal的地方——典型地,在 Animal a=Fn(Cat(...)) 這種語境下進行呼叫,由於 Cat 是 Animal 的子類所以即使 Fn 接受一隻 Animal 也同樣是安全的。一般規則是:

S1 → S2 ≦ T1 → T2 當T1 ≦ S1且S2 ≦ T2.

換句話說,類型構造符→對輸入類型是逆變的對輸出類型是協變的。這一規則首先被Luca Cardelli正式提出。[1]

在處理高階函數時,這一規則可以應用多次。例如,可以應用這一規則兩次,得到(A'→B)→B ≦ (A→B)→B 當 A'≦A。即,型別(A→B)→B在A位置是協變的。在跟蹤判斷為何某一型別特化不是型別安全的可能令人困擾,但是比較容易計算哪個位置是協變或逆變:一個位置是協變若且唯若在偶數個箭頭的左邊。

例如,在Visual Basic中,允許把lambda表達式(匿名函數)賦值給委託(delegate)類型的實例,如果參數是widen,返回值是narrowen:

' 定义委托 Del1
Delegate 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

物件導向語言中的繼承

[編輯]

當一個子類重寫一個超類的方法時,編譯器必須檢查重寫方法是否具有正確的類型。雖然一些語言要求類型必須與超類相同,但允許重寫方法有一個「更好的」類型也是類型安全的。對於大部分的方法子類化規則來說,這要求返回值的類型必須更具體,也就是協變,而且接受更寬泛的參數類型,也就是逆變。

對於以下範例,假設 CatAnimal 的子類,而且我們以及擁有了這兩個類(使用Java語法)

class AnimalShelter {
    Animal getAnimalForAdoption() {
      ...
    }

    void putAnimal(Animal animal) {
      ...
    }
}

問題是:如果我們子類化 AnimalShelter,我們可以讓 getAnimalForAdoptionputAnimal 具有什麼類型?

返回值的協變

[編輯]

在允許協變返回值的語言中, 子類可以重寫 getAnimalForAdoption 方法來返回一個更窄的類型:

class CatShelter extends AnimalShelter {
    Cat getAnimalForAdoption() {
        return new Cat();
    }
}

主流的物件導向語言中,JavaC++允許返回值協變,C#不支援。添加返回值協變是1998年C++標準委員會最先允許的對C++語言核心的修改之一。[2] ScalaD語言也支援返回值協變。

方法參數的逆變

[編輯]

類似地,子類重寫的方法接受更寬的類型也是類型安全(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 社區里稱為「貓呼叫問題」)由來已久。許多年以來,人們組合使用各種全域 / 局部靜態分析以及新的語言特性來進行補救[3] [4],有些已被寫進了一些 Eiffel 編譯器。

拋開類型安全問題不談,Eiffel 的設計者認為在對現實世界建模這一點上,協變的參數類型是不可或缺的[4]。貓庇護所問題演示了一種常見現象:它是一種動物庇護所,但有着額外的限制;而用繼承和受限參數類型又似無不可。通過提出繼承的這種應用方式,Eiffel 設計者們拒絕了 Liskov 代換原則(即子類對象受的限制一定比它們父類別對象少)。

另一個參數類型協變可能有益的例子是所謂二元方法,即其參數與方法所在對象的類型相同。例如 compareTo 方法:a.compareTo(b) 檢查 ab 在某種排序下的先後關係,但比較不同類型對象——比如,比較兩個有理數以及比較兩個字串——的方式可以大相逕庭。其它的常見二元方法例子還有相等性比較、算術運算、以及諸如求交集 / 併集的集合運算。

在舊一點的 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)。

去除對參數類型協變的依賴

[編輯]

其它語言特性可能用來彌補缺乏參數類型協變的缺乏。

在有泛型(即參數化多型受限量詞英語bounded quantification)的語言中,前面的例子可用更類型安全的方式重寫[5] :不定義 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 的正確選擇其實依賴於 ab 兩者的類型,但在經典的物件導向語言中只有 a 的類型被納入考慮。在有CLOS 樣式多分派特性的語言中,比較方法可以寫成一個泛型方法,其兩個參數類型都在方法選擇中被考慮。

Giuseppe Castagna[6] 觀察到在一個有類型而且有多分派的語言中,泛型函數的各個參數有些控制分派而餘下那些則否。因為方法選擇的規則是在可用方法中選擇特化程度最高的,如果一個方法重寫了另一個方法那麼,它(前者)就會在那些控制性的參數上有更特化的類型。而另一方面,為了保證類型安全,語言又得要求剩下的參數越泛化越好。用上面的術語來說,執行時方法選擇中使用的類型是協變的,而沒用到的類型則是逆變的。常規的單分派語言,例如 Java,也遵循這種規則:只有在其上呼叫方法的對象(this)類型才用來選擇方法,而在子類別方法里的 this 的類型也確實要比在父類別那裏更特化。

Castagna 提議在需要參數類型協變的地方——尤其是二元方法——改用多分派,它本性就是協變的。然而不幸的是,大多數程式語言都不支援多分派。

變型和繼承的總結

[編輯]

下表總結了在上面討論的語言有關覆寫方法的規則。

參數類型 返回類型
C++ (自1998年), Java (自J2SE 5.0), Scala, D 不變 協變
C# 不變 不變
Sather 逆變 協變
Eiffel 協變 協變

泛型類型

[編輯]

在支援泛型(即參數化多型)的語言中,程式設計師可以用新的構造器擴充型別系統。例如,C# 的泛型介面 IList<T> 可以構造 IList<Animal>IList<Cat> 這樣的新類型。那麼接下來的問題就是這些類型構造器應具有何種變型性質。

有兩種主要的處理方式。在有着聲明點變型標記法(如 C#)的語言中,程式設計師在泛型類型處標註其類型參數的預想變型方式;而在使用點變型標記法(如 Java)的語言中,程式設計師改在泛型類型實例化的位置標註。

聲明點變型標記法

[編輯]

具有這種記法的最流行語言套件括 C#(使用關鍵字 inout)、Scala 以及 OCaml(這兩者使用加號減號)。其中,C# 只允許在介面類型上標記變型,而 Scala 和 OCaml 既允許在介面類型上標記、也允許在具體的資料類型上標記變型。

介面

[編輯]

在 C# 中,每個泛型介面的類型參數都可被標註為協變(out)、逆變(in)或不變(不標註)。例如,可以定義一個介面 IEnumerator<T> 作為唯讀的迭代器,並聲明它在其類型參數上具有協變性:

interface IEnumerator<out T>{
    T Current{
        get;
    }
    bool MoveNext();
}

通過這樣聲明,IEnumerator<T> 就會在其類型參數上具有協變性。例如,IEnumerator<Cat>IEnumerator<Animal> 的子類型。

型別檢查器保證介面里每個函數聲明都通過符合 in/out 規則的方式使用其類型參數。也就是說,被聲明為協變的參數不得出現在任何逆變的位置(一個位置稱為逆變的,如果它經過了逆變類型構造器的奇數的應用)。精確的規則[7][8]是介面里所有函數的返回值類型都必須協變合法,而所有函數參數的類型都必須逆變合法。具體來說,協 / 逆變合法定義如下:

  • 非泛型類型(類、結構、列舉等)既協變合法、也逆變合法。
  • 類型參數 T 如果沒有標 in,那麼是協變合法;如果沒有標 out,那麼是逆變合法。
  • 陣列類型 A[] 是協 / 逆變合法,如果相對應地 A 是協 / 逆變合法。(C# 的陣列是協變的)
  • 泛型類型 G<A1, A2, ..., An> 是協 / 逆變合法,如果對於每個類型參數 Ai:
    • Ai 是協 / 逆變合法,並且 G 中的第 i 個參數被聲明為協變;或者
    • Ai 是逆 / 協變合法(反轉),並且 G 中的第 i 個參數被聲明為逆變;或者
    • Ai 既協變合法又逆變合法,並且 G 中的第 i 個參數被聲明為不變。

舉例而言,考慮下面的 IList<T> 介面:

interface IList<T>{
    void Insert(int index, T item);
    IEnumerator<T> GetEnumerator();
}

Insert 函數的參數類型 T 必須逆變合法,即 T 不得被標註為 out。相似地,由於 GetEnumerator 函數以一個協變的介面類型 IEnumerator<T> 為返回值類型,T 必須不是 in。這樣一來,IList<T> 既不能是協變,也不能是逆變。

在諸如 IList<T> 這種泛型數據結構的通常情況下,上述的限制意味着 out 參數只能用在從對象中讀數據的函數上,而 in 參數只能用在寫數據的函數上。這也就是為何選擇這兩個單詞作為關鍵字的原因。

數據

[編輯]

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] 對待。乍看之下這個泛化的類型似乎不那麼可靠,但如果程式設計師真拿那個簡單的聲明出來的話、類型錯誤會指出需要泛化的地方的。

變型的推斷

[編輯]

設計一個讓編譯器能在所有類型參數上自動推斷出儘量好的變型的型別系統是可能的[9]。然而,分析過程可能由於許多原因而變得複雜:其一,分析過程不是局部的,因為一個介面的變型性質取決於其所有使用到的介面;其二,為了得到最佳解,型別系統必須允許雙向變型——既是協變、同時也是逆變——的類型參數;其三,類型參數的變型性質應當是介面設計者深思熟慮的結果,而不是隨機發生的事情。

因此[10],許多語言都幾乎對變型不做干預。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 catIntMap.t animal 的子類型。

使用點變型標記法(萬用字元)

[編輯]

聲明點標記法的一個缺點是許多介面類型必須是不變的。例如,前面的 IList<T> 需要是不變的,因為其中既有協變的函數也有逆變的函數。為了暴露更多的變型性,API 設計者可以提供附加的介面以提供可用方法的子集——例如,一個只提供 Insert 函數的「唯寫列表」。然而這太笨拙了。

使用點標記法試圖給某個類的用戶以更多的機會去繼承,而不要求該類的設計者分開定義具有不同變型性質的若干介面。當某個類或介面被應用於類型聲明中時,程式設計師可以指明用到的只有成員函數的一個子集。就效果而言,類的定義同時也給出了相當於該類的協變和逆變的「部分」的介面。因此,類的設計者不再需要把變型納入考慮,從而提高了可重用性,

Java 通過萬用字元提供使用點變型標記,這是一種有界的約束存在量化形式。一個參數化類型可以通過萬用字元 ? 加上上下界的形式實例化,例如 List<? extends Animal> 或者 List<? super Animal>。(諸如 List<?> 這樣不加約束的萬用字元等價於 List<? extends Object>,因為 Java 的所有類型都衍生自 Object)。List<X> 這樣的類型表明了未知類型 X 滿足約束這件事。例如,如果變數 lList<? extends Animal> 類型,那麼型別檢查器會接受

Animal a = l.get(3);

因為已知類型 XAnimal 的子類,相反

l.add(new Animal())

將會導致類型錯誤,因為一個 Animal 並不一定是個 X。一般而論,給定某個介面 I<T>,一個 I<? extends A> 的記法禁止使用需要 T 逆變的函數;反之,如果 l 的類型是 List<? super Animal>,我們可以呼叫 l.add 但不能呼叫 l.get

Java 中的萬用字元子類階層可以畫成立方體形狀。

雖然 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 庫的調查[9]發現 39% 的萬用字元標記本可以用一個聲明點標記直接換掉,也即那剩下的 61% 是 Java 受益於有這麼個使用點變型系統的地方。

在聲明點變型語言中,庫必須要麼更少地暴露變型、要麼定義更多的介面。例如,Scala 集合庫給每個介面都定義了三個分開的版本:基本版本是不變型的、也不提供任何寫操作,有帶副作用函數的可寫版本,還有不可寫但把類型參數(通常)標為協變的版本[11]。這種設計跟聲明點標註配合得很好,但大量的介面給庫的用戶帶來了複雜性開銷。並且,修改庫介面可能不是一個可行選項——具體來說,Java 泛型的一個目標就是要維持二進制向下相容性。

另一方面,Java 的萬用字元本身就有夠複雜。在一場會議講演[12],Joshua Bloch 就批評它們太過難懂難用,聲稱當添加閉包支援時「再來一個萬用字元簡直就是不能承受之重」。早期版本的 Scala 使用使用點標註,然而程式設計師覺得它們難於實際應用,而聲明點標註就在設計類時有大用[13]。後期版本的 Scala 添加了 Java 樣式的存在類型和萬用字元;然而據 Martin Odersky 所說,假如沒有跟 Java 的互操作性需求的話,這些根本都不會被加進來[14]

Ross Tate 爭辯說[15] Java 萬用字元的複雜性有一部分是因為決定了要用存在類型的記法來標記使用點變型。原本的提案[16] [17]是使用專門用途的語法來標記變型,寫作 List<+Animal> 而不是 Java 這麼囉嗦的 List<? extends Animal>

既然萬用字元是存在類型的一種形式,它們就不僅可以用來做變型這一種事。一個諸如 List<?>(某種列表)的類型允許對象不必指定類型參數就能被傳遞給函數或者放進變數里。這對於像 Class 這樣的類而言尤其有用,因為其中的大多數函數都根本不管類型參數是什麼。

然而,對於存在類型的類型推導是一個難點。對於編譯器實現者來說,Java 的萬用字元提出了型別檢查器終結、類型參數推導、以及歧義程式的問題[18]。對程式設計師來說,它則帶來了複雜的類型錯誤訊息。Java 通過把萬用字元換成新類型變數的方式進行型別檢查(所謂擷取檢查),這會讓錯誤資訊更難讀,因為它們現在指向了程式設計師根本沒直接寫出的類型變數。例如,試圖將一個 Cat 加到 List<? extends Animal> 會得到類似這樣的錯誤:

 函数 List.add(capture#1) 不能应用
   (实参 Cat 不能被函数调用转换成 capture#1)
 其中 capture#1 是新类型变量:
   capture#1 extends Animal,由于捕获了 ? extends Animal

由於聲明點變型和使用點變型都有各自的用處,有些型別系統乾脆兩者都提供了[9][15]

Dart 中的協變泛型

[編輯]

Dart 語言並不跟蹤變型,而是把所有參數化類型都當作協變對待。語言規約[19]是這麼說的:

由於泛型類型的協變性,型別系統並不穩健。這是故意為之(當然也無疑會引起爭論)。經驗表明穩健的泛型類型規則在程式設計師的直覺面前如同廢紙。如果想的話,工具仍可簡單地提供穩健的類型分析,這可能對諸如重構之類的任務有所幫助。

「協變」一詞的來源

[編輯]

這些術語來源於範疇論函子的記法。考慮範疇 C,其中的對象是類型、其態射代表了子類關係≦(這是一個任何偏序集合可被看成範疇的例子);那麼諸如函數的類型構造器接受兩個類型 p 和 r 並建立一個新類型 p→r,即它把 C2 中的對象對映到 C 中。通過函數類型的子類規則,這個運算逆轉了第一參數上的≦順序而在第二參數上保持該順序,即它是一個在第一參數上逆變、而在第二參數上協變的函子。

參見

[編輯]

參考文獻

[編輯]
  1. ^ Luca Cardelli. A semantics of multiple inheritance (PDF). Semantics of Data Types (International Symposium Sophia-Antipolis, France, June 27 – 29, 1984). Lecture Notes in Computer Science 173. Springer. 1984 [2014-01-24]. doi:10.1007/3-540-13346-1_2. (原始內容存檔 (PDF)於2014-02-01). (Longer version in Information and Computation, 76(2/3): 138-164, February 1988.)
  2. ^ Allison, Chuck. What's New in Standard C++?. [2014-01-24]. (原始內容存檔於2012-05-27). 
  3. ^ Bertrand Meyer. Static Typing (PDF). OOPSLA 95 (Object-Oriented Programming, Systems, Languages and Applications), Atlanta, 1995.. October 1995 [2014-01-24]. (原始內容存檔 (PDF)於2012-11-14). 
  4. ^ 4.0 4.1 Howard, Mark; Bezault, Eric; Meyer, Bertrand; Colnet, Dominique; Stapf, Emmanuel; Arnout, Karine; Keller, Markus. Type-safe covariance: Competent compilers can catch all catcalls (PDF). April 2003 [2013-05-23]. (原始內容存檔 (PDF)於2013-10-05). 
  5. ^ Franz Weber. Getting Class Correctness and System Correctness Equivalent - How to Get Covariance Right. TOOLS 8 (8th conference on Technology of Object-Oriented Languages and Systems), Dortmund, 1992. 1992 [2014-01-24]. (原始內容存檔於2013-10-08). 
  6. ^ Giuseppe Castagna, Covariance and contravariance: conflict without a cause, ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 17, Issue 3, May 1995, pages 431-447.
  7. ^ Eric Lippert. Exact rules for variance validity. 2009-12-03 [July 2013]. (原始內容存檔於2013-05-28). 
  8. ^ Section II.9.7 in ECMA International Standard ECMA-335 Common Language Infrastructure (CLI) 6th edition (June 2012); available online頁面存檔備份,存於互聯網檔案館
  9. ^ 9.0 9.1 9.2 John Altidor; Huang Shan Shan; Yannis Smaragdakis. Taming the wildcards: combining definition- and use-site variance (PDF). Proceedings of the 32nd ACM SIGPLAN conference on Programming language design and implementation (PLDI'11). 2011 [2014-01-24]. (原始內容 (PDF)存檔於2012-01-06). 
  10. ^ Eric Lippert. Covariance and Contravariance in C# Part Seven: Why Do We Need A Syntax At All?. 2007-10-29 [October 2013]. (原始內容存檔於2010-01-23). 
  11. ^ Marin Odersky; Lex Spoon. The Scala 2.8 Collections API. 2010-09-07 [May 2013]. (原始內容存檔於2014-05-30). 
  12. ^ Joshua Bloch. The Closures Controversy [video]. Presentation at Javapolis'07. November 2007 [May 2013]. (原始內容存檔於2014-02-02). 
  13. ^ Martin Odersky; Matthias Zenger. Scalable component abstractions (PDF). Proceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications (OOPSLA '05). 2005 [2014-01-24]. (原始內容存檔 (PDF)於2013-01-24). 
  14. ^ Bill Venners and Frank Sommers. The Purpose of Scala's Type System: A Conversation with Martin Odersky, Part III. 2009-05-18 [May 2013]. (原始內容存檔於2014-02-01). 
  15. ^ 15.0 15.1 Ross Tate. Mixed-Site Variance. FOOL '13: Informal Proceedings of the 20th International Workshop on Foundations of Object-Oriented Languages. 2013 [2014-01-24]. (原始內容存檔於2014-02-01). 
  16. ^ Atsushi Igarashi; Mirko Viroli. On Variance-Based Subtyping for Parametric Types (PDF). Proceedings of the 16th European Conference on Object-Oriented Programming (ECOOP '02). 2002 [2014-01-24]. (原始內容 (PDF)存檔於2006-06-22). 
  17. ^ Kresten Krab Thorup; Mads Torgersen. Unifying Genericity: Combining the Benefits of Virtual Types and Parameterized Classes (PDF). Object-Oriented Programming (ECOOP '99). 1999 [2014-01-24]. (原始內容 (PDF)存檔於2015-09-23). 
  18. ^ Tate, Ross; Leung, Alan; Lerner, Sorin. Taming wildcards in Java's type system. Proceedings of the 32nd ACM SIGPLAN conference on Programming language design and implementation (PLDI '11). 2011 [2014-01-24]. (原始內容存檔於2014-02-09). 
  19. ^ The Dart Programming Language Specification. 2013-05-06 [May 2013]. (原始內容存檔於2014-01-02). 

外部連結

[編輯]