COMP 310	Covariance and Contravariance of Hosts and Visitors

In his book Effective Java, Joshua Bloch coined the pneumonic device PECS: Producer Extends, Consumer Super. This device can help us remember which Java keyword (extends or super) to use when specifying the bounds on generic types.   Let's explore how this idea can be applied to a Visitor Design Pattern system of hosts and visitors.

Example

Let's say that we have some generic boxes that can hold whatever we want.

class Box<T> { ... }

Let's say that we also have some operations that we want to perform on these boxes. We implement these actions using a visitor, parameterized on the type of data contained in the host box U and the result type of the operation R.

class BoxVisitor<U, R> { ... }

We'll assume three classes of objects we might put in our boxes.

Fuel

>

Plants

>

Bamboo

Above, the > sign designates a substitutability relationship. Since Fuel > Plants, we can use Plants anywhere that simply requires a Fuel. This is because plant matter is a type of fuel. Similarly, since Bamboo is a type of plant, we can use Bamboo anywhere that requires Plants or Fuel; therefore, Plants > Bamboo and Fuel > Bamboo. This is the subtype relationship that we're so familiar with.

We'll also assume three classes of objects that might want to do something with our boxes (i.e. our visitors).

Consumer of anything that burns

<

Consumers of plants

<

Consumers of bamboo

Interestingly, the substitutability relationship goes in the opposite direction here. Although a panda is a type of herbivore, we see that Herbivore < Panda. This is because, although pandas are a subset of the herbivores, the panda's dietary restrictions prevent us from substituting it for a general consumer of all plants. However, since the class herbivores should be able to eat any kind of plant, we could substitute a consumer of plants anywhere that we need a consumer of bamboo. The class declaration for pandas might look like the following.

class Panda<R> extends BoxVisitor<Bamboo, R> { ... }

Covariance of Boxes

Boxes are hosts. Hosts are producers because they just provide the data for some action by a visitor. Therefore, host types should use the extends keyword to create an upper-bounded generic type (remember: Producer Extends). An upper-bounded type parameter implies that this is a covariant relationship.

if you need to feed a...		you can give it a...

class BoxVisitor<U, R> {
    public R visit(Box<? extends U> host) {
      // ...
    }
}

Contravariance of Visitors

Our BoxVisitors are consumers because they consume the data provided by the host and apply some action. Therefore, visitor types should use the super keyword to create a lower-bounded generic type (remember: Consumer Super). A lower-bounded type parameter implies that this is a contravariant relationship.

if you have a...		you can give it to...

class Box<T> {
    public <R> R accept(BoxVisitor<? super T, R> visitor) {
      // ...
    }
}

Relation to Function Subtyping

Visitors are basically just an implementation of a function. As such, the same rules apply for visitor subtyping as for function subtyping.  As such, the argument (host-data) type-parameter should be contraviarant, and the return-type should be covariant. 

public <R> R accept(Visitor<? super T, ? extends R> visitor) { ... } 

However, looking at our earlier declaration for a host's accept method

public <R> R accept(Visitor<? super T, R> visitor) { ... } 

we see that R is not declared covariantly.   Remember that since the type parameter R is declared on the method (not on the class), R will be bound to the visitor argument's declared return type at each location where the method is invoked. Also remember that the result of the accept method can be assigned to any variable with a type that is a super-type of R (by the normal covariant value assignment rules afforded by polymorphism). Thus, there is no loss of generality by omitting an explicit covariant declaration for R in the host's accept method because the covariance is handled automatically by assignments of the return value.

Note that we would need an explicitly covariant type parameter in accept if the type parameter R were declared on the host class rather than on the accept method—but we don't want to declare R at the level of the class since R is not an invariant of the host class.

For a more code-oriented discussion of this topic please see Covariant and Contravariant Generic Relationships in OO Systems.

The images in this page are licensed under the Creative Commons Share-Alike License. The producer/consumer figures were adapted from a wonderful diagram by Andrey Tyukin (local copy of diagram).

Many thanks to Nick Vrvilo for generously researching and writing this page.

© 2017 by Stephen Wong