Visitor statt Multiple Dispatch

4

Vor einiger Zeit hab ich mal Multimethoden vorgestellt. Dabei hab ich auch angedeutet, dass man Multiple Dispatch über das Visitor-Pattern simulieren kann. Das hab ich jetzt mal selbst gebraucht. Da bietet sich direkt mal die Gelegenheit, das vor zu führen. Der Einfachheit halber bleibe ich bei meinem Asteroids-Beispiel.

Normalerweise gibt es beim Visitor-Pattern zwei getrennte Hierarchien: Elemente und Visitor. In unseren Fall fallen beide Hierarchien zusammen. Wir haben nur eine Hierarchie, nämlich die Hierarchie der Objekte, die kollidieren können. Im folgenden betrachten wir daraus Raumschiffe und Asteroiden.

Das Problem ist ja eigentlich, wie im oben verlinkten Blog-Post erläutert, dass der dynamische Typ des Parameters bzw. der Parameter nicht bekannt ist. Zumindest nicht direkt. Der Parameter selbst kennt natürlich seinen dynamischen Typ. Und das ist auch schon die Idee, die man braucht um Multiple Dispatch zu simulieren: Der Parameter weiß den Typ, also kann der Parameter auch gleich die ganze Arbeit machen.

Und so sieht das Ganze im Code aus:

Das wäre die Lösung mit Multimethoden:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Thing
begin
  method collideWith(thing: Thing);
  begin
    // etwas kollidiert mit irgend etwas anderem.
    // default könnte hier ein elastischer Stoß sein.
  end method;
end class;

class SpaceShip extends Thing
begin
  method collideWith(asteroid: Asteroid);
  begin
    // Schiff kollidiert mit Asteroid ==> peng!
  end method;
end class;

class Asteroid extends Thing
begin
  method collideWith(spaceShip: SpaceShip);
  begin
    // Asteroid kollidiert mit Schiff ==> peng!
  end method;

  method collideWith(asteroid: Asteroid);
  begin
    // Asteroid kollidiert mit anderem Asteroid. Hier könnten wir beim
    // elastischen Stoß bleiben oder auch - um die Sache etwas
    // interessanter zu machen - mit ner bestimmten Wahrscheinlichkeit
    // die beiden Asteroiden verschmelzen lassen o.ä.
  end method;
end class;

Der naive Ansatz wäre wohl folgender:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Thing
begin
  method collideWith(thing: Thing);
  begin
    if thing is Asteroid then
    begin
      self.collideWithAsteroid(thing);
    else if thing is SpaceShip then
      self.collideWithSpaceShip(thing);
    else
      self.collideWithThing(thing);
    end if;
  end method;

  method collideWithThing(thing: Thing);
  begin
    // etwas kollidiert mit irgend etwas anderem.
    // default könnte hier ein elastischer Stoß sein.
  end method;

  method collideWithSpaceShip(thing: Thing);
  begin
    // etwas kollidiert mit dem Raumschiff ==> peng
  end method;

  method collideWithAsteroid(thing: Thing);
  begin
    // etwas kollidiert mit einem Asteroid
    // default könnte hier ein elastischer Stoß sein.
  end method;
end class;

class SpaceShip extends Thing
begin
  method collideWithAsteroid(asteroid: Asteroid);
  begin
    // Schiff kollidiert mit Asteroid ==> peng!
  end method;
end class;

class Asteroid extends Thing
begin
  method collideWithShip(ship: SpaceShip);
  begin
    // Asteroid kollidiert mit Schiff ==> peng!
  end method;

  method collideWithAsteroid(asteroid: Asteroid);
  begin
    // Asteroid kollidiert mit anderem Asteroid. Hier könnten wir beim
    // elastischen Stoß bleiben oder auch - um die Sache etwas
    // interessanter zu machen - mit ner bestimmten Wahrscheinlichkeit
    // die beiden Asteroiden verschmelzen lassen o.ä.
  end method;
end class;

Und so kann man das mit dem Visitor-Pattern umsetzen. Anstatt alles selbst machen zu wollen, delegiert man einfach an den Parameter:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Thing
begin
  method collideWith(thing: Thing);
  begin
    thing.collideWithThing(self); // an Parameter weiterreichen
  end;

  method collideWithThing(thing: Thing);
  begin
    // etwas kollidiert mit irgend etwas anderem.
    // default könnte hier ein elastischer Stoß sein.
  end method;

  method collideWithSpaceShip(thing: Thing);
  begin
    // etwas kollidiert mit dem Raumschiff ==> peng
  end method;

  method collideWithAsteroid(thing: Thing);
  begin
    // etwas kollidiert mit einem Asteroid
    // default könnte hier ein elastischer Stoß sein.
  end method;
end class;

class Asteroid extends Thing
begin
  method collideWith(thing: Thing);
  begin
    thing.collideWithAsteroid(self); // an Parameter weiterreichen
  end method;

  method collideWithShip(ship: SpaceShip);
  begin
    // Asteroid kollidiert mit Schiff ==> peng!
  end method;

  method collideWithAsteroid(asteroid: Asteroid);
  begin
    // Asteroid kollidiert mit anderem Asteroid. Hier könnten wir beim
    // elastischen Stoß bleiben oder auch - um die Sache etwas
    // interessanter zu machen - mit ner bestimmten Wahrscheinlichkeit
    // die beiden Asteroiden verschmelzen lassen o.ä.
  end method;
end class;

class SpaceShip extends Thing
begin
  method collideWith(thing: Thing);
  begin
    thing.collideWithSpaceShip(self); // an Parameter weiterreichen
  end method;

  method collideWithAsteroid(asteroid: Asteroid);
  begin
    // Schiff kollidiert mit Asteroid ==> peng!
  end method;
end class;

Der Aufwand ist in etwa gleich mit dem beim naiven Ansatz. Der Vorteil ist hier aber, dass diese Lösung die Polymorphie ausnutzt und man somit um das manuelle und fehleranfällige Prüfen des dynamischen Typs drum herum kommt („Never write code to find code.„). Somit ist dieser Ansatz robuster. Noch schöner wäre natürlich, wenn Multiple Dispatch möglich wäre, aber das ist leider bei den wenigsten Sprachen der Fall.

4 Kommentare


  1. Einen Nachteil sehe ich schon: „Thing“ ist sehr stark an seine geerbten Klassen gekoppelt – wenn ich dem Schema folge, muss ich für jede geerbte Klasse eine weitere Methode anhängen. Wirkt auf mich unschön, denn von einer Klasse zu erben, sollte auf diese keine Wirkung haben, hat in diesem Fall aber schon.

    Eine alternative statisch typisierte Lösung kann ich allerdings nicht anbieten – mir würden nur dynamische Lösungen einfallen. Vielleicht wäre eine solche sogar besser geeignet.


  2. Gut erkannt. Im Kern ist das eine Auswirkung des Expression Problem.

    Man könnte die Klassen besser entkoppeln, wenn man den Visitor nicht auf die bestehenden Klassen mappt, sondern als eigene Klasse realisiert. Das ginge dann in etwa folgendermaßen:
    – Es gibt neben der Thing-Hierarchie eine CollisionVisitor-Hierarchie
    – Thing hat eine Factory-Methode getCollisionVisitor(), die einen passenden Visitor erzeugt. Also SpaceShip.getCollisionVisitor() gibt einen SpaceShipCollisionVisitor zurück.
    – Die collideWith()-Methode holt sich dann zuerst den passenden Visitor vom übergebenen Objekt und ruft darauf dann die passende Methode auf.

    Damit wäre man das Problem los. Thing kennt seine Subklassen nicht mehr und alle Kollisionsmethoden wären in den Visitor-Klassen gruppiert. Der Nachteil hierbei ist natürlich wieder, dass das den gesamten Ansatz noch weiter verkompliziert.

    Vielen Dank für deinen Kommentar. Wie du siehst, bringt er mich auf interessante Ideen. Vielleicht mache ich da einen separaten Blog-Post draus.

    Timo Reitz
    […] mir würden nur dynamische Lösungen einfallen.

    Wie würdest du das in dynamisch typisierten Sprachen lösen?


  3. Den Begriff „Expression Problem“ kannte ich noch gar nicht, danke (das Problem selbst allerdings schon).

    An dynamisch typisierte Sprachen hatte ich gar nicht gedacht, sondern daran, dass die Kollision ausgelagert wird, z.B. in separate Klassen. Jedem Objekt wird dabei nicht nur ein Kollisionsobjekt zugeordnet, sondern mehrere. Wenn nun eine Kollision stattfindet, so wird die Kette durchlaufen, die Kollisionsobjekte prüfen jeweils, ob sie zuständig sind und falls ja, tun sie irgendwas. Standardmäßig könnte als letztes Glied der Kette beispielsweise eine ElasticCollision vorliegen, die einfach immer einen elastischen Stoß repräsentiert. Das entsprechende Pattern heißt „Chain of Responsibility“ (in Sprachen, die Methoden mit gleichen Namen, aber unterschiedlichen Signaturen zulassen, kommt das implizit zur Geltung).

    Ob das wirklich besser ist, weiß ich jedoch nicht, müsste ich mal umfangreicher ausprobieren. 😉


  4. Eine CoR… hm… etwas weniger intuitiv, aber ist ne interessante Idee.

    Ich mein, ich hab Asteroids jetzt nicht wirklich durchdacht. Ich brauchte halt n Beispiel um Multiple Dispatch zu erläutern. Aber Asteroids an sich scheint generell ein interessantes Beispiel zu sein. Wenn ich Zeit hab, mach ich mir dafür vielleicht mal Gedanken…

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert