1

Is it theoretically possible to create a perfect compiler for a language (for example C) meaning that if two different persons make two different implementations of the same algorithm then the generated assembly (or machine) code is going to be the same in both cases?

I assume that both the programs give the same output for a given input.

  • 3
    From a viewpoint of a compiler, there is no difference between an algorithm and an "implementation of an algorithm". So "two different implementations of the same algorithm" are simply two different sets of input data to the compiler, which makes the question sound quite absurd, don't you think? – Doc Brown Jun 10 '18 at 7:43
  • 2
    This might be interesting question for CS Stack Exchange. But instead of compiling, ask if two structurally different turing machines can have same input/output. And if yes, if it is possible to convert between them. My intuition tells me this would be same as solving halting problem. Eg. even theoretically impossible. – Euphoric Jun 10 '18 at 18:46
  • Are you assuming that the said compiler has "known optimizations" that convert any implementations to "the best implementation" for a given algorithm ? That's highly unlikely. – S.D. Jun 11 '18 at 4:33
10

No:

First, let's note that there are many, many equivalent yet differing code sequences when it comes to machine code (let alone other languages).  A simple case is swapping two registers where the performance is otherwise equivalent.

Second, workload for programs/applications can be highly variable.  There is no such thing as a perfect code sequence, only better or worse for a given test case or set of test cases.  Since one sequence may perform better on one test (or tests), while another sequence better on another test (or tests) — in the abstract — we cannot absolutely judge which sequence is better: we would need to judge the relative importance of test cases, which, I think, wanders outside of the scope of your question.

Third, we should note that the notion of the same algorithms used by two different persons is problematic in that compilers use such a large variety of heuristics governed by tuning factors.  There is no reason to believe, a prior, that the tuning factors would be the same even if the algorithms are.  However, even regarding the algorithms being equal, we have to examine the level of abstraction of the application of the algorithm.  A sufficiently abstract algorithm will allow a great latitude in ordering among totally equivalent solutions, which would result, as just one example, in differing register choices, and thus differing code sequences.

  • 1
    As an example, sort the array is a great building-block. But there are many many ways to sort. – Deduplicator Jun 10 '18 at 14:29
3

No, this is theoretically impossible. The reason is, that this corresponds to the capability to determine the equivalence of two algorithms, which belongs to the class of undecidable problems.

Assume your perfect compiler is possible. Then, you can simply turn it into an equivalence prover. Take algorithm A and algorithm B, compile both and then simply compare the resulting machine code. Since the comparison of the machine code is trivial (and therefore can be implemented), the perfect compiler you describe must be impossible to implement.

Why is the equivalence test impossible to implement? See https://stackoverflow.com/questions/1132051/is-finding-the-equivalence-of-two-functions-undecidable.

2

To a certain degree, yes. Many security sensitive applications like Tor and Bitcoin creates a compilation process that are deterministic build. This build process allows multiple people compiling the same source code to produce the exact bit-to-bit identical build.

The big problem here is determining what is equivalent source code. You can get a long way if you strip the compiled code so that code that you get identical build if you simply rename variables, and do dead code elimination optimisation. You'd then have to avoid non deterministic optimisations, while still doing optimisations that may eliminate superficial differences between different ways people write code (e.g. for-loop vs while-loop). Disabling optimisations that may cause the compiler to produce duplicate codes would also help reduce any chance the compiler producing lots of similar code with just slight differences for optimisations (in gcc, maybe turn on optimise for size). More difficult is deciding whether code that relies on a bunch of if-statements vs code that uses class inheritance to select code path should be considered the same if they behave similarly.

Another aspect that may make such compiler more or less difficult to create is the target machine's instruction set. A register-based target machine like x86 is likely more difficult for this purpose, since you have to select certain registers with the instructions, and the are many functionally equivalent machine code that are different just by their register allocations. A stack based target machine like JVM are likely easier for this purpose as the instruction set always assume that the top of stack are ordered in specific ways, so code that works similarly would be more likely to also end up with similar machine code than register based target language. Note that many compilers actually compiles first to an intermediate language that are based on a stack machine language, before doing optimisations and register allocations.

Ultimately though, what makes this stuff really difficult is defining what are identical is very subjective and there isn't always a right answer. Things like concurrency guarantee, code that are otherwise behave identically in single thread application may behave differently in multi threaded scenario due to differences in sequence points, should they be treated as the same or different code? Or if one code uses bubble sort and the other uses quick sort, should they be considered to be the same or different code? How about code that are only different in the data type they use (e.g. int vs long, single vs double precision floats), should they be considered the same or different code. When you dig down into these issues, there are a lot of worms in this can that makes it non-obvious what should be considered equivalent vs different code.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.