Pytanie Jak mogę rozwinąć (kompilować) pętlę interpretera?


Słyszałem, że niektóre języki przechodzą od zinterpretowanej do skompilowanej przez "rozwijanie pętli interpretera".

Załóżmy, że mam następujący interpreter pseudokodowania kodu dla drzewa ast.

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

Jak rozwinąć tę pętlę, aby utworzyć skompilowany program?

Widzę, że wszyscy tak mówicie, bo nie wiem, o czym mówię, ale tutaj jest cytat z Wikipedii, który stwierdza dokładnie to, co opisuję.

"Factor został pierwotnie zinterpretowany, ale jest teraz w pełni skompilowany (nieoptymalizowany kompilator zasadniczo rozwija pętlę interpretera"


14
2018-02-08 20:51


pochodzenie


Myślę, że użycie Wikipedii "rozwijanie pętli" tutaj jest całkowicie odpowiednie, nawet jeśli jest to raczej przenośne. Prawidłowe, a co bardziej interesujące pytanie. - Konrad Rudolph


Odpowiedzi:


"Rozwijanie pętli" zwykle oznacza zastąpienie powtórzenia sekwencją czynności. Pętla:

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

rozwinie się w odpowiednik:

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

Wydaje mi się, że ktokolwiek cytowany był przez Wikipedię, używał tego zwrotu w nieco metaforycznym znaczeniu. W tym sensie ...

Twoja próbka będzie normalnie wywoływana wewnątrz interpretera, który krąży wokół drzewa węzłów AST, co może wyglądać mniej więcej tak:

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

i interpret funkcja miałaby dodatkowe opcje:

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

Jeśli idziesz z tym AST interpet funkcja (faktycznie wykonująca operacje), którą interpretujesz. Ale jeśli funkcja dokumentacja czynności, które należy wykonać, a nie wykonanie oni, kompilujesz. W pseudokod (właściwie pseudokod dwa razy, jako że zakładam hipotetyczną maszynę stosu jako cel kompilacji):

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

Wzywając compile na tym AST (ignorując wszelkie pseudokodowe literówki ;-) wyplułoby coś takiego:

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

FWIW, raczej uważałbym to za rozwinięcie AST, niż rozwijanie interpretatora, ale nie będę krytykował cudzej metafory bez czytania jej w kontekście.


14
2018-02-08 21:09



Rekursja to fantazyjna pętla. - strager
Możesz wspomnieć o tym, jaki kod generujesz tutaj (maszyna stosowa a inne formy pośredniego języka). W przeciwnym razie dobra odpowiedź. - Konrad Rudolph
@Konrad: Dzięki za sugestię. Zmontowałem go, aby go włączyć. - joel.neely


Jestem nieco zdezorientowany. Nie sądzę, że "rozwijanie pętli" jest tu właściwym terminem. Nawet jeśli zredagujesz kod, aby nie wykonywać żadnych rekurencyjnych połączeń, nadal będziesz korzystać z tłumacza.

Możesz skompilować ten program z GCC. Wtedy będziesz miał skompilowany program, chociaż skompilowany program będzie interpretował AST.

Jednym ze sposobów przekształcenia tego w kompilator będzie, zamiast robić return interpret(child(0))+interpret(child(1));, generowałbyś instrukcję montażu, która zamiast tego robiłaby dodatek, a następnie wysyłała je do pliku.


3
2018-02-08 21:00





Naprawdę nie masz tu pętli, ponieważ nie wszystkie połączenia do interpret są ogonem.

Kompilator najbliżej Ciebie, zakładając model stosu ...

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

ale myślę rozwijanie w tym kontekście bardziej pasuje do interpretera kodu bajtowego niż do interpretatora AST. Instrukcje kodu bajtowego są zwykle interpretowane w pętli. Następnie technika "rozwijania" polega na emisji kodu odpowiadającego każdej instrukcji kodu bajtowego.

Czynnik jest podobny do FORTH. Zazwyczaj FORTH ma zewnętrzny interpreter, który generuje kod z gwintem. Gwintowany kod może być wyposażony w tablicę wskaźników funkcyjnych (istnieje kilka wariantów, gwintowanie bezpośrednie, gwintowanie pośrednie, gwintowanie podprogramu itp.). Gwintowany kod jest wykonywany przez wewnętrznego interpretera. Rozwinięcie interpretera w tym przypadku dotyczy wewnętrznego interpretera i jest kwestią połączenia wątkowego kodu.


2
2018-02-08 21:04





Fabryka jest językiem stosowym, a nie tłumaczem opartym na AST.

Używałem języków stosowych dla tłumaczy aktorskich, więc w ten sposób stworzyłem pracę, która może nie być całkowicie odmienna od Factor.

Każda funkcja jest zaimplementowana jako funkcja, która pobiera stos i zwraca stos (w moim przypadku zmutowaną wersję tego samego stosu, nie jestem pewien, czy czynnik jest funkcjonalny czy mutujący). W moich tłumaczach każda funkcja umieszcza także kontynuację funkcji na górze stosu, więc tłumacz wie, co dalej:

Interpreter wywołujący następną funkcję na stosie ma coś takiego:

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

Biorąc pod uwagę funkcję foo:

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

add można zdefiniować jako:

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

i foo jako:

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

a stos wywoływania foo (5,6) będzie ewoluował w podobny sposób na każdym etapie pętli:

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

Prosty kompilator może rozwinąć pętlę dla funkcji foo, generując równoważny kod z wątkiem:

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

2
2018-02-09 11:48





To może nie być związane, ale także sprawdź drugą projekcję Futamury

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

który mówi, że kompilator jest tylko interpretatorem z częściową oceną / stałym fałdowaniem (dobre w teorii, ale nie w praktyce).


2
2018-02-10 03:12





W Ten artykuł Podałem przykład automatycznego przekonwertowania interpretera na kompilator (choć kompilowany do schematu, a nie do kodu maszynowego). Jest to ten sam pomysł, który inni podali tutaj, ale może się okazać, że pomocne będzie zautomatyzowanie go.


1
2018-02-08 22:11





Interpreter skanuje każdy kod bajtowy (lub węzeł AST) w czasie wykonywania i wywołuje wywołania funkcji (zwykle za pomocą instrukcji switch w nieskończonej pętli).

Kompilator robi zasadniczo to samo, ale w czasie kompilacji. Kompilator skanuje każdy kod bajtowy (lub węzeł AST) w czasie kompilacji i emituje kod (kod maszynowy lub jakiś wyższy język pośredni, taki jak C), aby wywołać odpowiednią funkcję w czasie wykonywania.


0
2018-02-08 21:08





Myślę, że oznacza to, że zamiast pętli nad instrukcjami i ich wykonywanie, pętli nad instrukcjami i wypisywano kod interpretera, który zostałby wykonany.

Zasadniczo, to, co się dzieje, to kod, który byłby wykonywany w pętli interpretera, zostanie wbudowany w nową funkcję. Pętla zostaje "rozwinięta", ponieważ kiedy kod jest wykonywany, nie jest już w pętli interpretera, jest to po prostu liniowa ścieżka przez wygenerowaną funkcję.


0
2018-02-08 21:11