C# covariance and contravariance

Hey guys. Sorry that I was not posting bigger stuff for a long time. I’ve had some personal time-eaters during the last months, but I hope it will get better soon. Today’s topic during this article is covariance and contravariance in general and especially in C#. What is it? Who needs it? How is it supported today? How will it be supported in C# 4.0? Answers have to be found…

So, covariance and contravariance are features of a programming language’s type system (not limited to C# at all). More precisely (and theoretically), they are characteristics of binary operators, which convert one type to another type. Generally if an operator changes the type in some kind, it’s called variant. If it retains the type (the type is fix), then it’s called invariant. Two types of variant operators are contravariant and covariant operators. In fact, there are other types of variance (consider dynamic typing, duck typing etc.), thus covariant/contravariant operators are just two examples for that. If an operator orders types in the way from general to more specific for any type, then it is called to be covariant. If it orders types reversely from specific to more general, then it’s contravariant.

So far the theoretical introduction. It’s pretty much saying nothing about what both terms mean in your practical coding life, isn’t it? Well… in programming languages there are two features where co- and contravariance can make sense: return type covariance and parameter type contravariance.

Return type covariance

Let’s consider the interface IClonable for a moment. It’s declared as:

public interface ICloneable
{
    object Clone();
}

If we want a class Foo to implement this interface, then it has to apply the exact same signature:

public class Foo : ICloneable
{
    public object Clone()
    {
        Foo clone = new Foo();
        // cloning implementation
        // ...

        return clone;
    }
}

Wouldn’t it be nice to have a method public Foo Clone() instead? That’s what return type covariance means. With this, the return type would be narrowed by more specific implementations or derivations. It would give type-safety to all callers of the method. Yes, this would be nice, indeed. But that’s a feature, which is currently not implemented in the C# language. The more general return type in the interface or a base class can not be narrowed on implementing or deriving classes. The same problem arises in a number of cases and on generics, as we will see later on.

Parameter type contravariance

If we got a method on an interface or base class which takes a parameter X, then contravariance is all about wanting a more general parameter in the implementation method of that interface or in a derived class. C# doesn’t support that, yet. For example, the following will not work:

class Fruit { }
class Apple : Fruit { }
class Cherry : Fruit { }
class FlavorComparer : IComparer<Fruit> { ... }

public void SortApples()
{
    List<Apple> apples = GetSomeApples();
    IComparer<Fruit> flavorComparer = new FlavorComparer();
    apples.Sort(flavorComparer);
}

FlavorComparer compares two fruits based on their flavor. Apples are fruits, so why shouldn’t they be sorted with use of the FlavorComparer? This would be nice, but Sort() needs a IComparer<Apple> and not the more general argument IComparer<Fruit>. It should be no problem for using the more general comparer, but C# doesn’t support this at the moment.

Covariance on arrays

Since the first C# (1.0), covariance on arrays is supported. Thus, one could write:

Fruit[] fruits = new Apple[10];
fruits[0] = new Cherry();

An array of a reference type can be viewed as an array of its base type or any implemented interface. That’s no problem for the compiler, it just works. But at runtime, that example would produce an ArrayTypeMismatchException and that’s what one would expect in this example. Creating apples and setting one to a cherry is no good idea.

Well, but why does it compile? That’s a historical problem. In the first version of C#, it has been designed to attract as many developers as possible and since this type of covariance worked in Java, the C# guys applied it to their language as well. Not that good idea, but that’s another story…

Covariance and contravariance on generics

Generics in C# 1.0 to 3.0 are invariant (fix). If we map the array example to generics, then the following code will not work:

List<Fruit> fruits = new List<Apple>();
fruits.Add(new Cherry());

In this case, there’s no exception thrown at runtime, but already the compiler comes up with an error message at the first line. Invariance on generics is a serious limitation of current C# versions, since it doesn’t allow many intuitively correct cases.

For example, if you have a method List<Fruit> GetFruits() on the Fruit class, which gets overridden by the Apple class, then you can’t return an instance of List<Apple>, which should be no problem intuitively. The following code on Apple is not working:

public List<Fruit> GetFruits()
{
    List<Apple> fruits = GetApples();
    return fruits;
}

The same problem arises, if we want to have a list of fruits, which should be a Union of apples and cherries, which are both fruits…

List<Fruit> fruits = new List<Fruit>();
List<Cherry> cherries = GetCherries();
List<Apple> apples = GetApples();

fruits = fruits.Union(cherries).Union(apples);

This or similar code doesn’t work as well.

C# 4.0

Having all that in mind, C# 1.0-3.0 is some kind of nerving limited in terms of covariance and contravariance. It has covariance on arrays of reference types and C# 2.0 introduced covariance and contravariance on delegates (which obviates some really annoying workarounds), but at the whole there should be better language support of those type-system features.

But a knight in shining armour is approaching: C# 4.0 arises on the horizon! But does it hold what it looks like? In fact, with C# 4.0 you have the in and out keywords, which you can define on type arguments of interfaces and delegates.

With the out keyword you can define a type parameter to be covariant. This means, that implementations of methods which return an object of this type can also return a more specific type. The standard example in this case is IEnumerable<out T>:

public interface IEnumerable<out T> : IEnumerable
{
    IEnumerator<T> GetEnumerator();
}

public interface IEnumerator<out T> : IDisposable, IEnumerator
{
    T Current { get; }
}

This allows you to write e.g.:

IEnumerable<object> list = new List<string>();

and

IEnumerable<Fruit> fruits = new List<Apple>();

It allows you to have a base type as type parameter of an IEnumerable instance and a more specific type if you assign something to it. But wait: there’s a limitation on that… out T means: no method in this interface is allowed to use T as parameter! The word „out“ makes this clear and it limits the use of those covariance to just a few interfaces. For example, this cannot be set on the ICollection<T> interface (and furthermore on IList<T>, because of IList<T> : ICollection<T>). ICollection<T> includes a method Add(T item) and since no T is allowed to be used when out T is declared, that wouldn’t work. Now, most of my own generic interfaces and many .NET interfaces as well use type parameters as in- and output, so this new type of covariance seems to be not this influencing. For example, the following code would not work:

IList<object> list = new List<string>();

But why? There’s an important aspect on that and that is the same as on the array example in the paragraph „Covariance on arrays“. Having the Add() method, one could add an instance of type object to the list and that has not to be allowed:

IList<object> list = new List<string>();
list.Add(new object());  // mustn't be allowed

Sure, that’s a big limitation, but it makes sense and is absolutely necessary!

The same comes true for the in keyword. One can define an interface with type parameter in T. With that, T can only be used as type parameter and not as return value. But this brings contravariance on the type parameters to life. Having the FlavorComparer example from above in mind? That will work, if IComparer<in T> is declared by the .NET framework. The limitation of T to be set as method parameter only is necessary due to the same aspect as for the out keyword. If IList<in T> should have been declared and one defines a variable IList<string> list and calls list.Add(new object()), then it would make no sense to iterate through all list elements as string, because the inserted object is no string and would cause problems.

So in the end, the knight’s armour is not that shiny. C# 4.0 comes with some nice covariance and contravariance features, but the out and in parameters are fairly limited (and using them together is (luckily) not allowed). Many people are annoyed about that, but I don’t share their opinion. It’s a good thing to have covariance and contravariance on type parameters separated from each other! Else this would produce heavy problems as we have seen in the examples above and in the array covariance section. My opinion is, that the language designers have done a good job here. I don’t want to have some kind of ArrayTypeMismatchException on generics and thus in/out on type parameters are a good thing.

Links:

kick it on DotNetKicks.com

PDC 2008

Morgen geht es los mit der PDC, Microsoft’s jährlicher Professional Developer Conference, die nicht selten den Ausgangspunkt für viele der neuesten Technologien (nicht nur für Entwickler) dargestellt hat. Ich freue mich darauf, aus der Ferne von News in den Bereichen .NET, C# und Visual Studio zu erfahren und einen Ausblick darauf zu erhaschen, was Microsoft in der Zukunft mit diesen Technologien vor hat.

Im Vorfeld der PDC konnte man bereits einiges erfahren und auch die Agenda gibt einigen Aufschluss. Das Thema Parallel Computing ist sicher ein wichtiges für C# bzw. das .NET Framework und mit der Integration der Parallel Extensions wird Microsoft einen wichtigen Schritt in diese Richtung tun. Doch das kann nicht alles sein, gerade im Bereich Patterns ist da noch mehr nötig und hier wird auf der PDC sicherlich einiges auf uns zukommen.

Eins steht schon fest: .NET bekommt ein neues Logo. Hier ist es:

Mich freut’s… das alte war doch „leicht“ angestaubt und erinnerte eher an Zeiten von Windows 98 und ME anstatt an ein aktuelles Entwicklungs-Framework…

Also ich bin gespannt auf die News dieser Woche und werde in diesem Blog auf die besten davon eingehen.

Die Zukunft von C#

Da ich stets in aktuellen Entwicklungen von C# interessiert bin, habe ich ein wenig im Internet recherchiert und fasse nachfolgend einige interessante Hinweise mit den entsprechenden Links zusammen, wo die Reise hin geht. In Zukunft möchte ich diesen Text mit aktuellen Entwicklungen weiter ausbauen, die derzeitige Version ist lediglich als Ausgangspunkt gedacht.
 
Integration von C-Omega Sprachelementen
 
C-Omega ist eine experimentelle Sprache von Microsoft Research und offiziell gibt es keine Pläne für deren Verwendung. Trotzdem fand bereits die Übernahme einiger Sprachelemente in C# statt, wie es auch in einem Interview mit Anders Hejlsberg zur Sprache kommt. Bei C-Omega handelt es sich um eine Spracherweiterung von C#. Sie fokussiert dabei vor allem auf Probleme, welche bei der Erstellung netzwerkartiger, lose gebundener Applikationen entstehen. Diese betreffen die nebenläufige/parallele Programmierung auf der einen Seite und die Integration von relationalen Daten und XML auf der anderen Seite.
 
Beim Thema Nebenläufigkeit werden einige Konzepte eingeführt, die zunächst unter dem Namen „Polyphonic C#“ implementiert wurden und auf die bessere Unterstützung paralleler Abarbeitung (zum Beispiel durch neue Sprachelemente und die bessere Unterstützung von Asynchronität) abzielen. Mit einer besseren Einbindung relationaler Daten sollen weiterhin die bisher nahezu getrennten Welten der Programmiersprachen und der Datenbanken miteinander vereint werden, indem ein leichterer Datenzugriff aus der Programmiersprache heraus stattfindet und dabei für Typsicherheit gesorgt wird. C-Omega setzt diese Idee um mit LINQ wurde dieses Konzept in .NET übernommen. Auch der getypte Zugriff auf XML-Daten bzw. die einfache und typsichere Traversierung eines XML-Baums ist in C-Omega möglich, allerdings fand noch keine direkte Übernahme in C#/.NET statt (abgesehen von der LINQ-Unterstützung für XML-Daten). Hier darf man gespannt sein, ob und wann dies nachgeholt wird.
 
Nebenläufige/Parallele Programmierung
 
In der besseren Unterstützung nebenläufiger Programmierung bzw. der Erstellung paralleler Programme liegt eine große Herausforderung für die weitere Programmiersprachenentwicklung, bei der C# durch seine derzeit noch vorherrschende hohe Dynamik eine Vorreiterrolle spielen kann. Dem Thema Parallelität kommt dabei eine wachsende Bedeutung zu, da sich die Architektur heutiger Rechner und Netzwerke durch die Verbreitung von Multicore-Ansätzen und der lose gekoppelter Netzwerke (Cloud Computing) stetig wandelt. Jedoch wird Parallelität auch von aktuellen Programmiersprachen wie C# oder Java nur über Thread-und-Lock-Ansätze unterstützt, welche in den 1970er Jahren entwickelt wurden und die Programmierung nebenläufiger Applikationen schwer und unhandlich machen.
 
Microsoft hat mit dem Parallel Computing Developer Center einen Bereich geschaffen, der sich dem Thema Parallelität/Nebenläufigkeit widmet und dem einige Hinweise auf Entwicklungen für C#/.NET entnommen werden können. So sind mit den Parallel Extensions eine ganze Reihe von Spracherweiterungen für C#/.NET verfügbar, welche erste Möglichkeiten für die einfache Erstellung paralleler Programme beinhalten. Neben thread-sicheren Collections bietet z.B. die Klasse System.Threading.Parallel statische Methoden „For“, „ForEach“ etc. an, mit denen eine einfache Parallelisierung von Programmkonstrukten erreicht werden kann. Interessant ist ebenfalls die Einbindung eines parallelen LINQ (PLINQ).
 
Zukünftig dürfte es nicht bei einer Spracherweiterung bleiben. Die Parallel Extensions werden meiner Meinung nach bald in neue Releases von C# bzw. das .NET-Framework selbst Einzug halten und so die parallele Programmierung vereinfachen. Doch das dürfte erst die Spitze des Eisberges sein. Mittelfristig ist ein kompletter Paradigmenwechsel zur parallelen Programmierung hin nötig, was allein über Spracherweiterungen schwer erreichbar erscheint. Auf jeden Fall sind neue Sprachkonzepte erforderlich, welche die Übersichtlichkeit bei der Erstellung großer paralleler Applikationen wahren und wiederkehrende Muster in eigene Konstrukte kapseln. Eine Art Katalog an „Parallel Design Patterns“ wäre hierbei sicherlich hilfreich.
 
Was Microsoft zu dem Thema zu sagen hat, wird auf der PDC 2008 öffentlich werden. Mit einem separaten Pre-Conference-Day und 4 Konferenz-Sessions auf der PDC wird der Parallelisierung genügend Raum geboten.
 
C# 4
 
In einem Interview mit den C#-Designern auf Channel 9 werden erste Details geliefert, in welche Richtung sich C# 4 entwickeln könnte. Unter anderem wird über die Notwendigkeit von C# gesprochen, mit „dynamischen“ Sprachen wie IronPython oder IronRuby zu interagieren und diese besser einzubinden. In diesem Zusammenhang könnte es auch zu einem Ausbau der Möglichkeiten für das Meta-Programming kommen. In dem Interview wird ebenfalls eine Vereinfachung konkurrierender Aufrufe angekündigt.
Insgesamt stellt sich die Frage, wie weit die Sprachdefinition selbst mit neuen Features aufgebläht werden sollte, ohne sie zu unübersichtlich zu machen und Entwickler (vor allem Neueinsteiger) abzuschrecken.
 
Diese anderen Sharp’s…
 
Ein Blick auf Microsoft Research lohnt immer, da Forschungs-Projekte zunächst zwar losgelöst sind von konkreten Applikationen, jedoch Microsoft auch einen Nutzen bringen sollen und damit früher oder später Auswirkungen auf bestehende Elemente wie C# und .NET haben.
 
Spec# stellt beispielsweise eine Spracherweiterung für C# dar, welche die Erstellung von Qualitätssoftware vereinfachen soll. Das grundlegende Prinzip ist dabei programming by contract. Der Programmierer gibt vor, wie sich beispielsweise eine Methode zu verhalten hat (Vor- und Nachbedingungen), was in der Spec#-Syntax geschieht. Zur Compilezeit wird geprüft, ob die Methode diesen „Vertrag“ einhält. Programming by contract ist auch für die Parallelisierung von Programmen interessant, da hierüber ausgesagt werden kann, wie sich eine Funktion verhält, z.B. ob sie interne Zustände einer Klasse ändert oder andere Seiteneffekte hat. Der Compiler kann dann anhand dieser Aussagen und ihrer Prüfung entscheiden, wie eine Parallelisierung anzustreben ist.
 
Dass sich gewisse Dinge in einer funktionalen Programmiersprache einfacher und schneller implementieren lassen, ist hinlänglich bekannt. Quicksort lässt sich z.B. in Haskell elegant in 3 Zeilen Code abhandeln. F# stellt eine Implementierung des funktionalen Programmierparadigmas dar, auch wenn es nicht „rein“ funktional ist. Gewisse Konstrukte wie die Lambda-Ausdrücke wurden bereits in C# integriert, andere Anleihen dürften folgen. Auch anderen Paradigmen wie der deklarativen Programmierung sollten man ein Augenmerk schenken, hier wurde mit WPF/XAML ja auch schon ein erster Beitrag geleistet. Funktionale Programmierung ist für das Sprach-Design-Team bei Microsoft besonders interessant, da funktionale Programme per se frei sind von Seiteneffekten. Sie lassen sich daher von Haus aus gut parallelisieren. Es wird zwar kein kompletter Paradigmenwechsel angestrebt (dafür sind funktionale Programme zu ineffektiv), aber es werden „Inseln“ in der funktionalen Programmierung gesucht, mit welchen sich die aktuellen Probleme imperativer Programmiersprachen wie C# elegant handhaben lassen.
 
Weitere Links