Le patron de conceptionVisiteur (1) a été inventé pour permettre de parcourir des structures objets en maintenant un typage fort et sans connaissance a priori de la topologie exacte à l'exécution des liens entre objets visités. En particulier, en présence de liens d'héritage, ce patron permet de spécialiser un traitement pour chacun des sous-types en laissant le systéme d'invocation de méthodes virtuelles du langage décidée de la méthode exacte qui sera appellée à l'exécution. Cette technique est particulièrement utile dans le traitement des arbres syntaxiques construits par des analyseurs syntaxiques.

Expressions arithmétiques

Un exemple classique en est donné par l'interprétation d'expressions arithmétiques. Toutes les expressions partagent le type Expression qui définit une méthode de visite à implanter dans chaque sous-classe. 


package oqube.visitor.expr;


public interface Expression { 


  Object visit(ExpressionVisitor v);
} 

Toutes les implantation de cette interface pourront alors implanter cette méthode de la manière suivante: 


  public Object visit(ExpressionVisitor v){
   return v.visit(this);
  }

et l'on peut alors écrire entre autres les classes Add, Mult, Neg, Literal et Var représentant respectivement les opérations d'addition, de multiplication, de négation, les littéraux (ici des entiers) et les variables.

Les types d'expressions

Les deux opérateurs binaires héritent de la même super-classe BinaryExpression qui stocke les deux sous expressions. 


package oqube.visitor.expr;


public class Add extends BinaryExpression { 


  public Add() {} 


  public Add(Expression left,Expression right) {
    super(left,right);
  }


  <<visit_method>>
} 


package oqube.visitor.expr;


public class Mult extends BinaryExpression { 
  public Mult(Expression left,Expression right) {
    super(left,right);
  }


  <<visit_method>>
} 

L'opérateur unaire Neg est encore plus simple: 


package oqube.visitor.expr;


public class Neg implements Expression { 
  private Expression sub;


  public Neg() {}


  public Neg(Expression sub) { 
   this.sub = sub;
  }


  <<accessors_neg>>
  <<visit_method>>
} 

Enfin les litéraux et variables: 


package oqube.visitor.expr;


public class Literal implements Expression { 
  public final int value;


  public Literal(int v) {
    this.value = v;
  } 


  <<visit_method>>
} 



package oqube.visitor.expr;


public class Var implements Expression { 
  public final String  var;


  public Var(String x) {
    this.var = x;
  } 


  <<visit_method>>
} 

Le visiteur d'expression

L'interface ExpressionVisitor correspondant à ces différentes implantations d'Expression est: 


package oqube.visitor.expr;


public interface ExpressionVisitor { 


  Object visit(Add add);


  Object visit(Mult mult);


  Object visit(Neg neg);


  Object visit(Literal lit);


  Object visit(Var var);
} 

Deux implantations typiques de visiteur dans le cadre des expressions arithmétiques sont:

  1. un évaluateur qui retourne la valeur d'une expression en fonction d'un environnement dans lequel les variables sont instanciées;
  2. un formatteur préfixe qui génère une expression préfixée à partir de son arbre syntaxique.

Évaluateur

Le code de l'évaluateur transporte la valeur de retour des expressions dans des objets Integer


package oqube.visitor.expr;


import java.util.Map;


public class Eval implements ExpressionVisitor { 
  // a map from String to Integer objects
  private Map env;


  public void setEnv(Map env) {
    this.env = env;
  }


  public Object visit(Add add) {
    return new Integer(((Integer)add.getLeft().visit(this)).intValue() + 
           ((Integer)add.getRight().visit(this)).intValue());
  }


  public Object visit(Mult mult) {
    return ((Integer)mult.getLeft().visit(this)).intValue() + 
           ((Integer)mult.getRight().visit(this)).intValue();
  }


  public Object visit(Neg neg) {
    return new Integer(-((Integer)neg.getSub().visit(this)).intValue());
  }


  public Object visit(Literal lit){
   return new Integer(lit.value);
  }


  public Object visit(Var var) {
   return env.get(var.var);
  }
} 

On notera que cette technique est inefficace et produit un code extêmement lourd et indigeste, ce qui pourra être notablement amélioré en utilisant la généricité et les possibilités d'auto-encapsulation des types primitifs de la version 5.0 du langage Java (voir visitor-java5.muse).

Pour tester cet évaluateur, on peut écrire les cas de tests suivants: 


package oqube.visitor.expr;


import junit.framework.TestCase;
import java.util.Map;
import java.util.HashMap;


public class EvalTest extends TestCase {


  public void test01Eval() {
   Map env = new HashMap();
   env.put("x",12);
   Eval ev = new Eval();
   ev.setEnv(env);
   // construct an expression
   Add add = new Add();
   add.setLeft(new Literal(20));
   add.setRight(new Var("x"));
   assertEquals(32,((Integer)add.visit(ev)).intValue());
  }
  <<other_tests>>
}

Héritage

Héritage d'un visiteur

Le comportement d'un visiteur peut-être étendu par héritage (ou composition d'ailleurs) sans probléme. Par exemple: 




  public void test02EvalDouble() {
   Map env = new HashMap();
   Eval ev = new Eval(){
   public Object visit(Add add) {
     return new
   Integer(((Integer)add.getLeft().visit(this)).intValue() *2 + 
           ((Integer)add.getRight().visit(this)).intValue() *2);
    }
   };
   ev.setEnv(env);
   // construct an expression
   Add add = new Add();
   add.setLeft(new Literal(20));
   add.setRight(new Literal(10));
   assertEquals(60,((Integer)add.visit(ev)).intValue());
  }

Héritage de visité

Par contre, lors de la définition d'un nouveau type de noeud par héritage, il est nécessaire de redéfinir dans la sous-classe la méthode visit(ExpressionVisitor) pour obtenir un comportement différent du visiteur, mais aussi de rédéfinir une nouvelle méthode (par nouveau type ajouté) dans l'interface visiteur et donc ses sous-classes. C'est le problème principal, bien connu, du couplage fort entre visiteurs et visités dû à l'utilisation du typage statique (1). 

previous


   class MyAdd extends Add {
       MyAdd(Expression left, Expression right) {
           super(left, right) ;
       }
   };


   class MyEval extends Eval {
       public Object visit(MyAdd add) {
         return new Integer(((Integer)add.getLeft().visit(this)).intValue() * 2 + 
                ((Integer)add.getRight().visit(this)).intValue() * 2);
       }  
   };


  public void test03InheritAdd() {
      MyAdd add = new MyAdd(new Literal(20), new Literal(10));
      assertFalse(60 == ((Integer)add.visit(new MyEval())).intValue());
  }

Surcharge de méthode

La surcharge, un peu lourde, de la méthode visit dans le Visiteur se justifie par les possibilités de polymorphisme qu'elle introduit en présence d'une hiérarchie de classes Visités. 


package oqube.visitor;


import junit.framework.TestCase;


public class HeritageTest extends TestCase {


   abstract class A {


     abstract Object visit(Visitor v) ;
  }


  class B extends A {


     Object visit(Visitor v) {
       return v.visit(this);
     }
  }


  class C extends A {


     Object visit(Visitor v) {
       return v.visit(this);
     }
  }


  class Visitor {


    Object visit(A a) {
       return a.visit(this);
    }


    Object visit(B b) {
      return "B";
    }


    Object visit(C c) {
      return "C";
    }
  }


   public void test01() {
     A a = new B();
     Visitor v = new Visitor();
     assertEquals("B",v.visit(a));
   }
  }   

Le Baladeur

Dans (2), une première approche générique du visiteur est proposée, sous le nom de Baladeur (Walkabout). Le code de cette classe fait appel aux propriétés de réflexion de Java pour parcourir une instance arbitraire et ses différents champs. 


/*
 * verbatim copy from Palsberg and Jay, The Essence of the Visitor
 * Pattern, Proc. COMPSAC'98
 */
package oqube.visitor;


public class Walkabout  {
}

Multi-méthodes

Le visiteur est un cas particulier d'une technique de programmation appelée double dispatching (double aiguillage) qui permet de simuler du polymorphisme dynamique dans les langages objets statiquement typés (C++, Java, C#).

Dans les langages dynamiquement typés et dans les systémes de polymorphisme paramétrique (cf. Haskell et ses type-classes), le choix d'une méthode en fonction des paramètres peut se faire à l'exécution lorsque plusieurs méthodes sont possibles. A contrario, lorsque le typage est statique, le sélecteur correspondant à une méthode doit être connu à la compilation, même si par la suite le mécanisme de redéfinition par héritage et de fonctions virtuelles change la méthode invoqué.

Multijava est une extension du langage Java permettant de définir des multi-méthodes et donc de réaliser un aiguillage dynamique sur l'ensemble des paramètres d'une méthode et non plus seulement sur un seul (ie. l'objet appelé). En l'absence de mécanismes spécifiques, le routage dynamique doit être implanté manuellement en utilisant les mécanismes de réflexion propres au langage considéré, au prix de performances amoindries.

Références

Design Patterns

The Essence of the Visitor Pattern

Monads, Shapely Functors and Traversals

(1) Merci à Raphaël Marvie pour cet exemple.

© 2006

\Nouveau et intéressant