Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Covariance and Contravariance: a fresh look at an old issue [pdf]

irif.univ-paris-diderot.fr

Post reply on HN
Print view View original

11–20 of 27 posts

Re: Covariance and Contravariance: a fresh look at an old issue [pdf]

#11

Post by catnaroek »

continuational wrote: post #5
btilly wrote: post #4

Covariance 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…

Inheritance isn't the same thing as subtyping:

(0) Inheritance is a (rather undisciplined) form of code reuse - it's literally automation for copying and pasting part of an existing definition into the body of another. It doesn't presuppose a notion of type.

(1) Subtyping is a semantic relationship between two types: all terms of a subtype also inhabit its supertype(s).

There's nothing too wrong with inheritance as long as you're aware that it doesn't always lead to the creation of subtypes. This is, for example, the case in OCaml.

Sadly, Java, C# and C++ confuse matters by conflating classes with types (which is tolerable) and subclasses with subtypes (which is a logical absurdity and leads to painful workarounds, I mean, design patterns, as we all have learnt the hard way).

Re: Covariance and Contravariance: a fresh look at an old issue [pdf]

#12

Post by catnaroek »

btilly wrote: post #4

Covariance 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…

> 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.

Somehow Haskell and OCaml programmers manage to get by! OCaml has proper variance management built into the core language. Similarly, GHC Haskell with Rank2Types (or anything subsuming it) enabled, this is what lets you say things like “every Lens is a Traversal”: Lens (resp. Traversal) has a Functor (resp. Applicative) constraint in contravariant position in what's otherwise the same type, and Applicative is a subclass of Functor, so Lens is a subtype of Traversal.

The notions of covariance and contravariance are too natural and useful to get rid of them. If your type system doesn't have them, people will work around it to express as much variance as they needed. Except the workarounds will be clumsy, ad-hoc and most likely incorrect.

Re: Covariance and Contravariance: a fresh look at an old issue [pdf]

#13

Post by shiro »

continuational wrote: post #8
jayd16 wrote: post #6

Earlier quoted context omitted.

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)

That part is fine. The difficulty arises when you want to take out an apple from a list of fruits.

Re: Covariance and Contravariance: a fresh look at an old issue [pdf]

#14

Post by btilly »

catnaroek wrote: post #12
btilly wrote: post #4

Covariance 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…

> 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. Somehow…

Most programmers shy away from Haskell and OCaml. :-P

Seriously, the average programmer trying to learn Haskell starts with wanting to print "Hello, world", eventually winds up at a tutorial about monads, then retires with their head spinning. Haskell remains on the, "I should learn that some day" bucket list and remains unlearned.

This is not to say that you don't have plenty who don't learn them. But now we have another problem. One of the biggest reasons to use a language is available libraries. Because of the initial barriers to entry for these more sophisticated languages, there is a smaller pool of people writing useful libraries. Which means in the real world that when you want to get something done, you'll be more likely to find what you need pre-written if you use a more mainstream language.

Just to get a sense, in the (admittedly highly flawed) TIOBE index, the top language with a strong inference system is Scala, and the next is F#, then Haskell, and nothing else is in the top 50. The sum of popularities for these three would tie with Groovy at #18.

I have never written anything more than a toy program in any of these languages. I doubt I ever will.

Re: Covariance and Contravariance: a fresh look at an old issue [pdf]

#15

Post by catnaroek »

shiro wrote: post #13
continuational wrote: post #8

Earlier quoted context omitted.

Non-trivial? In Scala it would be: fruits ++= apples.map(_.asFruit)

That part is fine. The difficulty arises when you want to take out an apple from a list of fruits.

Why should you be able to do that?

Re: Covariance and Contravariance: a fresh look at an old issue [pdf]

#16

Post by shiro »

catnaroek wrote: post #15
shiro wrote: post #13

Earlier quoted context omitted.

That part is fine. The difficulty arises when you want to take out an apple from a list of fruits.

Why should you be able to do that?

Right, if you take type-safety first, you shouldn't be able to. But a list of abstract fruits has very limited usage without the ability to accessing concrete fruit instance. The adoption of downcasting in some OO languages came out from such needs, given that they lacked generic and/or algebraic types. And with that regard, I thought your solution didn't address the original covariance/contravariance problem (that is, want to have heterogeneous list of fruits and allowing to access concrete types of individual elements).

There are type-safe ways, like making a fruit a sum type of apple and banana, or using traits or type classes, etc. But is-a/has-a discussion seems a bit off from that.

Re: Covariance and Contravariance: a fresh look at an old issue [pdf]

#17

Post by continuational »

btilly wrote: post #10
continuational wrote: post #5

Earlier 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…

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 s…

You can't have co/contravariance without subtyping. Remove the extends and the implements keyword from Java, and you're rid of it. You can still create instances of Fruit using annonymous classes.

Re: Covariance and Contravariance: a fresh look at an old issue [pdf]

#18

Post by continuational »

catnaroek wrote: post #11
continuational wrote: post #5

Earlier 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…

Inheritance isn't the same thing as subtyping: (0) Inheritance is a (rather undisciplined) form of code reuse - it's literally automation for copying and pasting part of an existing definition into the body of another. It doesn't presuppose a notion of type. (1) Subtyping is a semantic relationship between two types: all terms of a subtype also inhabit its supertype(s). There's nothing too wrong with inheritance as l…

The Java style (Nominal) subtyping is what most people are familiar with, and the most common reason why people think subtyping is necessary, so let's not stray into other kinds of subtyping until we can agree on this kind.

Re: Covariance and Contravariance: a fresh look at an old issue [pdf]

#19

Post by kbenson »

btilly wrote: post #14
catnaroek wrote: post #12

Earlier quoted context omitted.

> 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. Somehow…

Most programmers shy away from Haskell and OCaml. :-P Seriously, the average programmer trying to learn Haskell starts with wanting to print "Hello, world", eventually winds up at a tutorial about monads, then retires with their head spinning. Haskell remains on the, "I should learn that some day" bucket list and remains unlearned. This is not to say that you don't have plenty who don't learn them. But now we have an…

Unfortunately, I think this speaks more towards the failing humans have towards assessing risk in complex systems. The cheaper to learn (considering time and effort required) languages that provide less safeguards routinely get far more new users over time. These languages can be useful in their ease of use (hey, I'm a Perl programmer, so I can't knock them entirely), but they have a far wider share of the market than I think is warranted.

Re: Covariance and Contravariance: a fresh look at an old issue [pdf]

#20

Post by catnaroek »

continuational wrote: post #18
catnaroek wrote: post #11

Earlier quoted context omitted.

Inheritance isn't the same thing as subtyping: (0) Inheritance is a (rather undisciplined) form of code reuse - it's literally automation for copying and pasting part of an existing definition into the body of another. It doesn't presuppose a notion of type. (1) Subtyping is a semantic relationship between two types: all terms of a subtype also inhabit its supertype(s). There's nothing too wrong with inheritance as l…

The Java style (Nominal) subtyping is what most people are familiar with, and the most common reason why people think subtyping is necessary, so let's not stray into other kinds of subtyping until we can agree on this kind.

I never said subtyping isn't necessary, and if you read my reply to btilly, you'd see that I actually suggested otherwise: subtyping is basic, natural and necessary, so languages should do it right.

Also, as I again previously said, nominal typing and even nominal subtyping are fine (well, I said “tolerable”, since they have downsides for modularity, but that's a topic for another day), but conflating inheritance with subtyping is a problem. To put it in Java terms, a subclass should only be considered a subtype if:

(0) The subclass doesn't override any methods that aren't abstract in the superclass. A subclass can do whatever its implementor wishes, but a subtype can't behave differently from a supertype.

(1) The subclass doesn't directly mutate any inherited fields from the superclass - this destroys inherited invariants. OTOH, reading inherited fields is just fine in a subtype.

In other words, a subclass is a subtype if and only if the type-checker has enough information to tell that the Liskov substitution principle actually holds.

Post reply on HN