Encyclopedia > Covariance and contravariance (computer science)
A covariant type operator in a type system preserves the ordering ≤ of types. A contravariant operator reverses ≤. If neither of these apply, the operator is invariant. These terms come from category theory. In computer science, a type system defines how a programming language classifies values and expressions into types, how it can manipulate those types and how they interact. ...
In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ...
Typical examples:
- The array type is usually covariant on the base type: as String ≤ Object then ArrayOf(String) ≤ ArrayOf(Object). Note that this is only correct (i.e. type safe) if the array is immutable; if insert and remove operators are permitted, then the insert operator is covariant (e.g. one can insert a String into an ArrayOf(Object)) and the remove operator is contravariant (e.g. one can remove an Object from an ArrayOf(String)). Since the mutators have conflicting variance, arrays should be invariant on the base type.
- A function with a parameter of type T (defined as fun f (x : T) : Integer) can be replaced by a function g (defined as fun g (x : S) : Integer) if T ≤ S. In other words, if g cares less about the type of its parameter, then it can replace f anywhere, since both return an Integer. So, in a language accepting function arguments, g ≤ f and the type of the parameter to f is said to be contravariant.
- In the general case, the type of the result is covariant.
In object-oriented programming, substitution is also implicitly invoked by overriding methods in subclasses: the new method can be used where the old method was invoked in the original code. Programming languages vary widely on their allowed forms of overriding, and on the variance of overridden methods' types. This article does not cite any references or sources. ...
In computer science, a programming language is type safe when the language does not permit the programmer to treat a value as a type to which it does not belong. ...
Object-oriented programming (OOP) is a programming paradigm that uses objects and their interactions to design applications and computer programs. ...
Method overriding, in object oriented programming, is a language feature that allows a subclass to provide a specific implementation of a method that is already provided by one of its superclasses. ...
In object-oriented programming, the term method refers to a subroutine that is exclusively associated either with a class (called class methods, static methods, or factory methods) or with an object (called instance methods). ...
In object-oriented programming, a subclass is a class that inherits some properties from its superclass. ...
Origin of the terms
The origin of these terms is in category theory. Here we see the types in the type system as forming a category C, with arrows representing the subtype relationship. The subtype relationship supposedly reflects the substitution principle: that any expression of type t can be substituted by an expression of type s if s ≤ t. In mathematics, categories allow one to formalize notions involving abstract structure and processes that preserve structure. ...
In computer science, a type system defines how a programming language classifies values and expressions into types, how it can manipulate those types and how they interact. ...
Defining a function that accepts type p and returns type r creates a new type p → r in the type system which the new method name is associated with. This function definition operator is actually a functor F : C × C → C that creates the type as just said. From the substitution principle above, this functor must be contravariant in the first argument and covariant in the second (see Luca Cardelli). Did somebody just say functor? In category theory, a functor is a special type of mapping between categories. ...
Did somebody just say functor? In category theory, a functor is a special type of mapping between categories. ...
Did somebody just say functor? In category theory, a functor is a special type of mapping between categories. ...
An Italian computer scientist, currently working for Microsoft Research in Cambridge. ...
The controversy in object oriented languages The problem arises as different object oriented languages have different strategies to select the actual code used in a particular contexts and the first parameter is the object itself (which is not contravariant).
However, it was shown by Castagna (1995) that all depends on the method fetching algorithm: types used to select the method are contravariant; types not used to select the method are covariant. It's immaterial if the fetching occurs at run-time or at compile time.
These terms are also used in the context of modern programming languages that offer other functors to create new types with type variables, as in generic programming or parametric polymorphism, and exception handling where method definitions are enriched with annotations that indicate possible failures. Generic programming is a style of computer programming where algorithms are written in an extended grammar and are made adaptable by specifying variable parts that are then somehow instantiated later by the compiler with respect to the base grammar. ...
Polymorphism refers to features of various programming languages which allow a single piece of source code to operate on a variable whose type is not fixed. ...
Exception handling is a programming language construct or computer hardware mechanism designed to handle the occurrence of some condition that changes the normal flow of execution. ...
Overview of covariance/contravariance in some programming languages How types are built from basic types, thus defining the sub-type relationship, and how new methods are defined and override or not existing methods depends on the language and sometimes not necessarily follow the substitution principle above adding runtime checking instead.
Here a simple comparison of how overriding methods behave in some programming languages.
C++ C++ supports covariant return types in overridden virtual functions. Adding the covariant return type was the first modification of the C++ language approved by the standards committee in 1998. See Allison, Chuck. "What's New in Standard C++?". C++ (pronounced see plus plus, IPA: ) is a general-purpose programming language with high-level and low-level capabilities. ...
Return types are what results from calling a method or function in high-level programming languages, such as Java, C++, C, Prolog and many others. ...
In object-oriented programming (OOP), a virtual function or virtual method is a function whose behavior, by virtue of being declared virtual, is determined by the definition of a function with the same signature furthest in the inheritance lineage of the instantiated object on which it is called. ...
With generic programming, C++ allows for what amounts to covariance in argument as well as return type. For example, the argument and return types of member functions of the std::vector<T> class vary with T. The push_back method takes a const T&, so one pushes an int onto a vector<int> but a std::string onto a vector<string>. This is done at compile time (statically) and, strictly speaking, is parametric polymorphism. Generic programming is a style of computer programming where algorithms are written in an extended grammar and are made adaptable by specifying variable parts that are then somehow instantiated later by the compiler with respect to the base grammar. ...
Polymorphism refers to features of various programming languages which allow a single piece of source code to operate on a variable whose type is not fixed. ...
C# Arrays of reference-types are covariant: string[] is a subtype of object[], although with some caveats: // a is a single-element array of System.String string[] a = new string[1]; // b is an array of System.Object object[] b = a; // Assign an integer to b. This would be possible if b really were // an array of objects, but since it really is an array of strings, // we will get an ArrayTypeMismatchException with the following message: // "Attempted to store an element of the incorrect type into the array". b[0] = 1; Note: In the above case you can read from b without problem. It is only when trying to write to the array that you must know its real type.
Arrays of value-types are invariant: int[] is not a subtype of double[].
In the C# programming language, support for both return-type covariance and parameter contravariance for delegates was added in version 2.0 of the language. Neither covariance nor contravariance are supported for method overriding. The title given to this article is incorrect due to technical limitations. ...
A delegate is a form of type-safe function pointer used in the . ...
Eiffel Eiffel allows covariant return and parameter types in overriding methods. This is possible because Eiffel does not require subclasses to be substitutable for superclasses — that is, subclasses are not necessarily subtypes. Eiffel is an ISO-standardized object-oriented programming language designed for extensibility, reusability, reliability and programmer productivity. ...
Substitutability is a principle in computer programming. ...
However, this can lead to surprises if subclasses with such covariant parameter types are operated upon as though they were a more general class (polymorphism), leading to the possibility of compiler errors. In computer science, polymorphism means allowing a single definition to be used with different types of data (specifically, different classes of objects). ...
A diagram of the operation of a typical multi-language, multi-target compiler. ...
Java Arrays of objects are covariant: String[] is a subtype of Object[], although with some caveats: // 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 Integer, but since it really is an array of String, // we will get a java.lang.ArrayStoreException. b[0] = new Integer (1); Note: In the above case you can read from b without problem. It is only when trying to write to the array that you must know its real type.
Arrays of primitive types are invariant: int[] is not a subtype of long[], although int is in some sense a subtype of long.
Exception covariance has been supported since the introduction of the language. Return type covariance is implemented in the Java programming language version J2SE 5.0. Parameter types have to be exactly the same (invariant) for method overriding, otherwise the method is overloaded with a parallel definition instead. “Java language†redirects here. ...
Java Platform, Standard Edition or Java SE (formerly known as Java 2 Platform, Standard Edition or J2SE until the name was changed to Java SE in version 6. ...
Method overriding, in object oriented programming, is a language feature that allows a subclass to provide a specific implementation of a method that is already provided by one of its superclasses. ...
The Greek meaning of the words poly and morph together imply that a single entity can take on multiple forms. In the field of computer science, there are two fundamentally different types of polymorphism; subtype polymorphism, and parametric polymorphism. ...
REALbasic REALbasic added support for return type covariance in version 5.5. As with Java, the parameter types of the overriding method must be the same. REALbasic (RB) is an object-oriented dialect of the BASIC programming language developed and commercially marketed by REAL Software, Inc in Austin, Texas for Mac OS X, Microsoft Windows, and Linux. ...
Scala Scala supports both covariance and contravariance. Scala is a multi-paradigm programming language designed to express common programming patterns in a concise, elegant, and type-safe way. ...
Sather Sather supports both covariance and contravariance. Sather is an object-oriented programming language. ...
See also In computer science, polymorphism means allowing a single definition to be used with different types of data (specifically, different classes of objects). ...
This article or section does not cite any references or sources. ...
External links | 
Feeds |
Contact