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;
Listing 1: Employee structure
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);
}
Listing 2: Paying them
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);
}
Listing 3: Dynamically grow array
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);
}
Listing 4: Linked list
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;
}
Listing 5: Generic node pointers
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);
}
Listing 6: accessing void pointers
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();
}
Listing 7: add the wrong type to a Java ArrayList
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
Listing 8: compile-time type checking
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;
}
...
Listing 9: java.util.ArrayList (sort of)
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;
}
...
Listing 10: Concrete array list
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);
Listing 11: Trying to cast a list of Employee to a list of People
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);
}
Listing 12: adding a customer to a list of employees
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) {
Listing 13: accepting a list of employees
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);
Listing 13: adding people and customers to customer mailing list (wrong)
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);
Listing 14: Adding people and customers to customer mailing list (right)
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> {
Listing 15: Covariant class (not allowed)
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.
Add a comment:
Completely off-topic or spam comments will be removed at the discretion of the moderator.
You may preserve formatting (e.g. a code sample) by indenting with four spaces preceding the formatted line(s)
