¿Cómo desenrollo(compilo) un bucle de intérprete?

optimization compiler-construction

Question

Escuché que algunos idiomas van desde interpretados hasta compilados por "desenrollar el lazo del intérprete".

Digamos que tengo el siguiente intérprete de código pseudoc para un árbol ast.

int interpret(node)
{
    switch(node) {
        case PLUS:
             return interpret(child(0))+interpret(child(1));
        case MINUS:
             return interpret(child(0))-interpret(child(1));       
    }
}

¿Cómo puedo desenrollar este ciclo para crear un programa compilado?

Los veo revocar todo esto como si no supiera de lo que estoy hablando, pero aquí hay una cita de Wikipedia que dice exactamente lo que estoy describiendo.

"Originalmente, el factor solo se interpretaba, pero ahora está completamente compilado (el compilador que no optimiza básicamente desenrolla el bucle del intérprete"

Answer 1

"Desenrollar un bucle" normalmente significa reemplazar una repetición con una secuencia de acciones. El lazo:

for (int i = 0; i < 4; ++i) {
    a[i] = b[i] + c[i];
}

se desenrollaría en el equivalente:

a[0] = b[0] + c[0];
a[1] = b[1] + c[1];
a[2] = b[2] + c[2];
a[3] = b[3] + c[3];

Me parece que quien fue citado por Wikipedia estaba usando la frase en un sentido algo metafórico. Entonces, en ese sentido ...

Su muestra normalmente se invocará dentro de un intérprete que está caminando por un árbol de nodos AST, que podría verse más o menos así:

 ASSIGN
    |
 +--+---+
 |      |
REF   MINUS
 |      |
 x   +--+---+
     |      |
    VAR    PLUS
     |      |
     a   +--+--+
         |     |
        VAR  CONST
         |     |
         b     3

y la función de interpret tendría opciones adicionales:

int interpret(node) {
    switch(node) {
        case PLUS:
             return interpret(child(0))+interpret(child(1));
        case MINUS:
             return interpret(child(0))-interpret(child(1));       
        case ASSIGN:
             return set(child(0), interpret(child(1));
        case VAR:
             return fetch(child(0));
        case CONST:
             return value(child(0));
        ...
    }
}

Si recorre el AST con esa función de interpet (en realidad, realiza las operaciones), está interpretando. Pero si la función registra las acciones a realizar, en lugar de ejecutarlas , está compilando. En pseudocódigo (en realidad, pseudocódigo dos veces , ya que supongo que una máquina de pila hipotética es el objetivo de compilación):

string compile(node) {
    switch(node) {
        case PLUS:
             return(compile(child(0))) + compile(child(1)) + ADD);
        case MINUS:
             return(compile(child(0))) + compile(child(1)) + SUB);
        case ASSIGN:
             return(PUSHA(child(0))) + compile(child(1)) + STORE);
        case REF:
             return(PUSHA(child(0)));
        case VAR:
             return(PUSHA(child(0)) + FETCH);
        case CONST:
             return(PUSHLIT + value(child(0)));
        ...
    }
}

Invocar la compile en ese AST (ignorando cualquier tipo de error de pseudocódigo ;-) sería como:

PUSHA x
PUSHA a
FETCH
PUSHA b
FETCH
PUSHLIT 3
ADD 
SUB
STORE

FWIW, tendería a pensar en eso como desenrollar el AST, en lugar de desenrollar el intérprete, pero no criticaré la metáfora de otra persona sin leerla en contexto.

Answer 2

Creo que lo que significa es que en lugar de pasar por encima de las instrucciones y ejecutarlas, se repiten las instrucciones y se emite el código de intérprete que se habría ejecutado.

Básicamente, lo que sucede es que el código que se ejecutará en el bucle del intérprete se inserta en una nueva función. El bucle se "desenrolla" porque cuando el código se ejecuta, ya no está en el bucle del intérprete, es solo una ruta lineal a través de la función generada.

Answer 3

En este artículo , pasé por un ejemplo de convertir automáticamente un intérprete en un compilador (aunque compilando Scheme en lugar de código de máquina). Es la misma idea que otros han dado aquí, pero puede ser útil verla automatizada.

Answer 4

Estoy un poco confundido. No creo que ''desenrollar el ciclo'' sea el término correcto aquí. Incluso si refactoriza el código para que no tenga llamadas recursivas, seguirá utilizando un intérprete.

Puede compilar este programa con GCC. Luego tendrá un programa compilado, aunque el programa compilado interpretará el AST.

Una forma de convertir esto en un compilador sería, en lugar de hacer la return interpret(child(0))+interpret(child(1)); , generaría instrucciones de ensamblaje que realizarían la suma en su lugar y luego las generaría en un archivo.

Answer 5

Realmente no tiene un bucle aquí ya que no todas las llamadas para interpret son llamadas de cola.

El compilador más cercano al tuyo, asumiendo un modelo de pila ...

int compile(node)
{
    switch(node) {
        case PLUS:
             return compile(child(0))&&compile(child(1))&&compile_op(op_plus);
        case MINUS:
             return compile(child(0))&&interpret(child(1))&&compile_op(op_minus);       
    }
}

pero creo que desenrollar en este contexto es más aplicable a un intérprete de código de bytes en lugar de un intérprete de AST. Las instrucciones de bytecode generalmente se interpretan en un bucle. Luego, la técnica de "desenrollar" es emitir el código correspondiente a cada instrucción de código de bytes.

El factor es similar a FORTH. Normalmente, FORTH tiene un intérprete externo que genera código enhebrado . El código enhebrado puede visualizarse en una matriz de punteros de función (hay varias variantes, roscado directo, roscado indirecto, roscado de subrutina, etc.). El código enhebrado es ejecutado por un intérprete interno. Desenrollar el intérprete en este caso se refiere al intérprete interno, y es una cuestión de concatenación del código enhebrado.

Answer 6

Un intérprete escanea cada bytecode (o nodo AST) en el tiempo de ejecución y se envía a las llamadas a funciones (generalmente usando una instrucción switch en un ciclo infinito).

Un compilador hace esencialmente lo mismo, pero en tiempo de compilación. El compilador escanea cada bytecode (o nodo AST) en tiempo de compilación y emite código (código máquina o algún lenguaje intermedio de nivel superior como C) para llamar a la función apropiada en tiempo de ejecución.

Answer 7

Factory es un lenguaje basado en pila, no un intérprete basado en AST.

He usado los lenguajes basados ​​en pila para los intérpretes de actores, así que así es como he trabajado, lo cual puede no ser del todo diferente de Factor.

Cada función se implementa como una función que toma una pila y devuelve una pila (en mi caso una versión mutada de la misma pila, no estoy seguro si Factor es funcional o está mutando). En mis intérpretes, cada función también pone la continuación de la función en la parte superior de la pila, por lo que el intérprete sabe qué hacer a continuación:

Entonces el intérprete que llama a la siguiente función en la pila es algo así como:

for (;;)
    stack = (stack[0].function_pointer)(stack);

Teniendo en cuenta la función foo:

def foo (x,y):
   print( add(x, y) )

agregar se puede definir como:

pop a
pop b
stack[ return_offset ] = a + b
return stack 

y foo como:

pop x
pop y
push _
push &print
push y
push x
push &add

y la pila para invocar a foo (5, 6) evolucionaría algo así en cada paso del ciclo:

>> foo(5,6)
[&foo, 5, 6]
[&add, 5, 6, &print, _]
[&print, 11]
=> 11
[]

Un compilador simple podría desenrollar el bucle para la función foo, generando el código roscado equivalente:

compiled_foo (stack): 
    stack = begin_foo(stack) // arranges stack for call to add
    stack = add(stack)
    stack = print(stack)
    return stack

Answer 8

Esto puede no estar relacionado, pero también echa un vistazo a la segunda proyección de Futamura

http://en.wikipedia.org/wiki/Futamura_projection

que dice que un compilador es solo un intérprete con evaluación parcial / plegado constante (bueno en teoría pero no práctico).