👏🏼 🚂 ✌🏾 Nous implémentons des conversions de code Python 🤞 🈲 🧖🏿

Bonjour, Habr.

Aujourd'hui, nous vous proposons la traduction d'un article qui aborde un sujet qui n'est pas le plus discuté: compilation de code en Python, à savoir: travail avec arbre de syntaxe abstraite (AST) et code d'octet. Alors que Python est un langage interprété, de telles fonctionnalités sont extrêmement importantes d'un point de vue d'optimisation. Nous en parlerons aujourd'hui.

Vous êtes-vous déjà demandé comment le compilateur optimise exactement votre code pour qu'il fonctionne plus rapidement? Vous voulez savoir ce qu'est un arbre de syntaxe abstraite (AST) et à quoi il peut servir?

Cet article de revue décrit comment le code Python est converti en arborescence (AST). Après avoir construit l'AST de votre programme, vous pouvez passer à la recherche d'opportunités pour optimiser et transformer votre code. Cependant, gardez à l'esprit qu'il est extrêmement difficile d' optimiser les programmes Python de manière non triviale .

Code de programme sous forme d'arbre

Comment un ordinateur peut-il s'assurer qu'il évalue les expressions de votre code dans le bon ordre?
Pour ce faire, il refait d'abord le code de votre programme dans une arborescence appelée AST.

Lorsque vous travaillez avec un langage de programmation interprété (tel que Python), il est généralement admis que l'interprète passe par votre code et fait tout ce qu'il rencontre, directement sur place, sans convertir le code Python en code machine de quelque façon que ce soit. Cependant, dans la pratique, ce schéma d'exécution provoque de nombreux problèmes, ce qui le rend très gênant.
Prenons, par exemple, un problème aussi simple que la priorité des opérateurs. Dans une expression de vue 3 + 4 * x , la pièce est d'abord calculée4 * x, et alors seulement 3 peut être ajouté au résultat de la multiplication. Peut-être avez-vous appris la priorité des opérateurs dans les cours de mathématiques en dessinant ces arbres sous l'expression:

Python utilise les règles standard de la notation mathématique (d'abord, la multiplication, puis l'addition). Afin de ne pas confondre quoi que ce soit avec la priorité des opérateurs, en Python, au début, il est construit un tel arbre que dans l'image précédente. L'opération générale est l'addition (à la racine de l'arbre), et tandis que le côté gauche de cette somme est un nombre régulier, à droite, nous avons le produit. La structure de données résultante ressemble à ceci:

BinOp(
  left  = Num(3),
  op    = Add(),
  right = BinOp(
            left  = Num(4),
            op    = Mult(),
            right = Name('x')
          )
)

BinOpsignifie opération binaire (opération binaire) et indique que dans les opérations telles que l'addition et la multiplication - deux opérandes. Naturellement, vous n’obtiendrez aucun ajout si la bonne partie de l’expression n’a pas la valeur correcte. Par conséquent, vous devez d’abord multiplier.

Dans la théorie des compilateurs et des langages de programmation, un tel arbre est appelé Abstract Syntax Tree , ou AST pour faire court. L'AST dans l'exemple ci-dessus comprend deux nœuds BinOp, deux nœuds Numet un nœud Name.

Il existe une fonctionnalité intéressante dans Python - la possibilité de visualiser et d'afficher directement AST pour n'importe quel programme Python particulier. Il suffit d'importer un module standardast, analyser le programme, puis afficher le résultat à l'écran (soit dit en passant, l'analyse est le processus de conversion du code source du programme en arborescence AST).

import ast
my_tree = ast.parse("3 + 4*x")
print(ast.dump(my_tree))

Cependant, vous remarquerez qu'il y aura des nœuds et des champs supplémentaires dans l'AST généré par Python, et ils seront affichés sur une seule ligne, ce qui semble plus compliqué à première vue qu'il ne l'est en réalité.

Module(body=[Expr(value=BinOp(left=Num(n=3), op=Add(), right=BinOp(left=Num(n=4), op=Mult(), right=Name(id='x', ctx=Load()))))])

Divisons-le en nœuds séparés, comme la dernière fois - et rouvrons l'AST, déjà en haut, dans le cadre de l'arbre entier:

Module(body = [
    Expr(
        value = BinOp(
            left  = Num(n=3),
            op    = Add(),
            right = BinOp(
                left  = Num(n=4),
                op    = Mult(),
                right = Name(id='x', ctx=Load())
            )
        )
    )
])

De toute évidence, Python «pense» que la ligne que nous lui avons donnée pour l'analyse est un module entier. Le corps du module est une liste de toutes les instructions qu'il contient. La seule instruction dans notre exemple est une expression Exprdont le sens est exactement ce que nous avons discuté ci-dessus.

Remarque: le nœud Namea un champ supplémentaire ctx(abrégé en «contexte»), qui a une valeur Load(). Donc, Python dit que nous utilisons la valeur stockée dans la variable x, et non pas (re) définir ou supprimer le nom x. À présent, essayez d'analyser quelque chose comme del xou vous x = 123- même , et vous verrez comment le champ ctxdu nœud se Nametransforme en Del()ou Store(), respectivement.

Au fait: si vous installez le moduleastunparse, la sortie AST vers l'écran peut être rendue beaucoup plus belle, et même reconvertir l'AST en code Python en direct.

Le processus de compilation: le reste

Après avoir collecté les programmes AST, il est en principe possible de terminer l'ensemble du programme en passant par l'AST et en effectuant les opérations dans l'ordre dans lequel elles sont indiquées. Cependant, cette approche présente au moins deux inconvénients. Premièrement, AST peut occuper une quantité de mémoire relativement importante, surtout si elle contient des informations redondantes. Deuxièmement, la traversée AST peut prendre plus de temps que nécessaire. En bref: cela peut être fait, mais c'est inefficace.
Le compilateur ne traite pas directement l'AST, mais prépare le bytecode, qui est ensuite exécuté sur la machine virtuelle Python. Bien que la discussion des détails de ce processus dépasse le cadre de cet article, le principe de base est que le compilateur traduit l'AST en notation polonaise inversée (RPN). Au lieu de mettre un opérateur+entre les opérandes gauche et droite, nous le mettons après les deux opérandes. Dans l'exemple 3 + 4*xci-dessus, nous obtenons la séquence 3 4 x * +(et cette notation est particulièrement bonne car vous pouvez immédiatement voir à partir de la séquence: vous devez d'abord effectuer la multiplication, puis seulement l'addition). Étant donné que chacun des cinq éléments de cette séquence peut en principe être représenté comme un seul octet, un tel code est appelé code d'octets. Python utilise ensuite la machine virtuelle empilée pour exécuter efficacement ce code.

En d'autres termes, le processus de compilation d'un programme écrit en Python se déroule en deux étapes. Tout d'abord, le programme reçu par l'entrée est analysé et le résultat est un arbre de syntaxe abstraite (AST). Le compilateur passe ensuite par AST et génère un bytecode. Après cela, l'interpréteur Python exécute ce bytecode. Une fois optimisé, il peut être appliqué au niveau AST ou au niveau bytecode. Ces deux options ont leurs propres avantages et inconvénients.

Enfin, gardez à l'esprit que même si AST est courant dans toute implémentation Python, le processus de traduction d'AST en bytecode peut être différent, et dans certaines implémentations Python, disons, JavaScript, plutôt que bytecode, peut être généré à l'étape intermédiaire.

Paradigmes d'autres langages de programmation

Tous les langages de programmation n'utilisent pas la notation infixe, comme en Python. Deux exemples à noter dans ce cas sont PostScript, où le programme est écrit directement en notation polonaise inverse, et Lisp, bien sûr, où les programmes sont généralement écrits en notation polonaise. Ainsi, notre expression de l'exemple ci - dessus, Lisp prendrait la forme suivante: (+ 3 (* 4 x)).

Conversion de nœuds dans AST

Ayant un programme AST, comment convertir des parties individuelles de cet arbre? Avec les fonctionnalités intégrées pratiques de Python.

Si nous regardons AST et, par exemple, constatons que les champs leftet les rightnœuds BinOpsont des nombres (nœuds Num), nous pouvons effectuer les calculs correspondants à l'avance, puis les remplacer par un BinOpnœud normal Num.

Bien sûr, vous devez agir très soigneusement afin de ne pas changer le comportement du programme, en faisant de telles transformations. Par exemple, dans len([a(), b(), c(), d()]), il est clair que le résultat est 4. Mais nous ne pouvons pas remplacer tout l'expression du nombre 4 parce que quatre fonctions a, b, c, dont toujours invoqué correctement.

Encore une fois, commencez par une optimisation simple. Partout où un nom apparaît dans le code source d'un programme pi, remplacez-le par la valeur 3.14159265. Le module Python astfournit déjà les structures de données nécessaires pour ce faire: une classe de convertisseur NodeTransformerqui passe par tous les AST et vérifie pour chaque nœud s'il peut être remplacé. Par défaut, la méthode de transformation renvoie simplement le nœud source pour chaque nœud, afin que nous obtenions le même AST à partir duquel nous avons commencé. Mais nous pouvons facilement remplacer la méthode pour les nœuds Name, par exemple, afin qu'il vérifie pisi c'est le cas, puis renvoie le nœud Numau lieu du nœud avec le nom d'origine ...

	import ast
 
class MyOptimizer(ast.NodeTransformer):
 
    def visit_Name(self, node: ast.Name):
        if node.id == 'pi':
            return ast.Num(n=3.14159265)
        return node
 
tree = ast.parse("y = 2 * pi")
optimizer = MyOptimizer()
tree = optimizer.visit(tree)
print(ast.dump(tree))

Pour que le convertisseur / optimiseur passe par notre arbre, il est nécessaire d'appeler sa méthode visit, qui retournera alors un nouvel arbre modifié.

Malheureusement, il est impossible de compiler et d'exécuter l'AST résultant, la raison en est un détail technique. Ce n'est pas encore visible, mais (presque) tous les nœuds de l'AST ont également des champs linenoet col_offset. Ils indiquent la position exacte d'un nœud particulier dans le code source. Si vous ne les installez pas correctement, le compilateur jurera et refusera de fonctionner.

Copions donc les champs appropriés du nœud source Namevers le nouveau nœud Num. Vous pouvez ensuite compiler et exécuter l'AST résultant:

import ast
 
class MyOptimizer(ast.NodeTransformer):
 
    def visit_Name(self, node: ast.Name):
        if node.id == 'pi':
            result = ast.Num(n=3.14159265)
            result.lineno = node.lineno
            result.col_offset = node.col_offset
            return result
        return node
 
tree = ast.parse("print(2 * pi)")
optimizer = MyOptimizer()
tree = optimizer.visit(tree)
code = compile(tree, "<string>", "exec")
exec(code)

Remarque: la compilation de la fonction nécessite non seulement le code source (dans lequel peut être un programme lui - même, ou la ligne AST), mais le nom du fichier (comme nous avons demandé "<string>"), ainsi que l' un des trois: "exec", "eval"ou "single".

La nécessité de copier les champs décrivant la position du nœud dans le code source se pose assez souvent. Par conséquent, le module asta une fonction dédiée copy_locationjuste à cet effet, et nous pouvons écrire:

def visit_Name(self, node: ast.Name):
        if node.id == 'pi':
            result = ast.Num(n=3.14159265)
            return ast.copy_location(result, node)
        return node

Enfin, vous pouvez étendre l'exemple précédent pour qu'il effectue réellement l'optimisation, à savoir sur le nœud BinOp. Selon la règle de transformation, nous devons d'abord transformer / optimiser le nœud gauche, puis le nœud droit dans le cadre de BinOp. Si, par conséquent, il s'avère que les nœuds gauche et droit sont des nombres, les calculs peuvent être effectués directement sur place et remplacer l'original par le BinOprésultat numérique de l'opération.

class MyVisitor(ast.NodeTransformer):
 
    def visit_BinOp(self, node: ast.BinOp):
        node.left = self.visit(node.left)
        node.right = self.visit(node.right)
        if isinstance(node.left, ast.Num) and isinstance(node.right, ast.Num):
            if isinstance(node.op, ast.Add):
                result = ast.Num(n = node.left.n + node.right.n)
                return ast.copy_location(result, node)
            elif isinstance(node.op, ast.Mult):
                result = ast.Num(n = node.left.n * node.right.n)
                return ast.copy_location(result, node)
        return node
 
    def visit_Name(self, node: ast.Name):
        if node.id == 'pi':
            result = ast.Num(n=3.14159265)
            return ast.copy_location(result, node)
        return node
 
tree = ast.parse("y = 2 * pi + 1")
optimizer = MyOptimizer()
tree = optimizer.visit(tree)
print(ast.dump(tree))

Soit dit en passant, le compilateur CPython optimise déjà les nœuds BinOpcomme indiqué ici. Le code correspondant est écrit en C et est donné en Python / ast_opt.c . Remarque: l'optimiseur CPython est plus universel et fonctionne non seulement avec des nombres, comme dans l'exemple que nous considérons, mais avec différents types de valeurs constantes.

Vérification des nœuds dans AST

Comment s'assurer que les transformations que nous avons effectuées étaient correctes? Vous devez d'abord contourner complètement AST et inspecter l'ensemble du programme.

L'optimiseur présenté ci-dessus reste un grave défaut. Que se passe-t-il si vous redéfinissez quelque part dans le programme pi? Imaginez simplement quelque chose d'aussi simple et intelligible que pi = 4. Notre optimiseur remplacera simplement pi sur le côté gauche de l'expression par la valeur numérique 3.14159265, et Python refusera alors de compiler car il ne peut rien assigner à une valeur littérale.

C'est peut-être précisément le comportement que vous avez recherché, faisant de pi une vraie constante, qui est remplacée lors de la compilation et ne peut jamais être réaffectée, c'est-à-dire qu'elle ne peut pas obtenir une valeur différente. Cependant, cela viole définitivement la sémantique de Python.

Alors, que faire si nous voulons nous en tenir à la sémantique de Python, mais remplacer pi quand même dans la mesure du possible? Dans ce cas, vous devez d'abord parcourir l'ensemble du programme et vérifier si la valeur de est attribuée quelque part pi. Jusqu'à ce que nous le compliquions: nous n'aurons pas recours au remplacement de pi si au moins un point du programme a une affectation de valeur à pi.

Nous utilisons maintenant le nœud visiteur, similaire au nœud convertisseur décrit ci-dessus. Contrairement au convertisseur, le visiteur n'est pas destiné à changer les nœuds, il passe simplement par l'AST et examine les nœuds (les visite). Par conséquent, les méthodes de visite ne retournent rien.

Dans notre cas, nous vérifions si le nœud se réfère Nameà piet fait autre chose que le chargement de la valeurpi(rappelez-vous le champ contextuel ctx).

import ast
 
class MyVisitor(ast.NodeVisitor):
 
    def __init__(self):
        self.modify_pi = False
 
    def visit_FunctionDef(self, node: ast.FunctionDef):
        if node.name == 'pi':
            self.modify_pi = True
        self.generic_visit(node)
 
    def visit_Name(self, node: ast.Name):
        if node.id == 'pi' and not isinstance(node.ctx, ast.Load):
            self.modify_pi = True
 
program = """
def pi():
    return 3.1415
print(2 * pi())
"""
tree = ast.parse(program)
my_visitor = MyVisitor()
my_visitor.visit(tree)
print("Pi modified:", my_visitor.modify_pi)

La méthode generic_visit(node)est appelée par le visiteur pour chaque nœud pour lequel nous ne fournissons pas de méthode de visite spécialisée. En d'autres termes: il n'y a pas une telle méthode visit_FunctionDefdans la classe NodeVisitorque nous pourrions appeler using super(). En ce qui concerne les définitions de fonction, nous devons appeler un visiteur générique pour nous assurer que le corps entier de la fonction est également traité correctement. Sinon, nous pourrions masquer l'instruction dans la fonction global piet modifier globalement la valeur pi, afin que notre optimiseur ne remarque rien.

Valeurs locales en Python

Notre méthode, qui nous permet de déterminer si le programmeur a changé pi, s'est avérée plutôt grossière. Cependant, le compilateur Python agit de manière très similaire lorsqu'il détermine quels noms dans la portée d'une fonction correspondent aux variables locales. Si une variable change quelque part dans la portée de la fonction (et n'est pas explicitement rendue globale, par exemple, en utilisant l'instruction globale), alors cette variable est considérée comme locale dans toute la portée de la fonction.

L'exemple suivant s'exécutera correctement sans la quatrième ligne. Mais, bien que x = 0la quatrième ligne ne soit jamais exécutée, elle est toujours considérée comme une affectation àx et donc, x devient une variable locale à l'échelle de la fonction entière, et même sur la ligne 3. C'est pourquoi Python jure que la variable x sur la troisième ligne n'a pas encore d'importance.

x = 1
def print_x():
    print(x)
    if False: x = 0
print_x()

Si vous êtes intéressé par les détails du fonctionnement exact de Python ici, consultez Python / symtable.c .

Conclusion

En Python, comme dans la plupart des langages de programmation, un programme particulier n'est pas exécuté directement à partir du code source. En fait, la traduction du code source se déroule en deux étapes: d'abord, un arbre de syntaxe abstraite (AST) en est créé, puis du code d'octets pour la machine virtuelle empilée. Python fournit également un certain nombre de fonctionnalités très intéressantes pour analyser et même transformer l'AST d'un programme Python particulier, après quoi l'AST modifié peut être compilé et exécuté. Ainsi, nous pouvons facilement implémenter nos propres optimisations.

Bien sûr, j'ai simplement omis de nombreux détails ici. S'assurer que votre optimisation fonctionnera correctement dans tous les cas et circonstances possibles est une question très simple. Cependant, le but de cet article n'est pas de vous parler de l'optimisation prête à l'emploi en production, mais de donner une idée de base de la façon dont Python analyse votre code de programme afin que vous puissiez apprendre à le convertir correctement, puis à l'optimiser.

Nous implémentons des conversions de code Python