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

我的问题是，这两个定理今天都适用吗？类似地转换程序是否有任何好处？我的意思是说，这样的代码是否经过优化？（虽然递归调用比较慢，我知道）

我从这里读到，当编译器优化时，switch-cases几乎总是更快。这有什么区别吗。?

PS：我试图从这里了解编译器优化

我添加了c标签，因为这是我见过的唯一优化的语言。

4

3 回答 3

7

这是真的。图灵机本质上是一个永远重复的符号开关语句，因此它非常直接地基于图灵机计算一切。switch 语句只是一堆条件，因此您可以清楚地将这样的程序编写为仅带有条件的循环。一旦你有了它，从递归中创建循环就很容易了，尽管如果你的语言没有真正的词法作用域，你可能必须传递很多状态变量作为参数。

在实践中几乎没有理由这样做。此类程序的运行速度通常比原始程序慢，并且可能占用更多空间。那么为什么你可能会减慢你的程序，和/或让它的加载图像更大呢？

唯一有意义的地方是如果您打算混淆代码。这种技术通常被用作“控制流混淆”。

于 2012-04-25T21:04:08.157 回答
3

这基本上是编译器将程序翻译成机器代码时发生的情况。机器代码在处理器上运行，处理器在循环中一个接一个地执行指令。程序的复杂结构已经成为内存中数据的一部分。

于 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 回答