Der C3-Linearisierungsalgorithmus für die Methodenauflösung in OO-Sprachen mit Mehrfachvererbung: Suchen Sie nach einer Begründung für einige Implementierungsdetails

7

Gemäß dieser Beschreibung der Python-Methodenauflösungsreihenfolge (mro), auch bekannt als C3-Linearisierung , kann der Algorithmus rekursiv wie folgt beschrieben werden:

L(O) = <O>
L(C) = <C> + merge(L(B1),..., L(Bn), <B1,...,Bn>)

wo

  • O ist die Klasse, von der jede Klasse erbt.
  • Cist eine Klasse, die direkt von B1, ... Bn, in dieser Reihenfolge erbt .
  • <und >sind Listenbegrenzer.
  • + ist der Listenverkettungsoperator.
  • merge führt seine Listenargumente in einer einzigen Liste zusammen, wie nachstehend beschrieben wird.

Das Obige kann in Worten umformuliert werden (zitiert aus dem obigen Python-Dokument):

Die Linearisierung von C ist die Summe von C plus der Zusammenführung der Linearisierungen der Eltern und der Liste der Eltern.

Der mergeAlgorithmus wird wie folgt beschrieben (im Wesentlichen aus dem Python-Dokument zitiert, aber leicht umformuliert):

Betrachten Sie den Kopf der ersten Liste, dh L (B1) [0]: Wenn es sich um einen guten Kopf handelt, dh wenn er sich nicht im richtigen Ende einer der anderen Listen befindet, fügen Sie ihn zur Linearisierung von C hinzu und entfernen Sie ihn es aus allen Listen in der Zusammenführung. Andernfalls betrachten Sie den Kopf der nächsten Liste usw. Wiederholen Sie diesen Vorgang, bis keine Klassen mehr oder keine guten Köpfe mehr vorhanden sind. Im letzteren Fall ist es unmöglich, die Zusammenführung zu konstruieren.

Das folgende Beispiel dient zur Veranschaulichung. Angenommen, Aerbt direkt von Bund Cin dieser Reihenfolge und nehmen an, dass die Linearisierungen von Bund Csind

L(B) = <B, D, E, O>
L(C) = <C, D, F, O>

Dann ist Adie Linearisierung

L(A) = <A> + merge(<B,D,E,O>, <C,D,F,O>, <B,C>)
     = <A, B> + merge(<D,E,O>, <C,D,F,O>, <C>)
     = <A, B, C> + merge(<D,E,O>, <D,F,O>)
     = <A, B, C, D> + merge(<E,O>, <F,O>)
     = <A, B, C, D, E> + merge(<O>, <F,O>)
     = <A, B, C, D, E, F> + merge(<O>, <O>)
     = <A, B, C, D, E, F, O>

Meine Frage ist: Welchen Zweck hat es in Bezug auf die ursprüngliche Beschreibung des Algorithmus, die Liste <B1,...,Bn>der direkten Eltern als Argument anzugeben merge? Wird der Algorithmus unterschiedliche Ergebnisse liefern, wenn dieses Argument weggelassen wird?

algorithms programming-languages type-theory object-oriented Evan Aad
quelle

Antworten:

5

Ohne die letzte Liste:

merge(<B,D,O>, <C,F,O>, <D,O>) =
  <B,D,C,F,O>

Mit der letzten Liste:

merge(<B,D,O>, <C,F,O>, <D,O>, <B,C,D>) =
  <B> + merge(<D,O>, <C,F,O>, <D,O>, <C,D>) =
  <B,C> + merge(<D,O>, <F,O>, <D,O>, <D>) =
  <B,C,D,F,O>

Ohne die letzte Liste:

merge(<B,D,C,O>, <C,F,O>, <D,O>) =
  <B,D,C,F,O>

Mit der letzten Liste:

merge(<B,D,C,O>, <C,F,O>, <D,O>, <B,C,D>) =
  <B> + merge(<D,C,O>, <C,F,O>, <D,O>, <C,D>) =
  no-merge

Intuitiv erzwingt die letzte Liste, dass das Endergebnis mit der Bestellung kompatibel ist <B1,...,Bn>. Dies kann die Reihenfolge ändern oder dazu führen, dass die Zusammenführung fehlschlägt.

Chi
quelle