How to support contravariant generics in a structural type system?

Question

In a structural type system, a interface is just a list of properties with types and anything that has those properties automatically implements the interface. Typescript is one such example but it is (purposefully) not sound. Sound structural type systems are possible though.

There has been some confusion about what it means to be covariant or contravaraint. Feel free to skip this part if you are already familiar with the terms.

Consider I have the following types:

interface List<T> {}
interface HashMap<T, U>{}

interface Thing {}
interface Animal: Thing {}
interface Rabbit: Animal {}

If I have a function like this:

function k(b: List<Dog>) {
    ...
}

I could only pass List<Dog> instances. Not List<Cat> or List<Thing>. However, if the function body looked like this:

function k(b: List<Dog>) {
    print(b[0]) //actually a List<Rabbit> would have the same behavior
}

function k(b: List<Rabbit>) {
    b.push(new Rabbit); // Actually here a list of animals or a list of things would work too, since I can also push here
}

Thus I'm considering a syntax like this:

function k(b: I<in C>) // covariant type, supports only reads, subtypes accepted
function k(b: I<out C>) // contravariant type, supports only writes, supertypes accepted

A function can accept both covaraint in and contravariant out types like this:

function get(map: HashMap<out Animal, in Animal>) {
    Animal animal = map[Dog];
    print(animal)
}

function use<T: Thing, B: Rabbit>(p: HashMap<T, B>) {
    get(p);
}

Note there was some suggestion for auto-detection, but that wouldn't work in this case since it would transitively effect the use function, and any function that calls use etc. leading to errors often being very far away from where they are supposed to be.

If you wanted to write to the hash map, both would be contravariant:

function put(map: HashMap<out Animal, out Animal>) {
    map[new Animal] = new Animal
} 

put(new Map<Thing, Thing>)

---

This is theoretically sound. But I'm unsure how to formally specify this. What if you have something like b: I<in I<out C>>. What would that even mean? I<out I<in C>> is obviously nonsense, but how do I tell in a more complex example.

How do I tell if some combination of covariant and contravariant generics makes sense, if a specific type matches the type, and if a given type even makes sense?

Answer 1

In type systems I'm familiar with, you would specify covariance on the definition of a type, not on its use. For example:

interface I<in T> {
    property: T
}

would mean that in function k(b: I<C>), C is always covariant. If you want covariance, you would need to have a second interface definition. In this system, there is no equivalent to I<out I<in C>>.

---

Edit

Let's work this out with a more concrete example. Let's say we have the following types: Animal, Dog, Cat, List<T>.

So we want to be able to give a List<Dog> to a function pet(List<Animal>), but at the same time we want to prevent this situation:

function new_friend(animals: List<Animal>) {
    animals.push(new Cat)
}

my_pets: List<Dog> = ...
new_friend(my_pets) // oops! there is now a Cat in a List<Dog>

Instead of having function new_friend(animals: List<out Animal>), how about we decide that this is really about the type of animals?

We could have a syntax like:

function pet(animals: in List<Animal>) {
    for animal in animals { // okay
        animal.pet() // okay
    }
}

function new_friend(animals: out List<Animal>) {
    animals.push(new Cat) // okay
}

my_pets: List<Dog> = ...
new_friend(my_pets) // !!! type error: List<Dog> is not a supertype of List<Animal>

This way you still don't have the I<in I<out C>> problem, but that might be more suitable to a structural typing. It may be worth looking into how TypeScript does this, I am not all too familiar with it so I can't comment.

If functions are first class values in your language beware that functions are generally covariant in their return type but contravariant in their argument types. That always trips me up.

Answer 2

The conventional way to do this in a structural system is to use the structural system: given a type

type List<T> = {
    get(i : Integer) -> T
    add(val : T) -> None
}

then you can freely define consistent types

type ReadList<T> = {
    get(i : Integer) -> T
}
type WriteList<T> = {
    add(val : T) -> None
}

and use those as needed. These types are compatible supertypes under ordinary structural variance rules, and so values can already flow into them when required:

function j(b: ReadList<Animal>) {
    print (k[0])
}
function k(b : WriteList<Rabbit>) {
    k.add(new Rabbit)
}
j(new List<Dog>)
k(new List<Animal>)

A List of Dogs has a get method that always returns an Animal, so we're good there. A List of Animals has an add method that always accepts a Rabbit, so we're good there too. This is one of the strongest points in favour of structural types.

We can produce these types mechanistically just by omitting all methods that are not consistent with the variance you want in the parameters. A standard List already has the remaining methods, so it's compatible with those types. A list of a super/sub type will also have compatible methods for writing/reading, just ones that impose weaker requirements.

The List will have other methods too, but you're not going to access those ones; if you really want to require that they be present (so that you can't only satisfy the read/write types above), you can replace the methods' parametric types with bottom/top types to make them present but useless, but I don't see huge value in this for a structural system. To me, being able to make ad-hoc implementations like this is the point.

---

You can also do this for the HashMap examples, with only a little more complexity:

type OutOutHashMap<K,V> = {
    set(key : K, val : V)
    has(key : K) -> Boolean
    hasValue(val : V) -> Boolean
}
function put(map: OutOutHashMap<Animal, Animal>) {
    map[new Animal] = new Animal
}
put(new HashMap<Thing, Thing>)

is fine, because that accepts two Animals, and

type OutInHashMap<K, V> = {
    get(key : K) -> V
}
function get(map: OutInHashMap<Animal, Animal>) {
    Animal animal = map[aDog];
    print(animal)
}
function use<T: Thing, B: Rabbit>(p: HashMap<T, B>) {
    get(p);
}

is fine too. Nothing needs to change for use: HashMap<Thing, Rabbit> already has a get method that accepts an Animal and returns an Animal, and so it's allowed to flow in.

You don't need any sort of annotations for these cases. You could use your in/out syntax to generate these types on an ad-hoc basis (just removing all methods that used the parameter type in the parameter/return type), or allow trait-algebra style type differencing if you liked, but it's ultimately just about saving the programmer effort and making sure you don't miss something out (especially when it changes).

It may be easier to expand out any other parameterised types used in method parameters or return position when generating the ad-hoc types to make this detection easier, but ultimately it's readily detectable in the same way you already determine recursive structural subtyping.

---

For b: I<in I<out C>>, let's substitute in our List types for I: b : ReadList<WriteList<C>> - I think this is what you mean. This has type

{
    get(i : Integer) -> WriteList<C>
}

which is

{
    get(i : Integer) -> {
        add(val : C) -> None
    }
}

which is a perfectly fine type - it's a list of lists we can add values of type C to, but not add new lists to and not read the values of inner lists.

For b : I<out I<in C>>, I don't think that it is obvious nonsense, although it may not (or may) be useful. We have b : WriteList<ReadList<C>>, or

b : {
    add(val : ReadList<C>) -> None
}

which is

b : {
    add(val : { get(i : Integer) -> C }) -> None
}

This is also a meaningful type: we can add any List<C> or List<? extends C> to it, but not read any value from it.

You can always generate these types, just by removing the inconsistent methods. Some types may not have any suitable methods that don't use the parameter type both co- and contra-variantly at once: that's ok, you just get a universal type (i.e. with no methods); you can put anything into that type, but can't do anything with it once it's there. They may be useless, but they are what the programmer said, and they're not invalid.

If you are generating these ad-hoc, you could report an error on producing an empty type if you wanted to, or even if you end up with no methods that contain the parametric type (e.g. only size is left). It probably does indicate a mistaken assumption by the programmer, so this is reasonable, but it's not a soundness issue.

---

To formally address your questions at the end: all combinations of generics make sense, but some lose any relation to the parametric type, and this may be something you want to make an error out of if you are generating them - but you can also just stay out of it and let the programmer make their own types at will. You can tell if a specific type matches the type by ordinary structural subtyping, just as you do for existing parametric types, and without needing any extra care for variance.

Answer 3

Multiple interfaces

Going off of Jasmijn's answer about the placement of in and out, it's not infeasible to just end up with a lot of interfaces for the various use cases. For a hypothetical but not farfetched example:

interface Iterator<out T>
{
  T? Next();
}

interface Collector<in T>
{
  void Add(T);
}

class Queue<T> : Iterator<T>, Collector<T>
{
  // ...
}

Note that the class itself is invariant in the generic type.

Your read-only hashmap example could be achieved with an interface ReadOnlyMap<in Key, out Value>.