🧒🏿 🤟🏽 ㊙️ Wir implementieren Python-Code-Konvertierungen 🔃 👨‍❤️‍💋‍👨 🧑🏿‍🤝‍🧑🏼

Hallo Habr.

Heute bieten wir Ihnen eine Übersetzung eines Artikels an, der ein Thema behandelt, das nicht am meisten diskutiert wird: Kompilierung von Code in Python, nämlich: Arbeiten mit abstraktem Syntaxbaum (AST) und Bytecode. Während Python eine interpretierte Sprache ist, sind solche Funktionen aus Optimierungssicht äußerst wichtig. Wir werden heute darüber sprechen.

Haben Sie sich jemals gefragt, wie genau der Compiler Ihren Code so optimiert, dass er schneller funktioniert? Möchten Sie wissen, was ein abstrakter Syntaxbaum (AST) ist und wofür er verwendet werden kann?

In diesem Übersichtsartikel wird beschrieben, wie Python-Code in die Baumform (AST) konvertiert wird. Nachdem Sie den AST Ihres Programms erstellt haben, können Sie nach Möglichkeiten suchen, Ihren Code zu optimieren und zu transformieren. Beachten Sie jedoch, dass die Optimierung von Python-Programmen auf nicht triviale Weise äußerst schwierig ist .

Programmcode als Baum

Wie kann ein Computer sicherstellen, dass Ausdrücke aus Ihrem Code in der richtigen Reihenfolge ausgewertet werden?
Dazu erstellt er zunächst Ihren Programmcode in eine Baumstruktur namens AST.

Wenn Sie mit einer interpretierten Programmiersprache (wie Python) arbeiten, wird allgemein angenommen, dass der Interpreter Ihren Code durchläuft und alles, was ihm begegnet, direkt vor Ort ausführt, ohne Python-Code in irgendeiner Weise in Maschinencode umzuwandeln. In der Praxis verursacht dieses Ausführungsschema jedoch viele Probleme, die es sehr unpraktisch machen.
Nehmen Sie zum Beispiel ein so einfaches Problem wie die Priorität der Bediener. In einem Ansichtsausdruck 3 + 4 * x wird das Teil zuerst berechnet4 * xund nur dann kann 3 zum Ergebnis der Multiplikation addiert werden. Vielleicht haben Sie die Priorität von Operatoren in Mathematikklassen gelernt, indem Sie diese Bäume unter dem Ausdruck gezeichnet haben:

Python verwendet die Standardregeln der mathematischen Notation (zuerst Multiplikation, dann Addition). Um nichts mit der Priorität der Operatoren zu verwechseln, wird in Python zunächst ein solcher Baum wie im vorherigen Bild erstellt. Die allgemeine Operation ist Addition (an der Wurzel des Baums), und während die linke Seite dieser Summe eine reguläre Zahl ist, haben wir rechts das Produkt. Die resultierende Datenstruktur sieht folgendermaßen aus:

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

BinOpbedeutet Binäroperation (Binäroperation) und gibt an, dass bei Operationen wie Addition und Multiplikation zwei Operanden vorhanden sind. Natürlich erhalten Sie keine Addition, wenn der richtige Teil des Ausdrucks nicht den richtigen Wert hat. Daher müssen Sie zuerst multiplizieren.

In der Theorie der Compiler und Programmiersprachen wird ein solcher Baum als Abstract Syntax Tree oder kurz AST bezeichnet . Der AST im obigen Beispiel enthält zwei Knoten BinOp, zwei Knoten Numund einen Knoten Name.

In Python gibt es eine nette Funktion - die Möglichkeit, AST für ein bestimmtes Python-Programm direkt anzuzeigen und anzuzeigen. Sie müssen lediglich ein Standardmodul importierenastParsen des Programms und anschließendes Anzeigen des Ergebnisses auf dem Bildschirm (Parsen ist übrigens das Konvertieren des Programmquellcodes in den AST-Baum).

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

Sie werden jedoch feststellen, dass der von Python generierte AST zusätzliche Knoten und Felder enthält und in einer Zeile angezeigt wird, was ihn auf den ersten Blick komplizierter erscheinen lässt als er tatsächlich ist.

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()))))])

Teilen wir es wie beim letzten Mal in separate Knoten auf - und öffnen Sie den bereits oben befindlichen AST als Teil des gesamten Baums erneut:

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())
            )
        )
    )
])

Offensichtlich "denkt" Python, dass die Zeile, die wir zum Parsen angegeben haben, ein ganzes Modul ist. Der Hauptteil des Moduls ist eine Liste aller darin enthaltenen Anweisungen. Die einzige Anweisung in unserem Beispiel ist ein Ausdruck, Exprdessen Bedeutung genau der oben diskutierten entspricht.

Hinweis: Der Knoten Nameverfügt über ein zusätzliches Feld ctx(abgekürzt als „Kontext“), das einen Wert hat Load(). Python sagt also, dass wir den in der Variablen gespeicherten Wert verwenden xund den Namen nicht (neu) definieren oder löschen x. Versuchen Sie nun, etwas wie del xoder sich selbst zu analysieren x = 123, und Sie werden sehen, wie sich das Feld ctxim Knoten Namein Del()bzw. ändert Store().

Übrigens: wenn Sie das Modul installierenastunparseDann kann die AST-Ausgabe auf dem Bildschirm viel schöner gestaltet und der AST sogar wieder in Live-Python-Code konvertiert werden.

Der Kompilierungsprozess: der Rest

Nach dem Sammeln von AST-Programmen ist es grundsätzlich möglich, das gesamte Programm zu vervollständigen, indem das AST durchlaufen und die Vorgänge in der angegebenen Reihenfolge ausgeführt werden. Dieser Ansatz weist jedoch mindestens zwei Nachteile auf. Erstens kann AST eine relativ große Menge an Speicher belegen, insbesondere wenn es redundante Informationen enthält. Zweitens kann die AST-Durchquerung länger als nötig dauern. Kurz gesagt: Es kann getan werden, aber es ist ineffizient.
Der Compiler verarbeitet den AST nicht direkt, sondern bereitet den Bytecode vor, der dann auf der virtuellen Python-Maschine ausgeführt wird. Obwohl die Erörterung der Details dieses Prozesses den Rahmen dieses Artikels sprengt, besteht das Grundprinzip darin, dass der Compiler den AST in die umgekehrte polnische Notation (RPN) übersetzt. Anstatt einen Operator zu setzen+zwischen dem linken und rechten Operanden setzen wir es nach beiden Operanden. Im 3 + 4*xobigen Beispiel erhalten wir die Sequenz 3 4 x * +(und diese Notation ist besonders gut, da Sie sofort anhand der Sequenz sehen können: Zuerst müssen Sie die Multiplikation und erst dann die Addition durchführen). Da jedes der fünf Elemente in dieser Sequenz im Prinzip als einzelnes Byte dargestellt werden kann, wird ein solcher Code als Bytecode bezeichnet. Python verwendet dann die gestapelte virtuelle Maschine , um diesen Code effizient auszuführen.

Mit anderen Worten, das Kompilieren eines in Python geschriebenen Programms erfolgt in zwei Schritten. Zunächst wird das von der Eingabe empfangene Programm analysiert, und das Ergebnis ist ein abstrakter Syntaxbaum (AST). Der Compiler durchläuft dann AST und generiert Bytecode. Danach führt der Python-Interpreter diesen Bytecode aus. Nachdem die Optimierung aufgenommen wurde, kann sie entweder auf AST-Ebene oder auf Bytecode-Ebene angewendet werden. Beide Optionen haben ihre eigenen Vor- und Nachteile.

Beachten Sie schließlich, dass, obwohl AST in jeder Python-Implementierung üblich ist, der Prozess der Übersetzung von AST in Bytecode unterschiedlich sein kann und in einigen Python-Implementierungen beispielsweise JavaScript anstelle von Bytecode in der Zwischenphase generiert werden kann.

Paradigmen aus anderen Programmiersprachen

Nicht alle Programmiersprachen verwenden die Infix-Notation wie in Python. Zwei bemerkenswerte Beispiele in diesem Fall sind PostScript, bei dem das Programm direkt in umgekehrter polnischer Notation geschrieben ist, und Lisp, bei dem Programme normalerweise in polnischer Notation geschrieben sind. Unser Ausdruck des obigen Beispiels in Lisp würde also die folgende Form annehmen : (+ 3 (* 4 x)).

Knotenkonvertierung innerhalb von AST

Wie konvertiere ich mit einem AST-Programm einzelne Teile dieses Baums? Mit den praktischen integrierten Funktionen von Python.

Wenn wir uns AST ansehen und beispielsweise feststellen, dass sowohl Felder leftals auch rightKnoten BinOpZahlen (Knoten Num) sind, können wir die entsprechenden Berechnungen im Voraus durchführen und sie dann durch einen BinOpnormalen Knoten ersetzen Num.

Natürlich müssen Sie sehr vorsichtig handeln, um das Verhalten des Programms bei solchen Transformationen nicht zu ändern. Zum Beispiel in len([a(), b(), c(), d()]), ist es klar , dass das Ergebnis 4., aber wir können alle den Ausdruck der Nummer 4 , weil vier Funktionen nicht ersetzen a, b, c, dnoch richtig aufgerufen haben.

Beginnen Sie erneut mit einer einfachen Optimierung. Wenn im Quellcode eines Programms ein Name vorkommt pi, ersetzen Sie ihn durch den Wert 3.14159265. Das Python-Modul aststellt bereits die dafür erforderlichen Datenstrukturen bereit: Eine Konverterklasse NodeTransformer, die alle ASTs durchläuft und für jeden Knoten prüft, ob er ersetzt werden kann. Standardmäßig gibt die Transformationsmethode einfach den Quellknoten für jeden Knoten zurück, sodass wir denselben AST erhalten, von dem aus wir gestartet sind. Aber wir können die Methode für Knoten leicht überschreiben, zum Beispiel, um zu prüfen Name, piob dies der Fall ist, und dann den Knoten Numanstelle des Knotens mit dem ursprünglichen Namen zurückgeben ...

	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))

Damit der Konverter / Optimierer unseren Baum durchläuft, muss seine Methode aufgerufen werden visit, die dann einen neuen, geänderten Baum zurückgibt.

Leider ist es nicht möglich, den resultierenden AST zu kompilieren und auszuführen. Der Grund dafür ist ein technisches Detail. Dies ist noch nicht sichtbar, aber (fast) alle Knoten im AST haben auch Felder linenound col_offset. Sie geben die genaue Position eines bestimmten Knotens im Quellcode an. Wenn Sie sie nicht ordnungsgemäß installieren, schwört der Compiler und weigert sich zu arbeiten.

Kopieren wir also die entsprechenden Felder vom Quellknoten Nameauf den neuen Knoten Num. Sie können dann den resultierenden AST kompilieren und ausführen:

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)

Hinweis: Funktion der Kompilierung erfordert den Quellcode nicht nur (in dem ein Programm selbst sein kann, oder die AST - Linie), aber der Dateiname (wie wir gefragt "<string>"), sowie ein von drei: "exec", "eval"oder "single".

Die Notwendigkeit, die Felder zu kopieren, die die Position des Knotens im Quellcode beschreiben, tritt ziemlich häufig auf. Daher hat das Modul nur für diesen Zweck asteine spezielle Funktion copy_location, und wir können schreiben:

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

Schließlich können Sie das vorherige Beispiel so erweitern, dass es tatsächlich eine Optimierung durchführt, und zwar auf dem Knoten BinOp. Gemäß der Transformationsregel müssen wir zuerst den linken und dann den rechten Knoten als Teil von BinOp transformieren / optimieren. Wenn sich als Ergebnis herausstellt, dass sowohl der linke als auch der rechte Knoten Zahlen sind, können die Berechnungen direkt vor Ort durchgeführt werden und das Original durch das BinOpnumerische Ergebnis der Operation ersetzen .

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))

Übrigens optimiert der CPython-Compiler bereits Knoten BinOpwie hier gezeigt. Der entsprechende Code ist in C geschrieben und in Python / ast_opt.c angegeben . Bitte beachten Sie: Das CPython-Optimierungsprogramm ist universeller und funktioniert nicht nur mit Zahlen, wie im Beispiel, sondern auch mit verschiedenen Arten von konstanten Werten.

Überprüfen von Knoten in AST

Wie kann sichergestellt werden, dass die von uns vorgenommenen Transformationen korrekt waren? Zuerst müssen Sie AST vollständig umgehen und das gesamte Programm überprüfen.

Der oben vorgestellte Optimierer bleibt ein schwerwiegender Fehler. Was passiert, wenn Sie irgendwo im Programm neu definieren pi? Stellen Sie sich etwas so Einfaches und Verständliches vor wie pi = 4. Unser Optimierer ersetzt einfach pi auf der linken Seite des Ausdrucks durch den numerischen Wert 3.14159265, und Python weigert sich dann zu kompilieren, da es einem Literalwert nichts zuweisen kann.

Vielleicht ist dies genau das Verhalten, das Sie gesucht haben, wodurch pi zu einer echten Konstante wird, die während der Kompilierung ersetzt wird und niemals neu zugewiesen werden kann, dh keinen anderen Wert erhalten kann. Dies verstößt jedoch definitiv gegen die Semantik von Python.

Was tun, wenn wir uns an die Semantik von Python halten, aber pi wo immer möglich ersetzen möchten? In diesem Fall müssen Sie zuerst das gesamte Programm durchgehen und prüfen, ob der Wert für irgendwo zugewiesen ist pi. Bis wir es komplizieren: Wir werden nicht auf das Ersetzen von pi zurückgreifen, wenn mindestens einem Punkt im Programm ein Wert zugewiesen ist pi.

Jetzt verwenden wir den Besucherknoten, ähnlich dem oben beschriebenen Konverterknoten. Im Gegensatz zum Konverter soll der Besucher keine Knoten ändern, er geht einfach durch den AST und untersucht die Knoten (besucht sie). Dementsprechend geben Besuchsmethoden nichts zurück.

In unserem Fall überprüfen wir , ob der Knoten bezieht sich Nameauf piund tut etwas anderes als den Wert geladenpi(Denken Sie an das Kontextfeld 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)

Die Methode generic_visit(node)wird vom Besucher für jeden Knoten aufgerufen, für den wir keine spezielle Besuchsmethode bereitstellen. Mit anderen Worten: Es gibt keine solche Methode visit_FunctionDefin der Klasse NodeVisitor, die wir mit aufrufen könnten super(). In Bezug auf Funktionsdefinitionen müssen wir einen generischen Besucher anrufen, um sicherzustellen, dass auch der gesamte Funktionskörper korrekt verarbeitet wird. Andernfalls könnten wir die Anweisung in der Funktion ausblenden global piund den Wert global ändern pi, sodass unser Optimierer nichts bemerkt.

Lokale Werte in Python

Unsere Methode, mit der wir feststellen können, ob der Programmierer pi geändert hat, erwies sich als ziemlich unhöflich. Der Python-Compiler verhält sich jedoch sehr ähnlich, wenn er bestimmt, welche Namen im Bereich einer Funktion lokalen Variablen entsprechen. Wenn sich eine Variable irgendwo im Funktionsumfang ändert (und beispielsweise mit der globalen Anweisung nicht explizit globalisiert wird), wird diese Variable im gesamten Funktionsumfang als lokal betrachtet.

Das folgende Beispiel wird ohne die vierte Zeile einwandfrei ausgeführt. Obwohl x = 0die vierte Zeile nie ausgeführt wird, wird sie dennoch als Zuweisung an betrachtetx und deshalb wird x eine lokale Variable auf der Skala der gesamten Funktion und sogar in Zeile 3. Deshalb wird Python schwören, dass die Variable x in der dritten Zeile noch keine Rolle spielt.

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

Wenn Sie genau wissen möchten , wie Python hier funktioniert, lesen Sie Python / symtable.c .

Fazit

In Python wird wie in den meisten Programmiersprachen ein bestimmtes Programm nicht direkt aus dem Quellcode ausgeführt. Tatsächlich erfolgt die Übersetzung des Quellcodes in zwei Schritten: Zuerst wird ein abstrakter Syntaxbaum (AST) daraus erstellt und dann Bytecode für die gestapelte virtuelle Maschine. Python bietet auch eine Reihe sehr nützlicher Funktionen zum Analysieren und sogar Transformieren des AST eines bestimmten Python-Programms, wonach der modifizierte AST kompiliert und ausgeführt werden kann. So können wir problemlos unsere eigenen Optimierungen implementieren.

Natürlich habe ich hier einfach viele Details weggelassen. Es ist nicht trivial, sicherzustellen, dass Ihre Optimierung in allen möglichen Fällen und Umständen korrekt funktioniert. Der Zweck dieses Artikels besteht jedoch nicht darin, Sie über die Optimierung zu informieren, die für die Produktion bereit ist, sondern eine grundlegende Vorstellung davon zu geben, wie Python Ihren Programmcode analysiert, damit Sie lernen, wie Sie ihn richtig konvertieren und dann optimieren.

Wir implementieren Python-Code-Konvertierungen