本页使用了标题或全文手工转换

协变与逆变

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

許多程式設計語言型別系統支持子型別。例如,如果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一級函數)。注意到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的地方。一般規則是:

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

协变的方法参数类型[编辑]

在主流的语言中,Eiffel 允许一个重写的方法参数比起父类中的那一个有更加具体的类型,即参数类型协变。因此,Eiffel 版本的 putAnimal 会如下所示:

    class CatShelter extends AnimalShelter {
        void putAnimal(Cat animal) {
           ...
        }
    }

这并不是类型安全的。通过把 CatShelter 转换为 AnimalShelter,程序员可以把“狗”放进猫庇护所里。这种类型安全性的缺失(在 Eiffel 社区里称为“猫调用问题”)由来已久。许多年以来,人们组合使用各种全局 / 局部静态分析以及新的语言特性来进行补救[3] [4],有些已被写进了一些 Eiffel 编译器。

抛开类型安全问题不谈,Eiffel 的设计者认为在对现实世界建模这一点上,协变的参数类型是不可或缺的[4]。猫庇护所问题演示了一种常见现象:它是一种动物庇护所,但有着额外的限制;而用继承和受限参数类型又似无不可。通过提出继承的这种应用方式,Eiffer 设计者们拒绝了 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)。

去除对参数类型协变的依赖[编辑]

其它语言特性可能用来弥补缺乏参数类型协变的缺乏。

在有泛型(即参数化多态受限量词)的语言中,前面的例子可用更类型安全的方式重写[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>这样的新类型。接下来就会出现一个问题,即这些类型构造器应具有何种变型性质。

参见[编辑]

参考文献[编辑]

  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. 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 (PDF). 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 (PDF). 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 (PDF). 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 (PDF). 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 (PDF). 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 (PDF). 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]. 

外部链接[编辑]