¿Cómo desenrollar (compilar) un intérprete bucle?

Question

He oído que algunos idiomas ir de interpretarse compilado por "desenrollar el intérprete de bucle".

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

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 desenrollar este bucle para crear un programa compilado?

Yo veo todo downvoting este como no sé de qué estoy hablando, pero aquí es una cita de la Wikipedia en la que expresa exactamente lo que estoy describiendo.

"Factor fue originalmente sólo se interpreta, pero ahora es totalmente compilado (que no compilador de optimización básicamente desenrolla el intérprete de bucle"

Answer 1

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

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

se desenrolla 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 todo el que estaba siendo citado por Wikipedia utilizaba la frase en un sentido algo metafórica. Por lo tanto, en ese sentido ...

Su muestra normalmente se invoca dentro de un intérprete que está andando un árbol de nodos AST, lo que podría ser algo como esto:

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

y la función 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 usted camina la AST con esa función interpet (en realidad llevar a cabo las operaciones), que está interpretando. Pero si la función registros las acciones a realizar, en lugar de ejecutar ellos, se está compilando. En pseudocódigo (en realidad, pseudocódigo dos veces , ya que estoy asumiendo una máquina de pila hipotético como 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)));
        ...
    }
}

La invocación de compile en ese AST (ignorando los errores tipográficos pseudocode ;-) sería escupir algo como:

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

Fwiw, me tienden a pensar que a medida que se desenrolla la AST, en lugar de desenrollar el intérprete, pero no va a criticar de otra persona metáfora sin leerlo en su contexto.

Answer 2

Estoy un poco confundido. No creo 'desenrollar el bucle' es el término aquí. Incluso si usted refactorizar el código para no tener llamadas recursivas, todavía se va a utilizar un intérprete.

Se puede compilar este programa con GCC. A continuación, tendrá un programa compilado, aunque el programa compilado será la interpretación de la AST.

Una forma de convertir esto en un compilador sería, en vez de hacer return interpret(child(0))+interpret(child(1));, sería generar instrucciones de montaje que hacer la adición lugar, y entonces la salida aquellos en un archivo.

Answer 3

En realidad, no tiene un bucle de aquí, ya que no todas las llamadas a interpret son llamadas de cola.

El compilador más cercana a la suya, 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 desenrollado en este contexto es más aplicable a un intérprete de código de bytes en lugar de un intérprete AST. Las instrucciones de código de bytes se suelen interpretarse en un bucle. A continuación, la técnica de "desenrollamiento" es para emitir el código correspondiente a cada instrucción de código de bytes.

Factor es similar a Forth. Típicamente ADELANTE tiene un intérprete exterior que genera código roscado . El código de roscado se puede prever una matriz de punteros de función (hay varias variantes, roscados directa, indirecta roscados, de subrutina roscado, etc.). El código de roscado es ejecutado por un intérprete interior. Desenrollar el intérprete en este caso se refiere a la intérprete interior, y es una cuestión de la concatenación del código roscado.

Answer 4

La fábrica es una pila basada en el lenguaje, no un AST de intérpretes.

He utilizado la pila de idiomas para intérpretes de actores, así que esto es como el que he hecho el trabajo, que puede no ser del todo a diferencia 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 de si el Factor es funcional o mutación).En mi intérpretes, cada función también pone a la continuidad de la función en la parte superior de la pila, por lo que el intérprete sabe qué hacer a continuación:

Por lo que el intérprete para llamar 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 podría ser definida 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 los foo(5,6) sería evolucionar a algo como esto en cada paso del bucle:

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

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

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

Answer 5

Esto no puede estar relacionado, pero también revisar la segunda proyección Futamura

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

que dice que un compilador es sólo un intérprete con evaluación parcial / plegado constante (bien en teoría, pero no la práctica).

Answer 6

En este artículo Fui a través de un ejemplo de la conversión automática de un intérprete en un compilador ( aunque la compilación con el Esquema vez de código máquina). Es la misma idea que otros han dado aquí, pero es posible que le resulte útil para verla automatizado.

Answer 7

Un intérprete escanea cada código de bytes (o nodo AST) en tiempo de ejecución y el envío a las funciones de llamadas (típicamente usando una instrucción switch en un bucle infinito).

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

Answer 8

Creo que lo que significa es que en lugar de un bucle sobre las declaraciones y la ejecución de ellos, se recorre las declaraciones y la salida del código del intérprete que habrían ejecutado.

Básicamente, lo que sucede es que el código que se ejecuta en el bucle intérprete se inline en una nueva función. El bucle se "desenrolla" porque cuando se ejecuta el código, no es en el bucle intérprete más, es simplemente una trayectoria lineal a través de la función generada.