Covariance and Contravariance: a fresh look at an old issue [pdf]
irif.univ-paris-diderot.fr
Covariance and Contravariance: a fresh look at an old issue [pdf]
1–10 of 27 posts
Re: Covariance and Contravariance: a fresh look at an old issue [pdf]
#2A very nice explanation about what covariance and contravariance mean, especially in the context of subtyping (with potential parametric polymorphism).
And implementation details are provided. An undergrad should be able to understand this.
Re: Covariance and Contravariance: a fresh look at an old issue [pdf]
#3Prior submission a year ago, not much by the way of comments at the time: https://news.ycombinator.com/item?id=9771718
Re: Covariance and Contravariance: a fresh look at an old issue [pdf]
#4Covariance and contravariance are wonderful ways to notice key OO design problems. Unfortunately it is very hard to learn to think that way.
Consider an OO language with classes and inheritance. Each class is a type. (There may be types that aren't classes, for example Java an interface also represents a type. The equivalent in a dynamic language with duck typing is "all objects that satisfy this contract".) An object belongs to the type of its class, and every class you inherit from. (For instance an integer is an integer, a number, and an object.)
So far, so good.
Covariance occurs when we can use objects of any subtype freely. For instance we can insert integers into a list of numbers.
Contravariance occurs when we can allow an object to be of some supertype freely. For instance it is safe to assume that numbers from our list of numbers are objects.
The problem is that we can almost never do both. For example in Java you can put integers into a list of numbers, but you can't read numbers out of a list of numbers and assume that they will be integers! (Not even if you only put integers in - the type system won't let you do it.)
So, which do we want? Well, sometimes one, and sometimes the other. For example the Liskov substitution principle says that an object of a subtype should be usable anywhere we can use an object of the original type. Which means that if we override a method in a subclass, we are OK if we change the method's signature to accept a supertype, but are breaking the rule if we change it to require a subtype of the original.
Unfortunately it sometimes makes sense to have a subtype override a method and require a subtype be passed in. The paper offers a graphics example involving colors.
When we have this, we have 3 options. 1) Disallow it because the type system can't easily guarantee that things won't break. (Static languages like Java mostly do this.) 2) Assume that the programmer isn't an idiot then throw run-time errors if the programmer was. (Most dynamic languages do that.) 3) Build a sophisticated type system that can figure things out and reason out problem cases in a clever way. (This is what the author would like language designers to do.)
Unfortunately for the author, there is a chicken and egg problem here. Few programmers understand the sophisticated type system required for the reasoning solution, or can understand the weird errors that the type system can give you to say why it won't let you do something stupid. So developers shy away from languages that provide such types. Therefore there is little demand for languages that provide it.
As a result language designers have little reason to do anything other than either simple type systems with easy to understand checks, or dynamic dispatch with run-time errors. Which is a frustration to people who have put effort into how to have clever type systems that provide both programming flexibility and automatically catch common classes of errors.
Re: Covariance and Contravariance: a fresh look at an old issue [pdf]
#5Covariance and contravariance are wonderful ways to notice key OO design problems. Unfortunately it is very hard to learn to think that way. Consider an OO language with classes and inheritance. Each class is a type. (There may be types that aren't classes, for example Java an interface also represents a type. The equivalent in a dynamic language with duck typing is "all objects that satisfy this contract".) An objec…
Is there really enough value in subtyping to keep it around?
Sure, lots of things in the real world are naively "is-a" relationships, eg.
interface Fruit {
boolean isSoft();
}
class Apple implements Fruit {
boolean isSoft() { ... }
}
class Banana implements Fruit {
boolean isSoft() { ... }
}
interface Fruit {
boolean isSoft();
}
class Apple {
Fruit asFruit() { ... }
}
class Banana {
Fruit asFruit() { ... }
}
Re: Covariance and Contravariance: a fresh look at an old issue [pdf]
#6Covariance and contravariance are wonderful ways to notice key OO design problems. Unfortunately it is very hard to learn to think that way. Consider an OO language with classes and inheritance. Each class is a type. (There may be types that aren't classes, for example Java an interface also represents a type. The equivalent in a dynamic language with duck typing is "all objects that satisfy this contract".) An objec…
Is there really enough value in subtyping to keep it around? Sure, lots of things in the real world are naively "is-a" relationships, eg. interface Fruit { boolean isSoft(); } class Apple implements Fruit { boolean isSoft() { ... } } class Banana implements Fruit { boolean isSoft() { ... } } But this is both less explicit and less flexible than modelling it as a "has-a" relationship, eg. interface Fruit { boolean isS…
Simple things like adding a list of Apples to a list of Fruits become non-trivial.
Re: Covariance and Contravariance: a fresh look at an old issue [pdf]
#7A shorter, possibly easier to understand writeup from six months ago: https://www.mikeash.com/pyblog/friday-qa-2015-11-20-covarian...
I believe it was written by an HN commenter, and accumulated 67 comments: https://news.ycombinator.com/item?id=10606355
Re: Covariance and Contravariance: a fresh look at an old issue [pdf]
#8Earlier quoted context omitted.
Is there really enough value in subtyping to keep it around? Sure, lots of things in the real world are naively "is-a" relationships, eg. interface Fruit { boolean isSoft(); } class Apple implements Fruit { boolean isSoft() { ... } } class Banana implements Fruit { boolean isSoft() { ... } } But this is both less explicit and less flexible than modelling it as a "has-a" relationship, eg. interface Fruit { boolean isS…
Simple things like adding a list of Apples to a list of Fruits become non-trivial.
Non-trivial? In Scala it would be:
fruits ++= apples.map(_.asFruit)Re: Covariance and Contravariance: a fresh look at an old issue [pdf]
#9The way I explain variance is with a "bakers and chefs" example. Chefs turn ingredients into food and bakers turn dough into bread. Since dough is an ingredient and bread is a food, you may think all bakers are chefs. But this isn't true, because a chef should be able to handle any ingredient, and a baker may not necessarily know what to do with broccoli.
Re: Covariance and Contravariance: a fresh look at an old issue [pdf]
#10Covariance and contravariance are wonderful ways to notice key OO design problems. Unfortunately it is very hard to learn to think that way. Consider an OO language with classes and inheritance. Each class is a type. (There may be types that aren't classes, for example Java an interface also represents a type. The equivalent in a dynamic language with duck typing is "all objects that satisfy this contract".) An objec…
Is there really enough value in subtyping to keep it around? Sure, lots of things in the real world are naively "is-a" relationships, eg. interface Fruit { boolean isSoft(); } class Apple implements Fruit { boolean isSoft() { ... } } class Banana implements Fruit { boolean isSoft() { ... } } But this is both less explicit and less flexible than modelling it as a "has-a" relationship, eg. interface Fruit { boolean isS…
This can be summed up with, Favor composition over inheritance. :-)
Indeed it is a good idea to use composition whenever feasible. But your problems aren't over. Suppose you write a method that can accept anything that implements the Fruit interface. You've got covariance again. Suppose you have a dictionary whose values are of type Apple. You can pass those values into that method. That's contravariance again. And so it goes.
It doesn't matter whether you're defining types by classes, or what interfaces you implement. You will have types of some sort, and as soon as you do, you have covariance and contravariance as concepts again.