[loup-vaillant]

Wait, if I recall correctly, covariance has long been established as a mistake. I would guess that if TypeScript had adopted contravariance the problems you mention would go away. We could then argue that TypeScript does need subtyping (like everyone else), as long as it’s contravariant.

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.

[paldepind2]

> Wait, if I recall correctly, covariance has long been established as a mistake.

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.

[pansa2]

> function returns should be contravariant

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?

[paldepind2]

> I'm not very familiar with these relations, but shouldn't function returns be covariant? `String => Cat` is a subtype of `String => Animal`?

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?

[pansa2]

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

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.

[0] https://dart.dev/language/type-system#covariant-keyword

[sparkie]

The use case would be where the arguments are expected to be filled in by the function - ie, as additional return types.

Consider if we have `A <= B <= C`, and a function:

    int Copy([out] Array<B> dest, [in] Array<B> src);

Given some potential inputs:

    Buffer<A> asrc = ...
    Buffer<B> bsrc = ...
    Buffer<C> csrc = ...

    Buffer<A> adest = allocate(...)
    Buffer<B> bdest = allocate(...)
    Buffer<C> cdest = allocate(...)

The following should be true:

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

If the `dest` argument were contravariant, it would permit invalid copies and forbid valid ones.

    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

In a purely functional setting, you should not need a covariant parameter type because all writes would end up in the return type.

    copy : Array<B> -> Array<B>

[kragen]

Maybe this is intentionally introducing logical unsoundness into Dart's type system for pragmatic purposes, perhaps supplemented with some implicit dynamic checks?

[hmry]

Read-only parameters should be contravariant, write-only parameters should be covariant, and read-write parameters should be invariant.

[sparkie]

`String => Cat` and `String => Animal` are the types of the functions themselves - not the arg and return types.

If we consider inside the function:

    foo : arg:String => result:Animal
    foo = 
        ;; arg <: String
        ;; Animal <: result

However, outside of the function, when calling it, the opposite is true.

    let result = foo (arg)
        ;; String <: arg
        ;; result <: Animal

It's easy to get them mixed up when looking at it from the wrong perspective - but we should be looking at functions from the outside, not the inside - so yes, parameters should be contravariant and return types covariant.

[pansa2]

> parameters should be contravariant

Always? In that case, do you know why Dart has a `covariant` keyword [0], which makes function parameters covariant?

[0] https://dart.dev/language/type-system#covariant-keyword

[kragen]

Others have pointed out that "covariance is a mistake" is nonsense, because, if you have subtyping, it's perfectly correct to make function types covariant on return types and contravariant on argument types. And it's useful.

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.

[jyounker]

Correct solution: Contravariance for arguments, Covariance for return types.

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