A Refinement Algebra for Object-Oriented Programming

In this article we introduce a comprehensive set of algebraic laws for ROOL, a language similar to sequential Java but with a copy semantics. We present a few laws of commands, but focus on the object-oriented features of the language. We show that this set of laws is complete in the sense that it is sufficient to reduce an arbitrary ROOL program to a normal form expressed in a restricted subset of the ROOL operators. We also propose a law for data refinement that generalises the technique from traditional modules to class hierarchies. Together, these laws are expressive enough to derive more elaborate rules that can be useful, for example, to formalize object-oriented design practices; this is illustrated through the systematic derivation of a refactoring from the proposed laws.