Is it possible to unify the concepts of inheritance and parametric polymorphism?

Question

I wonder if it is generally possible to unify the concepts of inheritance and parametric polymorphism ("generics"), especially regarding variance but also in terms how ("syntax") and where (use-site/declaration-site) they would have to be defined?

Consider this point of view:

• Sub-typing e. g. S <: T can be perceived as co-variant behavior, because input arguments accepting T will also accept S.
• Changing the "variance of the inheritance model" to invariant is only possible at definition-side by disallowing sub-typing (e. g. adding a final modifier to a class definition), contra-variance is not possible as far as I have seen in most cases
• Parametric polymorphism is invariant by default, but can be made co-/contra-variant

There seems to be a non-negligible concept mismatch between both, considering

• the pains languages have generated by allowing "unsafe" covariance (e. g. String[] <: Object[] in Java/C#)
• the differences in how inheritance/parametric polymorphism is declared and used compared to inheritance

In some languages it can be seen that both work together nicely though, like

class Foo extends Ordered[Foo]

to implement ordering/comparison behaviour.

• Is it conceivable that the concepts of inheritance and parametric polymorphism could be unified and gain the same default variance behavior (e. g. covariance by default or would that cause the necessity to mark most types with an invariance annotation instead, therefore just moving the ugliness to another point)? Would this be more practical as if data structures would become immutable by default, too?
• Is there a formal system in which this has been proven to be sound?
• Which syntax options/changes would be most likely necessary, regardless of a concrete programming language?
• Is there some working example or a language where this/something similar is already working?

Answer 1

By covariance/contravariance, one usually means this. Suppose X, Y, Z are types. Suppose further that a → b denotes a function type with an argument of type a and a result of type b. <: denotes the subtype relation, or perhaps some other notion of "conformance". The ⇒ arrow reads "entails". Then the following holds:

X <: Y ⇒ (Z → X) <: (Z → Y)
X <: Y ⇒ (Y → Z) <: (X → Z)

That is, the function type constructor is covariant with respect to the result type (data source), and contravariant with respect to the argument type (data sink). This is a basic fact and you more or less cannot do anything too creative about it, like reversing the directions of arrows. Of course you can always use no-variance in place of co- or contravariance (most languages do).

Object types can be canonically encoded with function types, so there's not too much freedom here either. Every type parameter represents either data source (covariant) or data sink (contravariant) or both (novariant). If it's sound and contravariant in one language, then in another language it's going to be either contravariant or unsound.

I think Scala is pretty close to an ideal language in this respect. You cite an example that looks a lot like Scala, so you are most likely familiar with the language. I wonder why you think that its type system works nicely only in some instances. What are the other instances?

One theoretical work that every aspiring language designer should read is "A Theory of Objects" by Luca Cardelli.