Objektorientierte Programmierung
LVA 185.162, VL 2.0, 2010 W

Hinweise zur 5. Übungsaufgabe

Einleitung:

Die vorläufige Beurteilung der 5. Aufgabe (reguläre Abgabe) ist recht schlecht ausgefallen. Diese Seite soll die häufigsten und wichtigsten Fehler, die dabei gemacht wurden, aufzeigen, Hinweise zur empfohlenen Lösung geben und wahrscheinliche Gründe für das Zustandekommen der Fehler erklären.

Die Aufgabe ist so aufgebaut, dass Generizität sehr überlegt eingesetzt werden muss, um alle vorgegebenen Testfälle ohne Warnungen durch den Compiler lösen zu können. Ein Hintergedanke dabei war, dass Sie mehrere Lösungsvarianten durchprobieren und dabei auf verschiedene Anwendungsmöglichkeiten der Generizität und deren Grenzen stoßen. Nur wenigen Gruppen ist es gelungen, die Aufgabe in allen Details richtig zu lösen.

Häufigste Fehler:

Der schwerwiegendste Fehler war, nur eine sehr unvollständige oder überhaupt keine Lösung abzugeben. Dafür gibt es naturgemäß nur sehr wenige oder gar keine Punkte. Anscheinend haben viele Gruppen erst spät begonnen, Programmcode zur Lösung der Aufgabe zu schreiben. Vielleicht ist vorher viel Zeit in generelle Überlegungen geflossen, wie man an diese Aufgabe herangehen kann. Aber gerade bei dieser Aufgabe führen solche Überlegungen kaum zum Ziel. Einfacher wäre es vermutlich gewesen, ohne lange Überlegungen so gut es geht darauf los zu programmieren und beim Auftauchen von Problemen diese über geeignete Einschränkungen auf den Typparametern oder durch Einführung zusätzlicher Typen oder Typparameter zu umgehen.
Es ist wenig überraschend, dass die häufigsten Fehler in direktem Zusammenhang mit Generizität stehen. Je nach dem, wie weit fortgeschritten die Suche nach einer guten Lösung war, wurden Teile der Aufgabe nicht gelöst, eigentlich nicht erlaubte Sprachkonstrukte verwendet, Warnungen des Compilers akzeptiert, einschränkende Interpretationen der Aufgabe gefunden, oder einige Testfälle weggelassen. Dabei wurden Punkteabzüge offensichtlich bewusst in Kauf genommen.
In einigen Lösungen wurden (vielleicht unbewusst) raw types verwendet, also auf notwendige Typparameterersetzungen verzichtet. Das führte meist zu Warnungen des Compilers. In einigen Lösungen wurde übersehen, dass diese Warnungen oft nur kleine Ursachen haben, die sich durch die Angabe von Typen in spitzen Klammern (= Typparameterersetzungen) leicht lösen lassen. Manchmal geht das aber nicht, weil es bei bestimmten Lösungsansätzen keine konsistente Lösung gibt; in diesen Fällen wurden die Warnungen nur in Kauf genommen, um echte Fehler im Ansatz zu verdecken.
Anscheinend haben rekursive Typen zu Verständnisproblemen geführt, z.B. weil nicht klar war, wie man einen Typ AssocIter<A,AssocIter<A,...>> auf einfache Weise darstellen kann. Das geht sehr leicht durch Einführung einer spezialisierten Variante des Typs, z.B. durch interface S extends AssocIter<A,S>. Eigentlich haben alle einigermaßen vollständigen Lösungen im Endeffekt etwas Derartiges enthalten, aber die genaue Form der Konstruktion ist gelegentlich abenteuerlich.
Viele Lösungen haben Teile der Aufgabe sehr einschränkend interpretiert um Teile der Lösung zu vereinfachen. Beispielsweise wurde häufig angenommen, dass assoc in AssocIter nur Instanzen von AssocIter zurückliefern kann, wodurch ein schwer zu spezifizierender Typparameter weggefallen ist. Für solche Vereinfachungen der Aufgabenstellung wurden Punkte abgezogen.
Viele haben sich die Frage gestellt, ob ValueTree ein Untertyp von Tree sein kann. Niemand hat es geschafft, Typparameter so zu verwenden, dass die Untertypbeziehung gelten kann und trotzdem alle anderen Bedingungen in der Aufgabenstellung erfüllt sind. Viele Gruppen haben eine gute Lösung, die aber keine Untertypbeziehung zwischen diesen Typen zulässt. Lösungsansätze, in denen die Untertypbeziehung gelten könnte, sind nicht schön bzw. erstrebenswert – siehe weiter unten. Daher wurde eine Lösung ohne Untertypbeziehung als richtig beurteilt.
Sehr oft waren Zusicherungen mangelhaft oder einfach nicht vorhanden. Der Hauptgrund dafür dürfte eher im Zeitdruck als am Wissen, wie es richtig wäre, liegen.
Gelegentlich wurde kaum auf Sichtbarkeit geachtet. Auch das dürfte manchmal mit Zeitdruck zu begründen sein. Häufig wurden Teile der Implementierung von Bäumen oder Listen auf public Klassen (wie Listenknoten oder Iteratoren) ausgelagert statt innere Klassen zu verwenden. Dies stellt insoferne einen Fehler dar, als dadurch zahlreiche Zugriffsfunktionen geschaffen wurden, die von überall verwendet werden können. Gelegentlich wurden damit geschaffene Zugriffsmöglichkeiten auch dazu verwendet, um von der Testklasse aus direkt auf Implementierungsdetails zuzugreifen, wodurch (vermutlich fehlerhaft implementierte) Iteratoren gar nicht benötigt wurden.
Gelegentlich sind auch scheinbar einfache Probleme bei der Programmierung zutage getreten, die nichts mit Generizität zu tun haben, oder ein vollständig fehlendes Verständnis für Generizität – z.B. den Unterschied zwischen einer Klasse MyInt und einem Typparameter namens MyInt nicht erkannt. Aus solchen Lösungsversuchen kann man kaum Ursachen für die Fehler herauslesen; es stimmt einfach nichts zusammen.

Empfohlene Lösung:

Hier werden nur einige essentielle Teile der Lösung skizziert, nicht die ganze Lösung.

Die Interfaces für die vorgegebenen Iteratoren sind ziemlich unspektakurlär, alle Einschränkungen darauf sollten nur in Untertypen erfolgen:

interface Iter<A> {...}
interface AssocIter<A,B> extends Iter<A> {...}
interface ValueIter<A,B,C> extends AssocIter<A,B> {...}

wobei A für den Ergebnistyp von next steht, B für den von assoc und C für den von get.

Für die Beziehungen zwischen ADescriptor, BDescriptor, Descriptor und MyInt gibt es nur wenig Spielraum. Wir brauchen einen zusätzlichen generischen Typ (z.B. Comparable), der die Methode compareTo beschreibt, welche in Descriptor und MyInt implementiert ist. Die Struktur muss so aussehen:

interface Comparable<A> {...}
class MyInt implements Comparable<MyInt> {...}
abstract class Descriptor implements Comparable<Descriptor> {...}
class ADescriptor extends Descriptor {...}
class BDescriptor extends Descriptor {...}

Das Schema dahinter entspricht ziemlich genau dem MyInteger-Beispiel aus der Vorlesung zusammen mit dem Untertyp U von MyInteger (Folie 7 vom 17. November). Entsprechend müssen auch Tree und ValueTree Typparameter wie auf dieser Folie haben:

class Tree<L extends Comparable<? super L>> ...
class ValueTree<L extends Comparable<? super L>, V> ...

Der Typparameter A auf Comparable kann eine Schranke enthalten, um die beabsichtigte Verwendung genauer zu beschreiben, aber diese Schranke ist nicht notwendig. Statt Wildcard-Typen könnte man zusätzliche Typparameter verwenden, aber eine solche Lösung hat niemand gewählt. Wildcard-Typen (oder zusätzliche Typparameter) sind unbedingt notwendig, um den 4. Testfall der Aufgabenstellung lösen zu können.

Eine Schwierigkeit in den Implementierungen von Tree und ValueTree besteht darin, den Ergebnistyp von assoc richtig auszudrücken. Mit einem unendlichen Typ

    AssocIter<L, AssocIter<L,...>>

kann man ja nicht umgehen. Die Tatsache, dass man den gewünschten Typ gerne durch einen solchen unendlichen Ausdruck darstellen würde, ist ein deutlicher Hinweis darauf, dass man einen rekursiv definierten Typ braucht. Ein einfacher Lösungsansatz besteht darin, direkt die Iterator-Implementierungen rekursiv zu definieren:

class TreeIter implements AssocIter<L, TreeIter>
class ValueTreeIter implements ValueIter<L, ValueTreeIter, V>

Eine schönere Lösung bekommt man, wenn man zwischen der Iterator-Implementierung und AssocIter bzw. ValueIter noch eine Typebene einzieht:

interface RecAssocIter<A> extents AssocIter<A, RecAssocIter<A>> {}
interface RecValueIter<A,C> extents ValueIter<A, RecValueIter<A,C>, C> {}

Ein Problem dieses Ansatzes besteht darin, dass damit keine Untertypbeziehung zwischen ValueTree und Tree erreichbar ist, da sich die Typen, die den Typparameter B in AssocIter bzw. ValueIter ersetzen, verschieden sind. Für eine Untertypbeziehung zwischen ValueTree und Tree bräuchten wir auch eine Untertypbeziehung zwischen Typen, die RecValueIter und RecAssocIter entsprechen und gleichzeitig von ValueIter und AssocIter abgeleitet sind, ohne dass die Typparameterersetzungen einander widersprechen. So etwas können wir nicht konstruieren.

Um eine Untertypbeziehung zwischen ValueTree und Tree zu erreichen, brauchen wir einen anderen Ansatz, in dem wir in ValueTree und Tree denselben Typ für B in AssocIter bzw. ValueIter verwenden können. Eine Lösungsvarinate wäre, dass auch assoc in Tree eine Instanz von RecValueIter zurückgibt. Das würde (wenn man genau schaut) der Aufgabenstellung entsprechen, wäre aber keinesfalls eine schöne Lösung. Mit etwas Kosmetik wäre dieser eigentlich sehr einfache Ansatz durchaus ausbaubar. Jedoch wurde von niemandem ein derartiger Lösungsansatz gewählt.

Fehlerursachen:

Die tatsächlichen Ursachen für die häufigsten Fehler können nur vermutet werden. Folgendes dürfte eine Rolle gespielt haben:

Vermeidung von Unbekanntem:: Mit Generizität waren viele StudentInnen noch nicht vertraut, andere Konzepte wie Untertypen oder Typumwandlungen waren aber schon bekannt. Natürlich versucht man, aufgetretene Probleme mit bekannten Mitteln zu lösen und bekannte Denkmuster einzusetzen. Diese Mittel haben sich jedoch als widerspenstig erwiesen. Die Denkmuster hinter der Generizität sind eigentlich sehr einfach; es gibt kaum mehr, als in der Vorlesung gemacht wurde. Trotzdem wurden diese Denkmuster oft vermieden und statt dessen wesentlich kompliziertere Denkmuster aus anderen Bereichen auf die Generizität übertragen. Das kann aber für diese Aufgabe nicht funktionieren.
Zu viel Respekt vor komplexen Zusammenhängen:: Die Aufgabenstellung enthält viele Typen und Beziehungen zwischen Typen, wobei sich die Beziehungen nicht auf vertraute Strukturen (aus der objektorientierten Modellierung) herunterbrechen lassen. Das ist typisch für Aufgaben zum Thema Generizität, da Generizität vor allem dann zum Einsatz kommt, wo die objektorientierte Modellierung an ihre Grenzen stößt. Anscheinend haben trotzdem viele Gruppen versucht, die Komplexität über übliche Konzepte der objektorientierten Modellierung in den Griff zu bekommen, und haben dabei nur herausgefunden, dass die Aufgabe sehr komplex ist, ohne sich einer Lösung zu nähern. Viele dürften aus Respekt vor der Aufgabe aufgegeben haben, noch bevor der erste Code entstanden ist. Andererseits sind die Typen und Beziehungen absichtlich so gewählt, dass sie den Beispielen aus der Vorlesung (Folien 2 und 7) ziemlich direkt entsprechen. Für Gruppen, die dies frühzeitig erkannt haben, war die Aufgabe im Kern relativ rasch lösbar, bis auf eher Kleinigkeiten, wie den Fragen nach dem Bestehen einer Untertypbeziehung und der Vermeidung unendlicher Typdarstellungen. Wer allerdings vorher schon gesehen hat, wie kompliziert die Aufgabe aus der Sicht der objektorientierten Modellierung ist, hat vermutlich nicht mehr an eine einfache Lösung geglaubt, wodurch diese Kleinigkeiten zu beinahe unüberwindlichen Hürden wurden.
Konzentration auf eine Sache:: Für viele verlorene Punkte waren gar nicht Probleme im Zusammenhang mit Generizität verantwortlich, sondern beispielsweise ein schlampiger Umgang mit Zusicherungen oder Sichtbarkeit. Der Hauptgrund dürfte darin liegen, dass man sich ganz auf eine Sache, nämlich Generizität konzentriert und dabei andere für die Beurteilung relevante Aspekte übersehen hat.
Generizität gar nicht verstanden:: Von einigen Gruppen ist Generizität offensichtlich noch kaum oder gar nicht verstanden worden. Unter diesen Voraussetzungen ist die Aufgabe einfach nicht lösbar.