14

我听说有些语言通过“展开解释器循环”从解释变为编译。

假设我有以下用于 ast 树的伪 c 代码解释器。

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

如何展开此循环以创建已编译的程序？

我看到你们所有人都对此表示反对，就像我不知道我在说什么一样，但这里有一段来自维基百科的引述，它准确地说明了我所描述的内容。

“因子最初只是解释，但现在完全编译（非优化编译器基本上展开解释器循环”

4

8 回答 8

14

“展开循环”通常意味着用一系列动作替换重复。循环：

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

如果您使用该interpet功能（实际上执行操作）遍历 AST，那么您就是在解释。但是如果函数记录了要执行的动作，而不是执行它们，那么你就是在编译。在伪代码中（实际上，伪代码两次，因为我假设一个假设的堆栈机器作为编译目标）：

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，而不是展开解释器，但不会在不阅读上下文的情况下批评别人的隐喻。

于 2009-02-08T21:09:38.440 回答
3

我有点困惑。我不认为“展开循环”在这里是正确的术语。即使您将代码重构为没有任何递归调用，您仍将使用解释器。

你可以用 GCC 编译这个程序。然后您将拥有一个已编译的程序，尽管已编译的程序将解释 AST。

将其转换为编译器的一种方法是return interpret(child(0))+interpret(child(1));，您将生成汇编指令，而不是执行加法，然后将其输出到文件中。

于 2009-02-08T21:00:51.317 回答
2

您在这里并没有真正的循环，因为并非所有的调用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。通常 FORTH 有一个生成线程代码的外部解释器。线程代码可以设想为函数指针数组（有几种变体，直接线程、间接线程、子程序线程等）。线程代码由内部解释器执行。在这种情况下展开解释器是指内部解释器，并且是连接线程代码的问题。

于 2009-02-08T21:04:17.000 回答
2

Factory 是一种基于堆栈的语言，而不是基于 AST 的解释器。

我已经为演员解释器使用了基于堆栈的语言，所以这就是我所做的工作的方式，这可能与 Factor 并不完全不同。

每个函数都作为一个函数实现，该函数接受一个堆栈并返回一个堆栈（在我的情况下，是同一堆栈的变异版本，我不确定 Factor 是功能性的还是变异的）。在我的解释器中，每个函数也将函数的延续放在堆栈顶部，因此解释器知道下一步该做什么：

所以调用栈上下一个函数的解释器是这样的：

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

考虑函数 foo：

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

add 可以定义为：

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

和 foo 作为：

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
于 2009-02-09T11:48:28.717 回答
2

这可能不相关，还要查看第二个 Futamura 投影

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

这表示编译器只是具有部分评估/常量折叠的解释器（理论上很好，但在实践中不好）。

于 2009-02-10T03:12:31.100 回答
1

在本文中，我介绍了一个将解释器自动转换为编译器的示例（尽管编译为 Scheme 而不是机器代码）。这与其他人在这里给出的想法相同，但您可能会发现看到它自动化会有所帮助。

于 2009-02-08T22:11:48.367 回答
0

解释器在运行时扫描每个字节码（或 AST 节点）并分派给函数调用（通常在无限循环中使用 switch 语句）。

编译器基本上做同样的事情，但在编译时。编译器在编译时扫描每个字节码（或 AST 节点）并发出代码（机器代码或一些更高级别的中间语言，如 C）以在运行时调用适当的函数。

于 2009-02-08T21:08:00.940 回答
0

我认为这意味着不是循环语句并执行它们，而是循环语句并输出将执行的解释器代码。

基本上，正在发生的事情是将在解释器循环中执行的代码内联到一个新函数中。循环被“展开”，因为当代码执行时，它不再在解释器循环中，它只是通过生成函数的线性路径。

于 2009-02-08T21:11:21.697 回答