| One way to determine “sufficient completeness” suggests considering all sequences of calls that can take an object to a state. This enumeration suggests important test cases. |
How do you know an object “works”? A branch of formal methods known as axiomatic specification can give us some insights.
Mutators and Accessors
We talk of an object as having state and methods to encapsulate some idea. Some methods let us look at the object: these are accessors. (It’s immaterial whether these compute a value or return a stored value.) Other methods change an object; these are mutators. Some methods do both, e.g., a pop() method that reads the top of the stack, pops it, and returns it. For our purposes here, split those into two methods. (Martin Fowler calls this refactoring Separate Query from Modifier.)
This analysis is an abstraction. It doesn’t deal with objects that change spontaneously or with threads. But that’s ok – many interesting objects don’t have those challenges.
The first insight is this: for many objects, the state of the object is determined by the sequence of mutator operations called. We can use a “nested function call” expression to represent this.
To be concrete, we’ll work with a Money example. For starters, we can create some new Money, add to it, and find its value. If we look at:
value(add(10, add(2, new)))
we expect “12” back.
Here’s where the axiomatic part comes in. We can specify the value() method’s behavior using axioms (rules):
value(new) = 0
value(add(n, m)) = n + value(m)
(“n” is an integer, “m” is a Money object.) With these rules,
value(add(10, add(2, new)))
= 10 + value(add(2, new))
= 10 + 2 + value(new)
= 10 + 2 + 0
= 12, as expected.
Let’s add another mutator into the mix, subtract:
value(subtract(n, m)) = value(m) – n
Note that this definition lets us have negative amounts; e.g.,
value(subtract(2,new)) = -2
Sufficient Completeness
Sufficient completeness is the idea that we have defined things in such a way that we’ve assigned a value to any expression. In object terms, this says that our methods know how to work regardless of the sequence of mutator operations that led to the current state of the object.
One simple way to assure sufficient completeness is to look at all the ways an object can be formed, and make sure each accessor is defined for all those possibilities.
In this case, it’s fairly simple to show, using an inductive argument. The base case is new. We’ve defined value(new) directly, so that’s ok. The other cases are add(n,m) and subtract(n,m). In both cases, we’ve defined value for the two forms, in terms of (the simpler) value(m). By induction, we’ve defined value for all sequences.
Testing
This approach to sufficient completeness suggests a testing strategy: test each accessor for each possible expression form. In this case, we expect to see value tested at least three ways: on new Money, on Money that’s been added to, and Money that’s been subtracted from. If we don’t cover at least those three possibilities, an error might creep in. (We don’t want to omit the other domain either – integers. A minimal test would use integers that are negative, zero, and positive.)
From Money to Wallet
Let’s try a variation on Money – a Wallet. A Wallet has remove instead of subtract, but they key difference is that you can only remove a bill you’ve added earlier. The first two definitions are the same:
value(new) = 0
value(add(m, w)) = n + value(w)
When we go to define value(remove(m,w)), we realize that removing depends on what w is. If w contains a bill of denomination n, we can manage it; otherwise we have a problem. To go down this path, we’ll introduce some rules for remove:
remove(n, new) = error
remove(n, add(m, w)) = if m==n then w else add(m, remove(n, w))
Are these definitions sufficiently complete? This time, the argument is trickier:
value(new) – defined directly
value(add(n, w)) – defined directly
value(remove(n, w)) – defined only if remove can always be converted to new and add
And:
remove(n, new) – defined as a failure
remove(n, add(m, w)) – defined – but notice that we define it into an expression of the same length in one case. We have to convince ourselves that this expression is somehow simpler. It is – remove(n,w) is simpler than the longer expression – it pushes the remove to the right where it will either hit the first case of the if clause, or it will try to remove from an empty wallet. Moving the add to the front is no problem; value is defined for add directly.
remove(n, remove(m, w)) – (This case is easy to forget, but the rules for sufficient completeness tell us to systematically consider each possibility.) If w begins with new or add, then we’re covered by the above. If not, apply this rule again until we get to such a w. The result can always be reduced to new and add, so the approach will terminate.
Therefore: yes, our definition is sufficiently complete.
This suggests a number of test cases. We certainly want to get the value of new, add, and remove. For remove, we have four cases: remove on a new, remove on an add with the same value, remove on an add with a different value, and remove from a wallet that’s been removed from before. Our arguments for sufficient completeness suggest a good starting set of test cases.
| value(new) |
| value(add(2, new)) |
| value(remove(1, new)) |
| value(remove(2, add(2, new))) |
| value(remove(1, add(5, new))) |
| value(remove(2, remove(5, add(2, add(5, new)))) |
In Practice
In practice: I rarely sit down and try to write axioms for objects (perhaps once in a year). Even then I don’t force myself to be formal and complete.
But I use these ideas day to day:
- An object’s state results from the sequence of mutator calls
- Each method needs to do its job for every call sequence that led to the current state
- The possible sequences of mutator calls suggest test cases that need to be covered
Our demonstration of sufficient completeness used a “combinatorial” approach: check every method on every possible call sequence form. This provides a systematic way to identify important values to test.
[Written April 12, 2006.]