15 March, 2018

Invariants, Covariants and Contravariants

For one of the projects that I worked on, I needed to learn Scala and I encountered one particular problem while I was writing a trait (Scala's word for Java 'interface'):

trait DList[+T] {
  def isEmpty: Boolean  def value: T  def next: DList[T]
  def add(elem: T): DList[T]

Simple generic immutable dynamic linked list. However, 'add' method is the one that was causing a trouble during the compilation and message is somewhat incomprehensible: 'covariant type T occurs in contravariant position in type T of value elem'. What the hell is this and is there a workaround? I decided to do additional research and to solve this.

What I know so far:

I can't say that I never heard for terms, covariants and contravariants. It has something to do with the generic types and type parameter (those types in <> brackets) inheritance during the variable declaration. Very important: not during the class definition and not during the class instantiation. They appear (briefly) in Oracle's Java certification for Programmer II, so I will first explain what I know so far in Java:
Let's assume that we have a following relationship. For example: class Cat is a subtype of the Animal class

Relationship of animals

When you declare generic variable like this:
List<? extends Animal> covariantAnimalList;
this is called covariant, and when you declare generic variable like this:
List<? super Animal> contravariantAnimalList;
this is called contravariant.

All what I knew is that covariantAnimalList cannot add any Animal objects (or its subtypes), but it can return Animal objects. In fact, it will not accept any argument that is a generic type parameter.
For contravariantAnimalList I know that you can add any Animal object (or its supertypes), but you cannot return any Animal object from it. It will not return any value that is a generic type parameter.

They are commonly used in producer/consumer pattern, where you use covariant generic type to read (and maybe remove) data from the list or queue, while you use contravariant generic type for inserting data to the list or queue.

Now let's demystify what these variants really are. Examples are in Scala, but same definitions apply in Java too.


These variants define the inheritance relationship between type parameters. By default, type parameters in generic type do not have any relationship between themselves. So if Cat is a subtype of Animal and if it is a type parameter then there are no relationship between generic classes that uses them.
For example, if you have trait defined like this:
trait DList[T]
and declared values like this:
val animalList : DList[Animal]
val catList : DList[Cat]
There is no way that compiler will allow you to do something like this:
animalList = catList // compiler error
Cat and Animal may be related, but in scope of type parameter there are no relationship.
This is called invariance.

Of course, if you have:
val animalList : DList[Animal]
val animalLinkedList : LinkedList[Animal]
where LinkedList extends DList, then this is compiled without problems:
animalList = animalLinkedList
Remember, variance only defines relationship of generic type parameters, not generic classes itself.

Invariance Example


Covariant type is probably the one that you though that should be default:
Covariance Example

In scala, it is defined like this:
trait DList[+T]
Here, type parameters retain their relationship and previous example will work without problems:
val animalList : DList[Animal]
val catList : DList[Cat]
animalList = catList
Of course, this will not work:
val albinoCatList : DList[AlbinoCat]
val catList : DList[Cat]
albinoCatList = catList // compiler error


As name suggests, here, the type parameters relationships are reversed:
Contravariance Example

In scala, it is defined like this:
trait DList[-T]
As you suspected, this code will no longer compile:
val animalList : DList[Animal]
val catList : DList[Cat]
animalList = catList // compiler error
However, by everyone's surprise, these lines of code WILL compile:
val albinoCatList : DList[AlbinoCat]
val catList : DList[Cat]
albinoCatList = catList
Remember, in contravariance (look for the clue in the name) relationship between type parameters is reversed.

Covariant type T occurs in contravariant position in type T of value elem

Now, let's back to the problem from the beginning of the text and let me explain what could happen if compiler allowed such "hack".
Assume that we have developed such generic type:
trait Cage[+T] {
  def getVar: T  def setVar[T](elem: T): Unit

// this class will not compile, but let's assume that it can
class SteelCage[+T] extends Cage[T] {
  var captive: T
  override def getVar: T = captive
  override def setVar[T](elem: T): Unit = captive = elem
Class SteelCage expands from trait Cage and it is just a data holder with getters and setters. Of course, in Scala, you will almost never define mutable variables and you will need to modify your class logic to be immutable, but for the sake of the test we will let captive slip as var.

We will use our covariance figure:
Covariance with cages

Examine the following code:
val catCage : Cage[Cat] = new SteelCage[Cat]();  // 1
catCage.setVar(new Cat()) // 2
val animalCage : Cage[Animal] = catCage; // 3
animalCage.setVar(new Dog()) // 4

Let's walk through this code:
One line 1, we declared a value of type Cage[Cat] and assigned it an instance of SteelCage[Cat].
We then, in next line 2, set the variable to the Cat instance. So far everything is looking good.
Now, on line 3, we declare new value of type Cage[Animal] and reference value catCage, which is an instance of SteelCage[Cat] at runtime. Since that we are using covariance, this command is valid as Cage[Cat] is a subtype of Cage[Animal]
Now take a look at line 4. We are setting animalCage var to the instance of the Dog!! animalCage is defined as Cage[Animal] so Dog is acceptable, but at the runtime animalCage is actually an instance of SteelCage[Cat]!! This is an error, as we just slipped Dog into the Steel Cage that can accept only cats!!

This is the reason why this message exists 'covariant type T occurs in contravariant position in type T of value elem' (although you might get different compile error for different situation, but eventually you will get this one at the end). That is why, in covariance, you are not allowed to take an argument of type parameter, because, with the proper casting, you can end up at assigned variable that is not in the proper relationship.

Contravariant type T occurs in covariant position in type T of value elem

Let's see the contravariant example:
Here is our class in contravariant example (and yes most things will not compile):
// this class will not compile, but let's assume that it can
trait Cage[-T] {
  def getVar: T  def setVar[T](elem: T): Unit

// this class will not compile, but let's assume that it can
class SteelCage[-T] extends Cage[T] {
  var captive: T
  override def getVar: T = captive
  override def setVar[T](elem: T): Unit = captive = elem

Here is our contravariance figure:
Contravaraince with Cages

Let's look at a slightly different code:
val catCage : Cage[Cat] = new SteelCage[Cat]();  // 1
catCage.setVar(new Cat()) // 2
val albinoCatCage : Cage[AlbinoCat] = catCage; // 3
val albinoCat : AlbinoCat = albinoCatCage.getVar() // 4
First two lines are the similar from the previous example. Now, on line number 3 it gets more interesting. We are declaring albinoCatCage that references SteelCat[Cat]. By the rules of contravaraince this is perfectly fine as Cage[Cat] is a subtype of Cage[AlbinoCat]. Keep in mind that relationship between types Cat and AlbinoCat is reversed.
Line 4 is where the all hell broke lose. albinoCatCage will return an instance of Cat because albinoCatCage references an instance of SteelCage[Cat] which holds a Cat. However, value at the left side accepts only AlbinoCat type and its subtypes, and there is no way that it could have known that on runtime albinoCatCage will return a Cat instance which is a super type of AlbinoCat! You can, of course, change the type of albinoCat value to Cat, but Cage[AlbinoCat] clearly states that it can return AlbinoCat and all its subtypes, not its super types.
This is the reason why error 'Contravariant type T occurs in covariant position in type T of value elem' to prevent such possibilities.

Solution to the problem at the beginning:

Well, you should change the architecture of these classes. Generally, in Scala, you will mostly use immutable data, so there will not be many situations where you will face such problem.
To return to the my example from the beginning regarding the DList. To explain: Add method should be adding new element to the list, by creating whole new List and adding it at the beginning. Remember: Scala favors immutable data types. However, Scala compiler don't know what I am going to do with the argument (I might somehow, try to assign it in the existing DList implementation), so I have to using bounding types to make compiler happy.
trait DList[+T] {
  def isEmpty: Boolean  
  def add[S >: T](elem: S): DList[S]
This updated 'add' method accepts the argument that is a subtype of T or has an exact type of T. This keeps compiler happy, as it knows that I cannot reassign some internal variable due to the type mismatch.
Compiler will not allow me to have var in covariant or contravariant anyway, but that is another story.


I hope that this example will give you a much clearer picture on what are invariants, covariants and contravariants and reason why they have limited functionalities in some cases. Always, remember that generic type parameters do not inherit relationships with their 'normal' type counterparts and consider that, by default, there are no relationships between them. If you decide to give them one of two possible relationship models (covariance or contravariance), then be aware of the limitations of each approach. Sometimes, those limitations are just the ones that you need, especially in producer/consumer pattern where you want to make sure that producer can only add things and never be able to get anything; while the consumer can only take things, but never put anything back in it.

18 March, 2014

Passing parameters for XSL, using Builder Design Pattern

It is being a while since I posted something here. This is an older post that I found as a draft. :) Maybe someone will find it useful. 

Recently, new requirement came for the project that I was working on. In short: I had to pass another parameter to updated XSL transformation files. There were already certain parameter passing and I needed to add one more. Adding one more line can't hurt a bit, BUT passing value to method that calls XSL transformation could turn to a nightmare. Luckily, Builder Design pattern solved the problem like a magic :)

22 December, 2011

My experiences with ATI graphic card drivers on Ubuntu

From the very beginning of Linux, users had problems with its device drivers. Why is this problem so common? Because Linux is Open Source and hardware manufacturers usually have to invest their own funds in developing drivers that are compatible with it. On the other hand: Microsoft (Windows) and Apple (MacOS) usually pay big bucks to produce drivers and to keep them updated. That practically means that OS vendors finance hardware vendors themselves to develop drivers. Logical assumption is: Why to finance driver development for OS (Linux) that is not widely used (yet), when other OSs with more market share gives you money for driver development.
In graphic card driver world for Linux, this problem is so evident that most computer experts advice beginners to stay away from 3D and other cool stuff until they master basics of Linux. In this post I will try to summarize some of my experiences and thoughts about it. 

21 November, 2011

Reparing corrupted root system partition in Ubuntu 10.10

Usually, they say that Linux is unbreakable. This statement might be correct to certain degree, but only if you understand how Linux works.
Recently, I had a problem of booting Ubuntu installation. Took me a whole week to find a solution, which came in the nick of time, since I was preparing to wipe out Ubuntu installation. Apparently, it was a root filesystem problem.

08 September, 2011

Adding syntax highlighter to blogger platform using google sites

Most, if not all, programming blogs contains syntax highlighter (sometimes called syntax colorizer) to distinguish normal text from computer code and thus making blog more readable. Using just HTML you can use pre tag or differently styled paragraph to insert same-width font, like lucida console. There is also a nice online free tool that does syntax highlighting using only styled HTML tags.
How about using pre-made CSS/JavaScript combination that automatically highlight code in your blog? All what you have to do is to surround programming code with certain tag and choose language for highlighting. This tutorial will show you how to use Google's syntax highlighter on Blogger platform, while hosting syntax highlighter project on Google Sites service.

16 July, 2011

Tutorial: Setting up ZK project using Maven

ZK RIA framework is becoming more and more popular framework these days. Most of the folks are beginning to use it, without prior knowledge of JSP, servlets and JavaScripts. Honestly, with ZK you might not even need to know anything about these.
What about Maven with ZK? ZK authors did a good job, making it available through their's Maven repository. Usually, beginners use ZK Studio plugin for Eclpise to automatically setup fresh ZK project. Unfortunately, when using Maven, you must manually set your project to use ZK. This procedure might be confusing for users who are not very experienced with Maven and servlets.

23 June, 2011

Missing menu icons in Eclipse (GNOME)

Recently, I noticed that Eclipse (and other programs as well) is missing icons from menu items. Following screenshot best describes the problem:
Firstly, I though that this was Eclipse related problem, but since other windows are missing icons too, GNOME was to blame. With a little help of Google, I found an easy working solution.