Search code examples
semantics

Can different program implementations have the same program semantics?

So for any given language, if we implement the same program(i.e same output for any given input) twice, using different syntax (i.e. using i++ instead of i+1) will the two programs have the same semantics? Why? Does the same apply in case where we use different constructs (i.e. Arrays vs Arraylists)?

Thanks

Solution

  • Yes. Depending on the programming language, there can be (combinations of) different syntax constructs with identical semantics.

    For example, we can define a programming language with 3 constructs: A and B, both of which are semantically equivalent, and composition (e.g XY for any X and Y where any of these can either be A, B or any composition thereof). Hence program A is equivalent to program B. Also AA is equal to AB, BA and BB etc.

    Further, if we extend the language with C which is semantically equivalent to AA, then, for example, BC is equivalent to AAA etc.