Rucksackproblem; algorithmen

BLOG / ENTWICKLUNG - C#



DIE DREI INTERESSANTESTEN FEATURES VON C#


KONTAKT ›

I n der Softwareentwicklung sind wir neben Werkzeugen wie integrierten Entwicklungsumgebungen, Text-Editoren und Quellcode-Verwaltung natürlich auch ständig mit den Programmiersprachen konfrontiert, in denen unsere Software implementiert ist. Deshalb freuen sich Softwareentwickler immer sehr über sprachliche Möglichkeiten, die eine ausdrucksstarke und elegante Formulierung der Implementierungen erlauben. Insbesondere C# sticht dabei als moderne Programmiersprache durch die Umsetzung ausgereifter Ideen hervor, von denen wir einige kurz vorstellen möchten.

EINFÜHRUNG

C# ist eine multiparadigmatische1 Programmiersprache, die in erster Linie für Entwicklung innerhalb des .NET-Frameworks verwendet wird. Das .NET Framework, ab 2002 zunächst eine proprietäre Entwicklung von Microsoft, wurde später quelloffen zuerst als Mono2 und dann als .NET Core3 für andere Plattformen implementiert. Dadurch wurden die Einsatzmöglichkeiten von C# dramatisch vergrößert. Im Folgenden stellen wir einige der interessantesten Features (nämlich Einschränkungen für Typparameter, Ko- und Kontravarianz sowie Multiple Dispatch4) mit kurzen Beispielen vor, die in erster Linie der Illustration der Möglichkeiten dienen.

1. EINSCHRÄNKUNGEN FÜR TYPPARAMETER

Während in einigen Programmiersprachen, die generische Programmierung unterstützen, eine Einschränkung der Typparameter höchstens indirekt möglich ist5, wird diese in C# (ähnlich wie in Java6) direkt unterstützt. Ein einfaches, aber realistisches Beispiel dafür ist die generisch formulierte Bestimmung eines Minimums von zwei Objekten gleichen Typs T unter einer Funktion f, die dabei als Argument angegeben wird. Die Einschränkung des Typs des Wertebereichs von R fordert, dass dieser das ebenfalls generische Interface IComparable implementiert (semantisch also mit sich selbst vergleichbar ist). Dies stellt zur Compilezeit durch explizite Benennung einer Schnittstelle sicher, dass der für die Bestimmung des Minimums durchzuführende Vergleich überhaupt möglich ist und legt fest, wodurch er erfolgen soll.

Beispiel:
public static T ArgMin<T, R>(T t1, T t2, Func<T, R> f) where R : IComparable<R>
{
    return f(t1).CompareTo(f(t2)) > 0 ? t2 : t1;
}

Als positiver Nebeneffekt steht dabei die (erst durch die Einschränkung entstehende) Typinformation der Typparameter in Visual Studio dann auch IntelliSense zur Verfügung, was bereits das Entwickeln der generischen Implementierung stark erleichtert.

2. KO- UND KONTRAVARIANZ

Das Liskovsche Substitutionsprinzip7 sagt informell aus, dass alles, was mit Instanzen eines allgemeineren Typs Base korrekt funktioniert, auch mit Instanzen eines spezielleren Typs Derived korrekt funktionieren soll. Obwohl dies keine syntaktische, sondern eine semantische Forderung ist, ist aus objektorientierter Sicht der Wunsch naheliegend, dass Typhierarchien diesem Prinzip entsprechen. Durch Vererbung wird dabei auch ein syntaktischer Zusammenhang hergestellt. Vermöge expliziter Ko- und Kontravarianz ist es in C# möglich, einen solchen Zusammenhang zwischen Typen herzustellen, die selbst in keiner Ableitungsbeziehung zueinander stehen, aber dem Liskovschen Substitutionsprinzip entsprechen.

Wir betrachten dazu die folgende generische Implementierung eines Stacks8, bei der das Lesen und Schreiben des obersten Elements über die ebenfalls generischen Interfaces IPoppable und IPushable abstrahiert sind. Entscheidend sind dabei die Schlüsselwörter out und in, die für die jeweiligen Interfaces ihre Ko- bzw. Kontravarianz bzgl. des Typparameters T angeben.

Beispiel:
public interface IPoppable<out T>
{
    T Pop();
}
public interface IPushable<in T>
{
    void Push(T Obj);
}
public class Stack<T> : IPoppable<T>, IPushable<T>
{
    private int Position;
    private T[] Data = new T[100];
    public void Push(T Obj) { Data[Position++] = Obj; }
    public T Pop() { return Data[Position--]; }
}

Schließlich verwenden wir diese Implementierung zusammen mit der aus den Klassen Base und Derived bestehenden Typhierarchie.

Beispiel:
public class Base { }					// type hierarchy
public class Derived : Base { }
public static void Main()
{
    Stack<Base> BaseStack = new Stack<Base>();
    Stack<Derived> DerivedStack = new Stack<Derived>();
    IPoppable<Base> PoppableBase = DerivedStack;    	// covariance
    IPushable<Derived> PushableDerived = BaseStack; 	// contravariance
}

Insgesamt sind nun die mit covariance und contravariance kommentierten Zuweisungen interessant. Obwohl sie intuitiv dem Liskovschen Substitutionsprinzip entsprechen (es ist nämlich typsicher möglich, dem Stack jeweils Objekte allgemeineren Typs als T zu entnehmen und Objekte spezielleren Typs als T einzufügen), werden die beiden Zuweisungen erst durch die Verwendung der Schlüsselwörter out und in syntaktisch korrekt.

3. MULTIPLE DISPATCH

Gelegentlich tritt das Problem auf, dass Objekte aus jeweils zwei (oder mehr) voneinander zunächst unabhängigen Typhierarchien miteinander agieren sollen, wobei die auszuführende konkrete Aktion von den jeweiligen Laufzeittypen der Objekte abhängt. Ursprünglich wurde in C# nur das auch in anderen objektorientierten Programmiersprachen übliche Single Dispatch in Form von virtuellen Methoden unterstützt. Dies ermöglichte eine manuelle Implementierung von Double Dispatch9, indem die auszuführenden Aktionen in einer der beiden Typhierarchien implementiert werden, um dann von der anderen Typhierarchie aus in sie zu verzweigen – es wird also willkürlich eine der Typhierarchien ausgewählt, die dann die eigentliche Implementierung aufnimmt.

Dieser Ansatz wird möglicherweise von einem ungeschulten Auge nicht als solcher erkannt; weiter wird er unübersichtlich, wenn zusätzliche Typhierarchien hinzukommen. Dies änderte sich, als in C# in Version 4.0 das Schlüsselwort dynamic eingeführt wurde, das die direkte Auswahl einer Implementierung einer polymorphen Funktion zur Laufzeit über virtuelle Methoden hinaus ermöglicht.

Im folgenden Beispiel wird durch ABase und ADerived eine Typhierarchie gebildet, während eine andere aus BBase und BDerived besteht. Anschließend ist in vier Funktionen (da jeweils zwei Objekte aus zwei Typhierarchien auf insgesamt vier Arten miteinander agieren können) die jeweilige Aktion implementiert – hier exemplarisch durch Ausgabe der Namen der beteiligten Typen.

Beispiel:
public class ABase { }                  // type hierarchy A
public class ADerived : ABase { }
public class BBase { }                  // type hierarchy B
public class BDerived : BBase { }

public static void Act(ABase iABase, BBase iBBase)              // 1
{ Console.WriteLine("ABase, BBase"); }
public static void Act(ADerived iADerived, BBase iBBase)        // 2
{ Console.WriteLine("ADerived, BBase"); }
public static void Act(ABase iABase, BDerived iBDerived)        // 3
{ Console.WriteLine("ABase, BDerived"); }
public static void Act(ADerived iADerived, BDerived iBDerived)  // 4
{ Console.WriteLine("ADerived, BDerived"); }

static void Main(string[] args)
{
    ABase iABase = new ADerived();
    BBase iBBase = new BDerived();
    Act(iABase as dynamic, iBBase as dynamic);  // double dispatch
}

Es werden zwei Objektinstanzen aus den Typhierarchien erzeugt, wobei der Typ der Referenz aber die Basisklasse der jeweiligen Objekthierarchie ist und nicht der Laufzeittyp der referenzierten Instanzen. Entscheidend ist jetzt die jeweilige Umwandlung in dynamic in der mit double dispatch kommentierten Zeile. Dadurch wird zur Laufzeit die mit 4 kommentierte Überladung ausgewählt. Würde diese Umwandlung fehlen, so würde stattdessen zur Compilezeit die mit 1 kommentierte Überladung ausgewählt werden – unabhängig vom tatsächlichen Laufzeittyp der erzeugten Objekte, was in diesem Fall aber nicht gewünscht ist. Beim Hinzukommen weiterer Objekthierarchien würden die Signaturen der Überladungen von Act weitere Argumente der neuen Typen bekommen. Diese Lösung ist etwas übersichtlicher als die oben angedeutete Erweiterung von manuellem Double Dispatch zu manuellem Triple Dispatch.

AUSBLICK

Wir haben anhand von Beispielen drei ausdrucksstarke Sprachfeatures vorgestellt, die man schnell vermisst, wenn man sich erst einmal an sie gewöhnt hat. Weitere interessante Features sind Eigenschaften, Attribute, Erweiterungsmethoden und funktionale Programmierung (insbesondere Lambda-Ausdrücke). Insgesamt sind in C# reichhaltige Möglichkeiten vorhanden, so dass sich eine große Breite von Implementierungsansätzen direkt umsetzen lässt. Die Portierung bestehender Implementierungen aus anderen Sprachen fällt dadurch ebenfalls etwas leichter.


1 Es werden strukturierte, imperative, deklarative, objektorientierte, ereignisorientierte, funktionale, generische, reflexive und parallele Programmierung direkt unterstützt.

2 http://www.mono-project.com/

3 https://msdn.microsoft.com/de-de/library/Dn878908%28v=VS.110%29.aspx

4 Über Multiple Dispatch ausgewählte Funktionen werden gelegentlich auch als Multimethoden bezeichnet.

5 http://www.stroustrup.com/bs_faq2.html#constraints

6 https://docs.oracle.com/javase/tutorial/java/generics/bounded.html/

7 Barbara Liskov & Jeanette Wing: A Behavioural Notion of Subtyping, ACM Transactions on Programming Languages and Systems, 16 (6), 1811–1841, 1994.

8 Joseph Albahari & Ben Albahari: C# 6.0 – kurz & gut, O‘Reilly, 2016.

9 Karl Eilebrecht, Gernot Starke: Patterns kompakt – Entwurfsmuster für effektive Software-Entwicklung, Spektrum akademischer Verlag, 2010.