我如何展开（编译）译员循环？

Question

我听说有些语言从解释去了“展开的解释器”来进行编译。

让我们说我有一个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));       
    }
}

我如何展开这个循环来创建一个编译的程序？

我看到你所有的downvoting这就像我不知道我在说什么，但这里是维基百科报价，指出正是我所描述的。

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

Answer 1

“展开循环”通常是指具有的动作的序列替换一个重复。循环：

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

对AST调用compile（忽略任何伪错字;-)将吐出类似：

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

FWIW，我倾向于认为，作为展开的AST，而不是展开了解释，但没有在上下文中阅读它不会批评别人的比喻。

Answer 2

我略微困惑。我不认为这里“展开循环”是正确的术语。即使你重构代码没有任何递归调用，你仍然会使用解释。

可以编译这个程序与GCC。那么你将有一个编译的程序，尽管已编译的程序将被解释AST。

的一种方式把它变成一个编译器会是这样，而不是做return interpret(child(0))+interpret(child(1));，你会产生组装说明这将做加法，而不是，然后输出这些到文件中。

Answer 3

您真的没有一个循环这里，因为不是所有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具有产生外翻译的线程代码。螺纹代码可以设想函数指针数组（有几种变体，直接螺纹，螺纹间接，子程序螺纹等）。螺纹代码由内解释器执行。展开在这种情况下，解释程序是指内解释器，是串接线程代码的问题。

Answer 4

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

我已经用了演员口译基于堆栈的语言，所以这是一个人的我做了工作，这可能不是完全不像因素如何。

每个功能作为它接受一个堆栈，返回堆栈的功能来实现（在我的情况相同的堆栈的突变形式，我不知道是否是因子的功能性或突变）。在我的解释，各功能也使堆栈的顶部功能的延续，所以翻译知道下一步做什么：

因此，解释器来调用堆栈中下一个函数是这样的：

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为：

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

Answer 5

这可能不相关，而且还检查出第二二村投影

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

它说，一个编译器只是部分评价/常量合并处理的解释器（在理论好的，但不是实践）。

Answer 6

在这篇文章我通过的解释器自动转换成一个编译器的例子去（尽管编制方案，而不是机器代码）。这是同样的想法，其他人在此给出，但你可能会发现它有用看到它自动的。

Answer 7

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

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

Answer 8

我想它的意思是不是在循环语句和执行它们，你遍历所有的报表输出，将已经执行了解释器代码。

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