Multimethode

Als Multimethoden bezeichnet man Methoden einer objektorientierten Programmiersprache, deren Auswahl nicht nur anhand des Typs eines Objekts getroffen wird, sondern anhand der dynamischen Typen mehrerer Objekte. Diese Art der Methodenauswahl wird auch als

multiple dispatch

(‚mehrfache Verteilung‘) bezeichnet.

Zu unterscheiden ist die mehrfache Verteilung von der in vielen prozeduralen Programmiersprachen möglichen Überladung, bei der Methoden polymorph bezüglich der statischen Typen ihrer Parameter sind.

Während bei klassischen objektorientierten Sprachen wie Java ausschließlich der dynamische Typ des impliziten ersten Parameters this herangezogen wird, können in Sprachen mit multiple dispatch Methoden auch auf die dynamischen Typen aller ihrer Parameter spezialisiert werden. Die von vielen (insbesondere C-ähnlichen) kompilierten Sprachen angebotene Überladung entspricht einem multiple dispatch zur Übersetzungszeit. Interessanterweise bieten die meisten Skriptsprachen Multimethoden in Form von Überladung jedoch zu Gunsten dynamischer Typisierung nicht an. Allerdings schließt dynamische Typisierung Multimethoden nicht aus.

Die erste und bekannteste objektorientierte Umgebung, die diese Fähigkeit hat, ist das Common Lisp Object System (CLOS), aber auch Sprachen wie Dylan, Slate, Cecil, Guile, Seed7, Julia oder der Java-Abkömmling Nice bieten Derartiges. In C++ ist es möglich, Multimethoden als Funktoren und Templates auf verschiedene Weisen zu implementieren. In der JVM Welt ist z. B. Groovy eine Java-Syntax-kompatible Sprache mit größerer Verbreitung, die (sowohl bei dynamischer als auch statischer Kompilierung) standardmäßig Multimethoden unterstützt.

Multimethoden in Common Lisp

Die objektorientierte Programmierung mit Multimethoden unterscheidet sich in einigen Punkten grundlegend von eindimensionaler objektorientierter Programmierung. In Common Lisp basieren Multimethoden auf drei elementaren Konzepten, die anders zu verstehen sind als z. B. in Java:

• Klassen: Sie werden immer ohne eigene Methoden definiert. Zur Klassendefinition gehört nur die Liste der Superklassen und die Liste ihrer Slots (= „Membervariablen“). Auch später können der Klassendefinition keinerlei Methoden hinzugefügt werden.
• Generische Funktionen: Statt einer Klasse werden die Methoden unter einer generischen Funktion gleichen Namens zusammengefasst. Die generische Funktion ist selbst nur ein Container für die dazugehörigen Methoden.
• Methoden: Sie kennen keinen impliziten this-Parameter im Sinne eines einzelnen, diese Methode aufrufenden Objekts, weil es sonst auch this2, this3 usw. geben müsste. Stattdessen erscheinen alle angesprochenen Objekte wie normale Parameter in der Parameterliste der Methode.

Praktisches Beispiel in Common Lisp

Das folgende Beispiel verwendet Multimethoden, um die Bildung der Schnittmenge mit drei intern unterschiedlich dargestellten Mengen interoperabel zu implementieren.

Mengendarstellungen

Es sollen die folgenden drei Implementierungen für Mengen unterstützt werden:

1. Darstellung durch Intension

   Hierbei ist die Elementzugehörigkeit durch ein Prädikat gegeben:

   $M:=\lbrace x|P(x)\rbrace$

   Alle Elemente $x$, für die $P(x)$ wahr ist, gehören zu $M$. Die Menge kann unendlich groß sein. Die Darstellung von $P$ erfolgt durch einen anonymen Lambda-Ausdruck.

2. Darstellung durch Extension

   Bei dieser Darstellung werden alle Elemente der Menge aufgezählt:

   $M:=\lbrace 2,39,{\text{HUT}},{\text{STOCK}},{\text{REGENSCHIRM}}\rbrace$

3. Darstellung als Intervall

   Ein zusammenhängendes Intervall aus der Menge $\mathbb {Z}$ bildet die Menge $M$:

   $M:=\lbrace 10,\dotsc ,20\rbrace$

Programmcode

Klassendefinitionen

Für diese drei Darstellungen werden die Klassen set-by-intension, set-by-extension und integer-range-set definiert. Die beiden letzteren sind von der abstrakten Klasse enumeratable-set abgeleitet, die ihrerseits wie set-by-intension von der Hauptklasse any-set abgeleitet ist.

Die Beziehung der Klassen ist demnach wie folgt:

any-set

set-by-intension

enumerateable-set

set-by-extension

integer-range-set

Die Umsetzung der Klassenhierarchie in Common Lisp erfolgt in fünf einzelnen Definitionen.

Klasse any-set (abstrakt)

Common Lisp: (defclass …)

Klassen werden in Common Lisp mit (defclass <superclasses> <slot-definitions>) deklariert. Dabei ist <superclasses> die Liste der Superklassen und <slot-definitions> eine Liste von Slotdefinitionen.

(defclass any-set ()
  ())

Klasse set-by-intension

Diese enthält nur das einstellige Prädikat predicate als Funktion mit Wertebereich $\lbrace w,f\rbrace$, das entscheidet, ob das ihm übergebene Argument zu $M$ gehört:

(defclass set-by-intension (any-set)
  ((predicate :accessor predicate :initarg :predicate)))

Klasse enumerateable-set (abstrakt)

Ihr Zweck ist es, eine gemeinsame Elternklasse für die Klassen set-by-extension und integer-range-set als Bezugspunkt für Methodendefinitionen zur Verfügung zu haben.

(defclass enumerateable-set (any-set)
  ())

Klasse set-by-extension

Common Lisp: Slot-Definitionen

Die Definition von Slots (in Java „Membervariablen“) enthält als erstes den Namen (z. B. ext) und meistens auch den gewünschten Namen der Zugriffsfunktion (getter/setter), die in Lisp „Accessor“ heißt. Meistens wird auch noch der Name des Initialisierungsargumentes hinter dem Schlüsselwort :initarg angegeben, der bei der Instantierung benutzt wird, um dem Slot einen initialen Wert zuzuweisen. Im Beispielprogramm sind der Slotname, der :accessor und das :initarg immer identisch.

Sie enthält nur den Slot ext, der eine Liste der Elemente enthält:

(defclass set-by-extension (enumerateable-set)
  ((ext :accessor ext :initarg :ext)))

Klasse integer-range-set

Diese Form speichert von dem geschlossenen Ganzzahlenbereich den kleinsten Wert from und der größten Wert to.

(defclass integer-range-set (enumerateable-set)
  ((from :accessor from :initarg :from)
   (to   :accessor to   :initarg :to)))

Die leere Menge

Die leere Menge empty-set wird als konstante Instanz der Klasse set-by-extension ohne Elemente konstruiert. Die Instantiierung erfolgt in Common Lisp durch die Funktion make-instance unter Angabe der Klasse und des Initialisierungsargumentes, dass in obiger Klassendefinition :ext heißt. Für dieses Argument wird hier die leere Liste nil übergeben.

(defvar empty-set (make-instance 'set-by-extension :ext nil))

Generische Funktionen

Nun erfolgt die Definition der generischen Funktion enumeration für die Klasse enumerateable-set sowie der generischen Funktion intersection2 für zwei Argumente vom Typ any-set. Generische Funktionen legen nur die Signatur fest, sie definieren nur den Typ der Parameter, nicht die Parameternamen und sie haben keinen Funktionskörper. Die Definitionen kündigen die Existenz von (konkreten) Methoden für die genannten oder von ihnen abgeleitete Klassen an.

(defgeneric enumeration (enumerateable-set))
(defgeneric intersection2 (any-set any-set))

Methoden der generischen Funktion enumeration

Diese beiden Methoden sind noch keine Multimethoden. In Java würden sie einfach mit Enumeration enumeration(); als Methoden einer Klasse SetByExtension deklariert werden. enumeration liefert eine Aufzählung der Elemente einer indirekten Instanz von enumerateable-set, also von direkten Instanzen von set-by-extension und integer-range-set.

(defmethod enumeration ((s set-by-extension))
  (ext s))

(defmethod enumeration ((s integer-range-set))
  (loop for i from (from s) to (to s) collect i))

Konkrete Methoden der generischen Funktion intersection2

Common-Lisp: Funktionen und Makros

(remove-if-not …)

Übernimmt eine Funktion und eine Liste. Die Funktion wird der Reihe nach auf jedes Element der Liste angewandt. Zurückgegeben wird eine neue Liste aller Elemente, für die die Funktion „wahr“ geliefert hat.

---

(intersection ...)

Bildet eine Liste mit der Schnittmenge der Elemente aller übergebenen Listen. (intersection '(1 2 3) '(2 3 4)) liefert z. B. '(2 3).

---

(lambda …)

Übernimmt eine Parameterliste und einen Ausdruck, in dem die in der Liste genannten Parameter vorkommen dürfen. Es liefert eine anonyme Funktion zurück, die mit einer passenden Argumentenliste gerufen werden kann und mit dieser den übergebenen Ausdruck berechnet.

Die fünf Methoden der generischen Funktion intersection2 sind sämtlich Multimethoden.

(defmethod intersection2 ((a set-by-intension) (b enumerateable-set))
  (make-instance 'set-by-extension
         :ext (remove-if-not (predicate a)
                      (enumeration b))))

(defmethod intersection2 ((a set-by-intension) (b set-by-intension))
  ;; In diesem Fall wird aus den beiden Prädikaten von a und
  ;; b ein neues Prädikat durch UND-Verknüpfung zusammengesetzt und
  ;; die Ergebnis-Instanz der Klasse SET-BY-INTENSION damit
  ;; initialisiert:
  (make-instance 'set-by-intension
         :predicate (lambda (x)
                      (and (funcall (predicate a) x)
                           (funcall (predicate b) x)))))

(defmethod intersection2 ((a enumerateable-set) (b set-by-intension))
  (intersection2 b a)) ; Rückführung auf den kommutativen Fall

(defmethod intersection2 ((a enumerateable-set) (b enumerateable-set))
  (make-instance 'set-by-extension
         :ext (intersection (enumeration a) (enumeration b))))

Methode der generischen Funktion intersection2 für Aufrufe mit zwei Parametern der Klasse integer-range-set

Obwohl dieser Fall schon durch die vierte Methode oben abgedeckt ist, bietet es sich hier an, eine spezifischere Methode vorzusehen um wieder ein Ergebnis der Klasse integer-range-set zu erhalten, da deren Darstellung kompakter ist.

(defmethod intersection2 ((a integer-range-set) (b integer-range-set))
  ;; Es wird das Maximum N der unteren und das Minimum M der
  ;; Obergrenzen gebildet. Falls nun N>M gilt, ist die Schnittmenge
  ;; leer, sonst eine Instanz der Klasse INTEGER-RANGE-SET mit den
  ;; Grenzen N und M
  (let ((n (max (from a) (from b)))
        (m (min (to a) (to b))))
    (if (> n m)
      empty-set
      (make-instance 'integer-range-set :from n :to m))))

Zusätzliche Methoden für die generische Funktion intersection2 für den Umgang mit der leeren Menge

Common-Lisp: Der eql-Specializer

Common Lisp kann Methoden einer generischen Funktion nicht nur auf Klassen spezialisieren, sondern auch auf eine einzelne Instanz. Dazu wird als Typ des Parameters nicht eine Klasse angegeben, sondern der Ausdruck (eql <instanz>). Wenn die zugehörige generische Funktion nun mit genau dieser Instanz aufgerufen wird, dann ist diese Methode spezifischer als eine, die an der gleichen Position mit einer passenden Klasse definiert wurde und wird statt dieser aufgerufen.

Mit den folgenden beiden Methoden wird durch Verwendung eines eql-Specializers (siehe Box) erreicht, dass die Schnittmenge aus der leeren Menge und einer beliebigen Menge ohne weitere Untersuchung die leere Menge selbst ist:

(defmethod intersection2 ((a (eql empty-set)) (b any-set))
  empty-set)

(defmethod intersection2 ((a any-set) (b (eql empty-set)))
  empty-set)

print-object–Methoden

Mit obigen Definitionen ist die Funktionalität vollständig umgesetzt. Um den Dialog mit Common Lisp zu vereinfachen, erfolgt nun noch die Definition von geeigneten Methoden für die durch das System vordefinierte Generische Funktion print-object, die das Lisp-System zur Darstellung der Mengen bei der Ausgabe heranzieht.

(defmethod print-object ((s set-by-extension) stream)
  (prin1 (ext s) stream))

(defmethod print-object ((s set-by-intension) stream)
  (format stream "~A" (function-lambda-expression (predicate s))))

(defmethod print-object ((s integer-range-set) stream)
  (format stream "(~A .. ~A)" (from s) (to s)))

Anwendungsbeispiel

Common-Lisp: (loop … )

Das Makro loop ist ein mächtiges Iterationsmittel. loop-Schleifen können zumeist ganz naiv gelesen werden, um ihren Inhalt zu erfassen. Das Beispiel links kann so übersetzt werden:

• „n ist Primzahl wenn für jede natürliche Zahl von 2 bis zur Wurzel aus n gilt, dass der Divisionsrest von n/i niemals null ist“

Davor ist noch die Bedingung $n>1$ gesetzt, da die Zahl 1 im mathematischen Sinn keine Primzahl ist.

Die Gesamtfunktionalität ist aus folgendem Anwendungsbeispiel ersichtlich.

Die Menge aller Primzahlen kann durch das Prädikat prime dargestellt werden.

(defun prime (n)
   (when (> n 1)
      (loop for i from 2 to (isqrt n)
            never (eql 0 (mod n i)))))

Mit dieser Definition als Prädikat ist es jetzt möglich, die Menge aller Primzahlen set-of-primes als Instanz von set-by-intension zu konstruieren:

(set 'set-of-primes (make-instance 'set-by-intension
                                   :predicate #'prime))

Als zweite Menge fungiert die Menge first-100 der ganzen Zahlen von 1 bis 100:

(set 'first-100 (make-instance 'integer-range-set :from 1 :to 100))

Die Schnittmenge beider Mengen, also die Primzahlen von 1 bis 100, kann dann jetzt durch den Aufruf der Generischen Funktion intersection2 berechnet werden:

(intersection2 set-of-primes first-100)

Es erfolgt die korrekte Ausgabe

(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)

Erläuterung

• Am Methodenaufruf ist keine einzelne aufrufende Instanz syntaktisch erkennbar, da alle Parameter gleich behandelt werden. Es gibt kein implizites this, oder ähnliches.
• Methoden werden in Common Lisp nie direkt aufgerufen, sondern ausschließlich auf dem Umweg über die generische Funktion gleichen Namens.
• Die generische Funktion führt den Dispatch auf „eingehängten“ Methoden durch. Dazu ermittelt sie zunächst eine nach Spezifität sortierte Liste der anwendbaren Methoden und ruft die Methode mit der höchsten Spezifität auf. Anwendbar sind dabei alle Methoden, deren formale Parameter entweder den Klassen der aktuellen Parameter entsprechen oder direkt oder indirekt deren Elternklasse sind.
• Wird die Deklaration der generischen Funktion weggelassen, so erledigt Common Lisp das selbst, sobald die erste Methodendefinition erfolgt.
• Die Vererbungsmechanismen innerhalb der Klassenhierarchie bezüglich der Slots („Membervariablen“) arbeiten wie bei eindimensionaler objektorientierter Programmierung.
• In diesem Beispiel wird das Common Lisp Object System (CLOS) nur so weit vorgestellt, wie dies zum Verständnis von Multimethoden erforderlich ist. Der Funktionsumfang von CLOS geht erheblich weiter.
• Multimethoden können die eindimensionale objektorientierte Programmierung vollständig darstellen, aber nicht umgekehrt.

Literatur

• Common Lisp Standard – ANSI INCITS 226-1994 (R2004) (Memento vom 27. September 2009 im Internet Archive)
• Patrick M. Krusenotto Funktionale Programmierung und Metaprogrammierung – Interaktiv in Common Lisp Springer 2016, ISBN 978-3-658-13743-4.

Weblinks

• Common Lisp HyperSpec