3 ms·
Come on, you're intentionally and misleadingly nitpicking if you're claiming that the halting problem is a restriction for this. You can trivially detect a larg
by PeterisP 12y ago
Come on, you're intentionally and misleadingly nitpicking if you're claiming that the halting problem is a restriction for this. You can trivially detect a large set of terms that are semantically identical; and all the rest - possibly identical and possibly not identical - can be left alone. "i = i+1;" <=> "i++;" and such.
In particular, "syntactic sugar" explicitly refers to substitutions that can be (and are) made by considering only the local scope, and the rest of the program can't change the validity of this substitution; in the cases for syntactic [de]sugaring all the changes can be performed safely by looking at a statement or two (or their AST representations) in complete isolation.
If you have two functions that happen to be semantically equal but differ in other things than pure sugar - well, then they won't be affected by desugaring or sugaring, obiously, and we don't need to detect if they're actually equal or not.
Translating from source code to AST is clear and unambiguous and doesn't require anything related to the halting problem.
Translating from AST to some canonical representation of source code can also be done - it's not trivial, but if you have the original code, then you can get a better result than the current decompilers do.
This will result in cases where transforming back and forth will cause
A => A' => A
and
B => A' => A
which is the intended result.