Was ist der Punkt der accept () -Methode im Besuchermuster?

85

Es wird viel darüber geredet, die Algorithmen von den Klassen zu entkoppeln. Eines bleibt jedoch nicht erklärt.

Sie benutzen Besucher wie diesen

abstract class Expr {
  public <T> T accept(Visitor<T> visitor) {visitor.visit(this);}
}

class ExprVisitor extends Visitor{
  public Integer visit(Num num) {
    return num.value;
  }

  public Integer visit(Sum sum) {
    return sum.getLeft().accept(this) + sum.getRight().accept(this);
  }

  public Integer visit(Prod prod) {
    return prod.getLeft().accept(this) * prod.getRight().accept(this);
  }

Anstatt visit (element) direkt aufzurufen, fordert Visitor das Element auf, seine visit-Methode aufzurufen. Es widerspricht der erklärten Idee der Klassenunwissenheit über Besucher.

PS1 Bitte erkläre es mit deinen eigenen Worten oder zeige auf eine genaue Erklärung. Weil sich zwei Antworten auf etwas Allgemeines und Ungewisses beziehen.

PS2 Meine Vermutung: Da getLeft()das Basic zurückgegeben Expressionwird, visit(getLeft())würde ein Anruf dazu führen visit(Expression), während ein getLeft()Anruf visit(this)zu einem anderen, angemesseneren Besuchsaufruf führt. So,accept() führt die Typumwandlung (aka Gießen).

PS3 Scalas Pattern Matching = Besuchermuster auf Steroid zeigt, wie viel einfacher das Besuchermuster ohne die Akzeptanzmethode ist. Wikipedia fügt dieser Aussage hinzu : indem ein Artikel verknüpft wird, der zeigt, "dass accept()Methoden nicht erforderlich sind, wenn Reflexion verfügbar ist; führt den Begriff" Walkabout "für die Technik ein".

Val
quelle
Es heißt: "Wenn der Besucher Anrufe annimmt, wird der Anruf basierend auf dem Typ des Angerufenen versandt. Dann ruft der Angerufene die typspezifische Besuchsmethode des Besuchers zurück, und dieser Anruf wird basierend auf dem tatsächlichen Typ des Besuchers abgesetzt." Mit anderen Worten, es sagt das aus, was mich verwirrt. Können Sie aus diesem Grund bitte genauer sein?
Val

Antworten:

150

Das Besuchermuster visit/accept Konstrukte sind ein notwendiges Übel aufgrund von C-ähnliche Sprachen (C #, Java, etc.) Semantik. Das Ziel des Besuchermusters besteht darin, Ihren Anruf mithilfe des doppelten Versands so weiterzuleiten, wie Sie es vom Lesen des Codes erwarten.

Normalerweise ist bei Verwendung des Besuchermusters eine Objekthierarchie beteiligt, bei der alle Knoten von einem Basistyp abgeleitet sind Node, der im Folgenden als bezeichnet wird Node. Instinktiv würden wir es so schreiben:

Node root = GetTreeRoot();
new MyVisitor().visit(root);

Hierin liegt das Problem. Wenn unsere MyVisitorKlasse wie folgt definiert wurde:

class MyVisitor implements IVisitor {
  void visit(CarNode node);
  void visit(TrainNode node);
  void visit(PlaneNode node);
  void visit(Node node);
}

Wenn zur Laufzeit, unabhängig vom tatsächlichen Typ root, unser Aufruf in die Überlastung gehen würde visit(Node node). Dies gilt für alle vom Typ deklarierten Variablen Node. Warum ist das? Da Java und andere C-ähnliche Sprachen bei der Entscheidung, welche Überladung aufgerufen werden soll, nur den statischen Typ oder den Typ berücksichtigen, als den die Variable deklariert ist. Java unternimmt nicht den zusätzlichen Schritt, um bei jedem Methodenaufruf zur Laufzeit zu fragen: "Okay, was ist der dynamische Typ root? Oh, ich verstehe. Es ist einTrainNode . Mal sehen, ob es eine Methode inMyVisitor die einen Parameter vom Typ akzeptiertTrainNode... ". Der Compiler bestimmt zur Kompilierungszeit, welche Methode aufgerufen wird. (Wenn Java tatsächlich die dynamischen Typen der Argumente untersuchen würde, wäre die Leistung ziemlich schrecklich.)

Java bietet uns ein Tool, mit dem der Laufzeittyp (dh der dynamische Typ) eines Objekts beim Aufruf einer Methode berücksichtigt werden kann - der Versand virtueller Methoden . Wenn wir eine virtuelle Methode aufrufen, wird der Aufruf tatsächlich an eine Tabelle im Speicher gesendet, die aus Funktionszeigern besteht. Jeder Typ hat eine Tabelle. Wenn eine bestimmte Methode von einer Klasse überschrieben wird, enthält der Funktionstabelleneintrag dieser Klasse die Adresse der überschriebenen Funktion. Wenn die Klasse eine Methode nicht überschreibt, enthält sie einen Zeiger auf die Implementierung der Basisklasse. Dies verursacht immer noch einen Leistungsaufwand (bei jedem Methodenaufruf werden im Wesentlichen zwei Zeiger dereferenziert: einer zeigt auf die Funktionstabelle des Typs und einer auf die Funktion selbst), aber es ist immer noch schneller, als Parametertypen untersuchen zu müssen.

Das Ziel des Besuchermusters ist es, einen doppelten Versand zu erreichen - wird nicht nur der Typ des Anrufziels berücksichtigt ( MyVisitorüber virtuelle Methoden), sondern auch der Typ des Parameters (welche Art von betrachten Nodewir)? Das Besuchermuster ermöglicht es uns, dies durch die Kombination visit/ zu tun accept.

Indem Sie unsere Linie dahingehend ändern:

root.accept(new MyVisitor());

Wir können bekommen, was wir wollen: Über den Versand virtueller Methoden geben wir den richtigen accept () -Aufruf ein, wie er von der Unterklasse implementiert wurde. In unserem Beispiel mit geben TrainElementwir die TrainElementImplementierung von ein accept():

class TrainNode extends Node implements IVisitable {
  void accept(IVisitor v) {
    v.visit(this);
  }
}

Was weiß der Compiler an dieser Stelle im Rahmen von TrainNode's accept? Es weiß, dass der statische Typ von a thisistTrainNode . Dies ist eine wichtige zusätzliche Information, die dem Compiler im Bereich unseres Aufrufers nicht bekannt war: Dort wusste er rootnur, dass es sich um eine handelt Node. Jetzt weiß der Compiler, dass this( root) nicht nur ein Node, sondern tatsächlich ein ist TrainNode. Infolgedessen bedeutet die eine Zeile im Inneren accept(): v.visit(this)etwas ganz anderes. Der Compiler sucht nun nach einer Überladung visit(), die a benötigt TrainNode. Wenn es keinen findet, kompiliert es den Aufruf zu einer Überladung, die a benötigtNode. Wenn beides nicht vorhanden ist, wird ein Kompilierungsfehler angezeigt (es sei denn, Sie haben eine Überladung, die erforderlich ist object). Die Ausführung wird somit in das eingehen, was wir die ganze Zeit beabsichtigt hatten: MyVisitordie Implementierung von visit(TrainNode e). Es waren keine Abgüsse erforderlich, und vor allem war keine Reflexion erforderlich. Daher ist der Aufwand für diesen Mechanismus eher gering: Er besteht nur aus Zeigerreferenzen und sonst nichts.

Sie haben Recht mit Ihrer Frage - wir können eine Besetzung verwenden und das richtige Verhalten erzielen. Oft wissen wir jedoch nicht einmal, um welchen Knotentyp es sich handelt. Nehmen Sie den Fall der folgenden Hierarchie:

abstract class Node { ... }
abstract class BinaryNode extends Node { Node left, right; }
abstract class AdditionNode extends BinaryNode { }
abstract class MultiplicationNode extends BinaryNode { }
abstract class LiteralNode { int value; }

Und wir haben einen einfachen Compiler geschrieben, der eine Quelldatei analysiert und eine Objekthierarchie erzeugt, die der obigen Spezifikation entspricht. Wenn wir einen Interpreter für die als Besucher implementierte Hierarchie schreiben würden:

class Interpreter implements IVisitor<int> {
  int visit(AdditionNode n) {
    int left = n.left.accept(this);
    int right = n.right.accept(this); 
    return left + right;
  }
  int visit(MultiplicationNode n) {
    int left = n.left.accept(this);
    int right = n.right.accept(this);
    return left * right;
  }
  int visit(LiteralNode n) {
    return n.value;
  }
}

Casting würde uns nicht sehr weit bringen, da wir die Arten leftoder rightin den visit()Methoden nicht kennen . Unser Parser würde höchstwahrscheinlich auch nur ein Objekt vom Typ zurückgeben, Nodedas ebenfalls auf die Wurzel der Hierarchie zeigt, sodass wir dies auch nicht sicher umsetzen können. Unser einfacher Dolmetscher kann also so aussehen:

Node program = parse(args[0]);
int result = program.accept(new Interpreter());
System.out.println("Output: " + result);

Das Besuchermuster ermöglicht es uns, etwas sehr Mächtiges zu tun: Bei einer gegebenen Objekthierarchie können wir modulare Operationen erstellen, die über die Hierarchie arbeiten, ohne dass der Code in die Klasse der Hierarchie selbst eingefügt werden muss. Das Besuchermuster wird beispielsweise in der Compilerkonstruktion häufig verwendet. In Anbetracht des Syntaxbaums eines bestimmten Programms werden viele Besucher geschrieben, die diesen Baum bearbeiten: Typprüfung, Optimierungen und Emission von Maschinencode werden normalerweise als unterschiedliche Besucher implementiert. Im Falle des Optimierungsbesuchers kann er anhand des Eingabebaums sogar einen neuen Syntaxbaum ausgeben.

Das hat natürlich seine Nachteile: Wenn wir der Hierarchie einen neuen Typ hinzufügen, müssen wir visit()der IVisitorSchnittstelle auch eine Methode für diesen neuen Typ hinzufügen und bei allen unseren Besuchern Stub- (oder vollständige) Implementierungen erstellen. accept()Aus den oben beschriebenen Gründen müssen wir auch die Methode hinzufügen . Wenn Ihnen die Leistung nicht so viel bedeutet, gibt es Lösungen für das Schreiben von Besuchern, ohne die zu benötigen. accept()Diese beinhalten jedoch normalerweise Reflexionen und können daher einen ziemlich hohen Overhead verursachen.

Atanamir
quelle
5
Das effektive Java-Element Nr. 41 enthält die folgende Warnung: " Vermeiden Sie Situationen, in denen derselbe Parametersatz durch Hinzufügen von Casts an unterschiedliche Überladungen übergeben werden kann. " Die accept()Methode wird erforderlich, wenn diese Warnung im Besucher verletzt wird.
jaco0646
" Normalerweise ist bei Verwendung des Besuchermusters eine Objekthierarchie beteiligt, bei der alle Knoten von einem Basisknotentyp abgeleitet sind. " Dies ist in C ++ absolut nicht erforderlich. Siehe Boost.Variant, Eggs.Variant
Jean-Michaël Celerier
Es scheint mir, dass wir in Java die Methode accept nicht wirklich brauchen, weil wir in Java immer die spezifischste
Gilad Baruchian
1
Wow, das war eine großartige Erklärung. Es ist aufschlussreich zu sehen, dass alle Schatten des Musters auf Compiler-Einschränkungen zurückzuführen sind, und jetzt wird dank Ihnen klar.
Alfonso Nishikawa
@ GiladBaruchian, der Compiler generiert einen Aufruf der spezifischsten Typmethode, die der Compiler bestimmen kann.
mmw
15

Das wäre natürlich albern, wenn das das einzige wäre so Accept implementiert würde.

Aber es ist nicht.

Zum Beispiel sind Besucher wirklich sehr nützlich, wenn es um Hierarchien geht. In diesem Fall könnte die Implementierung eines nicht-terminalen Knotens so aussehen

interface IAcceptVisitor<T> {
  void Accept(IVisit<T> visitor);
}
class HierarchyNode : IAcceptVisitor<HierarchyNode> {
  public void Accept(IVisit<T> visitor) {
    visitor.visit(this);
    foreach(var n in this.children)
      n.Accept(visitor);
  }

  private IEnumerable<HierarchyNode> children;
  ....
}

Siehst du? Was Sie als dumm beschreiben, ist die Lösung für das Durchqueren von Hierarchien.

Hier ist ein viel längerer und ausführlicher Artikel, der mir den Besucher verständlich gemacht hat .

Bearbeiten: Zur Verdeutlichung: Die Besuchermethode Visitenthält Logik, die auf einen Knoten angewendet werden soll. Die AcceptMethode des Knotens enthält eine Logik zum Navigieren zu benachbarten Knoten. Der Fall, wo Sie nur doppelt versenden, ist ein Sonderfall, in dem einfach keine benachbarten Knoten zum Navigieren vorhanden sind.

George Mauer
quelle
7
Ihre Erklärung erklärt nicht, warum es eher die Verantwortung des Knotens als die entsprechende visit () -Methode des Besuchers sein sollte, um die Kinder zu wiederholen? Meinen Sie damit, dass die Hauptidee darin besteht, den Hierarchie-Traversal-Code zu teilen, wenn wir dieselben Besuchsmuster für verschiedene Besucher benötigen? Ich sehe keine Hinweise aus dem empfohlenen Papier.
Val
1
Zu sagen, dass Akzeptieren gut für die routinemäßige Durchquerung ist, ist vernünftig und für die allgemeine Bevölkerung wertvoll. Aber ich habe mein Beispiel aus jemandes "Ich konnte das Besuchermuster erst verstehen, als ich andymaleh.blogspot.com/2008/04/… gelesen habe " genommen. Weder dieses Beispiel noch Wikipedia oder andere Antworten erwähnen den Navigationsvorteil. Trotzdem fordern sie alle dieses blöde Akzeptieren (). Deshalb stelle ich meine Frage: Warum?
Val
1
@Val - was meinst du? Ich bin mir nicht sicher, was du fragst. Ich kann nicht für andere Artikel sprechen, da diese Leute unterschiedliche Ansichten zu diesem Thema haben, aber ich bezweifle, dass wir uns nicht einig sind. Im Allgemeinen können bei der Berechnung viele Probleme auf Netzwerke abgebildet werden, sodass eine Verwendung möglicherweise nichts mit Diagrammen in der Oberfläche zu tun hat, sondern tatsächlich ein sehr ähnliches Problem darstellt.
George Mauer
1
Die Angabe eines Beispiels, wo eine Methode nützlich sein könnte, beantwortet nicht die Frage, warum die Methode obligatorisch ist. Da die Navigation nicht immer benötigt wird, eignet sich die Methode accept () nicht immer für Besuche. Wir sollten daher in der Lage sein, unsere Ziele ohne sie zu erreichen. Trotzdem ist es obligatorisch. Dies bedeutet, dass es einen stärkeren Grund für die Einführung von accept () in jedes Besuchermuster gibt als "es ist manchmal nützlich". Was ist in meiner Frage nicht klar? Wenn Sie nicht versuchen zu verstehen, warum Wikipedia nach Möglichkeiten sucht, Akzeptanz zu beseitigen, sind Sie nicht daran interessiert, meine Frage zu verstehen.
Val
1
@Val Das Papier, das sie mit "Die Essenz des Besuchermusters" verknüpfen, stellt in seiner Zusammenfassung die gleiche Trennung von Navigation und Bedienung fest, die ich gegeben habe. Sie sagen lediglich, dass die GOF-Implementierung (nach der Sie fragen) einige Einschränkungen und Belästigungen aufweist, die durch Reflexion beseitigt werden können. Deshalb führen sie das Walkabout-Muster ein. Dies ist sicherlich nützlich und kann viel von dem tun, was der Besucher kann, aber es ist eine Menge ziemlich ausgefeilter Code und verliert (bei einer flüchtigen Lesart) einige Vorteile der Typensicherheit. Es ist ein Werkzeug für die Toolbox, aber schwerer als der Besucher
George Mauer
0

Der Zweck des Besuchermusters besteht darin, sicherzustellen, dass Objekte wissen, wann der Besucher mit ihnen fertig ist und abgereist ist, damit die Klassen anschließend alle erforderlichen Aufräumarbeiten durchführen können. Außerdem können Klassen ihre Interna "vorübergehend" als "ref" -Parameter verfügbar machen und wissen, dass die Interna nicht mehr verfügbar sind, sobald der Besucher weg ist. In Fällen, in denen keine Bereinigung erforderlich ist, ist das Besuchermuster nicht besonders nützlich. Klassen, die keines dieser Dinge tun, profitieren möglicherweise nicht vom Besuchermuster, aber Code, der zur Verwendung des Besuchermusters geschrieben wurde, kann mit zukünftigen Klassen verwendet werden, die nach dem Zugriff möglicherweise bereinigt werden müssen.

Angenommen, eine Datenstruktur enthält viele Zeichenfolgen, die atomar aktualisiert werden sollen, aber die Klasse, die die Datenstruktur enthält, weiß nicht genau, welche Arten von atomaren Aktualisierungen durchgeführt werden sollen (z. B. wenn ein Thread alle Vorkommen von "ersetzen möchte). X ", während ein anderer Thread eine beliebige Ziffernfolge durch eine numerisch höhere Folge ersetzen möchte, sollten die Operationen beider Threads erfolgreich sein. Wenn jeder Thread einfach eine Zeichenfolge vorliest, seine Aktualisierungen durchführt und sie zurückschreibt, den zweiten Thread das Zurückschreiben seiner Zeichenfolge würde die erste überschreiben). Eine Möglichkeit, dies zu erreichen, besteht darin, dass jeder Thread eine Sperre erhält, seine Operation ausführt und die Sperre aufhebt. Wenn Schlösser auf diese Weise freigelegt werden,

Das Besuchermuster bietet (mindestens) drei Ansätze, um dieses Problem zu vermeiden:

  1. Es kann einen Datensatz sperren, die bereitgestellte Funktion aufrufen und dann den Datensatz entsperren. Der Datensatz kann für immer gesperrt werden, wenn die angegebene Funktion in eine Endlosschleife fällt. Wenn die angegebene Funktion jedoch eine Ausnahme zurückgibt oder auslöst, wird der Datensatz entsperrt (es kann sinnvoll sein, den Datensatz als ungültig zu markieren, wenn die Funktion eine Ausnahme auslöst es ist wahrscheinlich keine gute Idee). Beachten Sie, dass es wichtig ist, dass ein Deadlock auftreten kann, wenn die aufgerufene Funktion versucht, andere Sperren zu erhalten.
  2. Auf einigen Plattformen kann ein Speicherort übergeben werden, der die Zeichenfolge als 'ref'-Parameter enthält. Diese Funktion könnte dann die Zeichenfolge kopieren, eine neue Zeichenfolge basierend auf der kopierten Zeichenfolge berechnen, versuchen, die alte Zeichenfolge mit der neuen zu vergleichen, und den gesamten Vorgang wiederholen, wenn CompareExchange fehlschlägt.
  3. Es kann eine Kopie der Zeichenfolge erstellen, die angegebene Funktion für die Zeichenfolge aufrufen und dann mit CompareExchange selbst versuchen, das Original zu aktualisieren, und den gesamten Vorgang wiederholen, wenn CompareExchange fehlschlägt.

Ohne das Besuchermuster würde das Ausführen atomarer Aktualisierungen das Aufdecken von Sperren und das Risiko eines Fehlers erfordern, wenn die aufrufende Software nicht einem strengen Sperr- / Entsperrprotokoll folgt. Mit dem Besuchermuster können atomare Aktualisierungen relativ sicher durchgeführt werden.

Superkatze
quelle
2
1. Besuchen bedeutet, dass Sie nur Zugriff auf öffentliche Besuchsmethoden haben, sodass interne Sperren für die Öffentlichkeit zugänglich sein müssen, damit sie für Besucher nützlich sind. 2 / Keines der Beispiele, die ich zuvor gesehen habe, impliziert, dass der Besucher zum Ändern des Status des Besuchs verwendet werden soll. 3. "Mit dem traditionellen VisitorPattern kann man nur bestimmen, wann wir einen Knoten betreten. Wir wissen nicht, ob wir den vorherigen Knoten verlassen haben, bevor wir den aktuellen Knoten betreten haben." Wie entsperren Sie nur mit visit anstelle von visitEnter und visitLeave? Schließlich fragte ich eher nach Anwendungen von accpet () als nach Visitor.
Val
Vielleicht bin ich mit der Terminologie für Muster nicht ganz auf dem neuesten Stand, aber das "Besuchermuster" scheint einem Ansatz zu ähneln, den ich verwendet habe, bei dem X Y einen Delegaten übergibt, an den Y dann Informationen weitergeben kann, die nur gültig sein müssen als solange der Delegat läuft. Vielleicht hat dieses Muster einen anderen Namen?
Supercat
2
Dies ist eine interessante Anwendung des Besuchermusters auf ein bestimmtes Problem, beschreibt jedoch nicht das Muster selbst oder beantwortet nicht die ursprüngliche Frage. "In Fällen, in denen keine Bereinigung erforderlich ist, ist das Besuchermuster nicht besonders nützlich." Diese Behauptung ist definitiv falsch und bezieht sich nur auf Ihr spezifisches Problem und nicht auf das Muster im Allgemeinen.
Tony O'Hagan
0

Die Klassen, die geändert werden müssen, müssen alle die Methode 'accept' implementieren. Clients rufen diese Akzeptanzmethode auf, um eine neue Aktion für diese Klassenfamilie auszuführen und dadurch ihre Funktionalität zu erweitern. Kunden können diese One-Accept-Methode verwenden, um eine Vielzahl neuer Aktionen auszuführen, indem sie für jede bestimmte Aktion eine andere Besucherklasse übergeben. Eine Besucherklasse enthält mehrere überschriebene Besuchsmethoden, die definieren, wie dieselbe spezifische Aktion für jede Klasse innerhalb der Familie ausgeführt werden soll. Diese Besuchsmethoden erhalten eine Instanz, an der gearbeitet werden soll.

Besucher sind nützlich, wenn Sie einer stabilen Klassenfamilie häufig Funktionen hinzufügen, ändern oder entfernen, da jedes Funktionselement in jeder Besucherklasse separat definiert wird und die Klassen selbst nicht geändert werden müssen. Wenn die Klassenfamilie nicht stabil ist, ist das Besuchermuster möglicherweise weniger nützlich, da viele Besucher jedes Mal geändert werden müssen, wenn eine Klasse hinzugefügt oder entfernt wird.

Andrew Pate
quelle
-1

Ein gutes Beispiel ist die Quellcode-Kompilierung:

interface CompilingVisitor {
   build(SourceFile source);
}

Kunden können ein implementieren JavaBuilder, RubyBuilder,XMLValidator usw. und die Umsetzung für das Sammeln und den Besuch der alle Quelldateien in einem Projekt nicht ändern müssen.

Dies wäre ein schlechtes Muster, wenn Sie für jeden Quelldateityp separate Klassen haben:

interface CompilingVisitor {
   build(JavaSourceFile source);
   build(RubySourceFile source);
   build(XMLSourceFile source);
}

Es kommt auf den Kontext an und darauf, welche Teile des Systems erweiterbar sein sollen.

Garrett Hall
quelle
Die Ironie ist, dass VisitorPattern uns anbietet, das schlechte Muster zu verwenden. Es heißt, dass wir eine Besuchsmethode für jede Art von Knoten definieren müssen, die besucht werden soll. Zweitens ist nicht klar, welche Beispiele gut oder schlecht sind. Wie hängen sie mit meiner Frage zusammen?
Val