Inputs are contravariant, outputs are covariant and input-outputs are invariant
Sounds erudite but what does it really mean? The concept is not new. Cliff B. Jones talks about it in his book on Vienna Development Method, except not in those words. Although the idea is not restricted to Object Oriented programming it has become better known in recent years (See Meilir Page-Jones “Fundamentals of Object Oriented Design in UML”, Chapter 11)
Let’s go back to model based program design for this discussion. Consider an instance A of a data model S. In model based design S should have an invariant. Any method that modifies A must maintain the invariant relation. As an example, let S denote a sorted vector. By definition, the invariant of a sorted vector is that it is sorted. Now consider the following operations:
- Add an element
- Delete an Element
- Check for existence of an element with a specific value.
Each of these methods must preserve the invariant. In addition, each of these methods must satisfy a post condition. For instance the post condition of Delete will be that A will contain all elements it had before the call to Delete except for the element that must be deleted. If A contains duplicate items then the invariant must be restated to indicate that. Hence the post condition of Delete must state whether it will delete all elements that match a value or a specific one. The precondition can be that the element must exist if that is what is intended. You could extend the precondition and say that non-existent values will be ignored or you could define it as a error condition depending upon the requirements.
Notice we are dealing only with specification here. We are not dealing with implementation just yet. For a simple data model like a sorted vector the implementation can follow the specification exactly. In other cases the specification cannot be translated to an implementation easily. Hence we go through a process of reification.
The above diagram indicates that any input that satisfies the input in the model also satisfies the input in the implementation. Any output from an actual implementation referred to as Real Output in the diagram must satisfy the post-conditions of the specification of the model. Let’s elaborate this a little more.
Computer programs deal with partially defined functions. Consider a function F(S,I,O) where S is a data model, I is the set of inputs and O is the set of outputs. Here S is not the data structure per se. It is a model in that it is defined by the invariants and the set of operations defined on it. For instance S could refer to a stack and an the implementation of stack could be a linked list or a vector or even a hash table.
Consider the implementation Fi of the specification F, or in object oriented terms F is an abstract method that must be implemented. The implementation Fi must satisfy the following requirements:
- It must preserve the invariant of the class or data structure. In other words input-outputs must be invariant
- If the input I satisfies all the pre-conditions in the model then the implementation must accept that input. The implementation can accept a wider range of inputs though. For example if the model indicates that the input must be an integer the actual implementation can accept all numbers. In other words inputs are contravariant.
- The output of the implementation must be at least as strong as that required by the model. If the output is required to satisfy a post condition in the model then the implementation must satisfy that post condition at the very least. It could be more strict but not less strict than the requirement. Thus the set of all actual outputs is less than or equal to the set of all possible outputs. Hence if the model prescribes a base class B as output then the implementation can output an object of type D which is derived from B. In other words outputs are covariant.
If an abstract definition cannot be implemented or it is not worthwhile to implement then the abstraction must be modified until a viable implementation can be found. This is known as reification.
