🐳 🖨️ 📅 Implementamos conversiones de código Python 🔑 🎎 🏄

Hola Habr

Hoy le ofrecemos una traducción de un artículo que toca un tema que no es el más discutido: la compilación de código en Python, a saber: trabajar con árbol de sintaxis abstracta (AST) y código de bytes. Si bien Python es un lenguaje interpretado, tales características son extremadamente importantes desde el punto de vista de la optimización. Hablaremos de ellos hoy.

¿Alguna vez te has preguntado cómo exactamente el compilador optimiza tu código para que funcione más rápido? ¿Quiere saber qué es un árbol de sintaxis abstracta (AST) y para qué se puede utilizar?

Este artículo de revisión describe cómo el código Python se convierte en forma de árbol (AST). Después de crear el AST de su programa, puede continuar buscando oportunidades para optimizar y transformar su código. Sin embargo, tenga en cuenta que optimizar los programas de Python de manera no trivial es extremadamente difícil .

Código de programa como un árbol

¿Cómo puede una computadora asegurarse de que evalúa las expresiones de su código en el orden correcto?
Para hacer esto, primero rehace el código de su programa en una estructura de árbol llamada AST.

Cuando se trabaja con un lenguaje de programación interpretado (como Python), generalmente se acepta que el intérprete pasa a través de su código y hace todo lo que encuentra, directamente, sin convertir el código de Python en código de máquina de ninguna manera. Sin embargo, en la práctica, este esquema de ejecución provoca muchos problemas, lo que lo hace muy inconveniente.
Tomemos, por ejemplo, un problema tan simple como la prioridad de los operadores. En una expresión de vista 3 + 4 * x , la parte se calcula primero4 * x, y solo entonces se puede agregar 3 al resultado de la multiplicación. Quizás aprendió la precedencia de los operadores en las clases de matemáticas al dibujar estos árboles bajo la expresión:

Python usa las reglas estándar de notación matemática (primero la multiplicación, luego la suma). Para no confundir nada con la prioridad de los operadores, en Python, al principio se construye un árbol como en la imagen anterior. La operación general es la suma (en la raíz del árbol), y aunque el lado izquierdo de esta suma es un número regular, a la derecha tenemos el producto. La estructura de datos resultante se ve así:

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

BinOpsignifica Operación binaria (Operación binaria) e indica que en operaciones como la suma y la multiplicación, dos operandos. Naturalmente, no obtendrá ninguna adición si la parte correcta de la expresión no tiene el valor correcto; por lo tanto, primero debe multiplicar.

En la teoría de compiladores y lenguajes de programación, dicho árbol se llama Árbol de sintaxis abstracta o AST para abreviar. El AST en el ejemplo anterior incluye dos nodos BinOp, dos nodos Numy un nodo Name.

Hay una buena característica en Python: la capacidad de ver y mostrar directamente AST para cualquier programa Python en particular. Todo lo que se requiere es importar un módulo estándarast, analiza el programa y luego muestra el resultado en la pantalla (por cierto, el análisis es el proceso de convertir el código fuente del programa al árbol AST).

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

Sin embargo, notará que habrá nodos y campos adicionales en el AST generados por Python, y se mostrará en una línea, lo que hace que parezca más complicado a primera vista de lo que realmente es.

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

Dividámoslo en nodos separados, como la última vez, y volvamos a abrir el AST, que ya está en la parte superior, como parte de todo el árbol:

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

Obviamente, Python "piensa" que la línea que le dimos para analizar es un módulo completo. El cuerpo del módulo es una lista de todas las instrucciones que contiene. La única instrucción en nuestro ejemplo es una expresión Exprcuyo significado es exactamente lo que discutimos anteriormente.

Nota: el nodo Nametiene un campo adicional ctx(abreviado como "contexto"), que tiene un valor Load(). Entonces Python dice que usamos el valor almacenado en la variable xy no (re) definimos o eliminamos el nombre x. Ahora su movimiento, intenta analizar algo así del xo usted mismo x = 123, y verá cómo el campo ctxen el nodo de Namecambios a Del(), o Store(), respectivamente.

Por cierto: si instala el móduloastunparse, la salida de AST a la pantalla se puede hacer mucho más bella e incluso convertir la AST nuevamente en código Python en vivo.

El proceso de compilación: el resto

Una vez recopilados los programas AST, en principio es posible completar todo el programa pasando por el AST y realizando las operaciones en el orden en que se indican. Sin embargo, este enfoque tiene al menos dos inconvenientes. En primer lugar, AST puede ocupar una cantidad relativamente grande de memoria, especialmente si contiene información redundante. En segundo lugar, el recorrido AST puede llevar más tiempo del necesario. En resumen: se puede hacer, pero es ineficiente.
El compilador no procesa el AST directamente, sino que prepara el código de bytes, que luego se ejecuta en la máquina virtual Python. Aunque discutir los detalles de este proceso está más allá del alcance de este artículo, el principio básico es que el compilador traduce el AST en notación polaca inversa (RPN). En lugar de poner un operador+entre los operandos izquierdo y derecho, lo colocamos después de ambos operandos. En el ejemplo 3 + 4*xanterior, obtenemos la secuencia 3 4 x * +(y esta notación es especialmente buena porque puedes ver inmediatamente de la secuencia: primero debes realizar la multiplicación, y solo luego la suma). Como cada uno de los cinco elementos en esta secuencia puede representarse en principio como un solo byte, dicho código se llama código de byte. Python luego usa la máquina virtual apilada para ejecutar eficientemente este código.

En otras palabras, el proceso de compilación de un programa escrito en Python tiene lugar en dos etapas. Primero, el programa recibido por la entrada se analiza y el resultado es un árbol de sintaxis abstracta (AST). El compilador luego pasa a través de AST y genera bytecode. Después de eso, el intérprete de Python ejecuta este bytecode. Una vez adoptada la optimización, puede aplicarse tanto a nivel AST como a nivel de bytecode. Ambas opciones tienen sus propias ventajas y desventajas.

Finalmente, tenga en cuenta que aunque AST es común en cualquier implementación de Python, el proceso de traducir AST a bytecode puede ser diferente, y en algunas implementaciones de Python, digamos, JavaScript, en lugar de bytecode, puede generarse en la etapa intermedia.

Paradigmas de otros lenguajes de programación.

No todos los lenguajes de programación usan notación infija, como en Python. Dos ejemplos dignos de mención en este caso son PostScript, donde el programa se escribe directamente en notación polaca inversa, y Lisp, por supuesto, donde los programas generalmente se escriben en notación polaca. Por lo tanto, nuestra expresión del ejemplo anterior, en Lisp podría adoptar la forma siguiente: (+ 3 (* 4 x)).

Conversión de nodos dentro de AST

Teniendo un programa AST, ¿cómo convertir partes individuales de este árbol? Con las prácticas funciones integradas de Python.

Si echamos un vistazo a AST y, por ejemplo, encontramos que tanto los campos leftcomo los rightnodos BinOpson números (nodos Num), podemos realizar los cálculos correspondientes de antemano y luego reemplazarlos por un BinOpnodo normal Num.

Por supuesto, debe actuar con mucho cuidado para no cambiar el comportamiento del programa, haciendo tales transformaciones. Por ejemplo, en len([a(), b(), c(), d()]), está claro que el resultado es 4. Sin embargo, no puede sustituir a toda la expresión del número 4 porque cuatro funciones a, b, c, dtodavía han invocado correctamente.

Nuevamente, comience con una optimización simple. Siempre que aparezca un nombre en el código fuente de un programa pi, reemplácelo con el valor 3.14159265. El módulo Python astya proporciona las estructuras de datos necesarias para hacer esto: una clase de convertidor NodeTransformerque pasa por todos los AST y verifica para cada nodo si se puede reemplazar. Por defecto, el método de transformación simplemente devuelve el nodo fuente para cada nodo, de modo que obtengamos el mismo AST desde el que comenzamos. Pero podemos anular fácilmente el método para los nodos Name, por ejemplo, para que verifique pisi es así, y luego devuelve el nodo en Numlugar del nodo con el nombre original ...

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

Para que el convertidor / optimizador atraviese nuestro árbol, es necesario llamar a su método visit, que luego devolverá un árbol nuevo y modificado.

Desafortunadamente, es imposible compilar y ejecutar el AST resultante, la razón de esto es un detalle técnico. Esto aún no es visible, pero (casi) todos los nodos en el AST también tienen campos linenoy col_offset. Indican la posición exacta de un nodo particular en el código fuente. Si no los instala correctamente, el compilador jurará y se negará a trabajar.

Entonces, copiemos los campos apropiados del nodo fuente Nameal nuevo nodo Num. Luego puede compilar y ejecutar el AST resultante:

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)

Nota: la función de compilación requiere no sólo el código fuente (en el que puede ser un programa en sí, o la línea AST), pero el nombre de archivo (como pedimos "<string>"), así como uno de los tres: "exec", "eval"o "single".

La necesidad de copiar los campos que describen la posición del nodo en el código fuente surge con bastante frecuencia. Por lo tanto, el módulo asttiene una función dedicada copy_locationsolo para este propósito, y podemos escribir:

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

Finalmente, puede ampliar el ejemplo anterior para que realmente realice la optimización, es decir, en el nodo BinOp. De acuerdo con la regla de transformación, primero debemos transformar / optimizar el nodo izquierdo y luego el nodo derecho como parte de BinOp. Si, como resultado, los nodos izquierdo y derecho son números, entonces los cálculos se pueden realizar en el acto y reemplazar el original con el BinOpresultado numérico de la operación.

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

Por cierto, el compilador CPython ya está optimizando nodos BinOpcomo se muestra aquí. El código correspondiente se escribe en C y se proporciona en Python / ast_opt.c . Tenga en cuenta: el optimizador de CPython es más universal y funciona no solo con números, como en el ejemplo que estamos considerando, sino con diferentes tipos de valores constantes.

Comprobación de nodos en AST

¿Cómo asegurarnos de que las transformaciones que hicimos fueron correctas? Primero debe omitir por completo AST e inspeccionar todo el programa.

El optimizador presentado anteriormente sigue siendo un grave defecto. ¿Qué sucede si redefine en algún lugar del programa pi? Solo imagina algo tan simple e inteligible como pi = 4. Nuestro optimizador simplemente reemplazará pi en el lado izquierdo de la expresión con el valor numérico 3.14159265, y Python se negará a compilar porque no puede asignar nada a un valor literal.

Quizás este sea precisamente el comportamiento que buscaba, haciendo de pi una verdadera constante, que se reemplaza en la compilación y nunca se puede reasignar, es decir, no puede obtener un valor diferente. Sin embargo, esto definitivamente viola la semántica de Python.

Entonces, ¿qué hacer si queremos mantener la semántica de Python, pero reemplazar pi de todos modos siempre que sea posible? En este caso, primero debe revisar todo el programa y verificar si el valor de está asignado en alguna parte pi. Hasta que lo compliquemos: no recurriremos a reemplazar pi si al menos un punto del programa tiene una asignación de valor a pi.

Ahora usamos el nodo visitante, similar al nodo convertidor descrito anteriormente. A diferencia del convertidor, el visitante no tiene la intención de cambiar ningún nodo, simplemente pasa por el AST y examina los nodos (los visita). En consecuencia, los métodos de visita no devuelven nada.

En nuestro caso, se comprueba si el nodo se refiere Namea piy hace otra cosa que cargar el valorpi(recuerda el campo de contexto 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)

El generic_visit(node)visitante llama al método para cada nodo para el que no proporcionamos un método de visita especializado. En otras palabras: no existe tal método visit_FunctionDefen la clase NodeVisitorque podríamos llamar usando super(). Con respecto a las definiciones de funciones, debemos llamar a un visitante genérico para asegurarnos de que todo el cuerpo de la función también se procese correctamente. De lo contrario, podríamos ocultar las instrucciones en la función global piy cambiar globalmente el valor pi, para que nuestro optimizador no note nada.

Valores locales en Python

Nuestro método, que nos permite determinar si el programador ha cambiado pi, resultó ser bastante grosero. Sin embargo, el compilador de Python actúa de manera muy similar cuando determina qué nombres en el alcance de una función corresponden a variables locales. Si una variable cambia en algún lugar del alcance de la función (y no se hace explícitamente global, por ejemplo, usando la instrucción global), entonces esta variable se considera local en todo el alcance de la función.

El siguiente ejemplo se ejecutará bien sin la cuarta línea. Pero, aunque x = 0la cuarta línea nunca se ejecuta, todavía se considera una asignación ax y por lo tanto, x se convierte en una variable local en la escala de toda la función, e incluso en la línea 3. Es por eso que Python jurará que la variable x en la tercera línea todavía no importa.

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

Si está interesado en los detalles de cómo funciona exactamente Python aquí, consulte Python / symtable.c .

Conclusión

En Python, como en la mayoría de los lenguajes de programación, un programa en particular no se ejecuta directamente desde el código fuente. De hecho, la traducción del código fuente tiene lugar en dos etapas: primero, se crea un árbol de sintaxis abstracta (AST), y luego el código de bytes para la máquina virtual apilada. Python también proporciona una serie de características muy agradables para analizar e incluso transformar el AST de cualquier programa Python en particular, después de lo cual el AST modificado se puede compilar y ejecutar. Por lo tanto, podemos implementar fácilmente nuestras propias optimizaciones.

Por supuesto, simplemente omití muchos detalles aquí. Asegurarse de que su optimización funcionará correctamente en todos los casos y circunstancias posibles es una cuestión muy trivial. Sin embargo, el propósito de este artículo no es informarle sobre la optimización que está lista para su uso en producción, sino dar una idea básica de cómo Python analiza el código de su programa para que pueda aprender cómo convertirlo correctamente y luego optimizarlo.

Implementamos conversiones de código Python