Liskovs Fluch
Frau Liskov haben wir nicht nur die abstrakten Datentypen, sondern auch noch das nach ihr benannte Prinzip zu verdanken. Letzteres bereitet allerdings gelegentlich Probleme. Und das ganz besonders, wenn Symmetrie angesagt ist.
- Michael Wiedeking
Frau Liskov haben wir nicht nur die abstrakten Datentypen, sondern auch noch das nach ihr benannte Prinzip zu verdanken. Letzteres bereitet allerdings gelegentlich Probleme. Und das ganz besonders, wenn Symmetrie angesagt ist.
Wer weiß noch, was eine Äquivalenzrelation ist? Sie ist zunächst einmal eine Relation. Hierbei soll aber weniger die formale Definition interessieren, und deshalb sei einfach mal vorgestellt, dass eine Relation auf einer Objektmenge M eine Funktion r mit der Signatur
r : (M, M) -> Boolean
ist. Eine Relation ist dann beispielsweise die Kleiner-als-Relation für Zahlen, die angibt, ob eine Zahl kleiner als eine andere ist:
a < b
Also wenn a kleiner als b ist, dann liefert der Ausdruck true, andernfalls false.
Eine Äquivalenzrelation auf der Objektmenge M ist eine Relation, die zusätzliche charakteristische Eigenschaften hat. Ein Äquivalenzrelation ist
- reflexiv,
- symmetrisch und
- transitiv.
Die Gleichheitsrelation ist eine solche Äquivalenzrelation, denn dort gilt:
- x = x (Reflexivität)
- x = y ⇔ y = x (Symmetrie)
- x = y ∧ y = z ⇔ x = z (Transitivität)
Das klingt plausibel und lässt sich entsprechend leicht in die Objektorientierung transportieren. So gibt es in vielen Programmiersprachen so etwas wie equals. Warum auch immer hat man diese Methode in die oberste Oberklasse gepackt und ihr die folgende Schnittstelle gegeben:
class Object {
...
boolean equals(Object o) {
return ...
}
...
}
Die Standardimplementierung vergleicht einfach die Referenzen.
boolean equals(Object o) {
return this == o;
}
Dieses equals ist tatsächlich auch eine Äquivalenzrelation, denn
o.equals(o)
liefert erwartungsgemäß true für alle Objekte (null ist in den meisten Sprachen nicht wirklich ein Objekt).
x.equals(y) == y.equals(x)
stimmt auch. Und wenn
x.equals(y) und y.equals(z)
gilt, dann gilt sicherlich auch
x.equals(z)
Und das gilt natürlich schon alleine deshalb, weil ja eben == auch eine Äquivalenzrelation ist.
Mit Objektorientierung
So weit, so gut. Allerdings kommt man mit der Objektidentität nicht besonders weit. Beispielsweise will man bei Strings nicht nur wissen, ob es sich um ein und denselben String handelt, man würde auch gerne wissen, ob zwei Strings inhaltlich gleich sind. Dank der Objektorientierung lässt sich das auch relativ einfach umsetzen. Es ist nur die equals-Methode zu überschreiben.
Gegeben sei ein Punkt mit ganzzahligen, kartesischen Koordinaten.
class Point {
final int x;
final int y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
Zwei solche Punkte sollen gleich sein, wenn die beiden Koordinaten jeweils übereinstimmen.
new Point(1, 2).equals(new Point(1, 2))
Da die Schnittstelle ein beliebiges Object akzeptiert, muss zunächst geprüft werden, ob es sich bei dem zu vergleichenden Objekt o überhaupt um einen Punkt handelt.
boolean equals(Object o) {
if (o instanceof Point) {
Point that = (Point) o;
return …;
}
return false;
}
Bei dieser Prüfung ist es ganz schön, dass mit der instanceof-Abfrage auch der Sonderfall null mit abgedeckt ist. Und da null auch kein Point ist, wird erwartungsgemäß in diesem Fall false geliefert. Jetzt müssen nur noch die Koordinaten verglichen werden:
return (this.x == that.x) && (this.y == that.y);
Perfekt. Schnell noch überprüfen, ob die Implementierung auch wirklich eine Äquivalenzrelation ist.
Point p = new Point(1, 2);
assert p.equals(p);
Point q = new Point(1, 2);
assert p.equals(q) == q.equals(p);
Point r = new Point(1, 2);
assert (p.equals(q) && q.equals(r)) == p.equals(r);
Das ist weiß Gott kein Beweis, aber ein kleines Indiz dafür, dass man soweit alles richtig gemacht hat.
Etwas Farbe, bitte
Diese Punkte leisten also etwa bei der Darstellung von Graphen hervorragende Arbeit, aber mit der Zeit stellt sich die Sache doch als ein bisschen farblos heraus. Es soll also eine neue Klasse ColoredPoint eingeführt werden, bei der man die Farbe eines Punktes angeben kann. Dabei gibt man der Einfachheit halber nur den Namen der Farbe an, den der Punkt bekommen soll.
class ColoredPoint extends Point {
final String color;
ColoredPoint(int x, int y, String color) {
super(x, y);
this.color = color;
}
}
Es soll hier ignoriert werden, dass ein Überschreiben der equals-Methode auch eine Änderung der hashCode-Methode erforderlich macht. Aber eigentlich geht es hier überhaupt nicht um das Vergleichen, weswegen hier darauf nicht näher eingegangen werden soll.
Point point = new Point(1, 2);
Point black = new ColoredPoint(1, 2, "black");
assert black.equals(point);
assert point.equals(black);
Point red = new ColoredPoint(1, 2, "red");
assert black.equals(red);
Und hier freut sich Frau Liskov, weil man auch hier erfolgreich ein Objekt einer abgeleiteten Klasse anstatt eines Objekts der Oberklasse nutzen konnte.
Dass black.equals(point) auch true liefert, mag ja vielleicht noch korrekt sein, aber dass bei black.equals(red) ein schwarzer Punkt gleich zu einem roten Punkt sein soll, ist dann doch etwas fragwürdig. Also bietet es sich an, auch bei ColoredPoint das equals zu überschreiben.
boolean equals(Object o) {
if (o instanceof ColoredPoint) {
ColoredPoint that = (ColoredPoint) o;
return super.equals(this, that) && this.color.equals(that.color);
}
return false;
}
Point red2 = new ColoredPoint(1, 2, "red");
assert !black.equals(point);
assert !black.equals(red);
assert red.equals(red2);
Dementsprechend sind der farbige Punkt black und der "alte" Punkt point verschieden, weil sie nicht zusammenpassen; black und red sind verschieden, weil sie nicht die gleiche Farbe haben; und red und red2 passen wunderbar zusammen, weil nicht nur deren Koordinaten übereinstimmen, sondern auch deren Farben. Leider gibt es jetzt ein kleines Problem. Denn es gilt immer noch
assert point.equals(black);
Liskows Fluch! So implementiert ist die equals-Funktion leider nicht mehr symmetrisch:
point.equals(black) != black.equals(point)
Das Problem lässt sich auch nicht trivial lösen. Würde man nämlich, was naheliegend erscheint, einfach in der equals-Methode von Point den konkreten Typ prüfen
boolean Point::equals(Object o) {
if (o.getClass() == Point.class) {
Point that = (Point) o;
return (this.x == that.x) && (this.y == that.y);
}
return false;
}
dann würde das Liskovsche Substitutionsprinzip bei abgeleiteten Klassen nicht mehr gelten (losgelöst davon, dass der Fall o == null noch separat behandelt werden müsste). Wird etwa eine neue Klasse abgeleitet, die nach außen Polarkoordinaten hat aber nach wie vor die geerbte Infrastruktur nutzt, gibt es keinen Grund, warum das equals nicht mehr funktionieren sollte.
Umgekehrt kann die abgeleitete Klasse recht einfach entscheiden, was im Falle eines "farblosen" Punkts gemacht werden soll. Nachdem bisher die Punkte immer schwarz dargestellt wurden, ist es doch naheliegend, dass ein "alter" Punkt genau dann bei gleichen Koordinaten als übereinstimmend gilt, wenn die Farbe schwarz ist.
boolean equals(Object o) {
if (o instanceof ColoredPoint) {
ColoredPoint that = (ColoredPoint) o;
return super.equals(that) && this.color.equals(that.color);
} else if (o instanceof Point) {
Point that = (Point) o;
return super.equals(that) && this.color.equals("black");
}
return false;
}
Das ist zwar gut gemeint, ändert aber leider immer noch nichts daran, dass ein Point genau so wie vorher noch nicht korrekt mit einem ColoredPoint umzugehen weiß. Und Frau Liskov kann da auch nicht helfen.
Lösung gesucht
Um das noch einmal festzuhalten: Auch wenn es vielleicht den Anschein haben mag, in diesem Beitrag ginge es um die korrekte Implementierung einer Vergleichsfunktion im Zusammenhang mit Vererbung – darum geht es nicht! Da haben sich schon andere den Kopf drüber zerbrochen; namentlich sei hier nur Josh Bloch erwähnt, der in seinem Buch "Effective Java" ausführlich darüber berichtet. Dass eine Implementierung der Vergleichsfunktion auch eine korrespondierende Hash-Funktion benötigt, hatte ich oben schon erwähnt; aber auch darum geht es nicht. Hier geht es um das allgemein existierende Symmetrieproblem im Zusammenhang mit Vererbung. Das Problem lässt sich etwa auf alle Relationen übertragen, die symmetrisch sein müssen. So verlangt etwa die Vergleichsfunktion a < b, wenn sie umkehrbar sein soll, dass auch b > a gelten soll.
Die Wahl fiel hier nur deshalb auf die Vergleichsfunktion, weil sie unabhängig von der Objektorientierung eindeutig definiert wurde. Und hier stellt sich nun die Frage, ob es überhaupt sinnvoll ist, diese im Zusammenhang mit der Liskovschen Substitutionsforderung allgemein auf Objekte zu übertragen. Da die Forderungen an eine Äquivalenzrelation erhalten bleiben müssen, muss wohl eine Oberklasse besser selbst eindeutig festlegen, was sie von ihren ableitenden Klassen erwartet, oder einfach verhindern, dass von ihr abgeleitet wird.
Wie dem auch sei: Gesucht wird nach einer möglichst einfachen (technischen) Lösung, die exemplarisch bei der Vergleichsfunktion sowohl der Oberklasse als auch den ableitenden Klassen das korrekte, symmetrische Leben so einfach wie möglich machen soll. Vielleicht fällt ja jemandem bis zum nächsten Mal etwas Passendes ein. ()
