Multimethoden oder: wie Asteroids zu SpaceBillard mutiert

Ein Feature, das ich bei den etablierten objektorientierten Programmiersprachen vermisse, sind Multimethoden, auch bekannt unter dem Namen „multiple dispatch“. Ein kurzes Beispiel soll verdeutlichen, was Multimethoden sind und was sie so interessant macht.

„Asteroids“ ist manchem vielleicht ein Begriff. Es handelt sich dabei um ein Arcade-Spiel aus dem Jahre 1979 (mit diversen Klonen, Abwandlungen, Portierungen, etc.). Der Spieler steuert ein kleines Raumschiff und muss Asteroiden und gegnerischen Raumschiffen ausweichen bzw. sie durch Abschießen unschädlich machen. Wird das Raumschiff von gegerischem Feuer oder von Asteroiden getroffen, wird es zerstört. Vielleicht hat das Raumschiff noch einen Schild, aber um so Feinheiten gehts mir hier nicht. Die Frage ist: Wie implementiert man sowas?

Nun, letztendlich hat man wohl eine Klasse Thing und davon abgeleitete Klassen SpaceShip (das Schiff), Fire (das, was das Schiff verschießt), Asteroid und ggf. noch ein paar andere. Interessant ist jetzt die Kollision. Wie wird die realisiert? So vielelicht[1]:

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
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 Fire extends Thing
begin
  method collideWith(asteroid: Asteroid);
  begin
    // der Asteroid wird gespalten und die Teile ändern ihre Richtung
    // ist der Asteroid sehr klein, wird er zerstört
  end method;
end class;

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

class Game
begin
  method nextStep();
  var
    thing, otherThing: Thing;
  begin
    // alle "Dinge" auf der Karte durchgehen, sie bewegen und ggf. kollidieren lassen
    for each thing in allThings do
    begin
      thing.move(); // alle Dinge einen Schitt weiter bewegen
      for each otherThing in allThings do
      begin
        // wenn etwas mit etwas anderem kollidiert, dann rufe die
        // entsprechende Methode auf, die das behandelt
        if doCollide(thing, otherThing) then
          thing.collideWith(otherThing);
      end for each;
    end for each;
  end method;
end class;

Sieht doch gut aus so, oder? Ja, sieht gut aus, nur funktionierts so nicht. Nicht in Delphi, nicht in Java, nicht in C++ und auch nicht in C#[2]. Das Schiff wird niemals zerstört, es wird immer nur das Default-Verhalten, der elastische Stoß, zu beobachten sein. Ebenso wird das Schiff mit seinem Feuer die Asteroiden zwar anstoßen können, jedoch nicht mehr. Das ist dann vielleicht SpaceBillard, aber kein Asteroids.

Was ist das Problem? Sofern wir keine ‚exotische‘ Sprache einsetzen, die Multimethoden kennt, haben wir nur single dispatch zur Verfügung. In objektorientierten Sprachen bestimmt ja der dynamische Typ einer Variablen, welche Methode aufgerufen wird.

1
2
3
4
5
var
  foo: Foo;
begin
  foo := new Bar.create(); // Bar ist von Foo abgeleitet
  foo.test(); // es wird Bar.test() aufgerufen

Der implizite Parameter Self/this ist aber der einzige für den der dynamische Typ betrachtet wird. Ansonsten richtet sich der Compiler nach dem statischen Typ. Und genau das ist unser Problem hier: thing und otherThing sind jeweils als Thing deklariert, enthalten aber Asteroiden und Schiffe. Angenommen thing ist ein Asteroid und otherThing ist unser Raumschiff und diese kollidieren. Wir erwarten eigentlich, dass die Methode Asteroid.collideWith(SpaceShip) aufgerufen wird. Da aber der statische Typ von otherThing immer noch Thing ist, wird stattdessen Asteroid.collideWith(Thing) aufgerufen. Deshalb ist es hier notwendig, händisch den Typ zu prüfen und dann zu verzweigen, das Visitor-Pattern zu bemühen oder sonst einen Workaround einzubauen.

Bei Multimethoden ist das anders. Dort wird der dynamische Typ von allen Parametern betrachtet und nicht nur der von Self/this. Deshalb auch der Name „multiple dispatch“. Manchmal wär sowas ja schon praktisch…

[1] Dass man auch mit mehreren Dingen gleichzeitig zusammenstoßen kann, ignorieren wir hier mal.
[2] Wie ich gerade gelesen habe, wird es in C# 4.0 möglich sein, multiple dispatch zu realisieren. Der im verlinkten Artikel gezeigte Ansatz mit den statischen Methoden gefällt mir zwar nicht, jedoch denke ich, dass auch die schönere Variante mit Instanzmethoden möglich wäre.

9 Kommentare



  1. Ich musste gerade selbst erst einmal eine Testanwendung schreiben, um zu verstehen, wo überhaupt das Problem ist. Aber es ist in der Tat ziemlich interessant.

    Soweit ich das gesehen habe, hat Delphi eher ein implizites Syntaxproblem: Damit die generelle Methode procedure DoSomething(Item : TItem); virtual; überladen werden kann, muss schon die virtuelle Methode mit overload geflaggt werden. Ansonsten wirft der Compiler bei der abgeleiteten Klasse den Fehler „Bei der vorherigen Deklaration von DoSomething wurde die Direktive ‚overload‘ nicht angegeben“. Overloading ist aber notwendig, um auf die verschiedenen Typen reagieren zu können.

    Wenn man die virtuelle Methode der Ausgangsklasse nun mit mehreren Methoden überschreiben will, erhält man für alle überladenen Methoden in der abgeleiteten Klasse den Fehler „Methode ‚DoSomething‘ nicht in Basisklasse gefunden“.

    Dieses Problem tritt in Delphi übrigens nur mit überladenen Methoden auf. Das von dir gezeigte Problem konnte ich in Delphi nicht feststellen. So liefert folgendes Programm zum Beispiel die korrekte Ausgabe:
    Ich benutze gerade ein Auto
    Ich benutze gerade ein Flugzeug

    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
    program Project1;

    {$APPTYPE CONSOLE}

    uses
      Unit1;

    var
      Item  : TItem;
      Line  : String;
      Owner : TItem;

    begin
      Owner := TOwner.Create;
      try
        Item := TAuto.Create;
        try
          Owner.DoSomething(Item);
        finally
          Item.Free;
        end;

        Item := TFlugzeug.Create;
        try
          Owner.DoSomething(Item);
        finally
          Item.Free;
        end;
      finally
        Owner.Free;
      end;

      ReadLn(Line);
    end.
    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
    unit Unit1;

    interface

    type
      TItem = class
      public
        procedure DoSomething(Item : TItem); virtual;
      end;

      TAuto = class(TItem)
      public
        procedure DoSomething(Item : TItem); override;
      end;

      TFlugzeug = class(TItem)
      public
        procedure DoSomething(Item : TItem); override;
      end;

      TOwner = class(TItem)
      public
        procedure DoSomething(Item : TItem); override;
      end;

    implementation

    procedure TItem.DoSomething(Item : TItem);
    begin
      WriteLn('ein Ding');
    end;

    procedure TAuto.DoSomething(Item : TItem);
    begin
      WriteLn('ein Auto');
    end;

    procedure TFlugzeug.DoSomething(Item : TItem);
    begin
      WriteLn('ein Flugzeug');
    end;

    procedure TOwner.DoSomething(Item : TItem);
    begin
      Write('Ich benutze gerade ');
      Item.DoSomething(nil);
    end;

    end.

    P.S.: Falls du tatsächlich das Problem mit der Überladung gemeint haben solltest, dann war das aus dem Text und dem Quelltext nicht ersichtlich, da dein Beispielquelltext keine überladene Methode enthält. Zudem ist dann auch der von dir geschilderte Quelltext nicht korrekt, denn implizit ist otherThing weiterhin eine Instanz der Klasse, von der es erzeugt worden ist.


  2. Ich habe gerade nochmal ein bisschen weiter probiert und bin auf eine andere Sache gestoßen: Delphi erlaubt die Kompilierung nur, wenn für die Variablentypen, mit denen eine Methode aufgerufen wird, eine exakt passende Parameterliste existiert. Der folgende Quelltext ist deshalb nicht kompilierbar:

    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
    program Project1;

    {$APPTYPE CONSOLE}

    uses
      Unit1;

    var
      ItemA : TItem;
      ItemB : TItem;
      Line  : String;
      Owner : TOwner;

    begin
      Owner := TOwner.Create;
      try
        ItemA := TAuto.Create;
        try
          ItemB := TFlugzeug.Create;
          try
            Owner.DoOwner(ItemA, ItemB);
          finally
            ItemB.Free;
          end;
        finally
          ItemA.Free;
        end;
      finally
        Owner.Free;
      end;

      ReadLn(Line);
    end.
    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
    59
    60
    61
    62
    unit Unit1;

    interface

    type
      TItem = class
      public
        procedure DoThing; virtual;
      end;

      TAuto = class(TItem)
      public
        procedure DoThing; override;
      end;

      TFlugzeug = class(TItem)
      public
        procedure DoThing; override;
      end;

      TOwner = class
      public
        procedure DoOwner(Auto : TAuto; Flugzeug : TFlugzeug); overload;
        procedure DoOwner(Auto : TAuto; AutoB : TAuto); overload;
      end;

    implementation

    procedure TItem.DoThing;
    begin
      Write('ein Ding');
    end;

    procedure TAuto.DoThing;
    begin
      Write('ein Auto');
    end;

    procedure TFlugzeug.DoThing;
    begin
      Write('ein Flugzeug');
    end;

    procedure TOwner.DoOwner(Auto : TAuto; Flugzeug : TFlugzeug);
    begin
      Write('Ich lade ');
      Auto.DoThing;
      Write(' in ');
      Flugzeug.DoThing;
      WriteLn(' ein');
    end;

    procedure TOwner.DoOwner(Auto : TAuto; AutoB : TAuto);
    begin
      Write('Ich hänge ');
      Auto.DoThing;
      Write(' an ');
      AutoB.DoThing;
      WriteLn(' an');
    end;

    end.

    Das Verhalten ist, meiner Meinung nach, jedoch sogar durchaus verständlich! Was würde zum Beispiel passieren, wenn nun 2 Flugzeuge übergeben werden würden? Würde der Quelltext einfach kompiliert werden, würden wir hier in eine Runtime-Exception laufen, die Delphi mit seinem starren Typensystem zu verhindern versucht.


  3. Hallo Kevin,

    schön dich hier auch mal zu sehen. 🙂

    Ich fürchte, du hast das Problem nicht ganz verstanden:

    Delphi – und die meisten anderen OO-Sprachen auch – haben nur Single-Dispatch. d.h. die Methodenauswahl geschieht nur aufgrund des dynamischen Typs des impliziten Self-Parameters (und der statischen Typen der Parameter). Die dynamischen Typen der Parameter spielen dabei keine Rolle. Und das ist das Problem. Der Unterschied zwischen statischem und dynamischen Typ ist dir klar?

    Damit du den Effekt sehen kannst, musst du ne überladene Methode haben, wobei die Typen des Parameters über ne Vererbungsbeziehung miteinander zusammenhängen. Und dann übergibst du als Parameter n Objekt mit dem statischen Typ der allgemeineren Klasse und dem dynamischen der spezielleren. Und in so nem Fall wird nur der statische Typ berücksichtigt, obwohl das in manchen Fällen unpraktisch ist.

    Aber jetzt nochmal langsam. Mit Beispiel:

    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
    // Das sollte echtes Delphi sein
    // (und kein Pseudocode).
    // Ich habs aber keinem Compiler zu fressen gegeben

    type
      TBase = class
      end;

      TDerived = class(TBase)
      end;

      TOther = class
      public
        procedure Foo(bar: TBase);
        procedure Foo(bar: TDerived);
      end;

    implementation

    procedure TOther.Foo(bar: TBase);
    begin
      WriteLn('mein Parameter ist ein TBase');
    end;

    procedure TOther.Foo(bar: TDerived);
    begin
      WriteLn('mein Parameter ist ein TDerived');
    end;
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    var
      other: TOther;
      bar: TBase;  // statischer Typ TBase
    begin
      other := nil;
      bar := nil;
      try
        other := TOther.Create;
        bar := TDerived.Create;  // dynamischer Typ TDerived
        other.Foo(bar);
      finally
        other.Free;
        bar.Free;
      end;
    end;

    Die Ausgabe ist „mein Parameter ist ein TBase“ und nicht etwa „mein Parameter ist ein TDerived“. Das ist aber manchmal unpraktisch. Probier einfach mal das Asteroids-Beispiel, Da wirst du sehen, dass in den Fall Multiple Dispatch helfen würde…

    mfg

    Christian


  4. Hallo… ja, der Unterschied zwischen dem dynamischen Typ und dem statischen Typ ist mir klar 😀 ! Dann hatte ich das Problem beim zweiten Mal also richtig verstanden 😉 .


  5. Dann hatte ich das Problem beim zweiten Mal also richtig verstanden ;-).

    Welches zweite Mal? Dein zweiter Kommentar hier? Kann das irgendwie nicht so rauslesen… egal…

    mfg

    Christian


  6. Ich hab mal auf meine neue Pseudocode-Syntax aktualisiert.



Schreibe einen Kommentar

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