Implémentation du patron de conception Visiteur en Python

Vous devez écrire un code qui traite ou parcourt une structure de données complexe composée de nombreux types d’objets différents, chacun d’eux devant être traité d’une manière différente. Par exemple, parcourir une arborescence et effectuer différentes actions en fonction du type de nœuds rencontrés.

Le problème abordé par cet article se pose souvent dans les programmes qui construisent des structures de données composées d’un grand nombre de différents types d’objets.

Pour l’illustrer, supposons que vous essayez d’écrire un programme qui représente des expressions mathématiques. Pour ce faire, le programme peut employer un certain nombre de classes, comme celle-ci:

class Noeud:
    pass

class OperateurUnaire(Noeud):
    def __init__(self, operande):
        self.operande = operande

class OperateurBinaire(Noeud):
    def __init__(self, gauche, droite):
        self.gauche = gauche
        self.droite = droite

class Ajouter(OperateurBinaire):
    pass

class Sous(OperateurBinaire):
    pass

class Mul(OperateurBinaire):
    pass

class Div(OperateurBinaire):
    pass

class InverserSig(OperateurUnaire):
    pass

class Numero(Noeud):
    def __init__(self, valeur):
        self.valeur = valeur

Ces classes seraient alors utilisées pour construire des structures de données imbriquées, comme ceci:

# Représentation de 1 + 2 * (3 - 4) / 5
t1 = Sous(Numero(3), Numero(4))
t2 = Mul(Numero(2), t1)
t3 = Div(t2, Numero(5))
t4 = Ajouter(Numero(1), t3)

Le problème n’est pas la création de telles structures, mais la rédaction d’un code qui les traitera plus tard.

Par exemple, étant donné une telle expression, un programme peut vouloir faire un certain nombre de choses (par exemple, produire des résultats, générer des instructions, effectuer une traduction, etc.).

Pour permettre un traitement général, une solution courante consiste à mettre en œuvre ce que l’on appelle le “patron de conception visiteurs” en utilisant une classe similaire à celle-ci:

class VisiteurNoeud:
    def visit(self, node):
        nom_methode= 'visit_' + type(node).__name__
        methode = getattr(self, nom_methode, None)
        if methode is None:
            methode = self.visit_generic
        return methode(node)

    def visit_generic(self, noeud):
        raise RuntimeError('Pas de méthode {}'.format('visit_' + type(node).__name__))

Pour utiliser cette classe, un programmeur en hérite et implémente différentes méthodes du formulaire visit_Nom(), où Nom est substitué par le type de noeud. Par exemple, si vous voulez évaluer l’expression, vous pouvez écrire ceci:

class Evaluateur(VisiteurNoeud):
    def visit_Numero(self, noeud):
        return noeud.valeur

    def visit_Ajouter(self, noeud):
        return self.visit(noeud.gauche) + self.visit(noeud.droite)

    def visit_Sous(self, noeud):
        return self.visit(noeud.gauche) - self.visit(noeud.droite)

    def visit_Mul(self, noeud):
        return self.visit(noeud.gauche) * self.visit(noeud.droite)

    def visit_Div(self, noeud):
        return self.visit(noeud.gauche) / self.visit(noeud.droite)

    def visit_Negate(self, node):
        return -node.operand

Voici un exemple d’utilisation de cette classe avec l’expression générée précédemment:

>>> e = Evaluateur()
>>> e.visit(t4)
0.6
>>>

A titre d’exemple complètement différent, voici une classe qui traduit une expression en opérations sur une simple machine à pile:

class CodePile(VisiteurNoeud):
    def generer_code(self, noeud):
        self.instructions = []
        self.visit(noeud)
        return self.instructions

    def visit_Numero(self, noeud):
        self.instructions.append(('PUSH', noeud.value))

    def opbin(self, noeud, instruction):
        self.visit(noeud.gauche)
        self.visit(noeud.droite)
        self.instructions.append((instruction,))

    def visit_Ajouter(self, noeud):
        self.opbin(noeud, 'AJOUTER')

    def visit_Sous(self, noeud):
        self.opbin(noeud, 'SOUS')

    def visit_Mul(self, noeud):
        self.opbin(noeud, 'MUL')

    def visit_Div(self, noeud):
        self.opbin(noeud, 'DIV')

    def opunaire(self, noeud, instruction):
        self.visit(noeud.operand)
        self.instructions.append((instruction,))

    def visit_InvSigne(self, noeud):
        self.opunaire(noeud, 'INVERSERSIG')

Voici un exemple de cette classe en action:

>>> s = CodePile()
>>> s.generer_code(t4)
[('PUSH', 1), ('PUSH', 2), ('PUSH', 3), ('PUSH', 4), ('SUB',),
 ('MUL',), ('PUSH', 5), ('DIV',), ('ADD',)]
>>>

Il y a vraiment deux idées clés dans ce programme. La première est une stratégie de conception où le code qui manipule une structure de données complexe est découplé de la structure de données elle-même.

C’est-à-dire, dans ce code, aucune des différentes classes de Noeud ne fournit d’implémentation qui fasse quoi que ce soit avec les données.

Au lieu de cela, toutes les manipulations de données sont effectuées par des implémentations spécifiques de la classe séparée VisiteurNoeud. Cette séparation rend le code extrêmement général.

La deuxième grande idée de cette solution est la mise en œuvre de la classe Visiteur elle-même. Dans le visiteur, vous souhaitez transférer les données vers une autre méthode de traitement en fonction d’une valeur telle que le type de nœud. Dans une implémentation naïve, vous pourriez être enclin à écrire un énorme si déclaration, comme ceci:

class VisiteurNoeud:
    def visit(self, noeud):
        noeudtype = type(noeud).__name__
        if noeudtype == 'Numero':
            return self.visit_Numero(noeud)
        elif noeudtype == 'Ajouter':
            return self.visit_Ajouter(noeud)
        elif noeudtype == 'Sous':
            return self.visit_Sous(noeud)
        ...

Cependant, il devient rapidement évident que vous ne voulez pas vraiment adopter cette approche. En plus d’être incroyablement verbeux, il fonctionne lentement, et il est difficile à maintenir si vous ajoutez ou modifiez le type de nœuds gérés.

Au lieu de cela, il est beaucoup mieux de jouer un petit truc où vous formez le nom d’une méthode et allez la chercher avec la fonction getattr(), comme montré.

La méthode visit_generic() du code est une solution de repli si aucune méthode de gestionnaire correspondante n’est trouvée. Dans cette recette, il lève une exception pour avertir le programmeur qu’un type de nœud inattendu a été rencontré.

Dans chaque classe visiteur, il est courant que les calculs soient effectués par des appels récursifs à la méthode visit(). Par exemple:

class Evaluateur(VisiteurNoeud):
    ...
    def visit_Ajouter(self, noeud):
        return self.visit(noeud.gauche) + self.visit(noeud.droite)

C’est cette récursivité qui permet à la classe visiteur de parcourir l’ensemble de la structure de données. Essentiellement, vous continuez à appeler visit() jusqu’à ce que vous atteigniez une sorte de nœud terminal, tel que Numero dans l’exemple.

L’ordre exact de la récursion et des autres opérations dépend entièrement de l’application. Il convient de noter que cette technique particulière d’envoi vers une méthode est également un moyen courant d’émuler le comportement des instructions de commutation ou de cas provenant d’autres langues.

Par exemple, si vous écrivez un framework HTTP, vous pourriez avoir des classes qui font un type d’envoi similaire:

class ManipulerHTTP:
    def Manipuler(self, requete):
        nom_methode = 'faire_' + requete.requete_method
        getattr(self, nom_methode)(requete)

    def faire_GET(self, requete):
        ...
    def faire_POST(self, requete):
        ...
    def faire_HEAD(self, requete):
        ...

L’une des faiblesses du modèle Visiteur est sa forte dépendance à l’égard de la récursivité.

Si vous essayez de l’appliquer à une structure profondément imbriquée, il est possible que vous atteigniez la limite de profondeur de récursion de Python (voir sys.getrecursionlimit()).

Pour éviter ce problème, vous pouvez faire certains choix dans vos structures de données. Par exemple, vous pouvez utiliser des listes Python normales au lieu de listes liées ou essayer d’agréger plus de données dans chaque noeud pour rendre les données moins profondes.

Vous pouvez également essayer d’utiliser des algorithmes de traversée non récursifs en utilisant des générateurs ou des itérateurs.

L’utilisation du patron de conception Visiteur est extrêmement courante dans les programmes liés au parsage et à la compilation. Une implémentation notable peut être trouvée dans le module ast de Python.

En plus de permettre la traversée d’arborescences, il fournit une variation qui permet de réécrire ou de transformer une structure de données au fur et à mesure qu’elle est traversée (p. ex., ajout ou suppression de nœuds). Consultez la source de l’ast pour plus de détails.

LAISSER UN COMMENTAIRE

Please enter your comment!
Please enter your name here