协变与逆变

维基百科,自由的百科全书
跳转至: 导航搜索

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

  • IEnumerable<Cat>IEnumerable<Animal>的子型別,因為型別構造器IEnumerable<T>是協變的(covariant)。注意到複雜型別IEnumerable的子型別關係和其介面中的參數型別是一致的,亦即,參數型別之間的子型別關係被保持住了。
  • Action<Cat>Action<Animal>的超型別,因為型別構造器Action<T>是逆變的(contravariant)。(在此,Action<T>被用來表示一個參數型別為Tsub-T一級函數英语First-class function)。注意到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 is a single-element array of String
    String[] a = new String[1];
 
    // b is an array of Object
    Object[] b = a;
 
    // Assign an Integer to b. This would be possible if b really were
    // an array of Object, but since it really is an array of String,
    // we will get a 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的地方。一般規則是:

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

换句话说,类型构造符→对输入类型是逆变的对输出类型是协变的。这一规则首先被Luca Cardelli正式提出。[1]

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

面向对象语言中的继承[编辑]

当一个子类重写一个超类的方法时,编译器必须检查重写方法是否具有正确的类型。虽然一些语言要求类型必须与超类相同,但允许重写方法有一个“更好的”类型也是类型安全的。对于大部分的方法子类化规则来说,这要求返回值的类型必须更具体,也就是协变,而且接受更宽泛的参数类型,也就是逆变。

对于一下示例,假设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既支持协变,也支持逆变。对于重写的方法,out参数和返回值是协变的,而常规的参数是逆变的。

变型和继承的总结[编辑]

下表总结了在上面讨论的语言有关覆写方法的规则。

参数类型 返回类型
C++ (自1998年), Java (自J2SE 5.0), Scala, D 不变 协变
C# 不变 不变
Sather 逆变 协变
Eiffel 协变 协变

泛型类型[编辑]

在支持泛型(即参数化多态英语Parametric polymorphism)的语言中,程序员可以用新的构造器扩展类型系统。例如,C#的泛型接口IList<T>可以构造 IList<Animal>IList<Cat>这样的新类型。接下来就会出现一个问题,即这些类型构造器应具有何种变型性质。

参见[编辑]

参考文献[编辑]

  1. ^ Luca Cardelli. A semantics of multiple inheritance, Lecture Notes in Computer Science, 173, Semantics of Data Types (International Symposium Sophia-Antipolis, France, June 27 – 29, 1984). Springer. 1984. doi:10.1007/3-540-13346-1_2. (Longer version in Information and Computation, 76(2/3): 138-164, February 1988.)
  2. ^ Allison, Chuck. What's New in Standard C++?. 
  3. ^ Bertrand Meyer. Static Typing. OOPSLA 95 (Object-Oriented Programming, Systems, Languages and Applications), Atlanta, 1995.. October 1995. 
  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. April 2003 [23 May 2013]. 
  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. 
  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. 3 December 2009 [July 2013]. 
  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. Proceedings of the 32nd ACM SIGPLAN conference on Programming language design and implementation (PLDI'11). 2011. 
  10. ^ Eric Lippert. Covariance and Contravariance in C# Part Seven: Why Do We Need A Syntax At All?. October 29, 2007 [October 2013]. 
  11. ^ Marin Odersky; Lex Spoon. The Scala 2.8 Collections API. September 7, 2010 [May 2013]. 
  12. ^ Joshua Bloch. The Closures Controversy [video]. Presentation at Javapolis'07. November 2007 [May 2013]. 
  13. ^ Martin Odersky; Matthias Zenger. Scalable component abstractions. Proceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications (OOPSLA '05). 2005. 
  14. ^ Bill Venners and Frank Sommers. The Purpose of Scala's Type System: A Conversation with Martin Odersky, Part III. May 18, 2009 [May 2013]. 
  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. 
  16. ^ Atsushi Igarashi; Mirko Viroli. On Variance-Based Subtyping for Parametric Types. Proceedings of the 16th European Conference on Object-Oriented Programming (ECOOP '02). 2002. 
  17. ^ Kresten Krab Thorup; Mads Torgersen. Unifying Genericity: Combining the Benefits of Virtual Types and Parameterized Classes. Object-Oriented Programming (ECOOP '99). 1999. 
  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. 
  19. ^ The Dart Programming Language Specification. May 6, 2013 [May 2013]. 

外部链接[编辑]