Как развернуть (скомпилировать) цикл интерпретатора? - PullRequest
Новая
       29

Как развернуть (скомпилировать) цикл интерпретатора?

14 голосов
/ 08 февраля 2009

Я слышал, что некоторые языки переходят от интерпретируемого к скомпилированному путем "развертывания цикла интерпретатора".

Допустим, у меня есть следующий интерпретатор псевдо-c-кода для дерева ast. 

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

Как развернуть этот цикл для создания скомпилированной программы?

Я вижу, что вы все отрицаете это, как будто я не знаю, о чем говорю, но вот цитата из Википедии, в которой точно говорится, что я описываю.

"Фактор изначально был только интерпретирован, но теперь полностью скомпилирован (неоптимизирующий компилятор в основном развертывает цикл интерпретатора"

Ответы [ 8 ]

14 голосов
/ 09 февраля 2009

«Развертывание цикла» обычно означает замену повторения последовательностью действий. Цикл: 

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

развернется в эквивалент: 

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

Мне кажется, что тот, кто цитировался в Википедии, использовал эту фразу в несколько метафорическом смысле. Итак, в этом смысле ...

Ваш образец обычно вызывается внутри интерпретатора, который проходит по дереву узлов AST, который может выглядеть примерно так: 

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

и функция interpret будут иметь дополнительные опции: 

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

Если вы проходите AST с помощью этой функции interpet (фактически выполняющей операции), вы интерпретируете. Но если функция записывает выполняемые действия, а не выполняет их, вы компилируете. В псевдокоде (фактически, псевдокод дважды , поскольку я предполагаю гипотетическую машину стека в качестве цели компиляции): 

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

Вызов compile для этого AST (игнорирование любых опечаток псевдокода ;-) выдаст что-то вроде: 

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

FWIW, я бы склонялся к тому, чтобы развернуть AST, а не развернуть переводчика, но не буду критиковать чужую метафору, не читая ее в контексте.

3 голосов
/ 09 февраля 2009

Я немного растерялся. Я не думаю, что «раскручивание петли» - это правильный термин здесь. Даже если вы реорганизуете код, чтобы не было никаких рекурсивных вызовов, вы все равно будете использовать интерпретатор.

Вы можете скомпилировать эту программу с GCC. Тогда у вас будет скомпилированная программа, хотя скомпилированная программа будет интерпретировать AST.

Один из способов превратить это в компилятор - вместо return interpret(child(0))+interpret(child(1)); вы будете генерировать инструкции по сборке, которые вместо этого будут выполнять сложение, а затем выводить их в файл.

2 голосов
/ 10 февраля 2009

Это может быть не связано, но также проверьте вторую проекцию Футамуры

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

, который говорит, что компилятор - это просто интерпретатор с частичной оценкой / константным свертыванием (хорошо в теории, но не на практике).

2 голосов
/ 09 февраля 2009

Фабрика - это основанный на стеке язык, а не интерпретатор на основе AST.

Я использовал стековые языки для актерских интерпретаторов, так что вот как я работал, что может не совсем отличаться от фактора.

Каждая функция реализована как функция, которая берет стек и возвращает стек (в моем случае это измененная версия одного и того же стека, я не уверен, работает ли Factor или мутирует). В моих интерпретаторах каждая функция также помещает продолжение функции на вершину стека, поэтому интерпретатор знает, что делать дальше:

Таким образом, интерпретатор для вызова следующей функции в стеке выглядит примерно так: 

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

С учетом функции foo: 

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

добавить можно определить как: 

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

и foo as: 

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

и стек для вызова foo (5,6) будет развиваться примерно так на каждом шаге цикла: 

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

Простой компилятор может развернуть цикл для функции foo, генерируя эквивалентный многопоточный код: 

compiled_foo (stack): 
    stack = begin_foo(stack) // arranges stack for call to add
    stack = add(stack)
    stack = print(stack)
    return stack
2 голосов
/ 09 февраля 2009

Здесь у вас нет петли, так как не все вызовы interpret являются хвостовыми.

Компилятор, ближайший к вашему, предполагая модель стека ... 

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

но я думаю развертывание в этом контексте больше применимо к интерпретатору байт-кода, чем к интерпретатору AST. Инструкции байт-кода обычно интерпретируются в цикле. Тогда метод «развертывания» состоит в том, чтобы испускать код, соответствующий каждой инструкции байт-кода.

Коэффициент похож на ФОРТ. Обычно FORTH имеет внешний интерпретатор, который генерирует поточный код . В многопоточном коде может быть представлен массив указателей на функции (есть несколько вариантов: прямая, косвенная, подпрограмма и т. Д.). Потоковый код выполняется внутренним интерпретатором. Развертывание интерпретатора в этом случае относится к внутреннему интерпретатору и является вопросом объединения потокового кода.

1 голос
/ 09 февраля 2009

В этой статье Я рассмотрел пример автоматического преобразования интерпретатора в компилятор (хотя компиляция в Scheme, а не в машинный код). Это та же идея, что и другие, но вам может быть полезно увидеть ее автоматизированной.

0 голосов
/ 09 февраля 2009

Я думаю, что это означает, что вместо циклического выполнения операторов и их выполнения вы циклически повторяете операторы и выводите код интерпретатора, который должен был бы выполняться.

По сути, происходит то, что код, который будет выполняться в цикле интерпретатора, встроен в новую функцию. Цикл становится "развернутым", потому что когда код выполняется, он больше не находится в цикле интерпретатора, это просто линейный путь через сгенерированную функцию.

0 голосов
/ 09 февраля 2009

Интерпретатор сканирует каждый байт-код (или узел AST) во время выполнения и отправляет вызовы функций (обычно с использованием оператора switch в бесконечном цикле).

Компилятор делает то же самое, но во время компиляции. Компилятор сканирует каждый байт-код (или узел AST) во время компиляции и выдает код (машинный код или некоторый промежуточный язык более высокого уровня, например C), чтобы вызвать соответствующую функцию во время выполнения.

...