Abstract
During software development, it is often necessary to compare the behaviour of several versions of the same programme fragment to ensure that there are no regressions. We have presented two examples: optimisation (performance improvement) through the gradual rewriting of source code, and the development methodology involving successive refinements of a specification. We then informally defined the concepts of equivalence and refinement between programmes, which correspond respectively to equality and inclusion of sets of observable behaviours. These concepts are easy to characterise for simple languages such as arithmetic expressions, but become increasingly complex when language features such as functions, lazy evaluation, higher-order functions, non-determinism, type abstraction, and functions and objects with internal mutable state are introduced.
We then defined observational equivalence—also known as Morris’s contextual equivalence—by drawing an analogy with exhaustive test suites. Owing to its very general definition and its sound mathematical properties, this equivalence is regarded as the ‘gold standard’ of programme equivalences. However, it is very difficult to prove directly, which explains why other techniques for proving equivalence or refinement are necessary. We mentioned four such techniques: denotational semantics, bisimulations, logical relations and relational logics, which will be studied in the following sessions of the course.