Perhaps the most subtle relationship in object-oriented programming is that of inheritance. Many object-oriented languages, including Java, distinguish between classes and interfaces, as a reaction to the problems languages such as C++ faced with multiple inheritance. This is a complex issue I will address in a later post. Now I want to focus on the logical relationships involved in inheritance. In order to avoid the class/interface dichotomy, I will use the notion of a subtype. A type A is a subtype of B if it inherits from it, whether both A and B are classes, both are interfaces, or A is a class and B is an interface. (Java uses the verb "extends" for the first two cases and "implements" for the third.)
An element of a subtype A may be used whenever an element of the supertype B is indicated. For example, suppose we have a type called Set that represents mathematical sets. It has a number of implementations inheriting from it, including ArraySet, which holds the elements of the set in an array, and HashSet, which holds the elements in a hash table. The Set type has various methods, including add(Object x), which adds an element to the set; get(), which returns an arbitrary element of the set; and has(Object x), which returns true if and only if x is in the set. Since a set can't contain the same object multiple times, we put a precondition on add(Object x) requiring that x is not already in the set: !has(x).
Unfortunately, our HashSet implementation doesn't support null as an element in the hash table, so we add another precondition to add(Object x), stating that x can't be null: x != null. Now, suppose we have a client C that uses our code, and receives a parameter s of type Set. When the programmer of the client code reads the contract for Set, he sees only one precondition: !has(x). He will certainly be careful not to insert the same element twice, for example by using the following code:
if (!s.has(element)) s.add(element);
But he has perfect confidence in the following piece of code:
if (!s.has(null)) s.add(null);
He will be rudely surprised, therefore, when this actually bombs on him somewhere inside the call to add in our HashSet implementation. He may not even have known about the existence of HashSet, since he received the object s, which happened to have this type, as a parameter. He is the proverbial innocent bystander, and should be protected from this kind of problem. After all, he kept his side of the contract, and has every right to expect us to keep our side!
This demonstrates a general problem, which will manifest itself whenever the precondition of a method in a subtype is stronger (that is, requires more) than that of the supertype. The rule must therefore be that subtypes are not allowed to strengthen method preconditions. We will have to add a precondition to Set.add, to warn potential users that some subtypes may not accept null as a parameter. Our ArraySet implementation can now weaken the precondition by removing this requirement. This is perfectly legal; clients that use ArraySet objects through the Set supertype will not be allowed to call add(null), but clients that use ArraySet directly will be able to enjoy the extended functionality.
Since we restrict Set.add not to accept null parameters, it looks like we can now put a postcondition on Set.get, stating that it will never return null. This will work well for HashSet, but will fail for ArraySet, which does accept null elements. By adding this postcondition to Set.get, we have again harmed innocent bystanders; in this case, a client of Set who happens to receive a HashSet object as its own parameter. Such a client feels perfectly justified in writing the following code:
if (!s.isEmpty()) System.out.println(s.get().toString());
He is careful to check the precondition of get, which states that it can't be called when the set is empty, and he is therefore entitled to rely on get's postcondition and to expect that no NullPointerException will be raised on the call to toString. He may not even be aware of the existence of ArraySet, and of the fact that it doesn't have this postcondition. The rule for postconditions therefore must be that postconditions must not be weakened by subtypes, although they can be strengthened; this enables clients of the subtype to benefit from extra features it supports.
These rules are consequences of Liskov's Behavioral Substitution Principle, which states that properties of the supertype must still be true of subtypes. This principle is true of all inheritance hierarchies which allow subtypes to be used as elements of their supertypes. After all, this is what a subtype means: if A is a subtype of B then every instance of A is, by definition, also an instance of B. (This does not apply to private inheritance in C++, which doesn't imply a subtype relationship, but it does apply to public inheritance in C++, as well as to all inheritance relationships in Java, C#, and similar languages.) The principle is true whether or not the developer uses design by contract, and writes contracts explicilty; a violation of the principle is still a bug, and a nasty one at that. Using design by contract makes it easier to prevent such violations in the first place.
Any developer who is ignorant of Liskov's Behavioral Substitution Principle can't claim to understand object-oriented programming, and should be prevented from writing any kind of inheritance relationship!
Friday, April 1, 2011
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!
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!
Thursday, March 3, 2011
What's in a Contract
The term "design by contract" is due to Bertrand Meyer, and is at the heart of his Eiffel language. But the concept of using assertions to specify the behavior of small units of software (such as function calls) is much older, and not specific to the object-oriented paradigm. Hoare logic, which I mentioned previously, consists of triples specifying program fragments with their preconditions and postconditions. With objects, and especially with inheritance, come new features, but I want to start with simpler languages.
At the most basic level, the contract of a software unit (which I will refer to as a function) consists of a precondition and a postcondition. The precondition is an assertion that must hold on entry to the function, and the postcondition must hold on exit. Obviously, it is the caller's responsibility to ensure that the precondition is satisfied before making the call. If that is not the case, then the function is under no obligation whatsoever; it may enter an infinite loop, return the wrong result, or blow up the computer. In particular, it is not obliged to satisfy the postcondition. However, if the precondition was true on entry, it is the supplier's responsibility to ensure that the computation of the function terminates, and that the postcondition holds on exit.
This scheme separates responsibilities very precisely between the client and supplier of the function, and enables modular reasoning. As a simple example, suppose you need to use the sine function, and discover that the implementation you have has a precondition that the angle is between 0 and 90 degrees. If the angle you want to compute the sine for happens to be in that range, you can go ahead and use the existing function. If not, you can use elementary trigonometry to convert your angle to one that is between 0 and 90 degrees and has the same sine value, possibly with a different sign; in that case, you have to invert the sign yourself. Of course, implementations of this function you are likely to encounter are able to compute the sine for any angle, and have no precondition. It is, of course, crucial to know the difference between functions that have this precondition and those that don't. If you call the former without being aware of the precondition, you are likely to get wrong results, which may or may not be easy to detect.
As another example, suppose you have a point (x, y) in the plain and you want to know the angle a line from the origin to (x, y) has with the positive direction of the x axis. Mathematically, this is arctan(y/x). However, the arctan function has a range of only 180 degrees; any implementation has to choose which range of values it will return. Typical values might be –90 to 90 degrees, or 0 to 180. This will be the correct angle only for two out of four quadrants in which the point (x, y) lies, and so you will need to convert the result to the proper quadrant based on the signs of x and y. Here, you must know the postcondition of the arctan function, which will tell you what is the range of possible results.
If you have contracts for your function and those that it calls, you can now think of verifying that your implementation is correct. You need to do is prove that your function fulfills its own contract, but instead of the proof having to involve all functions you call, and everything they call further down the chain, you only need to consider the contracts of called functions. This is not necessarily easy, but it is much easier than having to consider all called code, which can be very large. One thing you will still need to provide are loop invariants and variants for any loop in your own code. (In Eiffel, these are part of the language, although they are not considered part of the contract.)
This leads to a modular proof style, in which each function can be verified separately. Of course, you can only do full verification if contracts are complete specification. But even if they aren't, you may still be able to prove important properties of your code. Without contracts, this is a formidable task, which is very rarely even attempted. It's a pity that many programmers are not aware of this possibility.
At the most basic level, the contract of a software unit (which I will refer to as a function) consists of a precondition and a postcondition. The precondition is an assertion that must hold on entry to the function, and the postcondition must hold on exit. Obviously, it is the caller's responsibility to ensure that the precondition is satisfied before making the call. If that is not the case, then the function is under no obligation whatsoever; it may enter an infinite loop, return the wrong result, or blow up the computer. In particular, it is not obliged to satisfy the postcondition. However, if the precondition was true on entry, it is the supplier's responsibility to ensure that the computation of the function terminates, and that the postcondition holds on exit.
This scheme separates responsibilities very precisely between the client and supplier of the function, and enables modular reasoning. As a simple example, suppose you need to use the sine function, and discover that the implementation you have has a precondition that the angle is between 0 and 90 degrees. If the angle you want to compute the sine for happens to be in that range, you can go ahead and use the existing function. If not, you can use elementary trigonometry to convert your angle to one that is between 0 and 90 degrees and has the same sine value, possibly with a different sign; in that case, you have to invert the sign yourself. Of course, implementations of this function you are likely to encounter are able to compute the sine for any angle, and have no precondition. It is, of course, crucial to know the difference between functions that have this precondition and those that don't. If you call the former without being aware of the precondition, you are likely to get wrong results, which may or may not be easy to detect.
As another example, suppose you have a point (x, y) in the plain and you want to know the angle a line from the origin to (x, y) has with the positive direction of the x axis. Mathematically, this is arctan(y/x). However, the arctan function has a range of only 180 degrees; any implementation has to choose which range of values it will return. Typical values might be –90 to 90 degrees, or 0 to 180. This will be the correct angle only for two out of four quadrants in which the point (x, y) lies, and so you will need to convert the result to the proper quadrant based on the signs of x and y. Here, you must know the postcondition of the arctan function, which will tell you what is the range of possible results.
If you have contracts for your function and those that it calls, you can now think of verifying that your implementation is correct. You need to do is prove that your function fulfills its own contract, but instead of the proof having to involve all functions you call, and everything they call further down the chain, you only need to consider the contracts of called functions. This is not necessarily easy, but it is much easier than having to consider all called code, which can be very large. One thing you will still need to provide are loop invariants and variants for any loop in your own code. (In Eiffel, these are part of the language, although they are not considered part of the contract.)
This leads to a modular proof style, in which each function can be verified separately. Of course, you can only do full verification if contracts are complete specification. But even if they aren't, you may still be able to prove important properties of your code. Without contracts, this is a formidable task, which is very rarely even attempted. It's a pity that many programmers are not aware of this possibility.
Saturday, February 26, 2011
Design by Contract
As I mentioned before, the state of the art in logics of programs isn't yet capable of verifying large-scale programs, even with the best theorem provers currently available. As a result, the vast majority of programmers don't use any formal methods during software development, and the term "verification and validation" refers mainly to testing. What many people don't realize is that there is a middle way in using formal methods; it is possible to improve software quality by using limited but effective parts of the theory.
Design by Contract is a method of using assertions in object-oriented programs to specify their behavior. This importance of this specification is first and foremost methodological. The mere fact of writing these specifications and having them available in libraries focuses programmer attention to the correct use of program interfaces. Many errors stem from misunderstandings; a simple but common example is when the writer of a method assumes that a certain parameter may not be null, and omitting to check or handle the case of a null pointer, while the client of the method assumes that the method does something reasonable when given a null value. The contract defines precisely the responsibilities of the client and supplier; in particular, if the method doesn't handle null pointers, it must declare that fact in its contract. This contract is a formal part of the interface, and (unlike the source code) must be available to all programmers who use the method. They, in turn, must look at the contract and behave according to their responsibilities in it.
This simple process of writing the contract for suppliers and consulting it when writing clients can prevent many errors before they are even made. In order for this to work, the contract doesn't even need to be completely formal, as long as it is precise. And it has to be simple enough to be easily understood, otherwise it is worthless and may even cause damage. However, if developers take the trouble of writing formal contracts, they can be rewarded by more than methodological advantages. Indeed, if contracts are written using a formal notation, it is possible to create tools that give additional benefits.
First, it is possible (though by no means trivial) to write tools that check the contract at runtime. Many errors are time bombs waiting to happen. For example, storing a null value in a field of an object may by itself cause no harm. Only later, when the field is accessed under the assumption that it can't contain null, does the software present an error (in Java, it would be a NullPointerException, nicknamed NPE). The process of finding where in the program the original null value was assigned can be difficult and time consuming. A debugger is a useful tool, but it takes skill and time to use it to track such errors, because in many cases the method call that assigned the null value has already completed its execution and is no longer available on the stack to be examined by the debugger. A tool that checks contracts at runtime would alert the developer to the problem much earlier, thus speeding both discovery and fix of the problem.
Contracts also enable some level of verification. Instead of having to prove that the program as a whole has some desired properties, the method and class contracts provide "stepping stones" to a (partial) proof of correctness. If we can prove that all calls in the program satisfy the method of the called method, we will have increased our confidence in the correctness of the program. Because proving such properties is much easier than proving correctness of a whole program, tools such as theorem provers can be more effective there. While there aren't yet any commercial tools that do that, there is a lot of research on this topic, and I expect the benefits of automated theorem provers to become practical first in this limited arena.
One of the important advantages of design by contract is that it provides incremental benefits. Programmers can get immediate benefit from simple contracts, such as those having to do with null pointers. By adding more details to the contract, they can get more benefit. It isn't necessary (or even useful) to attempt a full specification in order to use this methodology.
Purists may scoff and say that this is not what logicians mean by verification, and is no better than testing. I would agree with the first part of this statement, but not with the second. Contracts are complementary to testing, and both are necessary. (I will have more to say about this in the future.) If you insist in full verification, meaning proofs of complete correctness, you will not bring practical value to software development for a very long time. Design by contract is a practical and useful methodology that should be employed by every software developer. I will discuss some of the reasons why this is not yet the case in a future post.
Design by Contract is a method of using assertions in object-oriented programs to specify their behavior. This importance of this specification is first and foremost methodological. The mere fact of writing these specifications and having them available in libraries focuses programmer attention to the correct use of program interfaces. Many errors stem from misunderstandings; a simple but common example is when the writer of a method assumes that a certain parameter may not be null, and omitting to check or handle the case of a null pointer, while the client of the method assumes that the method does something reasonable when given a null value. The contract defines precisely the responsibilities of the client and supplier; in particular, if the method doesn't handle null pointers, it must declare that fact in its contract. This contract is a formal part of the interface, and (unlike the source code) must be available to all programmers who use the method. They, in turn, must look at the contract and behave according to their responsibilities in it.
This simple process of writing the contract for suppliers and consulting it when writing clients can prevent many errors before they are even made. In order for this to work, the contract doesn't even need to be completely formal, as long as it is precise. And it has to be simple enough to be easily understood, otherwise it is worthless and may even cause damage. However, if developers take the trouble of writing formal contracts, they can be rewarded by more than methodological advantages. Indeed, if contracts are written using a formal notation, it is possible to create tools that give additional benefits.
First, it is possible (though by no means trivial) to write tools that check the contract at runtime. Many errors are time bombs waiting to happen. For example, storing a null value in a field of an object may by itself cause no harm. Only later, when the field is accessed under the assumption that it can't contain null, does the software present an error (in Java, it would be a NullPointerException, nicknamed NPE). The process of finding where in the program the original null value was assigned can be difficult and time consuming. A debugger is a useful tool, but it takes skill and time to use it to track such errors, because in many cases the method call that assigned the null value has already completed its execution and is no longer available on the stack to be examined by the debugger. A tool that checks contracts at runtime would alert the developer to the problem much earlier, thus speeding both discovery and fix of the problem.
Contracts also enable some level of verification. Instead of having to prove that the program as a whole has some desired properties, the method and class contracts provide "stepping stones" to a (partial) proof of correctness. If we can prove that all calls in the program satisfy the method of the called method, we will have increased our confidence in the correctness of the program. Because proving such properties is much easier than proving correctness of a whole program, tools such as theorem provers can be more effective there. While there aren't yet any commercial tools that do that, there is a lot of research on this topic, and I expect the benefits of automated theorem provers to become practical first in this limited arena.
One of the important advantages of design by contract is that it provides incremental benefits. Programmers can get immediate benefit from simple contracts, such as those having to do with null pointers. By adding more details to the contract, they can get more benefit. It isn't necessary (or even useful) to attempt a full specification in order to use this methodology.
Purists may scoff and say that this is not what logicians mean by verification, and is no better than testing. I would agree with the first part of this statement, but not with the second. Contracts are complementary to testing, and both are necessary. (I will have more to say about this in the future.) If you insist in full verification, meaning proofs of complete correctness, you will not bring practical value to software development for a very long time. Design by contract is a practical and useful methodology that should be employed by every software developer. I will discuss some of the reasons why this is not yet the case in a future post.
Thursday, February 24, 2011
Logics of Programs
From the early days of computers, it was obvious that programming is difficult and error-prone. The mathematical nature of computer programs leads to the obvious thought that the same methods used to make sure that mathematical theorems are correct can help ensure that programs are correct. This has led to a lot of research on logics for computer programs. There are many abstractions of programs, and correspondingly many logics that deal with them.
At the simplest level, it is possible to think of a program as being executed sequentially, instruction by instruction. This is almost never true; even the simplest processors typically interrupt the sequential flow to handle external events, such as pressing a key on a keyboard or control panel connected to the computer. However, if we trust the operating system to make a clean separation between such interrupt handlers and the running application, then it is possible to think at a higher level of abstraction of some applications as running sequentially. But many application are concurrent by nature, and these are the most difficult to get right. There are many examples of small programs with two parallel components that have subtle and hard-to-find bugs in them, and parallel or concurrent systems are notoriously hard to program.
Even the simple sequential model requires special mathematical treatment, because it has to represent the changing state of the computer. Every operation in a program changes the state of the machine in some way; otherwise, there would be no point in executing it. There are many types of changes: first, the location of the next instruction (the "program counter") changes, either to the next instruction in the sequence, or to a different place for instructions that change the flow of control. Some instructions change the contents of memory, registers, or various control bits (for example, one that records whether the previous comparison resulted in a zero value). High-level languages hide some of these details, but most (with the notable exception of functional and logic languages) still have the notion of changing state.
A logical model of programs with changing state must represent this state explicitly. If x is a variable in a program, the formula x=3 is meaningless with respect to a program, because it may true or false in different states of the computation of the same program. The logical model must have an explicit representation of states, and some syntactic way of referring to different states. One of the best known formalisms is called Hoare logic, after C. A. R. Hoare, Turing prize winner and famous, among other things, as the inventor of the quicksort algorithm.
Every formula in this logic is a Hoare triple of the form {P}A{Q}, where A is a (possibly partial) program and P and Q are logical statements about the variables of the program. This formula asserts that if P holds in the state just prior to the computation of A, and if this computation terminates, then Q will be true in the resulting state. For example, a (somewhat simplified) way of describing the effect of an assignment x := e in a program is by the formula {e = c} x := e {x = c}, where c is a constant. (Note the crucial difference between logical equality and assignment, so unfortunately blurred by languages from Fortran to Java that use "=" for assignment.) This formula asserts that if the value of the expression e in the state preceding the assignment is c, than the value of x after the assignment is also c.
As another example, consider how to prove that a certain formula holds for a conditional: {P} if C then A else B {Q}. If the condition C is true in the state before the computation, then the conditional will choose the subprogram A. In order for the desired formula to hold, it must be the case that if P and C are true before the computation, Q must be true afterwards (provided, as always, that the computation terminates). Formally, {P and C} A {Q} must be true. Similarly, {P and not C} B {Q} must hold to guarantee the desired result in the case where the condition C is initially false. And indeed, the desired formula follows from the latter two in Hoare logic.
As is the case for most logics of programs, the difficulty lies in reasoning about loops (and recursion). In order to prove a property of a loop using these logics, it is necessary to come up with a loop invariant. This is a property that always holds at the beginning of each iteration. In order to prove a property P following the loop, you prove that the invariant holds on entry to the loop, that it sustains itself across one iteration, and that if you exit the loop with the invariant holding, P must be true at that point.
This is very similar to a proof by induction; the first step is the base of the induction, and the second is the inductive step, in which you prove that if the invariant holds in the beginning of one iteration, it also holds on the beginning of the next one. As is the case with inductive proofs, coming up with a suitable invariant is difficult. Much of the work of automatic theorem provers (for mathematics as well as for logics of programs) is discovering the induction hypotheses or, equivalently, the loop invariants. (In fact, in one of my favorite theorem provers, ACL2, these are exactly the same.)
This kind of reasoning is very low-level, and it is impossible to use it to prove the correctness of a large program manually. Automated theorem provers are a great help, but the process is still difficult and time-consuming, and requires high skills in logic and the specific theorem prover. It is therefore limited to relatively small but safety-critical programs. Wide application of automatic theorem proving to large-scale programs seems to be far in the future. As a result, there is a chasm between the people developing logics of programs and associated theorem provers, and the general population of software developers, most of whom are not even aware of the existence of these methods and tools. But there is a middle way; I will discuss it in the next post.
At the simplest level, it is possible to think of a program as being executed sequentially, instruction by instruction. This is almost never true; even the simplest processors typically interrupt the sequential flow to handle external events, such as pressing a key on a keyboard or control panel connected to the computer. However, if we trust the operating system to make a clean separation between such interrupt handlers and the running application, then it is possible to think at a higher level of abstraction of some applications as running sequentially. But many application are concurrent by nature, and these are the most difficult to get right. There are many examples of small programs with two parallel components that have subtle and hard-to-find bugs in them, and parallel or concurrent systems are notoriously hard to program.
Even the simple sequential model requires special mathematical treatment, because it has to represent the changing state of the computer. Every operation in a program changes the state of the machine in some way; otherwise, there would be no point in executing it. There are many types of changes: first, the location of the next instruction (the "program counter") changes, either to the next instruction in the sequence, or to a different place for instructions that change the flow of control. Some instructions change the contents of memory, registers, or various control bits (for example, one that records whether the previous comparison resulted in a zero value). High-level languages hide some of these details, but most (with the notable exception of functional and logic languages) still have the notion of changing state.
A logical model of programs with changing state must represent this state explicitly. If x is a variable in a program, the formula x=3 is meaningless with respect to a program, because it may true or false in different states of the computation of the same program. The logical model must have an explicit representation of states, and some syntactic way of referring to different states. One of the best known formalisms is called Hoare logic, after C. A. R. Hoare, Turing prize winner and famous, among other things, as the inventor of the quicksort algorithm.
Every formula in this logic is a Hoare triple of the form {P}A{Q}, where A is a (possibly partial) program and P and Q are logical statements about the variables of the program. This formula asserts that if P holds in the state just prior to the computation of A, and if this computation terminates, then Q will be true in the resulting state. For example, a (somewhat simplified) way of describing the effect of an assignment x := e in a program is by the formula {e = c} x := e {x = c}, where c is a constant. (Note the crucial difference between logical equality and assignment, so unfortunately blurred by languages from Fortran to Java that use "=" for assignment.) This formula asserts that if the value of the expression e in the state preceding the assignment is c, than the value of x after the assignment is also c.
As another example, consider how to prove that a certain formula holds for a conditional: {P} if C then A else B {Q}. If the condition C is true in the state before the computation, then the conditional will choose the subprogram A. In order for the desired formula to hold, it must be the case that if P and C are true before the computation, Q must be true afterwards (provided, as always, that the computation terminates). Formally, {P and C} A {Q} must be true. Similarly, {P and not C} B {Q} must hold to guarantee the desired result in the case where the condition C is initially false. And indeed, the desired formula follows from the latter two in Hoare logic.
As is the case for most logics of programs, the difficulty lies in reasoning about loops (and recursion). In order to prove a property of a loop using these logics, it is necessary to come up with a loop invariant. This is a property that always holds at the beginning of each iteration. In order to prove a property P following the loop, you prove that the invariant holds on entry to the loop, that it sustains itself across one iteration, and that if you exit the loop with the invariant holding, P must be true at that point.
This is very similar to a proof by induction; the first step is the base of the induction, and the second is the inductive step, in which you prove that if the invariant holds in the beginning of one iteration, it also holds on the beginning of the next one. As is the case with inductive proofs, coming up with a suitable invariant is difficult. Much of the work of automatic theorem provers (for mathematics as well as for logics of programs) is discovering the induction hypotheses or, equivalently, the loop invariants. (In fact, in one of my favorite theorem provers, ACL2, these are exactly the same.)
This kind of reasoning is very low-level, and it is impossible to use it to prove the correctness of a large program manually. Automated theorem provers are a great help, but the process is still difficult and time-consuming, and requires high skills in logic and the specific theorem prover. It is therefore limited to relatively small but safety-critical programs. Wide application of automatic theorem proving to large-scale programs seems to be far in the future. As a result, there is a chasm between the people developing logics of programs and associated theorem provers, and the general population of software developers, most of whom are not even aware of the existence of these methods and tools. But there is a middle way; I will discuss it in the next post.
Tuesday, February 15, 2011
Thinking Formally
If there is no alternative to clear thinking about our programs, we should investigate what we can learn from the science of organized thought. Logic has a long history, with equal roots in philosophy and mathematics. In some sense, computer programs breath life into abstract logic and give logic the abilitiy to do real things. And, just like Pinocchio, they often misbehave!
One of the fundamental concerns of logic is the study of proofs: how can we convince ourselves in a precise and mechanical way of the truth of some claim. The desire to do so resulted from the need to distinguish between valid and invalid mathematical proofs, expressed using prose. Sometimes, hidden assumptions were not recognized, leading to faulty proofs. For example, consider the first axiomatic proof system, Euclidean geomerty, studied in middle school. It has five axioms, including the famous "parallel postulate". It is an amazing achievement, which is still an excellent example of how to reason formally, and was the source of many important advances in mathematics. But Euclidean geometry has many hidden assumptions, which are glossed over by the use of informal drawings. About 2200 years after Euclid, several mathematicians tried to completely formalize geometrical proofs. David Hilbert's axiomatization of geometry includes twenty axioms instead of Euclid's five. One of these states that between every two different points on a straight line there is a third point on the same line. This was so obvious to Euclid that he didn't even think to mention it in his list of axioms. But axioms are exactly those self-evident propositions on which the theory is based, and the proof isn't logically sound unless all these are stated explicitly.
Logic is closely tied with computation, although the connection was made explicit only towards the 20th century. A formal proof is a series of deductions, each of which is based on axioms or previously-proven propositions, using a set of deduction rules. It is supposed to be so simple that it can easily be checked for correctness, without any understanding of its subject matter, whether it is geometry, number theory, or abstract algebra. In other words, it should be easy to write a program that checks a formal proof; all you need to do is verify that each step follows from the axioms and from previous steps according to the rules.
But wait! Is there a limit to the complexity of the axioms or of the rules used in the proof? Without such limits, the whole exercise falls apart. For example, imagine a system of axioms that contains all true statements in number theory. This is, of course, an infinite set. How difficult is it to write a program to check whether a given statement is an axiom? Well, it turns out to be impossible! (This is a consequence of Gödel's first incompleteness theorem.) So, if we are to be able to write a program to check formal proofs, we need to restrict the possible sets of axioms. For example, in Gödel's theorems, the set of axioms is required to be recursively enumerable; this means that there is a (finite) program that can generate all axioms and never generates anything that is not an axiom. Of course, this program will never terminate if the set is infinite. That's acceptable, as long as the program is guaranteed to produce every axiom if you wait long enough.
So now, a concept about computability has entered the study of logic itself. It is only fair, then, to apply logic to computation; and, indeed, the study of logics of programs is an important field in computer science. There are even computer programs called theorem provers, which have been used to prove difficult mathematical theorems as well as to verify the correctness of other programs. However, this has still not affected the day-to-day work of most software developers. In the next post, I will discuss why this is the case and what formal tools can still be used for software development today.
One of the fundamental concerns of logic is the study of proofs: how can we convince ourselves in a precise and mechanical way of the truth of some claim. The desire to do so resulted from the need to distinguish between valid and invalid mathematical proofs, expressed using prose. Sometimes, hidden assumptions were not recognized, leading to faulty proofs. For example, consider the first axiomatic proof system, Euclidean geomerty, studied in middle school. It has five axioms, including the famous "parallel postulate". It is an amazing achievement, which is still an excellent example of how to reason formally, and was the source of many important advances in mathematics. But Euclidean geometry has many hidden assumptions, which are glossed over by the use of informal drawings. About 2200 years after Euclid, several mathematicians tried to completely formalize geometrical proofs. David Hilbert's axiomatization of geometry includes twenty axioms instead of Euclid's five. One of these states that between every two different points on a straight line there is a third point on the same line. This was so obvious to Euclid that he didn't even think to mention it in his list of axioms. But axioms are exactly those self-evident propositions on which the theory is based, and the proof isn't logically sound unless all these are stated explicitly.
Logic is closely tied with computation, although the connection was made explicit only towards the 20th century. A formal proof is a series of deductions, each of which is based on axioms or previously-proven propositions, using a set of deduction rules. It is supposed to be so simple that it can easily be checked for correctness, without any understanding of its subject matter, whether it is geometry, number theory, or abstract algebra. In other words, it should be easy to write a program that checks a formal proof; all you need to do is verify that each step follows from the axioms and from previous steps according to the rules.
But wait! Is there a limit to the complexity of the axioms or of the rules used in the proof? Without such limits, the whole exercise falls apart. For example, imagine a system of axioms that contains all true statements in number theory. This is, of course, an infinite set. How difficult is it to write a program to check whether a given statement is an axiom? Well, it turns out to be impossible! (This is a consequence of Gödel's first incompleteness theorem.) So, if we are to be able to write a program to check formal proofs, we need to restrict the possible sets of axioms. For example, in Gödel's theorems, the set of axioms is required to be recursively enumerable; this means that there is a (finite) program that can generate all axioms and never generates anything that is not an axiom. Of course, this program will never terminate if the set is infinite. That's acceptable, as long as the program is guaranteed to produce every axiom if you wait long enough.
So now, a concept about computability has entered the study of logic itself. It is only fair, then, to apply logic to computation; and, indeed, the study of logics of programs is an important field in computer science. There are even computer programs called theorem provers, which have been used to prove difficult mathematical theorems as well as to verify the correctness of other programs. However, this has still not affected the day-to-day work of most software developers. In the next post, I will discuss why this is the case and what formal tools can still be used for software development today.
Tuesday, February 1, 2011
Responsible Adults
If some programmers are not behaving maturely (see Programmers as Children), what can we do as responsible adults to make things better? There are many answers, and they depend on who is meant by "we".
First, however, I must mention what is perhaps Fred Brooks's best-known paper, "No Silver Bullet: Essence and Accidents of Software Engineering" (IEEE Computer, April 1987). In it, Brooks claims that software engineering is hard in essence, and therefore nothing can make it easy. While a lot of progress has been made on what Brooks calls accidental difficulties, which have to do with the way represent the abstract concepts of software engineering, these only expose the essential difficulty of the conceptual structures underlying software development. The silver bullet is the only effective way to kill werewolves; Brooks claims that no such magical cure can be found for the ills of software development.
This is, of course, a provocative statement, and it sparked lively discussion. But in spite of various opinions to the contrary, no silver bullet has yet been found. This is not to say that progress has not been made. Even if the essential problem is difficult, programmers are still being asked to develop larger and larger systems. They should use whatever cures are available, even if they cure only the symptoms and not the disease.
So what can we do? The most important thing is to be aware of the difficulties and look for ways to avoid them. There is no substitute for careful thinking, and no tool will do that for us until true artificial intelligence is available. (While great progress is being made – for example, see the Watson Jeopardy challenge – don't hold your breath waiting for "automatic programming" in the sense of the computer writing its own programs.) More concretely, there are many practices we can follow in order to make software development easier, more productive, more reliable, and also more fun. These fall into several categories, including methodology and process, languages and tools, and education. I will have something to say about each of these, but only a book the size of an encyclopedia can do justice to them all.
There are many software-developoment methodologies, and none is perfect. In fact, Daniel Berry of the University of Waterloo has a paper titled "The Inevitable Pain of Software Development: Why There Is No Silver Bullet". Another provocative paper, and one of the responses to the one by Brooks, this one focuses on why no methodology can ever be a silver bullet. Berry claims that every methodology has some inherent pain associated with it. It may be all pain, as in the maligned waterfall method, or the pain could be just a small part of it. In any case, it is unavoidable, and developers therefore evade it by not following the methodology rigorously, thus defeating its purpose. But this is like parenting: although no one knows of a sure method to raise perfect children, that doesn't keep us from trying. In the same way, the fact that there is no perfect development methodology doesn't mean that we should not attempt to find the best process for our situation and follow it to the best of our ability.
As I mentioned before, I'm a great believer in tools, and spend a lot of time developing new tools. I have also been involved with computer-science education, at both the university and high-school levels, and I have a lot to say about these topics. Stay tuned!
First, however, I must mention what is perhaps Fred Brooks's best-known paper, "No Silver Bullet: Essence and Accidents of Software Engineering" (IEEE Computer, April 1987). In it, Brooks claims that software engineering is hard in essence, and therefore nothing can make it easy. While a lot of progress has been made on what Brooks calls accidental difficulties, which have to do with the way represent the abstract concepts of software engineering, these only expose the essential difficulty of the conceptual structures underlying software development. The silver bullet is the only effective way to kill werewolves; Brooks claims that no such magical cure can be found for the ills of software development.
This is, of course, a provocative statement, and it sparked lively discussion. But in spite of various opinions to the contrary, no silver bullet has yet been found. This is not to say that progress has not been made. Even if the essential problem is difficult, programmers are still being asked to develop larger and larger systems. They should use whatever cures are available, even if they cure only the symptoms and not the disease.
So what can we do? The most important thing is to be aware of the difficulties and look for ways to avoid them. There is no substitute for careful thinking, and no tool will do that for us until true artificial intelligence is available. (While great progress is being made – for example, see the Watson Jeopardy challenge – don't hold your breath waiting for "automatic programming" in the sense of the computer writing its own programs.) More concretely, there are many practices we can follow in order to make software development easier, more productive, more reliable, and also more fun. These fall into several categories, including methodology and process, languages and tools, and education. I will have something to say about each of these, but only a book the size of an encyclopedia can do justice to them all.
There are many software-developoment methodologies, and none is perfect. In fact, Daniel Berry of the University of Waterloo has a paper titled "The Inevitable Pain of Software Development: Why There Is No Silver Bullet". Another provocative paper, and one of the responses to the one by Brooks, this one focuses on why no methodology can ever be a silver bullet. Berry claims that every methodology has some inherent pain associated with it. It may be all pain, as in the maligned waterfall method, or the pain could be just a small part of it. In any case, it is unavoidable, and developers therefore evade it by not following the methodology rigorously, thus defeating its purpose. But this is like parenting: although no one knows of a sure method to raise perfect children, that doesn't keep us from trying. In the same way, the fact that there is no perfect development methodology doesn't mean that we should not attempt to find the best process for our situation and follow it to the best of our ability.
As I mentioned before, I'm a great believer in tools, and spend a lot of time developing new tools. I have also been involved with computer-science education, at both the university and high-school levels, and I have a lot to say about these topics. Stay tuned!
Subscribe to:
Posts (Atom)