Design by Contract

Nothing astonishes men so much as common sense and plain dealing.

Ralph Waldo Emerson, Essays

Dealing with computer systems is hard. Dealing with people is even harder. But as a species, we've had longer to figure out issues of human interactions. Some of the solutions we've come up with during the last few millennia can be applied to writing software as well. One of the best solutions for ensuring plain dealing is the contract.

A contract defines your rights and responsibilities, as well as those of the other party. In addition, there is an agreement concerning repercussions if either party fails to abide by the contract.

Maybe you have an employment contract that specifies the hours you'll work and the rules of conduct you must follow. In return, the company pays you a salary and other perks. Each party meets its obligations and everyone benefits.

It's an idea used the world over ”both formally and informally ”to help humans interact. Can we use the same concept to help software modules interact? The answer is "yes."

DBC

Bertrand Meyer [Mey97b] developed the concept of Design by Contract for the language Eiffel. ^[1] It is a simple yet powerful technique that focuses on documenting (and agreeing to) the rights and responsibilities of software modules to ensure program correctness. What is a correct program? One that does no more and no less than it claims to do. Documenting and verifying that claim is the heart of Design by Contract (DBC, for short).

^[1] Based in part on earlier work by Dijkstra, Floyd, Hoare, Wirth, and others. For more information on Eiffel itself, see [URL 10] and [URL 11].

Every function and method in a software system does something. Before it starts that something, the routine may have some expectation of the state of the world, and it may be able to make a statement about the state of the world when it concludes. Meyer describes these expectations and claims as follows :

Preconditions. What must be true in order for the routine to be called; the routine's requirements. A routine should never get called when its preconditions would be violated. It is the caller's responsibility to pass good data (see the box on page 115).
Postconditions. What the routine is guaranteed to do; the state of the world when the routine is done. The fact that the routine has a postcondition implies that it will conclude: infinite loops aren't allowed.
Class invariants. A class ensures that this condition is always true from the perspective of a caller. During internal processing of a routine, the invariant may not hold, but by the time the routine exits and control returns to the caller, the invariant must be true. (Note that a class cannot give unrestricted write-access to any data member that participates in the invariant.)

Let's look at the contract for a routine that inserts a data value into a unique, ordered list. In iContract, a preprocessor for Java available from [URL 17], you'd specify it as

 /**       *  @invariant forall Node n in elements()  *  n.prev() != null  *  implies  *  n.value().compare To(n.prev().value()) > 0  */  public class  dbc_list {       /**         *  @pre contains(aNode) == false  *  @post contains(aNode) == true  */  public void  insertNode(  final  Node aNode) {         // ...

Here we are saying that nodes in this list must always be in increasing order. When you insert a new node, it can't exist already, and we guarantee that the node will be found after you have inserted it.

You write these preconditions, postconditions, and invariants in the target programming language, perhaps with some extensions. For example, iContract provides predicate logic operators ” forall, exists, and implies ”in addition to normal Java constructs. Your assertions can query the state of any object that the method can access, but be sure that the query is free from any side effects (see page 124).

DBC and Constant Parameters

Often, a postcondition will use parameters passed into a method to verify correct behavior. But if the routine is allowed to change the parameter that's passed in, you might be able to circumvent the contract. Eiffel doesn't allow this to happen, but Java does. Here, we use the Java keyword final to indicate our intentions that the parameter shouldn't be changed within the method. This isn't foolproof “subclasses are free to redeclare the parameter as non-final. Alternatively, you can use the iContract syntax variable @pre to get the original value of the variable as it existed on entry to the method.

The contract between a routine and any potential caller can thus be read as

If all the routine's preconditions are met by the caller, the routine shall guarantee that all postconditions and invariants will be true when it completes.

If either party fails to live up to the terms of the contract, then a remedy (which was previously agreed to) is invoked ”an exception is raised, or the program terminates, for instance. Whatever happens, make no mistake that failure to live up to the contract is a bug. It is not something that should ever happen, which is why preconditions should not be used to perform things such as user -input validation.

Tip 31

Design with Contracts

In Orthogonality, we recommended writing "shy" code. Here, the emphasis is on "lazy" code: be strict in what you will accept before you begin, and promise as little as possible in return. Remember, if your contract indicates that you'll accept anything and promise the world in return, then you've got a lot of code to write!

Inheritance and polymorphism are the cornerstones of object-oriented languages and an area where contracts can really shine . Suppose you are using inheritance to create an "is-a-kind-of" relationship, where one class "is-a- kind-of " another class. You probably want to adhere to the Liskov Substitution Principle [Lis88]:

Subclasses must be usable through the base class interface without the need for the user to know the difference.

In other words, you want to make sure that the new subtype you have created really "is-a-klnd-of" the base type ”that it supports the same methods, and that the methods have the same meaning. We can do this with contracts. We need to specify a contract only once, in the base class, to have it applied to every future subclass automatically. A subclass may, optionally , accept a wider range of input, or make stronger guarantees . But it must accept at least as much, and guarantee as much, as its parent.

For example, consider the Java base class java.awt.Component. You can treat any visual component in AWT or Swing as a Component, without knowing that the actual subclass is a button, a canvas, a menu, or whatever. Each individual component can provide additional, specific functionality, but it has to provide at least the basic capabilities defined by Component. But there's nothing to prevent you from creating a subtype of Component that provides correctly named methods that do the wrong thing. You can easily create a paint method that doesn't paint, or a setFont method that doesn't set the font. AWT doesn't have contracts to catch the fact that you didn't live up to the agreement.

Without a contract, all the compiler can do is ensure that a subclass conforms to a particular method signature. But if we put a base class contract in place, we can now ensure that any future subclass can't alter the meanings of our methods. For instance, you might want to establish a contract for setFont such as the following, which ensures that the font you set is the font you get:

 /**       *  @pre  f != null  *  @post getFont()  ==  f  */  public void  setFont(  final  Font f) {        // ...

Implementing DBC

The greatest benefit of using DBC may be that it forces the issue of requirements and guarantees to the forefront. Simply enumerating at design time what the input domain range is, what the boundary conditions are, and what the routine promises to deliver ”or, more importantly, what it doesn't promise to deliver ”is a huge leap forward in writing better software. By not stating these things, you are back to programming by coincidence , which is where many projects start, finish, and fail.

In languages that do not support DBC in the code, this might be as far as you can go ”and that's not too bad. DBC is, after all, a design technique. Even without automatic checking, you can put the contract in the code as comments and still get a very real benefit. If nothing else, the commented contracts give you a place to start looking when trouble strikes.

Assertions

While documenting these assumptions is a great start, you can get much greater benefit by having the compiler check your contract for you. You can partially emulate this in some languages by using assertions (see Assertive Programming). Why only partially? Can't you use assertions to do everything DBC can do?

Unfortunately, the answer is no. To begin with, there is no support for propagating assertions down an inheritance hierarchy. This means that if you override a base class method that has a contract, the assertions that implement that contract will not be called correctly (unless you duplicate them manually in the new code). You must remember to call the class invariant (and all base class invariants) manually before you exit every method. The basic problem is that the contract is not automatically enforced.

Also, there is no built-in concept of "old" values; that is, values as they existed at the entry to a method. If you're using assertions to enforce contracts, you must add code to the precondition to save any information you'll want to use in the postcondition. Compare this with iContract, where the postcondition can just reference " Variable @pre," or with Eiffel, which supports "old expression ."

Finally, the runtime system and libraries are not designed to support contracts, so these calls are not checked. This is a big loss, because it is often at the boundary between your code and the libraries it uses that the most problems are detected (see Dead Programs Tell No Lies for a more detailed discussion).

Language Support

Languages that feature built-in support of DBC (such as Eiffel and Sather [URL 12]) check pre- and postconditions automatically in the compiler and runtime system. You get the greatest benefit in this case because all of the code base (libraries, too) must honor their contracts.

But what about more popular languages such as C, C++, and Java? For these languages, there are preprocessors that process contracts embedded in the original source code as special comments. The preprocessor expands these comments to code that verifies the assertions.

For C and C++, you may want to investigate Nana [URL 18]. Nana doesn't handle inheritance, but it does use the debugger at runtime to monitor assertions in a novel way.

For Java, there is iContract [URL 17]. It takes comments (in JavaDoc form) and generates a new source file with the assertion logic included.

Preprocessors aren't as good as a built-in facility. They can be messy to integrate into your project, and other libraries you use won't have contracts. But they can still be very helpful; when a problem is discovered this way ” especially one that you would never have found ”it's almost like magic.

DBC and Crashing Early

DBC fits in nicely with our concept of crashing early (see Dead Programs Tell No Lies). Suppose you have a method that calculates square roots (such as in the Eiffel class DOUBLE ). It needs a precondition that restricts the domain to positive numbers . An Eiffel precondition is declared with the keyword require, and a postcondition is declared with ensure, so you could write

 sqrt: DOUBLE  is  --  Square root routine   require  sqrt_arg_must_be_positive: Current >= 0;            --- ...            ---  calculate square root here  --- ...  ensure  ((Result*Result) - Current).abs <= epsilon*Current.abs;               --  Result should  be  within error tolerance   end;

Who's responsible?

Who is repondible for cheeking the precondition, the caller or the routine being called? when implemented as part of the language, the answer is neither : the routine but before the routine itself is entered. Thus if there is any explicit checking of parameters to be done, it must be performed by the caller, because the routine itself will never see parameters that violate its precondition. (For languages without built-in support, you would need to bracket the called routine with a preamble and/or postamble that checks these assertions.)

Consider a program that reads a number from the console, calculate its square root (by calling sqrt ), and prints the result. The sqrt function has a precondition ”its argument must not be negative. If the user enters a negative number at the console, it is up to the calling code to ensure that it never gets passed to sqrt. This calling code has many options: it could terminate, it could issue a warning and read another number, or it could make the number postive and append an " i " to the result returned by sqrt. Whater its choice, this is definitely not sqrt 's problem.

By expressing the domain of the square root function in the precondition of the sqrt routine, you shift the burden of correctness to the call ”where it belongs. you can then design the sqrt routine secure in the knowledge its input will be in range.

If your algorithm for calculating the square root fails (or isn't within the specified error tolerance), you get an error message and a stack trace to show you the call chain.

If you pass sqrt a negative parameter, the Eiffel runtime prints the error "sqrt_arg_must_be_positive," along with a stack trace. This is better than the alternative in languages such as Java, C, and C++, where passing a negative number to sqrt returns the special value NaN (Not a Number). It may be some time later in the program that you attempt to do some math on NaN, with surprising results.

It's much easier to find and diagnose the problem by crashing early, at the site of the problem.

Other Uses of Invariants

So far we have discussed pre- and postconditions that apply to individual methods and invariants that apply to all methods within a class, but there are other useful ways to use invariants.

Loop Invariants

Getting the boundary conditions right on a nontrMal loop can be problematic . Loops are subject to the banana problem (I know how to spell " banana ," but I don't know when to stop), fencepost errors (not knowing whether to count the fenceposts or the spaces between them), and the ubiquitous "off by one" error [URL 52].

Invariants can help in these situations: a loop invariant is a statement of the eventual goal of a loop, but is generalized so that it is also valid before the loop executes and on each iteration through the loop. You can think of it as a kind of miniature contract. The classic example is a routine that finds the maximum value in an array.

  int  m = arr[0];   //  example assumes arr.length > 0   int  i = 1;     //  Loop invariant: m = max(arr[0:i-1])   while  (i < arr.length) {       m = Math.max(m, arr[i]);       i = i + 1;     }

( arr[m:n] is a notational convenience meaning a slice of the array from index m to n. ) The invariant must be true before the loop runs, and the body of the loop must ensure that it remains true as the loop executes. In this way we know that the invariant also holds when the loop terminates, and therefore that our result is valid. Loop invariants can be coded explicitly as assertions, but they are also useful as design and documentation tools.

Semantic Invariants

You can use semantic invariants to express inviolate requirements, a kind of "philosophical contract."

We once wrote a debit card transaction switch. A major requirement was that the user of a debit card should never have the same transaction applied to their account twice. In other words, no matter what sort of failure mode might happen, the error should be on the side of not processing a transaction rather than processing a duplicate transaction.

This simple law, driven directly from the requirements, proved to be very helpful in sorting out complex error recovery scenarios, and guided the detailed design and implementation in many areas.

Be sure not to confuse requirements that are fixed, inviolate laws with those that are merely policies that might change with a new management regime . That's why we use the term semantic invariants ”it must be central to the very meaning of a thing, and not subject to the whims of policy (which is what more dynamic business rules are for).

When you find a requirement that qualifies, make sure it becomes a well-known part of whatever documentation you are producing ” whether it is a bulleted list in the requirements document that gets signed in triplicate or just a big note on the common whiteboard that everyone sees. Try to state it clearly and unambiguously. For example, in the debit card example, we might write

E RR IN FAVOR OF THE CONSUMER .

This is a clear, concise , unambiguous statement that's applicable in many different areas of the system. It is our contract with all users of the system, our guarantee of behavior.

Dynamic Contracts and Agents

Until now, we have talked about contracts as fixed, immutable specifications. But in the landscape of autonomous agents, this doesn't need to be the case. By the definition of "autonomous," agents are free to reject requests that they do not want to honor. They are free to renegotiate the contract ”"I can't provide that, but if you give me this, then I might provide something else."

Certainly any system that relies on agent technology has a critical dependence on contractual arrangements ”even if they are dynamically generated.

Imagine: with enough components and agents that can negotiate their own contracts among themselves to achieve a goal, we might just solve the software productivity crisis by letting software solve it for us.

But if we can't use contracts by hand, we won't be able to use them automatically. So next time you design a piece of software, design its contract as well.

Related sections include:

Orthogonality
Dead Programs Tell No Lies
Assertive Programming
How to Balance Resources
Decoupling and the Law of Demeter
Temporal Coupling
Programming by Coincidence
Code That's Easy to Test
Pragmatic Teams

Challenges

Points to ponder: If DBC is so powerful, why isn't it used more widely? Is it hard to come up with the contract? Does it make you think about issues you'd rather ignore for now? Does it force you to THINK!? Clearly, this is a dangerous tool!

Exercises

14.	What makes a good contract? Anyone can add preconditions and postconditions, but will they do you any good? Worse yet, will they actually do more harm than good? For the example below and for those in Exercises 15 and 16, decide whether the specified contract is good, bad, or ugly, and explain why. First, let's look at an Eiffel example. Here we have a routine for adding a `STRING` to a doubly linked, circular list (remember that preconditions are labeled with `require,` and postconditions with `ensure` ). -- Add an item to a doubly linked list, -- and return the newly created NODE. add_item (item : STRING) : NODE is require item /= Void -- '/=' is 'not equal'. deferred -- Abstract base class. ensure result.next.previous = result -- Check the newly result.previous.next = result -- added node's links. find_item(item) = result -- Should find it. end
15.	Next, let's try an example in Java ”somewhat similar to the example in Exercise 14. `insertNumber` inserts an integer into an ordered list. Pre-and postconditions are labeled as in iContract (see [URL 17]) . private int data[]; /** * @post data[index-1] < data[index] && * data[index] == aValue / public* Node insertNumber ( final int aValue) { int index = findPlaceToInsert(aValue); ...
16.	Here's a fragment from a stack class in Java. Is this a good contract? /** * @pre anItem != null // Require real data * @post pop() == anItem // Verify that it's * // on the stack / public void* push( final String anItem)
17.	The classic examples of DBC (as in Exercises 14-16) show an implementation of an ADT (Abstract Data Type) ”typically a stack or queue. But not many people really write these kinds of low-level classes. So, for this exercise, design an interface to a kitchen blender. It will eventually be a Web-based, Internet-enabled, CORBA-fied blender , but for now we just need the interface to control it. It has ten speed settings (0 means off). You can't operate it empty, and you can change the speed only one unit at a time (that is, from 0 to 1, and from 1 to 2, not from 0 to 2). Here are the methods. Add appropriate pre- and postconditions and an invariant. int getSpeed() void setSpeed( int x) boolean isFull() void fill() void empty()
18.	How many numbers are in the series 0,5,10,15, , 100?