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:

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.
Complang
Puntigam
   Kontakt
   Research
   Lehre
      OOP
      Typsysteme
      EP2
      FOOP
      Prog.spr.
      frühere Lehre
         LVAs 2017 W
         LVAs 2017 S
         LVAs 2016 W
         LVAs 2016 S
         LVAs 2015 W
         LVAs 2015 S
         LVAs 2014 W
         LVAs 2014 S
         LVAs 2013 W
         LVAs 2013 S
         LVAs 2012 W
         LVAs 2012 S
         LVAs 2011 W
         LVAs 2011 S
         LVAs 2010 W
            OOP
               1. Aufgabe
               2. Aufgabe
               3. Aufgabe
               4. Aufgabe
               5. Aufgabe
                  Hinweise
               6. Aufgabe
               7. Aufgabe
               8. Aufgabe
            Typsysteme
         LVAs 2010 S
         LVAs 2009 W
         LVAs 2009 S
         LVAs 2008 W
         LVAs 2008 S
         LVAs 2007 W
         LVAs 2007 S
         LVAs 2006 W
         LVAs 2006 S
         LVAs 2005 W
         LVAs 2005 S
         LVAs 2004 W
         LVAs 2004 S
         LVAs 2003 W
   Links
Sitemap
Kontakt
Fakultät für Informatik
Technische Universität Wien
Anfang | HTML 4.01 | Datenschutzerklärung | letzte Änderung: 2010-12-01 (Puntigam)