Covariance and design principles

Thursday, October 18th, 2007 | Development

As promised in the last blog post, it is time to get down and dirty with technical facts. Or said in another way, it is time to look at: ‘Why C# let me down’ (you may imagine the blood dripping from the italicised letters). As the title may lead you to believe, the let-down has a lot to do with covariant types, but what are covariant types anyway? Why do they matter? And then how come C# does not have them?

The basic principles of object-oriented languages builds on what in type theory is known as subtyping relationships that are typically expressed σ <: τ, meaning that σ is a subtype of τ. Or expressed in a typical C# manner:

public class τ {}

public class σ : τ {}

So in other words, we have the property that σ inherits from τ, or that σ is a subtype of τ. It is typical of most object-oriented programs (sorry, most well-written object-oriented programs) to allow you to use the type σ in place of the type τ anywhere in the program and still have a correct program. This is what is typically called Liskov’s substitution principle, which can be formulated like this: x : τ ⊢ q(x) ∧ σ <: τ ⇒ y : σ ⊢ q(y). So that is fairly densely looking and what does it really mean? Basically it says: if q(x) is some property that holds on an object x of type τ and if σ is a subtype of τ then if y is an object of type σ then q(y) must also hold. Or in layman’s terms: it must be possible to use a child class instance everywhere a child’s class ancestor is expected, without changes to the program, maintaining correctness of the program. So that is probably a pretty good property to go looking for.

Now, before everything gets lost in theory, let us take a look at the actual problem in C#, using an illustrating example:

public abstract class RandomNumberGenerator {
  public abstract double NextValue();
}

public class DiceResultGenerator : RandomNumberGenerator {
  public DiceResultGenerator(int rolls, int sides) {
    rolls_ = rolls;
    sides_ = sides;
  }

  override public double NextValue() {
    ...
  }

  private int rolls_, sides_;
}

Okay, so this code is a sensible implementation of some random number generator and a dice roller… or is it? When was the last time you got floating point results from rolling a die? Let us fix that up right here and now by changing the double in the DiceResultGenerator to an int. This is a safe operation since int <: double (and because Liskov’s substitution principle otherwise applies here—every time you expect a double you can safely use an int in its place). Ignoring floating point representations and byte sizes this typically holds in most object-oriented languages since the integers are contained in the real numbers. So what happens if we compile the modified source code with the Mono C# compiler (the Microsoft one will give a comparable result)?

`DiceResultGenerator.NextValue()': return type must be `double' to match overridden member `RandomNumberGenerator.NextValue()'

Bummer, we have not got covariance in method return types. This means that whenever we use a DiceResultGenerator, we must get a double out of it, rather than a int, and we will subsequently have to cast it to an int. All this just because the DiceResultGenerator is part of a sensible inheritance hierarchy for different means to obtain random numbers and that most random numbers are floating point values. That is just plain depressing.

So this is exactly what a covariant return type is: when a child class wants to return a subtype of what the overridden function of the ancestor class returns. And it does not work in C#. Of course, it works in C++, but there are so many other things that annoy me with that language.

C# why did you let me down so?! Oh well, it must be time to find the next language I might actually like.

Edit: Astute readers found out that I had switched the subtype relation around in the definition of Liskov’s substitution principle. Sorry.

Tags: , , , ,

No comments yet.

Leave a comment