Stuart's Soliloquy to the void

Covariance and design principles

Thursday, October 18th, 2007 | Development | No Comments

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: C#, covariance, programming, programming language design, subtyping

The human(e) operating system

Tuesday, October 16th, 2007 | Personal | No Comments

A lot has happened in the OS world over the past year or so. Microsoft has released their newest and greatest OS, Vista, which is riddled with ‘difficulties’ and ‘issues’. Like throttling your network performance to 10% of the full capacity when you are listening to media files, due to DRM checking. In fact, DRM is a cornerstone of Vista’s construction and coupled with Microsoft’s ever-increasing arrogance and refusal to play nice with others (yes, I have been rather slow to fully realise the scope), I decided that it was about time to try something else when my computer died last December (blown PSU and motherboard and damages to the CPU, in case anyone was wondering).

Now, I have written about trying Ubuntu before, here, but as a blemish on my own name, it was somewhat scathing remarks that flowed from my keyboard about it. The truth of everything is that I probably expected it to work like Windows and with the same mannerisms, but, naturally, GNU/Linux does not work like Windows. So, bearing with me a decent portion of experience in running GNU/Linux now and then since the fairly early days, a high amount of being fed up with Microsoft, a dislike of Apple’s tricks for vendor lock-in, and a general idea that it was time to start acting according to my own ideals, I once again went looking at the GNU/Linux landscape.

One of the principal things to remember about GNU/Linux is that it is founded on openness, collaboration, and… choice. This means that there is a lot of different distributions: Ubuntu, Fedora, Debian, Slackware, and many, many others. Each of these distributions serve a particular segment of users and have each their way of organising things (mostly), so where do you start? One option is to go on and investigate them all at Distrowatch or for a slightly more limited amount of distributions you can check out Zegenie Studio’s Linux Chooser. Since I have run GNU/Linux several times before I already knew what distribution I would like to use: Ubuntu.

So with a lot of new shiny computer parts assembled, I booted the Ubuntu 7.04 (Feisty) LiveCD, clicked install, waited some time and then I had a fully functioning system, except for the integrated network chipset, which was unknown to Linux. The vendor had thoughtfully supplied a network driver that only worked on an older kernel version and generally wasn’t behaving very well after I tried to convert it to a newer kernel version (once a developer, always a developer, eh?). Fortunately, I had an old PCI network card lying around that I installed in the computer and then everything ran wonderfully.

The system isn’t too uncommon for a Windows user, but it has its small quirks here and there. One of the things I have been doing a lot has been .NET development, in particular in C#, so after having played around a bit with configuring themes, setting up power management and things like that I have the first panic attack, ‘there is no Visual Studio here, what do I do?!’ Carefully repeating the breathing exercises I had prepared in advance I quickly relaxed. There’s bound to be something around for working with .NET programs given Mono’s track record of keeping up with the .NET framework. Quite right so, there is MonoDevelop, which is based off of the freeware Windows editor, SharpDevelop. At the time I used it, there was still no debugger support and the auto-completion sort of worked, I hear it has gotten better since, but unfortunately C# started to annoy me around the time of the switch anyway (I shall try to remember to write more about my issues with it in another blog post), so I haven’t really done much personal development for .NET since then.

All in all, I have been glad that I chose to exert the effort of getting used to GNU/Linux and the way of doing things in this world as it frees me from the vendor lock-in that Microsoft and Apple dish out to their customers and once you get used to how things work in this different world, they actually just work. As an added bonus, several of the distributions come with a centrally managed repository of software that can be checked against for updates for all your applications at once. As an added added bonus, they never install updates without telling you, unlike some other companies.

Colour me convinced for a brighter future with GNU/Linux and open standards.

Tags: linux, ubuntu