mikeash.com: just this guy, you know?

Posted at 2015-11-20 14:16 | RSS feed (Full text feed) | Blog Index
Next article: Friday Q&A 2015-12-11: Swift Weak References
Previous article: Friday Q&A 2015-11-06: Why is Swift's String API So Hard?
Tags: fridayqna oop theory
Friday Q&A 2015-11-20: Covariance and Contravariance
by Mike Ash  

Subtypes and supertypes are a common part of modern programming. Covariance and contravariance tell us where subtypes are accepted and where supertypes are accepted in place of the original type. This shows up frequently in most of the programming most of us do, but many developers are unaware of the concepts beyond a loose instinctual sense. Today I'm going to discuss it in detail.

Subtypes and Supertypes
We all know what subclassing is. When you create a subclass, you're creating a subtype. To take a classic example, you might subclass Animal to create Cat:

    class Animal {
        ...
    }

    class Cat: Animal {
        ...
    }

This makes Cat a subtype of Animal. That means that all Cats are Animals, but not all Animals are Cats.

Subtypes can typically substitute for supertypes. It's obvious to any programmer who's been around a little while why in this Swift code the first line works and the second line doesn't:

    let animal: Animal = Cat()
    let cat: Cat = Animal()

This is true for function types as well:

    func animalF() -> Animal {
        return Animal()
    }

    func catF() -> Cat {
        return Cat()
    }

    let returnsAnimal: () -> Animal = catF
    let returnsCat: () -> Cat = animalF

All of this works in Objective-C too, using blocks. The syntax is much uglier, though, so I decided to stick with Swift.

Note that this does not work:

    func catCatF(inCat: Cat) -> Cat {
        return inCat
    }

    let animalAnimal: Animal -> Animal = catCatF

Confused yet? Not to worry, this whole article is going to explore exactly why the first version works while the second version doesn't, and hit on some more practical stuff along the way.

Overridden Methods
Similar things are at work with overridden methods. Imagine this class:

    class Person {
        func purchaseAnimal() -> Animal
    }

Now let's subclass it, override that method, and change the return type:

    class CrazyCatLady: Person {
        override func purchaseAnimal() -> Cat
    }

Is this legal? Yes. Why?

The Liskov substitution principle is the guiding principle for subclassing. It says, in short, that an instance of a subclass can always be substituted for an instance of its superclass. Anywhere you have an Animal, you can replace it with a Cat. Anywhere you have a Person, you can replace it with a CrazyCatLady.

Here's some code that uses a Person, with explicit type annotations for clarity:

    let person: Person = getAPerson()
    let animal: Animal = person.purchaseAnimal()
    animal.pet()

Imagine that getAPerson returns a CrazyCatLady. Does this code still work? CrazyCatLady.purchaseAnimal will return a Cat. That instance is placed into animal. A Cat is a valid Animal, so it can do everything an Animal can do, including pet. Having CrazyCatLady return Cat is valid.

Let's imagine we want to move the pet operation into Person, so we can have a particular person pet a particular animal:

    class Person {
        func purchaseAnimal() -> Animal
        func pet(animal: Animal)
    }

Naturally, CrazyCatLady only pets cats:

    class CrazyCatLady: Person {
        override func purchaseAnimal() -> Cat
        override func pet(animal: Cat)
    }

Is this legal? No!

To understand why, let's look at some code that uses this method:

    let person: Person = getAPerson()
    let animal: Animal = getAnAnimal()
    person.pet(animal)

Imagine that getAPerson() returns a CrazyCatLady. This line is still good:

    let person: Person = getAPerson()

Imagine that getAnAnimal() returns a Dog, which is a subclass of Animal with decidedly different behaviors from Cat. This line is still good as well:

    let animal: Animal = getAnAnimal()

Now we have a CrazyCatLady in person and a Dog in animal and we do this:

    person.pet(animal)

Kaboom! CrazyCatLady's pet method is expecting a Cat. It has no idea what to do with a Dog. It's probably going to be accessing properties and calling methods that Dog doesn't have.

This code is perfectly legal. It gets a Person, it gets an Animal, then it calls a method on Person that takes an Animal. The problem lies above, when we changed CrazyCatLady.pet to take a Cat. That broke the Liskov substitution principle: no longer can a CrazyCatLady be used anywhere a Person is used!

Thankfully, the compiler has our back. It knows that using a subtype for an overridden method's parameter is not legal, and will refuse to compile this code.

Is it ever legal to use a different type in an overridden method? Yes, actually: you can use a supertype. For example, imagine that Animal subclasses Thing. It would then be legal to override pet to take Thing:

    override func pet(thing: Thing)

This preserves substitutability. If treated as a Person, then this method will always be passed Animals, which are Things.

This is a key rule: function return values can changed to subtypes, moving down the hierarchy, whereas function parameters can be changed to supertypes, moving up the hierarchy.

Standalone Functions
The subtype/supertype relationship is obvious enough when it comes to classes. It directly follows the class hierarchy. What about functions?

    let f1: A -> B = ...
    let f2: C -> D = f1

When is this legal, and when is it not?

This is basically a miniature version of the Liskov substitution principle. In fact, you can think of functions as little mini-objects with just one method. When you have two different object types, when can you mix them like this? When the original type is a subtype of the destination. And when is a method a subtype of another method? As we saw above, it's when parameters are supertypes and the return value is a subtype.

Applied here, the above code works if A is a supertype of C, and if B is a subtype of D. Put concretely:

    let f1: Animal -> Animal = ...
    let f2: Cat -> Thing = f1

The two parts move in opposite directions. This may not be what you want, but it's the only way it can actually work.

This is another key rule: functions are subtypes of other functions if the parameter types are supertypes and the return types are subtypes.

Properties
Read-only properties are pretty simple. Subclass properties must be subtypes. A read-only property is essentially a function which takes no parameters and returns a value, and the same rules apply.

Read-write properties are also pretty simple. Subclass properties must be the exact same type as the superclass. A read-write property is essentially a pair of functions. The getter is a function with no parameters that returns a value, and the setter is a function with one parameter and no return value:

    var animal: Animal
    // This is like:
    func getAnimal() -> Animal
    func setAnimal(animal: Animal)

As we saw above, function parameters move up while function return types move down. Since both the parameter and the return value are forced to be the same type, that type can't change:

    // This doesn't work:
    override func getAnimal() -> Cat
    override func setAnimal(animal: Cat)

    // Neither does this:
    override func getAnimal() -> Thing
    override func setAnimal(animal: Thing)

Generics
How about generics? Given some type with a generic parameter, when does this work?

    let var1: SomeType<A> = ...
    let var2: SomeType<B> = var1

In theory, it depends on how the generic parameter is used. A generic parameter does nothing on its own, but is used as property types, method parameter types, and method return types.

If the generic parameter was used purely for method return types and read-only properties, then it would work if B were a supertype of A:

    let var1: SomeType<Cat> = ...
    let var2: SomeType<Animal> = var1

If the generic parameter was used purely for method parameter types, then it would work if B were a subtype of A:

    let var1: SomeType<Animal> = ...
    let var2: SomeType<Cat> = var1

If the generic parameter was used both ways, then it would only work if A and B were identical. This is also the case if the generic parameter was used as the type for a read-write property.

That's the theory. It's a bit complex and subtle. That's probably why Swift takes the easy way out. For two generic types to be compatible in Swift, they must have identical generic parameters. Subtypes and supertypes are never allowed, even when the theory says it would be acceptable.

Objective-C actually does this a bit better. A generic parameter in Objective-C can be annotated with __covariant to indicate that subtypes are acceptable, and __contravariant to indicate that supertypes are acceptable. This can be seen in the interface for NSArray, among others:

    @interface NSArray<__covariant ObjectType> : NSObject ...

Covariance and Contravariance
The astute reader may notice that the title of the article contains these two terms which I have carefully avoided using this whole time. Now that we're firm on the concepts, let's talk about the terminology.

Covariance is when subtypes are accepted. Overridden read-only properties are covariant.

Contravariance is when supertypes are accepted. The parameters of overridden methods are contravariant.

Invariance is when neither supertypes nor subtypes are accepted. Swift generics are invariant.

Bivariance is when both supertypes and subtypes are accpted. I can't think of any examples of bivariance in Objective-C or Swift.

You may find the terminology hard to remember. That's OK! It's not really that important. As long as you understand subtyping, supertyping, and what causes a subtype or supertype to be acceptable in any given place, you can just look up the terminology in the unlikely event that you need it.

Conclusion
Covariance and contravariance determines when a subtype or supertype can be used in place of a type. It most commonly appears when overriding a method and changing the argument or return types, in which case the return type must be a subtype, and the arguments must be supertypes. The guiding principle behind this is Liskov substitution, which means that an instance of a subclass must be usable anywhere an instance of the superclass can be used. Subtype and supertype requirements can be derived from this principle.

That's it for today. Come back for more exciting adventures. Or just come back for exciting adventures; "more" is probably out of place, since covariance is not exciting. In any case, Friday Q&A is driven by reader suggestions, so if you have a suggestion for an article here, please send it in!

Did you enjoy this article? I'm selling a whole book full of them. It's available for iBooks and Kindle, plus a direct download in PDF and ePub format. It's also available in paper for the old-fashioned. Click here for more information.

Comments:

George Kulakowski at 2015-11-20 16:57:43:
Nice post!

You're right that bivariance doesn't come up much in Swift (or Java or...). All you could do with a bivariant type parameter is use it to construct other bivariant generic types, or to not use it (and why might you want to do that?).

https://people.cs.umass.edu/~yannis/variance-extended2011.pdf talks about variance, and 3.3 about a setting where bivariant types could come into play, with recursive types. It's pretty readable, as these things go.

https://github.com/rust-lang/meeting-minutes/blob/master/workweek-2014-08-18/markers-variance.md and https://github.com/rust-lang/rfcs/blob/master/text/0738-variance.md talk about variance in Rust, where the interactions with lifetimes make things a bit more interesting. (I'm not sure how up-to-date these are, may not reflect Rust today, etc.)

Rick at 2015-11-20 22:09:06:
Even more complex and subtle: part of the deal with __covariant showing up in ObjC and NSArray might be compatibility/bridging with Swift.

Swift generics are normally invariant, but the Swift standard library collection types — even though those types appear to be regular generic types — use some sort of magic inaccessible to mere mortals that lets them be covariant.

Take a look... here's a quick concrete example of invariant generic types in Swift:

import UIKit

class Thing<T> { // could be a struct just as well
    var thing: T
    init(_ thing: T) { self.thing = thing }
}
var foo: Thing<UIView> = Thing(UIView())
var bar: Thing<UIButton> = Thing(UIButton())
foo = bar // error: cannot assign value of type 'Thing<UIButton>' to type 'Thing<UIView>'

But Array lets you do the same thing without error:

var views: Array<UIView> = [UIView()]
var buttons: Array<UIButton> = [UIButton()]
views = buttons

(Note that if you tried to assign buttons = views instead, you'd get an error: Swift collections are covariant, not contravariant or bivariant.)

Kyle McAlpine at 2015-11-21 11:45:33:
Thanks for this Mike! Just as I posted a SO question on this topic! Haha!

http://stackoverflow.com/questions/33752968/swift-cast-generic-type-into-same-generic-type-but-with-a-subclass-of-associate/33759858#33759858

J at 2015-11-21 16:22:07:
I think "subtype" and "supertype" are reversed in the Standalone Functions section

Applied here, the above code works if A is a subtype of C, and if B is a supertype of D.

should be

Applied here, the above code works if A is a supertype of C, and if B is a subtype of D.

Matthew Cheok at 2015-11-21 16:58:15:
Suppose the discussion for subclass applies to protocols as well? Thanks for this! It's succinct and easily digestible. I find it more helpful to replace A, B and C with something I'm more familiar with like NSObject, UIView and UILabel.

mikeash at 2015-11-21 18:00:20:
J: Thanks, fixed now. This stuff still does mix me up sometimes.

Matthew Cheok: It looks like protocols don't support changing types at all. If you take a protocol that inherits from another protocol and try to "override" the super-protocol's function with one that has different types, Swift just treats it as a new function regardless of variance. You can try this code to see:

class Thing {}
class Animal: Thing {}
class Cat: Animal {}

protocol SuperP {
    func f(animal: Animal) -> Animal
}

protocol SubP1: SuperP {
    func f(thing: Thing) -> Cat
}

protocol SubP2: SuperP {
    func f(cat: Cat) -> Thing
}

class ImplementsSubP1: SubP1 {
    func f(thing: Thing) -> Cat {
        return Cat()
    }
}

class ImplementsSubP2: SubP2 {
    func f(cat: Cat) -> Thing {
        return Thing()
    }
}


Neither of the two classes are considered to fully implement the protocols. If you add a second f to each class that's Animal -> Animal then it works.

Sven at 2015-11-22 10:36:28:
I believe subtype and supertype are mixed up in the Generics section as well. Method return types and r/o properties should be subtypes and method parameters should be supertypes, right?

VinDuv at 2015-11-23 12:36:19:
There is an interesting problem with generic collection covariance: it potentially allows objects of the wrong type to be inserted in the collection.

I’m told that the first version of Java had covariant arrays without sufficient protection, which allowed to downcast objects without compile time or runtime checks:

// Cat is a subclass of Animal
Cat[] cats = ...;
Animal[] animals = cats; // Array covariance is allowed
animals[0] = new Dog(); // Putting a Dog into an array of Animal: no complaint from the compiler, no runtime check
Cat cat = cats[0]; // We try to get a Cat from the array of Cat but it’s a Dog!
cat.purr(); // invalid method call, will probably crash the JVM

On current Java implementations, the above code still compiles, but the assignation to animals[0] fails with an ArrayStoreException.

Fortunately, with Swift’s copy-on-write arrays, this code is perfectly fine: the assignment of animals[0] will create a copy of the array, so cats will still only contain Cats.

Maybe this Array-specific feature could be provided to custom generic container types, but I’m not sure if it’s doable in a “safe” (compiler-checked) manner.

Spud at 2015-12-11 20:33:08:
the way you wrote:

    let returnsCat: () -> Cat = animalF

and started the following paragraph "All of this works in Objective-C too,d" made me think that was legal. suggest putting a comment beside it like // illegal

Saurav Nagpal at 2016-06-06 10:04:18:
Hi Mike

let returnsCat: () -> Cat = animalF

I think this will not work. Because return Cat is subtype of function animalF. As you said superTypes cannot substitute subtypes.

mikeash at 2016-06-08 01:54:25:
Right, the first line works, the second line doesn't.

Escorts in 5 Star Hotel in Gurgaon at 2017-02-25 06:20:56:
Thank you for sharing a great information and useful.


Comments RSS feed for this page

Add your thoughts, post a comment:

Spam and off-topic posts will be deleted without notice. Culprits may be publicly humiliated at my sole discretion.

Name:
Web site:
Comment:
Formatting: <i> <b> <blockquote> <code>. URLs are automatically hyperlinked.
Code syntax highlighting thanks to Pygments.
Hosted at DigitalOcean.