Sufficient Completeness and TDD

Posted on by

“Sufficient Completeness” is a characteristic of specifications, from the theory of abstract data types. It can help guide our testing.

One way of looking at objects is to consider the history of what has happened to them: the sequence of calls.

We can think of three types of “methods”:

  • Constructor – builds a new object
  • Mutator – changes the object
  • Accessor – “observes” the object (as a function of its state)

The state of the object is a consequence of the constructor and the sequence of called mutators.

I’m going to write the history like this:

accessor: mutatorN: ... : mutator1: constructor

(This is an alternative to a heavily parenthesized form. Read the history from right to left: first the constructor, then the mutators 1 to N, then the accessor is called.)

Collections

I’ve typically used these techniques for thinking about collections. I think it’s a combination of factors:

  • they’re complex enough that the extra tools provide value
  • we have well-understood things to map them to (sets, sequences
  • they’re somewhat self-contained (the container is meaningful independently of the elements it contains)

Please let me know if you find them helpful in other domains.

Sufficient Completeness

To say what an accessor means, we need to be able to say what it does about any possible sequence of constructor and mutator calls. But that means we must cover an infinite (usually) set of sequences.

Sufficient completeness means that the specification must define behavior for any combination of mutators.

Our definition will often be recursive – defined in terms of the last few mutators, and “the rest of the sequence”.

For example: We have an object with a constructor “zero”, a mutator “plusOne”, and an accessor “count”. 

count: zero = 0
count: plusOne: s = 1 + count:s

Note that we’ve covered all possible sequences (zero and plusOnes followed by a zero), so the definition for count is sufficiently complete – we’re never left wondering what the value should be.

A code example might look like this:

MySequence s = MySequence.zero
s.plusOne()
s.plusOne()
print(s.count())

We could analyze this by our spec like this:

count: plusOne: plusOne: zero
= 1 + count: plusOne: zero
= 1 + 1 + count:zero
= 1 + 1 + 0 
= 2

That matches our intuition about the meaning.

Reduced Form

To make it easier to specify things, we may be able to identify a reduced form – a simpler form that all possible sequences can map to. (It may, but need not be, a unique representation.)

For example, let’s add a minusOne operation to our previous sequence.

The value of count: plusOne: minusOne: plusOne: zero is 1.

But we can define a reduced form: Either:

zero    -OR-
(addOne:)+ zero    -OR-
(minusOne:)+ zero

(I’ve used the regular expression of “+” meaning “one or more”.

In many cases, if we find a reduced form, we can simplify our rules. Our specification becomes simpler: accessors need to be defined only for the reduced form. (We also need to demonstrate that we can convert objects to reduced form.)

Example

Let’s look at a double-ended queue (a “duque”).

  • Constructor: empty
  • Mutators: addFront, addRear, removeFront, removeRear
  • Accessors: front, rear, isEmpty, count

Reduced form: You should be able to convince yourself that any sequence resulting from a series of mutations will be equivalent to a sequence of this form: (addFront:)+ empty (You could alternatively use addRear).

Let’s define behavior with respect to the reduced form: (I’ll let you tackle isEmpty and count.)

front: empty = error
front: addFront x: d = x

rear: empty = error
rear: addFront x: empty = x
rear: addFront x: addFront y: d = rear: addFront y: d

Notice how the variable “d” lets the last case define what happens for a list of size 2 or greater.

What about the other mutators? We need to show that we can express them in reduced form.

addRear x: empty = addFront x: empty
addRear x: addFront y: d = addFront y: addRear x: d

removeFront: empty = error
removeFront: addFront x: d = d

removeRear: empty = error
removeRear: addFront x: empty = empty
removeRear: addFront x: addFront y: d = 
                 addFront x: removeRear: addFront y: d

Let’s work an example. Notice how we convert the expression to reduced form, and then evaluate the accessor.

rear: addFront x: removeFront: addFront y: empty
= rear: addFront x: empty        // by rule 2 of removeFront
= x                              // by rule 2 of rear

Test Cases for TDD

Looking at the specification rules gives me a starting point for tests.

Look back at “front”: its two rules tell me I have to cover at least an empty list and a list of one or more elements. For “rear”: I have to cover an empty list, exactly one element, and 2 or more elements. If I don’t test these cases, I’m not covering the specification.

Similarly, for “addRear”, “removeFront”, and “removeRear”.

Will these tests be sufficient? Unfortunately, no. Our implementation may add its own needs and consequences. For example, a doubly-linked list version of a deque does not privilege the addFront as our reduced form implies – it’s symmetric for front and rear; other things may go wrong.

The specifications have another use too: we can generate values from them, and test our functions on those generated values. This may fit more with a property-based testing style than typical TDD.

Hidden Methods

For some systems, behaviors cannot be fully specified solely in terms of their mutators. An example of this is a sequence that has a current point where changes in the middle can take place at a “cursor”.

A related problem can happen when an interface is too narrow to let you assess its effect. I ran across this in using a deque as part of a cache. It only needed a few operations:

  • removeRear – remove the “least recently used” element
  • addToFront – add a new element to the front
  • moveToFront – move an (existing) element to the front

These operations don’t make it easy to determine the state.

Specifications are allowed to have hidden methods (or functions or types) that can be used to specify behavior but are not revealed to the client.

For the cache, I found it useful to define two accessors, “valuesGoingForward” and “valuesGoingBackward”. That let me verify that operations preserved the constraint valuesGoingForward = reverse(valuesGoingBackward) These functions were for tests only, and used knowledge of the internal representation to do their job.

Conclusion

Thinking of our objects as if they were formally specified can give us insight into the essential trickiness of part of our code, and suggest a class of TDD test cases.

By identifying a reduced form, we can simplify the job of accessors (only needing to think about reduced form), provided we constrain our mutators (make sure that when you’re done, you leave the object looking as if it were always built in reduced form).

Finally, these test cases are not necessarily sufficient. We may need more test cases, or may need hidden methods to help us specify or verify our objects.

References