# Understanding Generic Type Variance (in Whiley)

For languages which support generic
types, an
important question is deciding whether or not a type `C<T>`

is a
*subtype* of another related type `C<S>`

. Since Whiley was recently
extended to support generic types, its interesting to think about how
this was handled. Firstly, let’s recap subtyping in Whiley:

```
type nat is (int n) where n >= 0
```

This defines a type `nat`

as a *subtype* of `int`

, meaning we can assign a `nat`

to an `int`

(but not the other way around). This makes sense as every value of `nat`

is an `int`

but not every `int`

is a `nat`

(e.g. `-1`

).

### Example 1

Let’s add a simple generic type to illustrate:

```
type Box<T> is { T item }
```

*The question arising is whether or not Box<nat> is a subtype of Box<int>?* Well, yes, this makes total sense! For example, the following is allowed:

```
Box<nat> b1 = {item:0}
Box<int> b2 = b1
```

In contrast the following is (quite rightly) not allowed:

```
Box<int> b1 = {item:-1}
Box<nat> b2 = b1
```

The above is not allowed because `{item:-1}`

is clearly not a valid instance of `Box<nat>`

.

### Example 2

Now, let’s add another simple generic type:

```
type Pred<T> is function(T)->(bool)
```

Here, `Pred<int>`

represents a lambda which accepts an `int`

and
returns a `bool`

. *So, is Pred<nat> a subtype of Pred<int>?* This is an interesting question. Let’s create a function to illustrate:

```
function f_n(nat x) -> (bool r):
...
```

I’ve left out the function body here, since it isn’t important. If `Pred<nat>`

is a subtype of `Pred<int>`

, then the following should be allowed:

```
Pred<int> p = &f_n
bool y = p(-1)
```

(Here, `&f_n`

returns a reference to function `f_n()`

and has type `Pred<nat>`

)

*But, isn’t there a problem here?* Yes, there is! If `Pred<nat>`

is a subtype of `Pred<int>`

then (as illustrated above) we can call `f_nat(-1)`

— *which does not make sense*.

### Recap

In summary, `Box<nat>`

should be a subtype of `Box<int>`

, but `Pred<nat>`

should *not* be a subtype of `Pred<int>`

. *So, for a given type C<T>, how can we tell which way around it is?* Good question! We need some theory here:

**(Covariance)**If`C<T>`

is a subtype of`C<S>`

whenever`T`

is a subtype of`S`

, we say that`T`

is*covariant*in`C<T>`

.**(Contravariance)**In contrast, if`T`

is*contravariant*in`C<T>`

, then`C<T>`

is a subtype of`C<S>`

whenever`T`

is a*supertype*of`S`

.**(Invariance)**Finally, we can say that`T`

is*invariant*in`C<T>`

meaning that (like Java without wildcards)`C<T>`

is*never*a subtype of`C<S>`

(unless`T=S`

).

From this, it follows that `Box<T>`

is *covariant* in `T`

, whilst `Pred<T>`

is *contravariant* in `T`

. *But how do we know this?* Well, roughly speaking, it really stems from the fact that `function(T)->(S)`

is *contravariant* in `T`

and *covariant* in `S`

. Therefore, any generic type containing a `function`

type is constrained accordingly. For example:

```
type BoxFn<T> is {
function test(T)->(bool),
...
}
```

The presence of field `test`

imposes a constraint that `BoxFn<T>`

cannot be *covariant* in `T`

. However, it can still be contravariant — but this depends on what other fields it contains. For example, the following variation is contravariant in `T`

:

```
type BoxFn<T> is {
function test(T)->(bool),
int value
}
```

In contrast, the following is *invariant* in `T`

:

```
type BoxFn<T> is {
function test(T)->(bool),
T value
}
```

The reason this is invariant is that the field `T value`

imposes a constraint that `T`

cannot be contravariant. Combining the constraints from both fields leaves only one possibility!

### Conclusion

Whiley follows
Rust in adopting
*definition-site variance* for generic types which (for example)
differs from the approach taken in Java. This means the permitted
subtyping relationships for a type are determined at its
definition-site (i.e. declaration). In contrast, Java supports
*use-site variance* through wildcards (e.g. we can give `ArrayList<? extends Number>`

for a variable’s type). Obviously there are some
pros/cons here, but that’s a story for another day…

## References

*Taming the Wildcards: Combining Definition and Use-Site Variance*, J. Altidor, S. Huang and Y Smaragdakis. In*PLDI'11*. PDF

*Follow the discussion on Twitter*