4
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ I don't follow this question ─ whether or not a type parameter is covariant, contravariant or invariant is determined by the way that type parameter is used. The language can have in and out annotations for type parameters, but these wouldn't change the subtyping relation in a structural type system; the purpose of the annotations is just to indicate intent, and the compiler can check whether the annotations are correct. In your example of I<T>, the type is invariant in T because of how T is used in the type, unless the property is readonly in which case I<T> is covariant in T. $\endgroup$
    – kaya3
    May 31, 2023 at 20:42
  • $\begingroup$ @kaya3 Auto detection is defiantly a option but it would be nice to know what parameters I can pass purely based on the function signature $\endgroup$
    – mousetail
    May 31, 2023 at 20:53
  • $\begingroup$ "Auto detection" of what types are subtypes of what other types is, essentially, the defining feature of a structural type system. The parameters you can pass are those whose type is assignable to I<C>, and whether or not I<D> is assignable to I<C> depends on how T is used in the definition of I. A function can't just declare for I to be covariant or contravariant in T if it isn't already. If I<D> isn't a structural subtype of I<C>, then the function cannot simply decide that it is a subtype, any more than it can decide string is a subtype of I<C>. $\endgroup$
    – kaya3
    May 31, 2023 at 20:59
  • $\begingroup$ @kaya3 The issue with autodetection is it means any function that calls this function and it itself generic might be autodetected to become invariant at any point, and then transitively any function that calls that function and eventually if there is a error with the variance it will be very far away from what actually caused the mistake $\endgroup$
    – mousetail
    May 31, 2023 at 21:17
  • $\begingroup$ I don't follow. If I<T> is supposed to be covariant in T but you accidentally declare I in a way that it is invariant in T, and a function accepts I<C> and is called with an argument of type I<D>, the error will occur at that call-site, but there will not be cascading errors in other functions which call the function that contains the error. Anyway, the mistake would be in the declaration of the type I<T>, so if you do want to allow annotations that the compiler checks, the annotation belongs in the declaration of I<T>. $\endgroup$
    – kaya3
    May 31, 2023 at 21:23

3 Answers 3

6
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ That seems contradictory, that means it would in no context be possible to write to the property thus be impossible to even construct the type $\endgroup$
    – mousetail
    May 31, 2023 at 19:31
  • 1
    $\begingroup$ Ah, I missed the "supports only reads" and "supports only writes" parts. I'm not sure how locking covariant to readonly and contravariant to writeonly would work in practice, but I can make another suggestion, I'll edit my answer. $\endgroup$
    – Jasmijn
    May 31, 2023 at 19:39
  • $\begingroup$ Thanks, but what if I have a type like HashMap<in Aminal, out Animal> where I need both a in and out parameter on the same type? $\endgroup$
    – mousetail
    May 31, 2023 at 20:24
  • $\begingroup$ I do not know, but I also do not know what it would even mean to have a HashMap<in K, out V> in this context. I'm afraid this goes above my paygrade, I hope someone else can answer your question. $\endgroup$
    – Jasmijn
    May 31, 2023 at 20:39
  • $\begingroup$ Basically it's a map that I can pass in any animal and would give me back any animal. If I can pass in a supertype of animal also it obivously doesn't matter and is still valid, and the same if it always returns some subtype of animal since that is still a animal. $\endgroup$
    – mousetail
    May 31, 2023 at 20:54
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is a more thorough version of what I was trying to get at with my answer. $\endgroup$
    – Bbrk24
    Jun 1, 2023 at 17:22
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .