Objektorientierte Programmierung
LVA 185.162, VL 2.0, 2009 W

Hinweise zur Beurteilung der 5. Übungsaufgabe

Einleitung:

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

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 sollten. Nur recht wenigen Gruppen ist es gelungen, die Aufgabe tatsächlich in allen Details richtig zu lösen.

Häufigste Fehler:

Es ist wenig überraschend, dass die häufigsten Fehler in direktem Zusammenhang mit Generizität stehen. Je nach dem, wie weit fortgeschritten die Gruppen bei der Suche nach einer guten Lösung waren, wurden Teile der Aufgabe nicht gelöst, eigentlich nicht erlaubte Sprachkonstrukte verwendet, Warnungen des Compilers akzeptiert, oder hilfreiche Interpretationen der Aufgabenstellung gefunden. Die Interpretation, dass reduce Seiteneffekte haben kann und dadurch kein neues Objekt erzeugt zu werden braucht, war zwar nicht beabsichtigt, entspricht aber der Aufgabenstellung und führte daher zu keinen Punkteabzügen (obwohl eine entsprechende Lösung keineswegs optimal ist). Weniger geschickte Lösungsversuche mit einem nicht ganz richtigen Ansatz führten zu Punkteabzügen, die davon abhängen, wie weit fortgeschritten die Lösung ist und wie schwerwiegend die Auswirkungen auf die Vollständigkeit, Korrektheit und Wartbarkeit sind.
Viele Lösungen verwenden eine Typumwandlung in reduced. Das führt (entsprechend einer Mail an alle Teilnehmer) nur zur kleinen Punkteabzügen. Leider wurde dabei in fast allen solchen Fällen (bis auf ganz wenige Ausnahmen) übersehen, dass Umwandlungen auf einen Typparameter immer unsicher sind, da entsprechende Informationen zur Laufzeit fehlen. Entsprechende Meldungen des Compilers wurden in Kauf genommen. Typumwandlungen, die in einem Typparameter enthaltene Informationen zu gewinnen versuchen, sind immer falsch und führten zu zusätzlichen Punkteabzügen. Akzeptabel sind nur Typumwandlungen, für die Typparameter keine Rolle spielen.
In einigen Lösungen wurden Meldungen des Compilers beispielsweise durch @SuppressWarnings unterdrückt. Dafür wurden mehr Punkte abgezogen als für entsprechende Compiler-Meldungen, da es dadurch deutlich schwieriger wird, im Nachhinein Fehler zu finden und zu korrigieren (das heißt, die Wartbarkeit leidet).
Gar nicht so selten wurden (vermutlich unbewusst) raw types verwendet, also auf notwendige Typparameterersetzungen vergessen. Nicht in jedem Fall gibt der Compiler dabei eine Warnung aus, da es ja auch sinnvolle Anwendungen für raw types gibt. In dieser Aufgabe wurden aber keine raw types benötigt und waren auch nicht zugelassen (da der Compiler Typsicherheit garantieren sollte) und stellen damit Fehler dar.
Die Aufgabenstellung kann so interpretiert werden, dass AccTree ein Untertyp von Tree ist, oder auch so, dass es keine Untertypbeziehung dazwischen gibt. Die Formulierung ist einfach nicht klar genug. Hauptsächlich geht es darum, ob ein Baum nur aus Instanzen von AccTree oder nur aus Instanzen von Tree gebildet werden darf, oder ob Instanzen von AccTree und Tree auch gemischt vorkommen dürfen. Auf die Inhalte der Bäume hat dieser Unterschied keinerlei Auswirkungen. Falsche Lösungen gab es in dieser Hinsicht nur, wenn keine Begründung für eine nicht bestehende Untertypbeziehung angegeben wurde oder eine gegebene Begründung keinen Grund für das Nichtbestehen einer Untertypbeziehung dargestellt hat.
Sehr oft waren Zusicherungen mangelhaft. Vor allem wurde in vielen Interfaces ganz auf Zusicherungen (bzw. Beschreibungen) verzichtet.
Gelegentlich wurde auch kaum auf Sichtbarkeit geachtet. Häufig wurden Teile der Implementierung von Bäumen auf public Klassen (wie Listen oder Iteratoren) ausgelagert statt innere Klassen zu verwenden. Dies stellt insoferne einen Fehler dar, dass dadurch zahlreiche Zugriffsfunktionen geschaffen wurden, die von überall verwendet werden können.
Überraschend häufig sind auch scheinbar einfache Probleme bei der Programmierung zutage getreten, die nichts mit Generizität zu tun haben. Beispielsweise wurde reduce in der abstrakten Klasse Component äußerst umständlich (oft mit dynamischen Typabfragen und Typumwandlungen) implementiert, obwohl es ganz einfach gewesen wäre, diese Methode abstrakt zu lassen und nur in den Unterklassen zu implementieren. Solche Probleme stellen zwar selbst keine Fehler dar, aber Lösungsversuche enthalten oft verschiedenste Arten von Fehlern.
Der Hauptgrund für starke Punkteverluste sind einfach nur unvollständige Lösungen, Kombinationen aus den oben genannten Fehlern, oder das Fehlen jeden Verständnisses von Generizität. Beispielsweise haben einige Gruppen den Unterschied zwischen Typen (wie Integer) und Typparametern offensichtlich noch gar nicht verstanden.

Empfohlene Lösung:

In allen guten Lösungsvarianten hat Reducible einen Typparameter (für den Typ des Arguments von reduce) mit oder ohne Schranke, und Component sieht ungefähr so aus:

public abstract class Component extends Reducible<Component>
{ ... }

Auf anderen Ansätzen kann man kaum sinnvoll aufbauen.

Es ist gar nicht schwer, die empfohlene Lösung hinsichtlich der Typparameter auf AccTree zu verstehen:

public class AccTree<A extends Reducible<A>, B extends A> ...
implements Reducible<AccTree<A,B>>
{
    ...
    public A reduced()
    {
        Iter<B> i = ...;
        A r = i.next();
        while (i.hasNext()) ...;
        return r;
    }
    ...
}

Der Typparameter A kann demnach für Component als Untertyp von Reducible<Component> stehen, und B für einen Untertyp davon wie z.B. Component, Device und Job. Für den 2. Testfall eignen sich daher Instanzen von AccTree<Component,Device> und AccTree<Component,Job>, für den 3. Testfall Instanzen von AccTree<Component,Component>. Wir können als Ersetzung von A und B aber auch AccTree<X,Y> als Untertyp von Reducible<AccTree<X,Y>> verwenden. Diese relativ einfache Lösung kommt ohne Wildcard-Typen aus.

Wenn wir statt zwei nur einen Typparameter verwenden wollen, dann müssen wir notgedrungen eine Entsprechung zu B verwenden. Beispielsweise könnten wir AccTree so definieren:

public class AccTree<T extends Reducible<? super T>> ...

T entspricht tatsächlich B, da ? (der Typparameter von Reducible) implizit A entspricht und T ein Untertyp von ? ist. Der einzige Unterschied zur obigen Lösung besteht darin, dass A implizit ist und daher in der Implementierung von reduced nicht anstelle eines Typs verwendet werden kann. Wir haben dadurch aber keine Möglichkeit, den Ergebnis-Typ von reduced richtig auszudrücken. Zusätzlich liefert reduce in Component nicht genug Information, um T als Ergebnis-Typ verwenden zu können. Wenn wir diesen Ansatz weiterverfolgen, stoßen wir auf die Probleme, die unter Häufigste Fehler angerissen sind. Eine (wenn auch nicht verallgemeinerbare) Lösung besteht darin, dass reduce die Kosten einfach nur aufaddiert und die Summe in this speichert; dann braucht reduced nicht das Ergebnis der Aufrufe von reduce zurückgeben, sondern nur das Ergebnis eines Aufrufs von get mit dem gewünschten Ergebnis-Typ T.

Die meisten Gruppen haben richtig erkannt, dass man mit einem einfachen Typparameter nicht auskommt und daher einen Wildcard-Typ verwenden muss. Leider haben nur mehr wenige Gruppen den letzten Schritt von Wildcard-Typen zur oben gezeigten Lösung mit zwei Typparametern geschafft, obwohl der Unterschied zwischen diesen Lösungsvarianten klein ist und kaum etwas am gesamten Programm verändert. Offensichtlich wurden auch die Hinweise per Mail nicht richtig verstanden.

Fehlerursachen:

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

Vertrauen auf Andeutungen und Ähnlichkeiten:: Als StudentIn entwickelt man sehr bald ein Gefühl dafür, aus welchen groben Andeutungen und Ähnlichkeiten zwischen Aufgabenstellungen man die gewünschte Struktur der Lösung ablesen kann. Der Hinweis auf die Verwendung von Typ-Wildcards war sicher wichtig, um einen großen Teil der Gruppen auf die richtige Fährte zu bringen. Verstärkend kommt hinzu, dass es auch in den letzten Jahren ähnliche Aufgaben gegeben hat, in denen eine sehr ähnliche Verwendung von Typ-Wildcards zur Lösung der Aufgabe notwendig war. In diesem Jahr haben auch mehr Gruppen eine annähernd richtige Lösung geschafft als in früheren Jahren. Kleine Unterschiede in der Aufgabe können aber große Unterschiede in der Lösung verursachen. Leider war es in diesem Jahr so, dass die optimale Lösung doch ohne Typ-Wildcards auskommt und sich sicher einige Guppen wegen der Hinweise nicht getraut haben, die optimale Lösung abzuliefern. Der später per Mail gekommene Hinweis auf eine sehr gute Lösung war vielleicht etwas zu spät.
Vertrauen auf (scheinbar) Bekanntes:: Mit Generizität waren viele StudentInnen noch nicht vertraut, andere Konstrukte wie Typumwandlungen waren aber vorher schon bekannt. Natürlich wurde versucht, aufgetretene Probleme mit bekannten Mitteln (beispielsweise Typumwandlungen) zu lösen. Diese Mittel haben sich jedoch als äusserst widerspenstig erwiesen, vor allem weil Typumwandlungen im Zusammenhang mit Generizität neue, bisher nicht gekannte negative Eigenschaften entwickelten. Trotzdem hat man sich eher darauf verlassen als auf die unbekannte Generizität, und man hat gar nicht versucht, Probleme über Generizität zu lösen. Tatsächlich ist der Umgang mit Generizität aber viel einfacher als mit sehr unsicheren Typumwandlungen. Diese Einsicht hat sich aber noch nicht verfestigt.
Vertrauen auf die magische Lösung:: Typ-Wildcards dürften bei einigen StudentInnen den Eindruck erweckt haben, eine magische Lösung für alle Zwecke darzustellen, in denen normale Typen bzw. Typparameter nicht mehr ausreichen. In dieser Vorstellung kann es keine Lösung geben, die noch magischer als die magische Lösung ist und auch funktioniert, wo die magische Lösung versagt. Es wurde daher gleich gar nicht nach einer einfachen Lösung gesucht.
Ursachen nicht gesucht oder gefunden:: In dieser Aufgabe kann man eine gute Lösung nur finden, indem man schrittweise vorgeht: Sobald man nach der Lösung eines Teilproblems auf Schwierigkeiten stößt, muss man die Ursachen dafür finden und beseitigen bevor man das nächste Teilproblem angeht. Vermutlich wollten viele sich nicht die Zeit für eine eingehende Analyse der Ursachen eines Problems nehmen und haben beim Auftreten von Schwierigkeiten einfach eine andere Variante gesucht, ohne die Ursachen zu kennen. Mit dieser Vorgehensweise ist man aber wahrscheinlich bald im Kreis gelaufen und immer wieder auf annähernd dieselben Schwierigkeiten gestoßen, ohne sich einer echten Lösung zu nähern. Wahrscheinlich hätte es in diesem Fall viel Zeit gespart, der Ursache für das Problem auf den Grund zu gehen.
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 gar nicht (nicht einmal im Ansatz) verstanden worden. Unter diesen Voraussetzungen ist die Aufgabe einfach nicht lösbar.

Beurteilungsschema

Für ein abgegebenes Programm, das sich übersetzen lässt, gibt es 100 Punkte. Davon werden für Fehler im Programm Punkte abgezogen:

Für eine fehlende Implementierung von reduced wurden 6 Punkte abgezogen. Sehr häufig waren es in der Summe jedoch deutlich höhere Abzüge, da reduced meist nur weggelassen wurde, wenn es auch andere schwerwiegende Mängel in der Lösung gab.
Für eine veränderte Semantik von reduced (meist wird ein int zurückgegeben) wurden drei Punkte abgezogen.
Für die Verwendung einer Typumwandlung in reduced wurden ebenso drei Punkte abgezogen, wenn diese Typumwandlung zu keiner Meldung durch den Compiler geführt hat. Meist lieferte der Compiler aber eine Meldung. In diesen Fällen wurden zusätzlich sechs Punkte für eine fehlerhafte Verwendung einer Typumwandlung abgezogen.
Für das Verschleiern von Compiler-Meldungen durch @SuppressWarnings wurden mindestens 18 Punkte abgezogen, auch bei kleinen Ursachen.
Punkteabzüge bei schwerwiegenderen Fehlern im Zusammenhang mit Generizität und bei fehlenden oder falsch durchgeführten Testfällen sind sehr individuell. Fehler im Zusammenhang mit Generizität und beim Testen gehen meist Hand in Hand.
Für fehlende oder mangelhafte Zusicherungen wurden 3 bis 15 Punkte (nach Schwere des Problems) abgezogen.
Für Fehler im Zusammenhang mit Sichtbarkeit wurden 3 bis 15 Punkte (nach Schwere) abgezogen.
Für fehlende oder mangelhafte Begründungen nicht bestehender Untertypbeziehungen werden 3 bis 9 Punkte abgezogen.
Weitere kleine Punkteabzüge gibt es für eine Vielzahl kleinerer und sehr individueller Probleme, die hier nicht aufgezählt sind.
Daneben gibt es lobende Erwähnungen (+0 Punkte) oder Hinweise auf Probleme (-0 Punkte), die nicht in die Beurteilung einfließen.