More Type Variance

I did a little type variance exploration way back when, but that was when dealing with go. And go doesn’t allow type variance! It was a “huh, be nice if I could do this, but the compiler hates it, wonder why…” journey. But now I am in rust-land where the type system is way gnarlier, for better or for worse. So I’d like to re-visit the topic.

A language’s type system is designed to help a programmer through restrictions. Which sounds a little counter-intuitive, but the idea is to tell the compiler what you think you are doing and it will double check it, “This function takes a Cat type, did I actually pass one to it?”. As you design these interfaces though, you do start to wonder if there is some flexibility to the rules. It kinda checks out that if a function needs an Animal type, a Cat type should also work. There is a relationship between the types, Cat is a subtype of Animal, a hierarchy (gonna punt on if defining a type hierarchy is a good idea). This sorta question doesn’t happen on just functions, it’s anywhere there is a generic parameter. The usual suspects are functions and data types, but there are higher order spots too. Here is the general rule.

“When you have some type constructor F<T> and a subtyping relationship A <: B, what’s the relationship between F<A> and F<B>?”

<: is a nifty “subtype” type theory symbol, Cat <: Animal “Cat is a subtype of Animal”. Anywhere you need an Animal, you can use a Cat, it does at least as much as an animal. And now, the types of type variance.

• Covariant (+T) // If Cat <: Animal, then Vec<Cat> <: Vec<Animal>. The relationship is preserved inside this wrapper type. A vector of cats can be used in a spot requiring a vector of animals. And in terms of type variance, vector can be any type constructor, vectors are just a great example here.
• Contravariant (-T) // If Cat<: Animal, then Fn(Animal) <: Fn(Cat). The relationship is flipped. A function that accepts animals can be used in a spot which requires a function which accepts cats.
• Invariant (=T) // A Cat is a Cat is a Cat. None of this variance trickiness, things are kept simple and must just equal each other.
• Bivariant // Both covariant and contravariant, which when you think about it, is pretty weird. Rarely used and probably means you are doing something wrong.

I have to imagine that if I was designing a type system, I would see the appeal of invariance. Checking all these hierarchies probably gets hairy. But that is not my job!

Nominal Typing

For a type system to have a chance at supporting variance, it must have some way to establish type relationships. Rust doesn’t support classic object oriented inheritance, but it does allow traits to define supertrait requirements. These relationships are explicitly declared and only are behavior related, not data.

// Animal is a supertrait of Dog.
trait Animal {
    fn speak(&self);
}

// Dog requires Animal.
trait Dog: Animal {  
    fn bark(&self) {
        println!("Woof!");
    }
}

// Any type implementing Dog must also implement Animal.
struct GoldenRetriever;

impl Animal for GoldenRetriever {
    fn speak(&self) { println!("Woof!"); }
}

impl Dog for GoldenRetriever {
    // bark() gets default implementation.
}

Supertrait usage in rust traits.

Yea, rust is pretty explicit. This is nominal typing where everything is officially declared. For GoldenRetriever to implement dogs it needs to *implement Animal. This is opposite of a type system which instead supports structural typing where a type implements a trait if it has the same structure. As in, it can implicitly implement an infinite number of declared traits. This is what languages like go or typescript support. But how these relationships are established is kinda orthogonal to if the type system supports variance. It just needs to understand the type relations.

Polymorphism and Monomorphization

You might be like me and think that variance will show up in rust’s trait bound features. Coming from a go background, this isn’t the craziest idea since a lot of implicit interface variance happens over there.

Trait bounds bound the type, but they don’t define what concrete type is required. It is a form of polymorphism, one interface across multiple types. But the rust compiler can implement this “shared” interface into many type-specific versions under the hood for static dispatch.

fn process_animals<T: Animal>(animals: Vec<T>) {
    for animal in animals {
        animal.speak();
    }
}

fn main() {
    let dogs: Vec<Dog> = vec![Dog, Dog];
    process_animals(dogs);
    
    let cats: Vec<Cat> = vec![Cat, Cat];
    process_animals(cats);
}

This might look like variance, but it is implemented with monomorphization resolved at compile time! The compiler is going to stamp out separate functions per-types, not shift interfaces.

Polymorphism is the relationship between types, and variance is types of operations which operate on those relations. Variance naturally requires a layer of indirection because we are trying to abstract across multiple concrete types with different memory requirements. We want to work on just the interface shared by the types, which sounds very dynamic-y.

References

Type variance shows up in rust wherever there are pointers involved. It is more explicit than in go, compare this shared function using the dyn keyword instead of trait bounds.

fn process(animal: &dyn Animal) { animal.speak(); }

let dog: &Dog = &Dog;
process(dog);

let cat: &Cat = &Cat;  
process(cat);

Polymorphism with variance, one function which relies on runtime covariant conversion to work on the animal interface.

One of the more interesting, and common, parts of pointer variance in rust is reference lifetimes. Rust treats lifetimes a having a subtyping relationship. The 'static lifetime can be used anywhere a shorter lifetime e.g. 'a is expected. 'static is a subtype of a shorter lifetime. And when we describe lifetimes as where 'a: 'b, “tick a outlives tick b”, we are saying that 'a is a subtype of 'b. References are covariant in lifetimes, so longer can become shorter.

fn main() {
    let s: &'static str = "hello";
    let t: &str = s;
    
    println!("{}", t);
}

The simplest example of reference covariance, a longer references being assigned to a smaller.