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

このループを展開してコンパイル済みプログラムを作成するにはどうすればよいですか?

私が何について話しているのかわからないように、皆さんがこれに反対票を投じているのを見ますが、これはウィキペディアからの引用であり、私が説明していることを正確に述べています.

「Factor はもともと解釈されるだけでしたが、現在は完全にコンパイルされています (非最適化コンパイラは基本的にインタプリタ ループを展開します」

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

その関数を使用して AST をinterpet実行する (実際に操作を実行する) 場合は、解釈しています。ただし、関数が実行するのではなく、実行するアクションを記録する場合は、コンパイルしています。疑似コード (実際には、架空のスタック マシンをコンパイル ターゲットとして想定しているため、疑似コードを 2 回使用します):

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 をアンロールすると考える傾向がありますが、文脈を読まずに他の誰かの比喩を批判するつもりはありません。

于 2009-02-08T21:09:38.440 に答える
3

少し混乱しています。ここで「ループを展開する」という用語は適切ではないと思います。再帰呼び出しがないようにコードをリファクタリングしたとしても、インタープリターを使用することになります。

このプログラムは GCC でコンパイルできます。次に、コンパイルされたプログラムがASTを解釈しますが、コンパイルされたプログラムができます。

これをコンパイラに変換する 1 つの方法はreturn interpret(child(0))+interpret(child(1));、 を実行する代わりに、加算を行うアセンブリ命令を生成し、それらをファイルに出力することです。

于 2009-02-08T21:00:51.317 に答える
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

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 インタープリターよりもバイト コード インタープリターに適していると思います。通常、バイトコード命令はループで解釈されます。次に、「展開」手法は、各バイトコード命令に対応するコードを発行することです。

Factor は FORTH に似ています。通常、FORTH には、スレッド化されたコードを生成する外部インタープリターがあります。スレッド化されたコードは、関数ポインターの配列として想定できます (いくつかのバリアント、直接スレッド化、間接スレッド化、サブルーチン スレッド化などがあります)。スレッド化されたコードは、内部インタープリターによって実行されます。この場合のインタープリターのアンロールは、内部インタープリターを参照し、スレッド化されたコードを連結することです。

于 2009-02-08T21:04:17.000 に答える
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 に答える