Come faccio a srotolo (compilo) un loop interprete?

Question

Ho sentito che alcune lingue vanno da interpretato compilato dal "srotolando il ciclo interprete".

Diciamo che ho il seguente interprete pseudo-c-codice per un albero di ast.

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

Come faccio a srotolare questo loop per creare un programma compilato?

ti vedo tutto questo downvoting come se non so cosa sto parlando, ma qui è una citazione da Wikipedia che indica esattamente quello che sto descrivendo.

"Fattore stato originariamente solo interpretato, ma è ora completamente compilata (la non ottimizzazione compilatore srotola sostanzialmente il ciclo interprete"

Answer 1

"apertolo un loop" normalmente significa sostituzione di una ripetizione di una sequenza di azioni. Il ciclo:

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

sarebbe srotolare nell'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];

Mi sembra che chi veniva citato da Wikipedia stava usando la frase in un senso un po 'metaforico. Quindi, in questo senso ...

Il campione viene normalmente lanciato all'interno di un interprete che sta camminando un albero di nodi AST, che potrebbe essere simile a questo:

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

e la funzione interpret avrebbe opzioni aggiuntive:

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));
        ...
    }
}

Se si cammina l'AST, con quella funzione interpet (in realtà eseguendo le operazioni), che stai interpretando. Ma se la funzione record le azioni da eseguire, invece di l'esecuzione di loro, si sta compilando. In pseudocodice (in realtà, pseudocodice due volte , come io sto assumendo una macchina pila ipotetica come l'obiettivo di compilazione):

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)));
        ...
    }
}

Invocare compile su quella AST (ignorando eventuali errori di battitura pseudocodice ;-) sarebbe sputare fuori qualcosa come:

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

FWIW, mi piacerebbe tendono a pensare che, come srotolare l'AST, piuttosto che srotolando l'interprete, ma non criticare qualcun altro metafora senza leggerlo nel contesto.

Answer 2

Sono un po 'confuso. Non credo che 'srotolando il ciclo' è il termine giusto qui. Anche se si refactoring il codice a non avere tutte le chiamate ricorsive, si continua a utilizzare un interprete.

È possibile compilare questo programma con GCC. Allora si avrà un programma compilato, anche se il programma compilato sarà interpretare l'AST.

Un modo per trasformare questo in un compilatore sarebbe, invece di fare return interpret(child(0))+interpret(child(1));, si potrebbe generare istruzioni di montaggio, che farebbero l'aggiunta, invece, e poi l'uscita coloro che in un file.

Answer 3

In realtà non si dispone di un ciclo qui poiché non tutti i chiamate a interpret sono chiamate di coda.

Il compilatore più vicina alla tua, ipotizzando un modello di 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);       
    }
}

ma credo che srotolamento , in questo contesto è più applicabile ad un interprete di byte code piuttosto che un interprete AST. Le istruzioni bytecode sono tipicamente interpretati in un ciclo. Quindi la tecnica "srotolamento" è quello di emettere il codice corrispondente a ciascuna istruzione bytecode.

Factor è simile a Forth. In genere ha avanti un interprete esterno che genera codice threaded . Il codice filettata può essere previsto un array di puntatori a funzione (esistono diverse varianti, filettati diretta, filettati indiretto, subroutine filettato, ecc). Il codice filettata è eseguito da un interprete interno. Srotolando l'interprete in questo caso si riferisce all'interprete interna, ed è una questione di concatenando il codice filettato.

Answer 4

Factory è un linguaggio stack di base, non un interprete basato AST.

Ho usato linguaggi basati pila per interpreti attore, quindi questo è il modo del lavoro che ho fatto uno, che non può essere del tutto a differenza Factor.

Ogni funzione è implementata come una funzione che prende una pila, e restituisce uno stack (nel mio caso una versione mutata della stessa risma, non sono sicuro se il fattore è funzionale o mutazione). Nei miei interpreti, ogni funzione mette anche la continuazione della funzione sulla parte superiore della pila, quindi l'interprete sa cosa fare dopo:

Quindi, l'interprete per chiamare la funzione successiva nello stack è qualcosa di simile:

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

Considerando la funzione foo:

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

aggiuntivo potrebbe essere definito come:

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

e foo come:

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

e lo stack per invocare foo (5,6) sarebbe evolvere qualcosa di simile in ogni fase del ciclo:

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

Un semplice compilatore potrebbe srotolare il ciclo per la funzione foo, la generazione del codice filettato equivalente:

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

Answer 5

Questo non può essere correlato, ma anche controllare la seconda sporgenza Futamura

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

che dice che un compilatore è solo un interprete con valutazione parziale / costante ripiegamento (bene in teoria ma non in pratica).

Answer 6

questo articolo ho attraversato un esempio di convertire automaticamente un interprete in un compilatore ( anche se la compilazione di sistema piuttosto che codice macchina). E 'la stessa idea che altri hanno dato qui, ma si potrebbe trovare utile per vederlo automatizzato.

Answer 7

Un interprete scansione di ogni bytecode (o nodo AST) in fase di esecuzione e invio alle funzioni chiamate (tipicamente utilizzando un'istruzione switch in un ciclo infinito).

Un compilatore fa essenzialmente la stessa cosa, ma al momento della compilazione. Il compilatore scansione di ogni bytecode (o nodo AST) al momento della compilazione ed emette codice (codice macchina o qualche lingua intermedia di livello superiore come C) per richiamare la funzione appropriata in fase di esecuzione.

Answer 8

Credo che cosa vuol dire è che invece di loop sulle dichiarazioni e la loro esecuzione, è un ciclo sulle dichiarazioni e in uscita il codice interprete che avrebbe eseguito.

In sostanza, quello che sta succedendo è che il codice che verrebbe eseguito nel ciclo dell'interprete viene inline in una nuova funzione. Il ciclo viene "srotolato", perché quando il codice viene eseguito, non è nel ciclo interprete più, è solo un percorso lineare attraverso la funzione generata.