DRAFT
SemanticEquivalenceImpliesSyntacticEquivalence
Misconception:
If two pieces of code are observationally equivalent, then they must be identical. If one is given a precise and fully detailed specification of observable behavior, then this specification determines every detail of the implementation, and there is only one way to implement that specification.
Incorrect
Two pieces of code with the same observable behavior have to be implemented in the same way
Correct
Two pieces of code with the same observable behavior can be implemented in different ways
CorrectionHere is what's right.
Here is what's right.
NOTE: We need to rename this misconception. The terms “semantic” and “syntactic” are not really used properly here. This is more about ”observational equivalence” vs. some other kind of equivalence.
Assume we ask a student to draw a control-flow graph of a piece of code, so that the code and the graph fully correspond to each other. Sometimes students draw a graph that is observationally equivalent to the code (represents the same end-to-end behavior), but that is not really a representation of the structure of the code.
For example, take the following code snippet:
for (int i=0; i<n; i++) {
if (i==n) {
break;
}
}Students may “optimize away” the if statement when they draw the control flow graph,
i.e., they may draw a graph of the following code:
for (int i=0; i<n; i++) {
}While the two are observationally equivalent, they really represent two programs.
Links
This is related to the so-called “superbug”.
This also has to do with the fact that we don’t define our “notional machines” (i.e., we just draw representations, but never really specify the “languages” we use).
Language
Java