協變與逆變

協變與逆變是在計算機科學中，描述具有父/子型別關係的多個型別透過型別構造器、構造出的多個複雜型別之間是否有父/子型別關係的用語。概述.許多程式設計語言的型別系統支援子型別。例如，如果是的子型別，那麼型別的表示式可用於任何出現型別表示式的地方。所謂的變型的子型別關係。當我們用型別構造出更複雜的型別，原本型別的子型別性質可能被保持、反轉、或忽略───取決於型別構造器的變型性質。例如在C#中：程式語言的設計者在制定陣列、繼承、泛型資料類別等的型別規則時，必須將“變型”列入考量。將型別構造器設計成是協變、逆變而非不變的，可以讓更多的程式俱備良好的型別。另一方面，程式員經常覺得逆變是不直觀的；如果為了避免執行時期錯誤而精確追蹤變型，可能導致複雜的型別規則。為了保持型別系統簡單同時允許有用的程式設計，一個程式語言可能把型別構造器視為不變的，即使它被視為可變也是安全的；或是把型別構造器視為協變的，即使這樣可能會違反型別安全。形式定義.在一門程式設計語言的型別系統中，一個型別規則或者型別構造器是：下文中將敘述這些概念如何適用於常見的型別構造器。陣列.首先考慮陣列型別構造器： 從型別，可以得到。 是否可以把它當作如果要避免型別錯誤，且陣列支援對其元素的讀、寫操作，那麼只有第3個選擇是安全的。並不是總能當作，因為當一個客戶讀取陣列並期望得到一個，但中包含的可能是個。所以逆變規則是不安全的。反之，一個也不能被當作一個。因為總是可以把一個放到中。在協變陣列，這就不能保證是安全的，因為背後的儲存可以實際是。因此協變規則也不是安全的—陣列構造器應該是不變。注意，這僅是可寫陣列，協變規則是安全的。這示例了一般現像。只讀資料型別是逆變的。可讀可寫型別應是“不變”的。Java與C#中的協變陣列.早期版本的Java與C#不包含泛型。在這樣的設定下，使陣列為“不變”將導致許多有用的多型程式被排除。例如，考慮一個用於重排陣列的函式，或者測試兩個陣列相等的函式，使用與方法. 函式的實現並不依賴於陣列元素的確切型別，因此可以寫一個單獨的實現而適用於所有的陣列：boolean equalArrays (Object[] a1, Object[] a2);void shuffleArray(Object[] a);然而，如果陣列型別被處理為“不變”，那麼它僅能用於確切為型別的陣列。對於字串陣列等就不能做重排操作了。所以，Java與C#把陣列型別處理為協變。在C#中，是codice_1的子型別，在Java中，是的子型別。如前文所述，協變陣列在寫入陣列的操作時會出問題。Java與C#為此把每個陣列物件在建立時附標一個型別。 每當向陣列存入一個值，編譯器插入一段程式碼來檢查該值的執行時型別是否等於陣列的執行時型別。如果不匹配，會丟擲一個：// a 是單元素的 String 陣列String[] a = new String[1];// b 是 Object 的陣列Object[] b = a;// 向 b 中賦一個整數。如果 b 確實是 Object 的陣列，這是可能的；然而它其實是個 String 的陣列，因此會發生 java.lang.ArrayStoreExceptionb[0] = 1;在上例中，可以從b中安全地讀。僅在寫入陣列時可能會遇到麻煩。這個方法的缺點是留下了執行時錯誤的可能，而一個更嚴格的型別系統本可以在編譯時識別出該錯誤。這個方法還有損效能，因為在執行時要執行額外的型別檢查。Java與C#有了泛型後，有了型別安全的編寫這種多型函式。陣列比較與重排可以給定引數型別boolean equalArrays (T[] a1, T[] a2);void shuffleArray(T[] a);也可以強制C#方法只讀方式訪問一個集合，可以用介面代替作為陣列。函式型別.支援一等函式的語言具有函式型別，比如“一個函式期望輸入一隻 Cat 並返回一隻 Animal。這些語言需要指明什麼時候一個函式型別是另一個函式型別的子型別—也就是說，在一個期望某個函式型別的上下文中，什麼時候可以安全地使用另一個函式型別。可以說，函式f可以安全替換函式g，如果與函式g相比，函式f接受更一般的引數型別，返回更特化的結果型別。例如，函式型別可安全用於期望的地方；類似地，函式型別可用於期望的地方——典型地，在 Animal a=Fn(Cat(...)) 這種語境下進行呼叫，由於 Cat 是 Animal 的子類所以即使 Fn 接受一隻 Animal 也同樣是安全的。一般規則是：S1 → S2 ≦ T1 → T2 當T1 ≦ S1且S2 ≦ T2.換句話說，型別構造符→對輸入型別是逆變的而對輸出型別是協變的。這一規則首先被Luca Cardelli正式提出。在處理高階函式時，這一規則可以應用多次。例如，可以應用這一規則兩次，得到(A'→B)→B ≦ (A→B)→B 當 A'≦A。即，型別(A→B)→B在A位置是"協變的"。在跟蹤判斷為何某一型別特化不是型別安全的可能令人困擾，但是比較容易計算哪個位置是協變或逆變：一個位置是協變當且僅當在偶數個箭頭的左邊。例如，在Visual Basic中，允許把lambda表示式型別的例項，如果引數是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' 合法的返回值賦值：' 整數匹配於整數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面嚮物件語言中的繼承.當一個子類重寫一個超類的方法時，編譯器必須檢查重寫方法是否具有正確的型別。雖然一些語言要求型別必須與超類相同，但允許重寫方法有一個“更好的”型別也是型別安全的。對於大部分的方法子類化規則來說，這要求返回值的型別必須更具體，也就是協變，而且接受更寬泛的引數型別，也就是逆變。對於一下示例,假設 是 的子類,而且我們以及擁有了這兩個類(使用Java語法)class AnimalShelter {Animal getAnimalForAdoption() {void putAnimal(Animal animal) {問題是:如果我們子類化 , 我們可以讓 和 具有什麼型別？返回值的協變.在允許協變返回值的語言中, 子類可以重寫 方法來返回一個更窄的型別：class CatShelter extends AnimalShelter {Cat getAnimalForAdoption() {return new Cat();主流的面嚮物件語言中, Java和C++允許返回值協變，C#不支援。新增返回值協變是1998年C++標準委員會最先允許的對C++語言核心的修改之一。 Scala和D語言也支援返回值協變。方法引數的逆變.類似地，子類重寫的方法接受更寬的型別也是型別安全的：class CatShelter extends AnimalShelter {void putAnimal(Object animal) {允許引數逆變的面嚮物件語言並不多——C++和Java會把它當成一個函式過載。然而，Sather既支援協變，也支援逆變。對於重寫的方法，"出"引數和返回值是協變的，而常規的引數是逆變的。協變的方法引數型別.在主流的語言中，Eiffel 允許一個重寫的方法引數比起父類中的那一個有"更加"具體的型別，即引數型別協變。因此，Eiffel 版本的 會如下所示：class CatShelter extends AnimalShelter {void putAnimal(Cat animal) {這並不是型別安全的。透過把 轉換為 ，程式設計師可以把“狗”放進貓庇護所裡。這種型別安全性的缺失由來已久。許多年以來，人們組合使用各種全域性 / 區域性靜態分析以及新的語言特性來進行補救，有些已被寫進了一些 Eiffel 編譯器。拋開型別安全問題不談，Eiffel 的設計者認為在對現實世界建模這一點上，協變的引數型別是不可或缺的。貓庇護所問題演示了一種常見現象：它是"一種"動物庇護所，但有著"額外的限制"；而用繼承和受限引數型別又似無不可。透過提出繼承的這種應用方式，Eiffel 設計者們拒絕了 Liskov 代換原則。另一個引數型別協變可能有益的例子是所謂二元方法，即其引數與方法所在物件的型別相同。例如 方法： 檢查 和 在某種排序下的先後關係，但比較不同型別物件——比如，比較兩個有理數以及比較兩個字串——的方式可以大相徑庭。其它的常見二元方法例子還有相等性比較、算術運算、以及諸如求交集 / 並集的集合運算。在舊一點的 Java 版本中，比較方法是以介面 的方式指定的：interface Comparable {int compareTo(Object o);這種方式的缺點是方法引數型別指定為 。一個典型的實現可能是先把這個引數向下強制轉換——如果不是期望的型別，那麼報錯：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);在有引數協變的語言中， 的引數可以直接定為希望的型別。去除對引數型別協變的依賴.其它語言特性可能用來彌補缺乏引數型別協變的缺乏。在有泛型的語言中，前面的例子可用更型別安全的方式重寫：不定義 ，改為定義一個引數化的類 。class Shelter {T getAnimalForAdoption() {void putAnimal(T animal) {class CatShelter extends Shelter {Cat getAnimalForAdoption() {void putAnimal(Cat animal) {相似地，在新版本的 Java 中 介面也被引數化了，從而允許以一種型別安全的方式省去向下型別轉換：class RationalNumber implements Comparable {int numerator;int denominator;...public int compareTo(RationalNumber otherNum) {return Integer.compare(numerator*otherNum.denominator,otherNum.numerator*denominator);另一個有助的語言特性是多分派。二元方法難寫的一個原因就是在類似於 的呼叫中，對 的正確選擇其實依賴於 和 兩者的型別，但在經典的面嚮物件語言中只有 的型別被納入考慮。在有CLOS 樣式多分派特性的語言中，比較方法可以寫成一個泛型方法，其兩個引數型別都在方法選擇中被考慮。Giuseppe Castagna 觀察到在一個有型別而且有多分派的語言中，泛型函式的各個引數有些控制分派而餘下那些則否。因為方法選擇的規則是在可用方法中選擇特化程度最高的，如果一個方法重寫了另一個方法那麼，它型別才用來選擇方法，而在子類方法裡的 的型別也確實要比在父類那裡更特化。Castagna 提議在需要引數型別協變的地方——尤其是二元方法——改用多分派，它本性就是協變的。然而不幸的是，大多數程式語言都不支援多分派。變型和繼承的總結.下表總結了在上面討論的語言有關覆寫方法的規則。泛型型別.在支援泛型的語言中，程式設計師可以用新的構造器擴充套件型別系統。例如，C# 的泛型介面 可以構造 和 這樣的新型別。那麼接下來的問題就是這些型別構造器應具有何種變型性質。有兩種主要的處理方式。在有著宣告點變型標記法的語言中，程式設計師改在泛型型別例項化的位置標註。宣告點變型標記法.具有這種記法的最流行語言包括 C#。其中，C# 只允許在介面型別上標記變型，而 Scala 和 OCaml 既允許在介面型別上標記、也允許在具體的資料型別上標記變型。介面.在 C# 中，每個泛型介面的型別引數都可被標註為協變。例如，可以定義一個介面 作為只讀的迭代器，並宣告它在其型別引數上具有協變性：interface IEnumerator{T Current{get;bool MoveNext();透過這樣宣告，IEnumerator 就會在其型別引數上具有協變性。例如， 是 的子型別。型別檢查器保證接口裡每個函式宣告都透過符合 in/out 規則的方式使用其型別引數。也就是說，被宣告為協變的引數不得出現在任何逆變的位置。精確的規則是接口裡所有函式的返回值型別都必須"協變合法"，而所有函式引數的型別都必須"逆變合法"。具體來說，協 / 逆變合法定義如下：舉例而言，考慮下面的 介面：interface IList{void Insert(int index, T item);IEnumerator GetEnumerator();Insert 函式的引數型別 T 必須逆變合法，即 T 不得被標註為 out。相似地，由於 GetEnumerator 函式以一個協變的介面型別 IEnumerator 既不能是協變，也不能是逆變。在諸如 IList 這種泛型資料結構的通常情況下，上述的限制意味著 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: Adef tail: List[A]/** 向列表頭新增元素 */def ::[B &gt;: A] (x: B): List[B] =new scala.collection.immutable.::(x, this)首先，具有變型型別的類成員必須是不可變的。在這裡， 成員具有型別 ，其宣告為協變將會得到一個型別錯誤。其次，即使資料結構是不可變的，它也經常會有返回值型別逆變的函式。例如，考慮向列表頭新增元素的函式 ::。這個函式最顯然的型別莫過於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 -&gt; 'b)編譯器會推斷出第一引數是逆變、第二引數是協變的。程式設計師也可以顯式提供標註、讓編譯器檢查是否滿足，因此下面的宣告等價於上面：type (-'a, +'b) t = T of ('a -&gt; 'b)當定義介面時，OCaml 中的顯式標註就有用了。例如，標準庫給關聯表的介面 Map.S 包括一個標註，指明型別構造器 map 的返回型別是協變的：module type S =sigtype keytype (+'a) tval empty: 'a tval mem: key -&gt; 'a t -&gt; boolend這保證了 是 的子型別。使用點變型標記法.宣告點標記法的一個缺點是許多介面型別必須是不變的。例如，前面的 IList 需要是不變的，因為其中既有協變的函式也有逆變的函式。為了暴露更多的變型性，API 設計者可以提供附加的介面以提供可用方法的子集——例如，一個只提供 Insert 函式的“只寫列表”。然而這太笨拙了。使用點標記法試圖給某個類的使用者以更多的機會去繼承，而不要求該類的設計者分開定義具有不同變型性質的若干介面。當某個類或介面被應用於型別宣告中時，程式設計師可以指明用到的只有成員函式的一個子集。就效果而言，類的定義同時也給出了相當於該類的協變和逆變的“部分”的介面。因此，類的設計者不再需要把變型納入考慮，從而提高了可重用性，Java 透過萬用字元提供使用點變型標記，這是一種有界的約束存在量化形式。一個引數化型別可以透過萬用字元 加上上下界的形式例項化，例如 或者 。。 這樣的型別表明了未知型別 滿足約束這件事。例如，如果變數 是 型別，那麼型別檢查器會接受Animal a = l.get(3);因為已知型別 是 的子類，相反l.add(new Animal())將會導致型別錯誤，因為一個 並不一定是個 。一般而論，給定某個介面 ，一個 的記法禁止使用需要 T 逆變的函式；反之，如果 的型別是 ，我們可以呼叫 但不能呼叫 。雖然 Java 中的普通泛型型別是不變的。透過把子類化的兩個步驟合併，我們就可以做到諸如給期望 型別引數的函式傳遞一個 引數這樣的事。這正是協變介面型別所允許的程式。 型別就像一個只包含 的那些協變的函式的介面，然而 的實現者並不需要預先作出定義。這就是使用點變型。在 IList 這種常見的泛型資料結構中，協變引數用於從結構中讀出資料，而逆變引數用於寫入資料。Joshua Bloch 所著《Effective Java》中提出的助記短語 PECS提供了一個合適使用協變 / 逆變的好記方法。萬用字元很靈活，但也有個缺點。雖然使用點變型意味著 API 設計者不需要考慮介面的型別引數的變型性質，他們卻經常需要使用更復雜的函式簽名。一個常見例子涉及到 Java 中的 介面。假設我們要寫一個查詢集合中最大元素的函式，這些元素需要實現 函式，所以首先我們可能會做如下嘗試：然而這並不夠泛型——我們會發現能夠找到一個 集合中的最大值，但對 而言則否。問題在於 並不實現 介面，而是實現了。不像 C#，在 Java 中 並不被認為是 的子類。因此 的型別要改成這樣：有界萬用字元 用來表明 只調用 介面的逆變函式。這個示例令人沮喪的原因是 介面中的"所有"函式都是逆變的，因此條件是平凡真、所有用到這個介面的函式都要這樣。宣告點變型的系統就可以讓這個例子不那麼囉嗦：只需要在 介面上標註即可。比較宣告點與使用點變型.使用點變型提供了額外的靈活性，允許更多程式得以透過型別檢查。然而，它們因為給語言帶來的複雜性、以及所引發的複雜型別簽名和錯誤訊息而飽受批評。一個評判這種額外靈活性是否有用的方法是看它能否應用在現存程式裡。一個對大量 Java 庫的調查發現 39% 的萬用字元標記本可以用一個宣告點標記直接換掉，也即那剩下的 61% 是 Java 受益於有這麼個使用點變型系統的地方。在宣告點變型語言中，庫必須要麼更少地暴露變型、要麼定義更多的介面。例如，Scala 集合庫給每個介面都定義了三個分開的版本：基本版本是不變型的、也不提供任何寫操作，有帶副作用函式的可寫版本，還有不可寫但把型別引數標為協變的版本。這種設計跟宣告點標註配合得很好，但大量的介面給庫的使用者帶來了複雜性開銷。並且，修改庫介面可能不是一個可行選項——具體來說，Java 泛型的一個目標就是要維持二進位制向後相容性。另一方面，Java 的萬用字元本身就有夠複雜。在一場會議講演，Joshua Bloch 就批評它們太過難懂難用，聲稱當新增閉包支援時“再來一個"萬用字元"簡直就是不能承受之重”。早期版本的 Scala 使用使用點標註，然而程式設計師覺得它們難於實際應用，而宣告點標註就在設計類時有大用。後期版本的 Scala 添加了 Java 樣式的存在型別和萬用字元；然而據 Martin Odersky 所說，假如沒有跟 Java 的互操作性需求的話，這些根本都不會被加進來。Ross Tate 爭辯說 Java 萬用字元的複雜性有一部分是因為決定了要用存在型別的記法來標記使用點變型。原本的提案是使用專門用途的語法來標記變型，寫作 而不是 Java 這麼囉嗦的 。既然萬用字元是存在型別的一種形式，它們就不僅可以用來做變型這一種事。一個諸如 的型別允許物件不必指定型別引數就能被傳遞給函式或者放進變數裡。這對於像 這樣的類而言尤其有用，因為其中的大多數函式都根本不管型別引數是什麼。然而，對於存在型別的型別推導是一個難點。對於編譯器實現者來說，Java 的萬用字元提出了型別檢查器終結、型別引數推導、以及歧義程式的問題。對程式設計師來說，它則帶來了複雜的型別錯誤訊息。Java 透過把萬用字元換成新型別變數的方式進行型別檢查，這會讓錯誤資訊更難讀，因為它們現在指向了程式設計師根本沒直接寫出的型別變數。例如，試圖將一個 加到 會得到類似這樣的錯誤：函式 List.add(capture#1) 不能應用其中 capture#1 是新型別變數：capture#1 extends Animal，由於捕獲了 ? extends Animal由於宣告點變型和使用點變型都有各自的用處，有些型別系統乾脆兩者都提供了。Dart 中的協變泛型.Dart 語言並不跟蹤變型，而是把所有引數化型別都當作協變對待。語言規約是這麼說的：由於泛型型別的協變性，型別系統並不穩健。這是故意為之。經驗表明穩健的泛型型別規則在程式設計師的直覺面前如同廢紙。如果想的話，工具仍可簡單地提供穩健的型別分析，這可能對諸如重構之類的任務有所幫助。“協變”一詞的這些術語範疇論中函子的記法。考慮範疇 C，其中的物件是型別、其態射代表了子類關係≦；那麼諸如函式的型別構造器接受兩個型別 p 和 r 並建立一個新型別 p→r，即它把 C2 中的物件對映到 C 中。透過函式型別的子類規則，這個運算逆轉了第一引數上的≦順序而在第二引數上保持該順序，即它是一個在第一引數上逆變、而在第二引數上協變的函子。