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.

Ein ähnliches Konzept wie die mehrfache Verteilung ist das in vielen prozeduralen Programmiersprachen möglichen Überladen, bei der Methoden polymorph bezüglich der statischen Typen ihrer Parameter sind. Der Unterschied ist, dass das Überladen bereits zur Übersetzungszeit stattfindet, die mehrfache Verteilung jedoch erst zur Laufzeit.

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),^[1] 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.^[2]

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.

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

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:

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

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

2. Darstellung durch Extension

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

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

3. Darstellung als Intervall

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

   ${\displaystyle M:=\lbrace 10,\dotsc ,20\rbrace }$

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:

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

(defclass any-set ()
  ())

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

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

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)
  ())

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)))

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 empty-set wird als konstante Instanz der Klasse set-by-extension ohne Elemente konstruiert. Die Instanziierung erfolgt in Common Lisp durch die Funktion make-instance unter Angabe der Klasse und des Initialisierungsargumentes, das 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))

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))

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))

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))))

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))))

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)

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)))

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)

• 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.

1. ↑ Common Lisp – The Language. 2nd Edition.
2. ↑ Groovy - Multi-methods

• 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.

• Common Lisp HyperSpec