6

私は最近、この定理をここで見つけました（下部にあります）：

Any program can be transformed into a semantically equivalent program of one procedure containing one switch statement inside a while loop.

記事は次のように続けています。

A corollary to this theorem is that any program can be rewritten into a program consisting of a single recursive function containing only conditional statements

私の質問は、これらの定理は両方とも今日適用可能ですか? 同様にプログラムを変換すると、何かメリットがありますか? つまり、そのようなコードは最適化されていますか? (再帰呼び出しは遅くなりますが、私は知っています)

hereから、コンパイラによって最適化されると、ほとんどの場合、スイッチケースが高速になることを読みました。それは違いますか。?

PS：ここからコンパイラの最適化についていくつかのアイデアを得ようとしています

cそして、最適化された唯一の言語であるため、タグを追加しました。

4

3 に答える 3

7

それは本当です。チューリング マシンは、基本的に、永遠に繰り返されるシンボルの switch ステートメントであるため、チューリング マシンがすべてを計算することに直接基づいています。switch ステートメントは条件の集まりにすぎないため、そのようなプログラムを条件のみのループとして明確に記述できます。それができれば、再帰からループを作成するのは非常に簡単ですが、言語に真の字句スコープがない場合は、パラメーターとして多くの状態変数を渡す必要があるかもしれません。

実際にこれを行う理由はほとんどありません。このようなプログラムは通常、元のプログラムよりも動作が遅く、より多くのスペースを必要とする場合があります。では、なぜプログラムを遅くしたり、ロード イメージを大きくしたりするのでしょうか?

これが意味を持つ唯一の場所は、コードを難読化する場合です。この種の手法は、「制御フローの難読化」としてよく使用されます。

于 2012-04-25T21:04:08.157 に答える
3

これは基本的に、コンパイラがプログラムを機械語に変換するときに起こることです。マシンコードはプロセッサ上で実行され、ループ内で命令を 1 つずつ実行します。プログラムの複雑な構造は、メモリ内のデータの一部になっています。

于 2012-04-25T21:13:57.510 に答える
2

switch ステートメントによる再帰ループを使用して、初歩的な仮想マシンを作成できます。仮想マシンがチューリング完全である場合、理論的には、このマシンで動作するようにプログラムを書き直すことができます。

int opcode[] {
   PUSH,
   ADD
   ....
};

while (true) {
    switch (*opcode++) {
    case PUSH:
        *stack++ = <var>;
        break;
    case ADD:
        stack[-1] += stack[0];
        --stack;
        break;
     ....
    }
}

もちろん、この仮想マシン用のコンパイラを作成することは別の問題です。:-)

于 2012-04-25T21:16:02.463 に答える