CSC/ECE 517 Fall 2011/ch6 6a pc

6a (was 5c). Lecture 18, Programming by contract. My notes for Lecture 18 are largely taken from 20-year-old articles by Bertrand Meyer. The principles are timeless, but there are undoubtedly new embellishments that would provide better background to the topics discussed in the lecture. Write a narrative, generally following the lecture organization, that explains programming by contract in more detail.

Terminology

Preconditions

A precondition is a condition that must be true prior to calling a method for which it is defined. Preconditions bind the caller of that method, that is, it is the responsibility of the caller to ensure that the preconditions are satisfied. The method is not responsible, nor expected, to check the preconditions. The output from the method is not defined for the case where the preconditions are violated. In that case the method could crash the system, go into an infinite loop, or do nothing at all.

The require block constitutes a precondition in the Eiffel programming language.

set_hour (a_hour: INTEGER)
            -- Set `hour' to `a_hour'
        require
            valid_argument: 0 <= a_hour and a_hour <= are23
        do
            hour := a_hour
        ensure
            hour_set: hour = a_hour
        end

Postconditions

A postcondition is a condition that must be true after execution of the method for which it is defined. Postconditions bind the method itself. The method is responsible for ensuring that these conditions are met. The caller of the method is guaranteed that the postconditions will hold if the original preconditions were satisfied when calling the method.

The ensure block constitutes a postcondition in Eiffel.

set_hour (a_hour: INTEGER)
            -- Set `hour' to `a_hour'
        require
            valid_argument: 0 <= a_hour and a_hour <= 23
        do
            hour := a_hour
        ensure
            hour_set: hour = a_hour
        end

Invariants

A class invariant is a condition that must hold true throughout the lifetime of an object. It is a condition imposed on the class itself rather than a method of that class. Class invariants are often checked before and after the execution of each method in that class. An object found in a state where the invariant does not hold, would indicate a bug in the system.

An example of a class invariant: A linked list has an instance variable length that stores the number of nodes in the list. length should always equal the actual number of nodes in the list.

class LinkedList {
    private Node head;
    private int length;  // length stores a cached version of the number of nodes. It should always equal the actual number of nodes.
    
    public LinkedList() {
        head = null;
        length = 0;
    }

    public getLength() {
        return length;
    }

    public void Add(int value) {
        Node n = new Node(value);

        if(head == null) {
            head = n;
        }
        else {
            Node current = head;

            while(current.getNext() != null) {
                current = current.getNext();
            }
            current.setNext(n);
            n.setPrevious(current);
        }
        length++;
    }

    /* other methods omitted */
}

Along with Preconditions and Postconditions, class invariants provide another means to write good code. Class invariants come to the fore when we look at guidelines for writing methods. We typically have two types of methods : accessors, that simply retrieve a value and modifiers, that modify the object on which they are called. There is an important guideline for modifier methods to observe if they are to do their jobs well: "Public methods should always keep objects in a well-formed state.".

Here, well-formed state seems like a very subjective term. A good way to specify what makes objects of a class well-formed is to list the class invariants. A class invariant is a statement about the state of objects of the class between public method calls.

Following example illustrates the usage and importance of class invariants. For the LinkedList class (refer to the Terminlogy section) following could be the class invariants:

1. The value of instance variable _length (underscore prefixed to indicate that this is a private instance variable) is always equal to the number of elements on the list.
2. The next instance variable of the last node on the list must have null or some other special placeholder object as its value.

With the first invariant, it is clear that we have to initialize _length to 0 in the constructor and update it appropriately in add and remove methods. This will prevent any bugs from creeping into the code and in case they did, debugging becomes much simpler. Similarly the second invariant makes sure that the linked list is well terminated. Otherwise a user traversing the list could end up writing at illegal memory location. Hence class invariants are valuable tools in writing good code.

How do we identify class invariants?

Since class invariants describe the state of an object between method calls, one easy way to identify them is to look at the instance variables of the class, since instance variables hold the state of an object. This has an implication that, many instance variables can lead to many Invariants and hence make it hard to debug. One should look at the trade-off between performance and the number of class invariants when deciding on adding instance variables. For instance, in the LinkedList example, not having _length instance variable would help us reduce the number of invariants, but this would mean that user will have to traverse the list each time he needs to count the number of items on the list.

Assertions

It is useful to check preconditions, postconditions, and invariants when debugging code. A violation of which constitutes a bug in the system. This can be accomplished using an assert statement in Java or Contract.Requires statement in C# 4.0. These programming features can be used to alert the programmer of bugs in development and can be turned off in production.

Software Reliability

A major concern in software design is Reliability, which depends on two factors: 1) Correctness - system's ability to perform its job according to the specification and 2) Robustness - handling abnormal conditions. Reliability is especially important in Object oriented software because of the additional complexity imposed by Reusability. Some of the common problems encountered when writing software include:

• System failure - CPU crash, Disk/Memory access errors, Network errors
• Invalid input data - Out of range data, Bad file name,etc.
• Programming errors - Memory leaks, Buffer overruns, etc.

There are many programming language features that help tackle these issues. Static typing, for example, is a major help for catching inconsistencies before they have had time to become bugs. Similarly Garbage collection helps to remove the specter of devious memory management errors. Various software design methodologies also come handy when dealing with complex software. For instance, reusability itself can help eliminate lots of bugs, if we are reusing existing code that has already been thoroughly tested and deployed. Polymorphism also helps in handling issues related to maintainability by reducing the size of the code and making it more elegant. But in a large and complex software involving multiple developers, we need a more systematic approach of specifying and implementing object-oriented software elements and their interactions. This is exactly what "Programming by contract" promises to do.

Programming by contract

Basically programming by contract creates a contract between the software developer and software user, which are referred to as the supplier and the consumer. Every feature, or method, starts with a precondition that must be satisfied by the consumer of the routine. And each feature ends with postconditions which the supplier guarantees to be true after it is executed(if and only if the preconditions were met). Consider the following example of a static Intersect() method on a Set object (Quoted from Skrien 4.6):

public static Set intersect(Set s1, Set s2)
  Precondition: s1 and s2 are not null.
  Postcondition: 
    Returns a Set with the common elements of s1 and s2, if s1 and s2 are not null.
    If s1 or s2 is null, an IllegalArgumentException is thrown.

Note here that this documentation is not overly specific about the implementation nor is it very general and vague. This can be stated concisely as a guideline: "The external documentation for a method should be sufficiently specific to exclude implementations that are unacceptable but sufficiently general to allow all implementations that are acceptable". are

Also, the above contract does not mention anything about the behavior of the method when preconditions are not satisfied. This is Meyer’s non-redundancy principle: "Under no circumstances shall the body of a routine ever test for the routine’s precondition". This implies that if the preconditions are not met, the behavior of the method is undefined (it could crash, throw an exception, or run in an infinite loop, etc.).

(Does it fit here?) In essence, this theory suggests associating a specification with every software element. These specifications (or contracts) govern the interaction of the element with the rest of the world. This is different from having a formal specification in that the specification language is embedded in the design and programming language (e.g. Eiffel). This makes it possible to use a single notation and a single set of concepts throughout the software life cycle, and since these are modeled based on the programming language itself, it provides a great deal of clarity about the requirements at each stage of software development.

Contract and Inheritance

An important implication of Programming by Contract is when Inheritance and polymorphism are involved. Subtype polymorphism means: "If S is a subtype of T,then any term of type S can be safely used in a context where a term of type T is expected". In case of object oriented programming, type is defined by a class and inheritance enables us to define subtypes of a class (If Base class defines a type, the Derived class becomes a subtype). In this situation, the Derived class should fully honor the Base class contract. Consider the following example:

Suppose you are given a class List, that has a public interface: insert(Item const& x) . And suppose you have to implement a new class SortedList, and provide insert method with the same signature. Isn't is obvious that SortedList be made a subclass of List and override the insert() method?. The answer is no!.

To decide whether we can override the List::insert() method, we will have to look at the Contract promised by this method. Suppose the base class insert() method has advertised its contract as "Promises a copy of Item will be inserted somewhere within this List". In this case the derived class can override this, since this is a weak post-condition which can be strengthened in the derived class. So the derived class insert() can say that "Promises a copy of Item will be inserted in the sorted order within this List" and no contract is broken.

Suppose, instead the Base class method has a strong post condition: "Promises a copy of Item will be inserted at the end of this List". Then the derived class cannot override this, since derived class cannot guarantee that the Item will be inserted at the end, hence a breach of Contract.

So why bother with all this Contract business?

Consider in the above example (strong post-condition case), suppose the derived class breaches the contract and overrides insert() anyway. Now a user who was using the List::insert() method assumes that the items are added at the end, i.e sorted based on time of insertion. But suppose he accidentally calls SortedList::insert() through the base class List pointer, then the Item would be inserted somewhere in-between based on the value it contains, rather than the time of insertion. This will surely introduce hard-to-find bugs in the code, which is the problem this principle was designed to solve. Liskov's substitution principle that deals with the Base-Derived relationship can be rephrased based on this understanding:

It is acceptable to subclass B from a class A, if for every public method with identical signatures in A and B,

1. Pre-conditions for B's method are no stronger than preconditions for A's method
2. Post-conditions for B's method are no weaker than postconditions for A's method

Comparison with Defensive Programming

Restating the crux of "Programming by contract": "The supplier class guarantees postconditions of its methods as long as client guarantees that preconditions of those methods are met". This implies that if the client fails to satisfy the preconditions, the behavior of supplier is undefined, meaning it could result in an Exception being thrown, or a system crash.

Defensive programming on the other hand, augments this guideline as - "Try to make your methods do something appropriate in all cases so that there are no preconditions". You know errors are almost certainly going to occur and illegal input is going to be given to methods, so make sure that your methods can defend against such input by doing something explicit in a way that is helpful to the user of those methods.

However, this approach could introduce major performance hit. For instance, consider a method that performs binary search on an integer array. A precondition for such a method is that the array is sorted. To eliminate this precondition, the binary search method could first check the array to see if it is sorted and, if not, throw an exception. However, in that case the method’s efficiency is reduced from O(log n) to O(n), where n is the array size.

When not to use Programming by Contract

Asserts and "by contract" specifications catch programmer errors not run-time errors! (Add more details)