Covariance and Contravariance in Generic types
When I first started studying academic computer science (as opposed to just plain-old programming) in the late 80's, a lot of attention was paid to sorting routines and linked lists. I'm not sure how they teach this stuff these days, but back then, sorting routines were your introduction to algorithms and linked lists and hash maps were your introduction to data structures. I missed the object-oriented revolution by a few years — there was an elective course on object oriented programming, but we did all of our assignments in procedural programming languages like C and Pascal. That meant that, if you wanted linked list, you had to code it yourself from pointer primitives.
Why are dynamic lists important? It didn't escape the attention of early programming researchers that most practical computer programs operated on lists of similar data elements: a payroll system operated on a list of employees, an ordering system operated on a list of line items, and a billing system operated on a list of customers. If the programmer knew in advance how long the list would be, it was a simple matter to allocate a static array to store the elements. A list of, say, the tax rates for all 50 states could be stored in 50 consecutive memory locations: the number of states isn't going to change while the program is running. In most cases, though, the lists would grow and shrink dynamically during operation, so the programmer was faced with a choice: pick an arbitrary maximum and allocate enough (contiguous) memory for that maximum or create a dynamic memory structure.
So, given an employee
definition like:
typedef struct {
char *first_name;
char *last_name;
float annual_salary;
float tax_rate;
float deductions;
} employee;
If the programmer can assume that the employee records occupy contiguous memory, iterating over them is straightforward:
employee employees[MAX_EMPLOYEES];
int num_employees = load_all_employees(employees);
for (int i = 0; i < num_employees; i++) {
float weekly_pay = employees[i].annual_salary / 52;
weekly_pay -= (weekly_pay * employees[i].tax_rate) + employees[i].deductions;
printf("Pay %s %s $%.2f\n", employees[i].first_name, employees[i].last_name, weekly_pay);
}
But there are a couple of problems with assuming contiguous memory: first, you have to put an upper limit on how many elements can be stored; if the input exceeds that limit, the program is unusable. Second, if the input is smaller than the maximum, the unused memory goes to waste.
One way to solve the first problem is to allocate a fixed amount of memory for the list, but allow it to grow dynamically by copying it
to a larger memory area when it exceeds its bounds. However, this means that you need a dedicated addEmployee
function to
grow the array; the memory area that it applies to is now being managed by that addEmployee
function. You can't read from
the memory area directly either, because the pointer will change when the memory is resized. Now you need a data structure to manage the
list itself:
typedef struct {
employee *employees;
int list_size;
int num_employees;
} employee_list;
#define GROW_LIST_AMOUNT 50
static void add_employee(employee_list *list,
const char *first_name,
const char *last_name,
float annual_salary,
float tax_rate,
float deductions) {
if (list->num_employees == list->list_size) {
employee *old_list = list->employees;
list->employees = (employee *) malloc(sizeof(employee) * (list->list_size + GROW_LIST_AMOUNT));
memcpy(list->employees, old_list, sizeof(employee) * list->list_size);
list->list_size += GROW_LIST_AMOUNT;
free(old_list);
}
list->employees[list->num_employees].first_name = first_name;
list->employees[list->num_employees].last_name = last_name;
list->employees[list->num_employees].annual_salary = annual_salary;
list->employees[list->num_employees].tax_rate = tax_rate;
list->employees[list->num_employees].deductions = deductions;
list->num_employees++;
}
...
employee_list employees;
load_employees(employees);
for (int i = 0; i < employees.num_employees; i++) {
float weekly_pay = employees.employees[i].annual_salary / 52;
weekly_pay -= (weekly_pay * employees.employees[i].tax_rate) + employees.employees[i].deductions;
printf("Pay %s %s $%.2f\n", employees.employees[i].first_name, employees.employees[i].last_name, weekly_pay);
}
Now, rather than just declaring a static array of MAX_EMPLOYEES
, you declare an indirect data structure and access the list
through it. Solving the second problem — the problem of unused memory — is even trickier; the general solution to this
problem is to use a linked list. Rather than dynamically copying the array to a new location each time the bounds are exceeded, each
record (e.g. employee
) points to the next one in the list.
typedef struct employee_struct {
const char *first_name;
const char *last_name;
float annual_salary;
float tax_rate;
float deductions;
struct employee_struct *next;
} employee;
...
static employee *add_employee(employee *head,
const char *first_name,
const char *last_name,
float annual_salary,
float tax_rate,
float deductions) {
employee *new_employee = malloc(sizeof(employee));
new_employee->first_name = first_name;
new_employee->last_name = last_name;
new_employee->annual_salary = annual_salary;
new_employee->tax_rate = tax_rate;
new_employee->deductions = deductions;
new_employee->next = (struct employee_struct *) head;
return new_employee;
}
...
employee *head = NULL;
head = load_all_employees(head);
for (employee *emp = head; emp != NULL; emp = emp->next) {
float weekly_pay = emp->annual_salary / 52;
weekly_pay -= (weekly_pay * emp->tax_rate) + emp->deductions;
printf("Pay %s %s $%.2f\n", emp->first_name, emp->last_name, weekly_pay);
}
There are, of course, endless variations on this theme - doubly-linked lists (to allow dynamic removal of items, which neither of these
two implementations address), red-black trees that keep elements in a sorted order, queues, stacks, hash maps, etc. all of which beginning
computer science students spend semesters mastering. But once you do master — or at least obtain a decent understanding of —
these data structures, there's a temptation to want to implement them once and re-use that implementation over and over again. This is
notoriously hard to do in a purely procedural programming language, though. Notice that the declaration of employee
in
listing 4 is self-referential (and has to use an awkward syntax as a result). If you wanted to try to genericize this, you'd have to
do something like listing 5:
typedef struct node_struct {
void *data;
struct node_struct *next;
} node;
static node *add_node(node *head,
data *data) {
node *n = malloc(sizeof(node));
n->data = data;
n->next = (struct node_struct *) head;
return n;
}
This sort of helps separate the list manipulation from the structure itself, but now iterating over it becomes the very awkward:
for (node *emp = head; emp != NULL; emp = emp->next) {
float weekly_pay = ((employee *) emp->data)->annual_salary / 52;
weekly_pay -= (weekly_pay * ((employee *) emp->data)->tax_rate) + ((employee *) emp->data)->deductions;
printf("Pay %s %s $%.2f\n", ((employee *) emp->data)->first_name, ((employee *) emp->data)->last_name, weekly_pay);
}
This isn't only ugly, it's dangerous - if some part of the program accidentally assigned the wrong pointer type there, you'd get a run-time
rather than a compile time error. The C programming language just isn't equipped to provide good static typing in this scenario —
in fact, if you go back and look at a lot of the early academic papers on object-oriented programming, they didn't talk about
Dog
inheriting Animal
or Car
inheriting Vehicle
; they talk about this sort of thing.
Any Java programmer can get an auto-grow list like the one in listing 3 or a linked list like in listing 5 "for free" with Java's built-in
ArrayList
and LinkedList
, respectively. However, until JDK 1.5, the Java implementations of these data
structures, as well as more advanced structures like HashMap and TreeMap suffered from the same problem in listing 5, above: they were
containers of Java's Object
class, the equivalent of C's void *
pointer. That meant that if you did something
like listing 7:
class Employee {
String firstName;
String lastName;
float annualSalary;
float taxRate;
float deductions;
}
...
List employees = new ArrayList();
employees.add("abcdef");
Iterator it = employees.iterator();
while (it.hasNext()) {
Employee emp = (Employee) it.next();
}
The code would compile with no warnings, only to fail with "Exception in thread "main" java.lang.ClassCastException: class java.lang.String cannot be cast to class Employee
"
at runtime. There was no way to declare that a collection was of a specific type until the introduction of generics with the
1.5 release of the language.
Although technically you could generify anything, generics were typically used to provide compiler-time type checking to collections. Now, listing 7 becomes:
List<Employee> employees = new ArrayList<>();
employees.add("abcdef"); // compile error here
It took a while to get generics in Java not because nobody thought of it (C++ had a similar feature named templates from it's first release) but because of the covariance/contravariance problem which I'll discuss below.
Conceptually, what happens when you declare new ArrayList<Employee>()
, it's as if a new class definition is dynamically
created. The java.util.ArrayList
code itself looks something like:
public class ArrayList<E> implements List<E> {
private static final int GROW_LIST_AMOUNT = 50;
private E[] elements;
private int size;
private int count;
public ArrayList() {
size = GROW_LIST_AMOUNT;
elements = new E[size];
count = 0;
}
public void add(E e) {
if (count == size) {
E[] old = elements;
elements = new E[size + GROW_LIST_AMOUNT];
System.arraycopy(old, 0, elements, 0, size);
size += GROW_LIST_AMOUNT;
}
elements[count++] = e;
}
...
This doesn't actually compile because Java doesn't allow generic array creation like this, but this is the concept, anyway.
E
in the type declaration specifies a placeholder for a class which will be named at instantiation time. When you
instantiate a new ArrayList
, the compiler behaves as if you had done something like:
public class ArrayList_Employee implements List_Employee {
private static final int GROW_LIST_AMOUNT = 50;
private Employee[] elements;
private int size;
private int count;
public ArrayList() {
size = GROW_LIST_AMOUNT;
elements = new Employee[size];
count = 0;
}
public void add(Employee e) {
if (count == size) {
Employee[] old = elements;
elements = new Employee[size + GROW_LIST_AMOUNT];
System.arraycopy(old, 0, elements, 0, size);
size += GROW_LIST_AMOUNT;
}
elements[count++] = e;
}
...
Now, if you try to pass a String
into add
, the compiler flags it as an error. You can also supply subclasses
of Employee
here, again just as if you had created a new class. Most newcomers to Java's generics
are surprised, though, when something like listing 11 fails:
class Person {
String firstName;
String lastName;
}
class Employee extends Person {
float annualSalary;
}
public class Covariance {
private static void processPeople(List people) {
for (Person p : people) {
System.out.println(p.lastName + ", " + p.firstName);
}
}
...
List<Employee> employees = new ArrayList<>();
employees.add(new Employee());
processPeople(employees);
However, in light of listing 10, it's obvious why this fails to compile: you have (conceptually, at least) two separate classes now
named ArrayList_Employee
and ArrayList_Person
with no inheritance relationship between the two. One can't
be cast to the other (not even with a manual typecast). This seems like an unnecessary limitation: the compiler hasn't stopped me from shooting myself in the foot
in this case. I can treat Employee
objects as if they were Person
objects after all — in this implementation, I'm
just accessing the first and last name parameters, which Employee
objects definitely do have.
The problem here, though, is that the list object is writable. The compiler is protecting me from making this mistake:
class Person {
String firstName;
String lastName;
}
class Employee extends Person {
float annualSalary;
}
class Customer extends Person {
float amountDue;
public Customer(float amountDue) {
this.amountDue = amountDue;
}
}
...
private static void processPeople(List people) {
people.add(new Customer(100.0F));
}
...
List<Employee> employees = new ArrayList<>();
employees.add(new Employee());
processPeople(employees);
for (Employee e : employees) {
System.out.println("Pay " + e.annualSalary);
}
If the compiler didn't stop me from passing the employee list to the processPeople
function, I'd get an error at
the end when I tried to dereference what was supposed to be a list of employees. Note that there's no way to define generics in such a
way that people.add(new Customer(100.0F))
is invalid: Customer
is a subclass of Person
and, by
definition, can be substituted anywhere a Person
is required.
This is where wildcards come in. In Java, you can re-declare the type definition like this:
private static void processPeople(List<? extends Person> people) {
This will compile and run as expected given listing 11. What about listing 12? Well, if you try to add a Customer
to a
List<? extends Person>
, you'll get a very cryptic error message:
error: incompatible types: Customer cannot be converted to CAP#1
CAP#1 refers to the wildcard capture. The javac
designers decided that the error message
cannot be converted to CAP#1
was better than cannot be converted to ? extends Person
for various internal
reasons that must have made sense at the time but effectively CAP#1
refers to the type of the declared list which, in this
case, is ? extends Person
. But wait, you may say, why not just Person
? Wouldn't it be OK to add a
new Person()
object to this list? Surely that would be safe, right?
Actually, no: we run into the same type-replacement problem we ran into before. Again, by definition, the compiler should accept a subclass
of Person
wherever it accepts a Person
. So ? extends Person
is not equivalent to
Person
here - if it were, somebody could do something like people.add((Person) new Customer())
(and let's be
realistic, somebody with a deadline would do exactly that). So, somewhat counterintuitively, even people.add(new Person())
throws the same error. This is why extends
isn't the default: you have to specifically declare that the function is
covariant this way.
You can actually do this in the other direction: you can declare that the collection can contain any supertype
of a particular
class. While most programmers are initially surprised that List<Employee>
isn't compatible by default with
List<Person>
, once they understand how to declare covariance, they're again surprised that the opposite —
contravariance — is specified at all. However, contravariance is probably what you actually want in the case I encountered
in listing 12: I'm trying to add a new Customer
to the list. If I'm passing a list into another method to be populated,
I (often) want it to be able to insert any of the supertypes of that list, but almost never the subtypes.
Suppose you had an in-memory cache of Customer
objects and you wanted to add some of them to a list of type Person
,
say to build a mailing list. If addToMailingList
were declared like this:
public void addToMailingList(List<Person> target) {
target.addAll(customers);
}
List<Customer> customers = new ArrayList<>();
addToMailingList(customers);
...
List<Person> people = new ArrayList<>();
addToMailingList(people);
This wouldn't compile. You could re-declare the parameter of addToMailingList
as List<Customer>
, but
then you wouldn't be able to pass in an actual list of Person
. Nor can you re-declare it as
? extends Person
to work around this — that's exactly the case that covariance prohibits. Instead, declaring this as:
public void addToMailingList(List<? super Customer> target) {
target.addAll(customers);
}
List<Customer> customers = new ArrayList<>();
addToMailingList(customers);
...
List<Person> people = new ArrayList<>();
addToMailingList(people);
allows this case to compile and run correctly. Contravariance is less common than covariance, but it does come in handy in some
cases: Comparator
implementations, for
example.
Note that you can't declare a class Co- or contra-variant in Java. That is, you can't do this:
public class CustomArrayList<? extends E> {
Since covariance is usually for reading types and contravariance for modifying them, it doesn't make sense in Java to specify this as part
of the class definition itself. In Scala, which favors immutable variables, on the other hand, parameterized types can and usually
do specify variance. Since Scala declares its List
type as List[+A]
(where the +
indicates
covariance), Scala lists are by default compatible with lists of their subclasses by default.