Quel est le but de la méthode accept() dans le pattern Visitor?

Question

Il y a beaucoup de discussions sur le découplage des algorithmes des classes. Mais, une chose reste non expliquée.

Ils utilisent un visiteur comme ceci

abstract class Expr {
  public < T > T accept(Visitor visitor) { return 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);
  }
}

Au lieu d'appeler directement visit(element), le Visiteur demande à l'élément d'appeler sa méthode de visite. Cela contredit l'idée déclarée d'un manque de connaissance des classes sur les visiteurs.

PS1 Veuillez expliquer avec vos propres mots ou indiquer une explication précise. Parce que deux réponses que j'ai reçues font référence à quelque chose de général et incertain.

PS2 Mon hypothèse: Puisque getLeft() retourne l'expression de base Expression, l'appel de visit(getLeft()) entraînerait visit(Expression), tandis que l'appel de getLeft() à visit(this) entraînerait une autre invocation de visite plus appropriée. Ainsi, accept() réalise la conversion de type (alias le cast).

PS3 L'association de correspondance de modèles de Scala = Modèle de visiteur sur stéroïdes montre à quel point le modèle de visiteur est plus simple sans la méthode accept. Wikipedia ajoute à cette déclaration: en reliant un article montrant "que les méthodes accept() ne sont pas nécessaires lorsque la réflexion est disponible ; introduit le terme 'Walkabout' pour la technique."

Answer 1

Les constructions visit/accept du pattern visiteur sont un mal nécessaire en raison de la sémantique des langages de type C (C#, Java, etc.). L'objectif du pattern visiteur est d'utiliser le double dispatch pour router votre appel comme vous vous y attendriez en lisant le code.

Normalement, lorsque le pattern visiteur est utilisé, une hiérarchie d'objets est impliquée où tous les nœuds sont dérivés d'un type de base Node, désigné dorénavant par Node. Instinctivement, nous l'écririons ainsi :

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

Voici le problème. Si notre classe MyVisitor était définie comme suit :

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

S'il s'avère, lors de l'exécution, que quel que soit le type réel de root, notre appel irait vers la surcharge visit(Node node). Cela serait vrai pour toutes les variables déclarées de type Node. Pourquoi ? Parce que Java et d'autres langages de type C se contentent de considérer le type statique, c'est-à-dire le type déclaré de la variable, du paramètre lors de la décision de l'appel à la surcharge. Java ne va pas vérifier, pour chaque appel de méthode, lors de l'exécution, "D'accord, quel est le type dynamique de root ? Ah, je vois. C'est un TrainNode. Voyons s'il y a une méthode dans MyVisitor qui accepte un paramètre de type TrainNode...". Le compilateur, lors de la compilation, détermine quelle méthode sera appelée. (Si Java inspectait effectivement les types dynamiques des arguments, les performances seraient assez mauvaises.)

Java nous donne un outil pour prendre en compte le type d'exécution (c'est-à-dire dynamique) d'un objet lors de l'appel d'une méthode -- la dispatche de méthode virtuelle. Lorsque nous appelons une méthode virtuelle, l'appel se fait en réalité vers une table en mémoire constituée de pointeurs de fonction. Chaque type possède une table. Si une méthode particulière est redéfinie par une classe, l'entrée de la table de fonction de cette classe contiendra l'adresse de la fonction redéfinie. Si la classe ne redéfinit pas une méthode, elle contiendra un pointeur vers l'implémentation de la classe de base. Cela engendre quand même un surcoût de performance (chaque appel de méthode sera essentiellement la déréférencement de deux pointeurs : l'un pointant vers la table de fonction du type et un autre pointant vers la fonction elle-même), mais c'est toujours plus rapide que d'inspecter les types de paramètres.

L'objectif du pattern visiteur est d'accomplir double dispatch -- non seulement le type de la cible d'appel est considéré (MyVisitor, via les méthodes virtuelles), mais aussi le type du paramètre (de quel type de Node s'agit-il) ? Le pattern Visiteur nous permet de faire cela grâce à la combinaison visit/accept.

En changeant notre ligne comme ceci :

root.accept(new MyVisitor());

Nous pouvons obtenir ce que nous voulons : via la dispatche de méthode virtuelle, nous entrons dans l'appel accept() correct tel qu'implémenté par la sous-classe -- dans notre exemple avec TrainElement, nous entrerons dans l'implémentation de accept() de TrainElement :

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

Que sait le compilateur à ce stade, à l'intérieur de la portée de accept de TrainNode ? Il sait que le type statique de this est un TrainNode. Il s'agit là d'un morceau d'information supplémentaire important auquel le compilateur n'était pas conscient dans la portée de l'appelant : là, tout ce qu'il savait de root était qu'il s'agissait d'un Node. À présent, le compilateur sait que this (root) n'est pas juste un Node, mais qu'il s'agit en fait d'un TrainNode. Par conséquent, la ligne trouvée à l'intérieur de accept() : v.visit(this), prend un sens totalement différent. Le compilateur recherchera maintenant une surcharge de visit() prenant un TrainNode. Si elle n'existe pas, il compilera l'appel vers une surcharge prenant un Node. Si aucune des deux n'existe, vous obtiendrez une erreur de compilation (sauf si vous avez une surcharge qui prend object). L'exécution entrera donc finalement dans ce que nous avions initialement prévu : l'implémentation de visit(TrainElement e) de MyVisitor. Aucun cast n'était nécessaire, et, surtout, pas de réflexion. Ainsi, le surcoût de ce mécanisme est plutôt faible : il se compose uniquement de références de pointeurs et rien d'autre.

Vous avez raison dans votre question -- nous pouvons utiliser un cast et obtenir le comportement correct. Cependant, souvent, nous ne connaissons même pas le type de Node. Prenons le cas de la hiérarchie suivante :

classe abstraite Node { ... }
classe abstraite BinaryNode extends Node { Node left, right; }
classe abstraite AdditionNode extends BinaryNode { }
classe abstraite MultiplicationNode extends BinaryNode { }
classe LitteralNode { int value; }

Et nous étions en train d'écrire un compilateur simple qui analyse un fichier source et produit une hiérarchie d'objets conforme à la spécification ci-dessus. Si nous écrivions un interpréteur pour la hiérarchie implémentée en tant que Visiteur :

class Interpreter implements IVisitor {
  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(LitteralNode n) {
    return n.value;
  }
}

Le cast ne nous mènerait pas très loin, car nous ne connaissons pas les types de left ou right dans les méthodes visit(). Notre analyseur renverrait très probablement également un objet de type Node qui pointerait à la racine de la hiérarchie, donc nous ne pourrions pas le caster en toute sécurité non plus. Ainsi, notre interpréteur simple pourrait ressembler à ceci :

Node programme = analyse(args[0]);
int résultat = programme.accept(new Interpreter());
System.out.println("Résultat : " + résultat);

Le pattern visiteur nous permet de faire quelque chose de très puissant : étant donné une hiérarchie d'objets, il nous permet de créer des opérations modulaires qui fonctionnent sur la hiérarchie sans avoir besoin de mettre le code dans la classe de la hiérarchie elle-même. Le pattern visiteur est largement utilisé, par exemple, dans la construction de compilateurs. Étant donné l'arbre syntaxique d'un programme particulier, de nombreux visiteurs sont écrits pour opérer sur cet arbre : vérification des types, optimisations, génération de code machine sont généralement implémentés en tant que visiteurs différents. Dans le cas du visiteur d'optimisation, il peut même produire un nouvel arbre syntaxique en fonction de l'arbre d'entrée.

Il a bien sûr ses inconvénients : si nous ajoutons un nouveau type dans la hiérarchie, nous devons également ajouter une méthode visit() pour ce nouveau type dans l'interface IVisitor, et créer des implémentations de stub (ou complètes) dans tous nos visiteurs. Nous devons également ajouter la méthode accept() aussi, pour les raisons décrites ci-dessus. Si les performances ne sont pas d'une grande importance pour vous, il existe des solutions pour écrire des visiteurs sans avoir besoin de l'accept(), mais elles impliquent généralement la réflexion et peuvent donc entraîner un surcoût assez important.

Answer 2

Bien sûr, ce serait stupide si c'était la seule façon dont Accept est implémenté.

Mais ce n'est pas le cas.

Par exemple, les visiteurs sont vraiment très utiles lorsqu'il s'agit de hiérarchies, auquel cas l'implémentation d'un nœud non terminal pourrait ressembler à ceci

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

  private IEnumerable children;
  ....
}

Vous voyez ? Ce que vous décrivez comme stupide est la solution pour traverser des hiérarchies.

Voici un article beaucoup plus long et approfondi qui m'a fait comprendre visitor.

Edit: Pour clarifier : La méthode Visit du visiteur contient la logique à appliquer sur un nœud. La méthode Accept du nœud contient la logique sur comment naviguer vers les nœuds adjacents. Le cas où vous faites seulement du double dispatch est un cas spécial où il n'y a tout simplement pas de nœuds adjacents à naviguer.

Answer 3

Le but du pattern Visitor est de garantir que les objets savent quand le visitor a fini avec eux et est parti, afin que les classes puissent effectuer toute opération de nettoyage nécessaire par la suite. Cela permet également aux classes d'exposer temporairement leurs internes en tant que paramètres 'ref', et de savoir que les internes ne seront plus exposés une fois le visitor parti. Dans les cas où aucun nettoyage n'est nécessaire, le pattern visitor n'est pas particulièrement utile. Les classes qui ne font ni l'un ni l'autre de ces choses ne bénéficieront peut-être pas du pattern visitor, mais le code écrit pour utiliser le pattern visitor pourra être utilisé avec des classes futures qui pourraient nécessiter un nettoyage après leur accès.

Par exemple, supposons que l'on dispose d'une structure de données contenant de nombreuses chaînes de caractères qui doivent être mises à jour de manière atomique, mais que la classe contenant la structure de données ne sait pas précisément quels types de mises à jour atomiques doivent être effectuées (par exemple, si un thread souhaite remplacer toutes les occurrences de "X", tandis qu'un autre thread souhaite remplacer toute séquence de chiffres par une séquence numériquement supérieure, les opérations des deux threads devraient réussir; si chaque thread se contentait de lire une chaîne, d'effectuer ses mises à jour et de la réécrire, le second thread à réécrire sa chaîne écraserait la première). Une façon d'y parvenir serait de faire en sorte que chaque thread acquière un verrou, effectue son opération, puis libère le verrou. Malheureusement, si les verrous sont exposés de cette manière, la structure de données n'aurait aucun moyen d'empêcher quelqu'un d'acquérir un verrou et de ne jamais le libérer.

Le pattern Visitor propose (au moins) trois approches pour éviter ce problème :

1. Il peut verrouiller un enregistrement, appeler la fonction fournie, puis déverrouiller l'enregistrement ; l'enregistrement pourrait rester verrouillé indéfiniment si la fonction fournie tombe dans une boucle infinie, mais si la fonction fournie retourne ou lance une exception, l'enregistrement sera déverrouillé (il peut être raisonnable de marquer l'enregistrement comme invalide si la fonction lance une exception ; le laisser verrouillé n'est probablement pas une bonne idée). Il est important de noter que si la fonction appelée tente d'acquérir d'autres verrous, un deadlock pourrait survenir.
2. Sur certaines plateformes, il est possible de passer un emplacement de stockage contenant la chaîne en tant que paramètre 'ref'. Cette fonction pourrait alors copier la chaîne, calculer une nouvelle chaîne basée sur la chaîne copiée, tenter de remplacer l'ancienne chaîne par la nouvelle à l'aide de CompareExchange, et répéter tout le processus si CompareExchange échoue.
3. Il peut faire une copie de la chaîne, appeler la fonction fournie sur la chaîne, puis utiliser CompareExchange lui-même pour tenter de mettre à jour l'original, et répéter tout le processus si CompareExchange échoue.

Sans le pattern Visitor, effectuer des mises à jour atomiques nécessiterait d'exposer des verrous et de risquer un échec si le logiciel appelant ne suit pas un protocole strict de verrouillage/déverrouillage. Avec le pattern Visitor, les mises à jour atomiques peuvent être effectuées relativement en toute sécurité.

Answer 4

Les classes qui nécessitent une modification doivent toutes implémenter la méthode 'accept'. Les clients appellent cette méthode accept pour effectuer une nouvelle action sur cette famille de classes, étendant ainsi leur fonctionnalité. Les clients peuvent utiliser cette seule méthode accept pour effectuer une large gamme de nouvelles actions en passant une classe de visiteur différente pour chaque action spécifique. Une classe de visiteur contient plusieurs méthodes de visite substituées définissant comment réaliser cette même action spécifique pour chaque classe de la famille. Ces méthodes de visite reçoivent une instance sur laquelle travailler.

Les visiteurs sont utiles si vous ajoutez, modifiez ou supprimez fréquemment des fonctionnalités à une famille stable de classes car chaque élément de fonctionnalité est défini séparément dans chaque classe de visiteur et les classes elles-mêmes n'ont pas besoin d'être modifiées. Si la famille de classes n'est pas stable, le motif visiteur peut être moins utile, car de nombreux visiteurs doivent être modifiés à chaque fois qu'une classe est ajoutée ou supprimée.

Answer 5

Un bon exemple est la compilation de code source :

interface VisiteurDeCompilation {
   construire(FichierSource source);
}

Les clients peuvent implémenter un JavaBuilder, RubyBuilder, XMLValidator, etc. et l'implémentation pour la collecte et la visite de tous les fichiers sources dans un projet n'a pas besoin de changer.

Ce serait un mauvais modèle si vous avez des classes séparées pour chaque type de fichier source :

interface VisiteurDeCompilation {
   construire(FichierSourceJava source);
   construire(FichierSourceRuby source);
   construire(FichierSourceXML source);
}

Cela dépend du contexte et des parties du système que vous souhaitez rendre extensibles.