I disagree with this article. Subtyping is what we have in TypeScript and it creates a lot of problems due to covariance.
If you have a type Animal, with subtypes Dog and Cat, then covariance means a list of Cat is a subtype of a list of Animal. The problem is that appending a Dog is a legal action for a list of Animals, but not a legal action for a list of Cats.
https://github.com/python/mypy/issues/4976 is an interesting discussion on this in Python: should a TypedDict be allowed where a dict argument is accepted? The basic consensus is no, because then one could modify the dict, adding keys that wouldn't be allowed in the specific TypedDict.
But this means that often you have to do cast(dict, my_typed_dict) to be able to interop with third party libraries that (quite naturally) believed that by typing their arguments as accepting a dict, they'd be accepting all dict-like things.
Const list<cat> is a subtype of Const list<animal>. But that does get complicated because. The difference between a mutable container of immutable elements and an immutable container of mutable elements is hard to get your head around, and verbose to capture in syntad.
My point is, we can’t say TypeScript doesn’t need subtyping just because they botched it. As such, it may not be a good counter example of the article’s thesis.
Perhaps you're just missing some words here, but, just for clarity: it doesn't make any sense to say that covariance is a mistake. Covariance applied in specific places, like Java's mutable covariant arrays which leads to unsoundness, can be a mistake, but covariance itself in fine and essential in languages with subtyping. Function parameters should be covariant, function returns should be contravariant, mutable data structures should be invariant, etc.
I'm not very familiar with these relations, but shouldn't function returns be covariant? `String => Cat` is a subtype of `String => Animal`?
> Function parameters should be covariant
For function parameters, doesn't it depend on how the parameter is used?
You're right :) I mixed up covariance and contravariance for function parameters and return value in my comment.
> For function parameters, doesn't it depend on how the parameter is used?
I don't think so, but maybe there's specific circumstances I don't know of? Function parameter types is a constraint on _input_ to the function. Changing that to a subtype amounts to the function receiving arguments that satisfies a stronger constraint. That seems that something that would hold no matter how the parameter is used?
> I don't think so, but maybe there's specific circumstances I don't know of?
I don't know specific circumstances either, but I presume they exist because of things like Dart's `covariant` keyword [0], which makes function parameters covariant instead of contravariant.
Consider if we have `A <= B <= C`, and a function:
int Copy([out] Array<B> dest, [in] Array<B> src);
Buffer<A> asrc = ...
Buffer<B> bsrc = ...
Buffer<C> csrc = ...
Buffer<A> adest = allocate(...)
Buffer<B> bdest = allocate(...)
Buffer<C> cdest = allocate(...)
Copy(adest, asrc); // No! - How would Copy know how to copy `A` values when it only knows about `B`?
Copy(adest, bsrc); // No! - src argument is OK, but how can it downcast them to `A`?
Copy(adest, csrc); // No! - Same as above, and src elements must be at least `B`s`.
Copy(bdest, asrc); // Ok. - Any `A` in the src are interpreted as `B`s.
Copy(bdest, bsrc); // Ok, - all values are interpreted as `B`s.
Copy(bdest, csrc); // No! - Argument elements must be at least `B`s`.
Copy(cdest, asrc); // Ok - values are interpreted as `B`s in src, and as `C`s in dest.
Copy(cdest, bsrc); // Ok
Copy(cdest, csrc); // No! Argument elements must be at least `B`s`.
Copy(adest, asrc); // pass (wrong)
Copy(adest, bsrc); // pass (wrong)
Copy(adest, csrc); // fail
Copy(bdest, asrc); // pass
Copy(bdest, bsrc); // pass
Copy(bdest, csrc); // fail
Copy(cdest, asrc); // fail (wrong)
Copy(cdest, bsrc); // fail (wrong)
Copy(cdest, csrc); // fail
copy : Array<B> -> Array<B>If we consider inside the function:
foo : arg:String => result:Animal
foo =
;; arg <: String
;; Animal <: result
let result = foo (arg)
;; String <: arg
;; result <: Animal
Always? In that case, do you know why Dart has a `covariant` keyword [0], which makes function parameters covariant?
Another way to put it, if I create a subtype, then the subtype's functions are allowed to be more general in what they accept, and more specific in what they return.
This implies that there is no subtype relation between X[Supertype] and X[Subtype].
To switch up the examples a bit, Natural is a subtype of Integer, so it's perfectly valid to make Natural => Natural (the type of IntegerSqrt) a subtype of Natural => Integer (the type of functions returning integers given a natural-number argument, such as n => (-2)**n), and to make Integer => Natural (the type of IntegerAbs) a subtype of Natural => Natural. If someone is expecting a Natural => Natural function, no surprises will result if you secretly smuggle them IntegerAbs. They just won't happen to call it with a negative argument.
And others have pointed out that covariance and contravariance are both logically unsound for mutable container types like arrays. In particular, covariance would allow you to infer Vector<Natural> is a subtype of Vector<Integer>, which, together with the function subtyping rules above, lets you pass a Vector<Natural> to a function like a => a[0] := -1. That will store a negative number into the Vector<Natural>, and down the line, that -1 will be incorrectly used in Natural calculations, possibly producing incorrect results. Contravariance is no better, because then functions like a => IntegerSqrt(a[0]) fall down go boom.
What I haven't seen anyone mention yet is that covariance is perfectly sound for immutable container types. If you have an immutable List container type supporting Car, Cdr, Cons, and IsEmpty functions, no surprises will result from passing a List<Natural> to a function expecting a List<Integer>. It can add -1 to the List with Cons(-1, xs) but that doesn't mutate the original List; it returns a new, longer List, which is already statically typed as a List<Integer>.
This is far from an original observation, so I was surprised not to see it mentioned.
Nothing obliges you to add function or immutable-container subtyping to your language just because you have subtyping of some kind. You could require implicit or explicit adaptors to be inserted in cases like the above, perhaps eliding those adaptors as a compilation optimization. Logically, that's a perfectly sound thing to do. I don't know why you would want to. It seems inconvenient. But maybe you do.