Benutzer:West of House/Multimethoden

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 im Einzelnen 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 unendllich 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,HUT,STOCK,REGENSCHIRM\rbrace$

3. Darstellung als Intervall

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

$M:=\lbrace 10,..,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 abgleitet, 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 des Setters/Getters, der in Lisp "Accessor" heißt. Meistens wird auch noch der Name des Intiialisierungsargumentes 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 Ganzahlenbereich 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 heisst. 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 der G.F. intersection2 für zwei Argumente vom Typ any-set. Generische Funktionen haben keinen Funktionskörper und nur anonyme Parameter. 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 G.F. intersection2

Common-Lisp: Funktionen und Macros

(remove-if-not ...)

Übernimmt eine Funktion und eine Liste. Die Funktion wird der Reihe nach auch 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 (G.F.) 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 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 G.F. intersection2 für Aufrufe mit zwei Parametern der Klasse integer-range-set

Obwohl dieser Fall schon durch die dritte 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 Mininum 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 G.F. 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 angegben sondern der Ausdruck (EQL <instanz>). Wenn die zugehörige Generische Funktion nun mit genau dieser Instanz aufgerufen wird, dann hat 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 eine EQL-Specializers (siehe Box) erreicht, dass die Schnittmenge aus der leeren Menge und einer bliebigen 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 Macro loop ist eine mächtiges Iterationsmittel. loop-Schleifen können zumeist ganz naiv gelesen werden, um ihren Inhalt zu erfassen. Das Beipiel 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 ermittlt 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 Deklartion 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 OOP.
• 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 OOP vollständig darstellen, aber nicht umgekehrt.