Convert any program to semantically equivalent

Question

I recently found this theorem here (below):

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

The article went on to say:

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

My questions are both of these theorems applicable today? Converts a program in the same way, getting any benefits? I want to say whether such code is optimized? (Although recursive calls are slower, I know)

I read from here that switch files are almost always faster when optimized by the compiler. It matters.

PS: I'm trying to get an idea about compiler optimization from here

And I added the c tag as the only one I saw optimized.

Answer 1

It's true. A Turing machine is, in fact, a switch statement on characters that repeat forever, so its based quite directly on Turing machines - calculates everything. The switch statement is just a collection of conditional expressions, so you can clearly write a program such as a loop with only conditional expressions. Once you do this, creating a loop from recursion is quite simple, although you may have to pass in a lot of state variables as parameters if your language does not have true lexical coverage.

There is little reason to do this in practice. Such programs usually work more slowly than the originals, and may take up more space. So, why could you slow down your program and / or increase its load image?

The only place this makes sense is the intention to confuse the code. This type of technique is often used as “obfuscation of control flow”.

Answer 2

This is basically what happens when the compiler translates the program into machine code. The machine code runs on a processor that executes the commands one at a time in a loop. The complex structure of the program has become part of the data in memory.

Answer 3

Recursive loops through the switch statement can be used to create an elementary virtual machine. If your virtual machine is filled with Turing, theoretically, any program can be rewritten to work on this machine.

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

Of course, writing a compiler for this virtual machine would be another matter. :-)