Generic Variance — Fundamental Principles

Demystifying variance once and for all — explaining the fundamental principles of variance from the bottom up, using assignability of functions.

— — — — — — — — — — — — — — —

THE CURRENT VERSION OF THIS ARTICLE IS PUBLISHED HERE.

— — — — — — — — — — — — — — —

Tags: #FYI++

This article is part of the Kotlin Primer, an opinionated guide to the Kotlin language, which is indented to help facilitate Kotlin adoption inside Java-centric organizations. It was originally written as an organizational learning resource for Etnetera a.s. and I would like to express my sincere gratitude for their support.

It is recommended to read the Introduction before moving on. Check out the Table of Contents for all articles.

The basic question we posed in the previous article is this: Can we, and when can we, take code (a class, a function) that was generated (using generics) for a Dog type and use it in place of code generated for an Animal type? Can we vary the generic type? And if so, under what conditions? More technically, when there is a sub-/super-type relationship between some types, does it, and when can it, translate to some sub-/super-type relationship between generic constructs using those types?

This is the question I’ll be answering in this article. But in order to do so, we first need to understand something about generics.

In a sense, generics always generate functions

To see why this is so, let’s break down the only two things that can be generated via generics: classes, and functions.

(Generic) functions are, well, functions, so that part is obvious. (Generic) classes are collections of methods (which are functions) and properties, which, in Kotlin, are represented by a getter and possibly a setter — both of them functions.

Why is this important? Because, if we accept that generic constructs are simply instructions for generating a set of functions, to determine the situations when one such construct can be used in place of another, all we need to do is answer this: under what conditions can one function type be used in place of a different function type?

val f1: <SomeFunctionType> = <something>

// When can we do this?
val f2: <SomeOtherFunctionType> = f1

Once we’ve answered that, answering the same question for generic constructs is easy — one construct can be used in place of another if all the functions generated in one can be used in place of the corresponding functions of the other.

Take a minute to absorb that before reading on.

Assignability of functions

First, let’s get the obvious out of the way — obviously, all the types appearing as arguments in one function must be sub-or-super-types of the types of corresponding arguments in the other function. There is no way a String can be assigned to an Int, so there’s no way to assign a function accepting or returning an Int to a function accepting or returning a String. The same goes for return values. There is also no way to mix functions accepting a different number of arguments.

In other words, it makes no sense to study functions whose structures are different and whose corresponding argument/return value types are not related to one another via inheritance.

We also know that if the second function has exactly the same types as the first one, it is obviously assignable, so we'll also skip that. That leaves four different scenarios:

• Assigning a function with a more general (i.e. supertype) argument and the same type of return value
• Assigning a function with a more specific (i.e. subtype) argument and the same type of return value
• Assigning a function with a more specific (i.e. subtype) return value and the same type of argument
• Assigning a function with a more general (i.e. supertype) return value and the same type of argument

Let’s go through them, one by one.

Is a function with a more general argument assignable?

Yes.

This works, because ::f1 accepts an Int and an Int is a Number, so ::assignedFun accepts it too. In other words, if the return values are compatible, any function accepting a supertype argument is assignable.

Intuitively, any function that can compute the same result from less information (i.e. a supertype instance) can be used — if we have an algorithm that works for Number, it will definitely work for Int.

This means that even though Number is a supertype of Int, (Number) -> CharSequence is a subtype of (Int) -> CharSequence, because you can assign the former to the latter.

Is a function with a more specific argument assignable?

No.

Intuitively, we can’t pretend we can create a CharSequence out of anything when we only know how to create a CharSequence out of Numbers. If we have an algorithm that works for Number, it sure as shit doesn’t mean we have an algorithm that works for Any.

This means that (Number) -> CharSequence is not a subtype of (Any) -> CharSequence. It is in fact its super-type, as we saw above, which is another reason why the answer is ‘no’ — a type cannot be a super-type and a subtype of another type at the same time!

Is a function with a more specific return value assignable?

Yes.

This works, because ::assignedFun returns a CharSequence and a CharSequence is an Any, so this conforms with ::f3's type. In other words, if the arguments are compatible, any function returning a subtype of the original's return value is assignable.

Intuitively, any function that can compute a more specific result (i.e. a subtype instance) from the same amount information can be used — if we have an algorithm that produces a CharSequence, it can definitely produce (actually, it is producing) an Any.

This means that, since CharsSequence is a subtype of Any, (Number) -> CharSequence is a subtype of (Number) -> Any.

Is a function with a more general return value assignable?

No.

Intuitively, we can’t pretend we know how to create Strings when all we know is how to create CharSequences. This means that, (Number) -> CharSequence is not a subtype of (Number) -> String. It is in fact its super-type, as we saw above, which, again, is another reason why the answer is ‘no’ — one cannot be both a subtype and the super-type of another type.

We can see that, when we want to substitute one function for another, we can vary the types in opposite directions — types that go in can be any super-type, while types that come out can be any subtype. The words we used in this sentence — in, out — are no coincidence, and are the basis of technical jargon that will be discussed in the following chapter.

Also, notice that a problem arises when a type goes both in and out:

This is precisely why problems arose when we changed val to var in the Result example of the previous chapter. As long as the value property was val, there was no place in Result where T went in — it always went out (val only generates getters). However, once we changed it to var, we suddenly got both a getter (where T comes out) and a setter (where a T goes in). Same with Comparable — the type T goes in in the compareTo method, and out in the getter.

And that is the rule — when we write a generic construct where the generic variable goes in in some places, and out in others, it is impossible to consistently translate sub-/super-type relationships between different T’s to sub-/super-type relationships between generic constructs involving T’s, without allowing runtime errors to happen. If the T’s only go in, or only go out, it’s possible to do that, but it’s not required, and doesn’t happen automatically. The in situation is called contravariance, the out situation is called covariance, and we’ll talk about them more in the following chapter.

Understand that all of these facts follow directly from a single fundamental principle of OOP — that a subtype is only assignable to itself or its supertypes. All of the above is completely general, and not bound to any single language. It arises implicitly with any implementation of generics, in every language that observes this simple OOP principle.

Armed with this knowledge, let’s recap what variance is all about — it is about being able to determine which of the above scenarios is permissible for a certain generic construct. And the way you do that is by studying if the generic variable appears only in in positions, only in out positions, or a mix of both. That’s all there is to it.

The following chapter will talk about keywords in Kotlin (in and out) that you use when one of the above situations is permissible and you specifically want to allow it.

Go back to Generic Variance — Motivation, jump to the Table of Contents, or continue to Covariance, Contravariance, Invariance.