Tuesday, March 8, 2011

Object-Oriented Contracts

The most basic contract includes preconditions and postconditions for each modular unit (function, subroutine, method, or whatever it is called in a particular programming language).  In object-oriented programming (OOP), there is an additional part of the contract, as well as interesting relationships between contracts in an inheritance hierarchy.

The basis of OOP is the association of operations with data types (or what are often called records in non-OO languages).  Every object has a state, composed of the values of its fields (also called attributes).  Operations on the object (often called methods) can access this state, and some also modify it.  Every object represents some abstraction.  These abstractions can be related to the application domain; for example, "employee", "salary", "student", "loan", or "flight segment".  They can also be internal to the implementation; for example, "set of nodes visited in a graph", "queue of tasks to perform", or "database connection".  It must always be possible to relate every concrete state of an object to the abstract entity it represents.  The representation function takes a concrete state to the abstract object it represents.

In general, however, there may be possible object states that have no associated abstraction.  For example, consider an implementation of a stack that uses an array rep to hold the objects in the stack together with an integer field count that represents the number of elements currently on the stack.  If count is negative, the object represents no abstract object, since there is no stack with a negative number of elements.  The representation function can therefore be partial: it isn't defined for all possible object states.  It is important to give a precise characterization of the domain of the representation function, since this distinguishes meaningful object states from meaningless ones.  If you ever find a meaningless object in your program, you know there's a bug in it.  The characterization of the domain of the representation function as a logical formula is called the representation invariant; the word "invariant" signifies that this is a property that must be true for all objects at all times.

The third part of an object-oriented contract is therefore the class invariant.  A crucial part of the class invariant is the representation invariant, but it can contain other assertions as well.  The class invariant must be true for all objects of the class at all times except while a method of the class is executing.  The last proviso is necessary since a method of the class may update several fields of the object; between the first and last updates, the object may be in an inconsistent state.  This is unavoidable, but causes problems, especially with concurrent programs.  Other problems arise from the fact that the invariant of one object may depend on other objects; for example, if an object that represents an agenda contains a list of items, each item must point back to the same agenda as its owner.  This can be defined as an invariant of the agenda, but operations on the items may invalidate this property.

In simple cases, proving that the class invariant always holds (that is, it is really invariant) is similar to an inductive proof: you need to show that the invariant holds immediately following the construction of the object, and that it is maintained by every operation of the class.  However, because of the problems mentioned above this isn't enough in many cases.  Still, it is a necessary condition, and one that is often easy to check.  Ignore it at your peril!

No comments:

Post a Comment