Compile time checking in Design by Contract?

Question

I read that compiler can enforce dbc at compile time.. How does it do it?

Answer 1

Which compiler and what language? Eiffel can do it to some extent. But remember that completely enforcing design-by-contract would mean being able to solve the Halting Problem (proof: assume you have a compiler that could do it. Then the compiler would have to be able to identify an arbitrary function with a true exit condition that can't achieve the exit condition because of an infinite loop or infinite recursion. Thus it reduces to halting.)

What is usually meant by this is that if you have a call

  foo(a);

and somewhere else define

  function foo(a:int) is
     assert 0 < a && a < 128
     ...
  end

then the compiler can check that a is, in fact, going to be in the open interval (0..128).

Answer 2

The compiler can use static analysis to look at your program and determine whether it does the right thing. As a simple example, the following code might try to take the square root of a negative number (C++):

double x;
cin >> x;
cout << sqrt(x) << endl;

If the compiler knows that sqrt should never be called with a negative number, it could flag this as a problem because it knows that reading from user input could return a negative number. On the other hand, if you do this:

double x;
cin >> x;
if (x >= 0) {
    cout << sqrt(x) << endl;
} else {
    cout << "Can't take square root of negative number" << endl;
}

then the compiler can tell that this code won't ever call sqrt with a negative number.

Answer 3

Design by Contract is a very abstract term, since there can be many specification formalisms with different powers of expression. In addition, there is at present a limit to the abilities of static analysis to check and enforce specifications. It's one of the most active academic and industrial research fields in computer science.

In practice, it is likely that you will use some subset of contracts and checking, and that depends on the language that you are using and on the plugins or programs you install.

In general, static analysis tries to build a model of the contract, and a model of the actual program, and compare them. For example, if the contract doesn't let you invoke a function when an object is in state S, it will try to determine whether in any invocation sequence you could end up in state S.

Answer 4

Some languages like D have reasonably powerful compile time constant folding and compile time condition checking (for D static assert(boolCond, msg);, IIRC C/C++ can use #if and pragma or #error)

Answer 5

As far as I know, the most powerful static DbC language so far is Spec# by Microsoft Research. It uses a powerful static analysis tool called Boogie which in turn uses a powerful Theorem Prover / Constraint Solver called Z3 to prove either the fulfillment or violation of contracts at design time.

If the Theorem Prover can prove that a contract will always be violated, that's a compile error. If the Theorem Prover can prove that a contract will never be violated, that's an optimization: the contract checks are removed from the final DLL.

As Charlie Martin points out, proving contracts in general is equivalent to solving the Halting Problem and thus not possible. So, there will be a lot of cases, where the Theorem Prover can neither prove nor disprove the contract. In that case, a runtime check is emitted, just like in other, less powerful contract systems.

Please note that Spec# is no longer being developed. The contract engine has been extracted into a library, called Code Contracts for .NET, which will be a part of .NET 4.0 / Visual Studio 2010. However, there will be no language support for contracts.