ABOUT
Does it really work? The Transformation Priority Premise
Given a simple problem of sorting numbers in an array, how come that one TDD session leads to Bubble sort while the other produces QuickSort?
Robert C. Martin proposed the question in his talk titled The Transformation Priority Premise at the Norwegian Developers Conference in 2011, which was brought to my attention by DeVill. The topic is also discussed in a blogpost. In short, when more and more tests are created during a TDD session, the test code gets more and more specific, which forces the production code to get more and more generic. While the third step of TDD is refactoring (i.e. changing the code without changing its external behavior, which is verified by the tests written so far), the second, the pass step utilizes transformations, in other words: changing the code to make its behavior more generic. Uncle Bob has a small list of such transformations, from which he recommends choosing the highest one that can make the failing test pass and avoiding the items near the bottom of the list if possible. Doing so is believed to yield better code.
({} -> nil) no code at all -> code that employs nil
(nil -> constant)
(constant -> constant+) a simple constant to a more complex constant
(constant -> scalar) replacing a constant with a variable or an arg
(statement -> statements) adding more unconditional statements
(statement -> if) splitting the execution path
(scalar -> array)
(array -> container)
(statement -> recursion)
(if -> while)
(expression -> function) replacing an expression with a func or algorithm
(stateless -> assignment) replacing the value of a variable.
Using only those transformations during the pass step of TDD will really force you to take baby-steps! :-)
According to Uncle Bob, the difference between the QuickSort and Bubble sort TDD sessions basically originates from one single decision at an early stage of development. For example, assume the following stage of the TDD iteration, in Python:
class SorterTest(unittest.TestCase):
def test_sorting(self):
sorter = Sorter()
self.assertEquals([], sorter.sort([]))
self.assertEquals([ 1 ], sorter.sort([ 1 ]))
self.assertEquals([ 1, 2 ], sorter.sort([ 1, 2 ]))
self.assertEquals([ 1, 2 ], sorter.sort([ 2, 1 ]))
class Sorter(object):
def sort(self, elements):
return elements
At this point, the test using [2,1] is failing and we are to modify the production code to make it pass. One possibility is to swap the elements of the input array if they are in the wrong order:
class Sorter(object):
def sort(self, elements):
if len(elements) > 1:
if elements[0] > elements[1]:
elements[0], elements[1] = elements[1], elements[0]
return elements
Swapping the elements of the input array will change the outside world as well since in Python, lists are passed by reference. This is obviously the last element from the list: (stateless->assignment). I tried it, and it trivially lead to a bubble sort. Here’s the screencast:
What surprised me is how easily it turned into quicksort when instead of swapping elements, I satisfied the failing testcase by appending elements to a new array:
class Sorter(object):
def sort(self, elements):
if len(elements) < 2:
return list(elements)
sorted = []
if elements[0] < elements[1]:
sorted.append(elements[0])
sorted.append(elements[1])
else:
sorted.append(elements[1])
sorted.append(elements[0])
return sorted
There’s a screencast for that as well:
Doing these experiments made me think. Does the same trick work for other well known algorithms? Take searching in a sorted list for example. I could not imagine how those baby-steps could lead to binary search, the fastest algorithm I know for this problem. My first experiment ended up with an implementation of linear search, kinda like what I expected:
However, I realized I’d broken the rules of TDD. TDD says that you must implement the simplest code that can make the currently failing test pass, but what I did for one of the tests near the beginning was not the simplest solution. At this early stage, everything was fine:
class SearchTest(unittest.TestCase):
def test_when_value_is_found_in_sorted_list_then_its_key_is_returned(self):
search = Search()
self.assertEqual(0, search.search([ 1 ], 1))
self.assertEqual(0, search.search([ 1, 2 ], 1))
def test_when_value_is_not_in_sorted_list_then_exception_is_raised(self):
search = Search()
self.assertRaises(NotFound, search.search, [], 1)
class Search(object):
def search(self, sorted_array, value):
if len(sorted_array) > 0:
if sorted_array[0] == value:
return 0
raise NotFound
Then I added a new test, which was still okay:
self.assertEqual(1, search.search([ 1, 2 ], 2))
But then I added two more if statements to the production code:
class Search(object):
def search(self, sorted_array, value):
if len(sorted_array) > 0:
if sorted_array[0] == value:
return 0
if len(sorted_array) > 1:
if sorted_array[1] == value:
return 1
raise NotFound
This is not the simplest code that can make the test pass. There is at least one that is more simple:
class Search(object):
def search(self, sorted_array, value):
if len(sorted_array) > 0:
if sorted_array[0] == value:
return 0
if sorted_array[1] == value:
return 1
raise NotFound
And when the constant 0 is turned into a variable named lower and the 1 is replaced with the last index of the array named upper, then the algorithm magically starts to resemble a binary search! Though implementing binary search this way is not a brainlessly trivial exercise (see the update at the end of the post for a detailed explanation), the algorithm almost fell out from my hands as I added more and more tests.
If I was surprised when quicksort appeared on my screen, I don’t know what I was when a shitload of if statements turned into binary search right before my very eyes.
P.S: yes, in the binary search demo, middle would have been a better name for the variable than i. :-)
Update: seems that this binary search screencast is not very self-explanatory. Let’s start from here:
class SearchTest(unittest.TestCase):
def test_when_value_is_found_in_sorted_list_then_its_key_is_returned(self):
search = Search()
self.assertEqual(0, search.search([ 1 ], 1))
self.assertEqual(0, search.search([ 1, 2 ], 1))
self.assertEqual(1, search.search([ 1, 2 ], 2))
def test_when_value_is_not_in_sorted_list_then_exception_is_raised(self):
search = Search()
self.assertRaises(NotFound, search.search, [], 1)
class Search(object):
def search(self, sorted_array, value):
if len(sorted_array) > 0:
if sorted_array[0] == value:
return 0
if sorted_array[1] == value:
return 1
raise NotFound
At this point, all the tests pass. I cannot seem to find a useful refactoring here, however, I don’t like those two if statements. I add a test that allows me to make one of them more generic:
self.assertEqual(2, search.search([ 1, 2, 3 ], 3))
This could be solved by inserting one more if statement, but there are transformations higher on the priority list that can also make the test pass: replacing the constant 1 with the last index in the array:
class Search(object):
def search(self, sorted_array, value):
if len(sorted_array) > 0:
if sorted_array[0] == value:
return 0
if sorted_array[len(sorted_array) - 1] == value:
return len(sorted_array) - 1
raise NotFound
Now let’s refactor: len(sorted_array) appears three times in the code. By changing the greater-than comparison to an equivalent greater-than-or-equal comparison in the condition, all three occurrences can be refactored to the exact same format. To get rid of this redundancy, this expression can be given a name by introducing a variable, however, the value of that variable never changes during an individual execution of the search() method, so what we have done so far can be viewed as a constant->constant+ transformation. Certainly higher on the list than statement->if.
class Search(object):
def search(self, sorted_array, value):
upper = len(sorted_array) - 1
if upper >= 0:
if sorted_array[0] == value:
return 0
if sorted_array[upper] == value:
return upper
raise NotFound
Still wearing the Refactoring hat, we can introduce a name for the other constant as well: it’s the lower boundary of the array.
class Search(object):
def search(self, sorted_array, value):
lower, upper = 0, len(sorted_array) - 1
if upper >= lower:
if sorted_array[lower] == value:
return lower
if sorted_array[upper] == value:
return upper
raise NotFound
Notice that at this point, we have the terminating condition for the loop of a binary search algorithm.
The similarity between the two inner if statements still bugs me, but I don’t know how to eliminate at least one of them, so I keep going by adding a new test:
self.assertEqual(1, search.search([ 1, 2, 3 ], 2))
This introduces the concept of an element in the middle of the array. Sadly enough, the highest item on the list I can come up with is another damn if statement:
class Search(object):
def search(self, sorted_array, value):
lower, upper = 0, len(sorted_array) - 1
if upper >= lower:
if sorted_array[lower] == value:
return lower
if sorted_array[1] == value:
return 1
if sorted_array[upper] == value:
return upper
raise NotFound
Carefully inserted into the middle. There it does not seem to hurt much, and at the same time, it’s still easy to enforce moving it from there by introducing a test that expects a NotFound exception to be raised when searching in an array of length 1. However, this does not solve the bigger problem with this new if statement. The last test was intended to make the code look at the middle element in the array but what this statement does is looking at the second element, no matter what. In other words, it’s not quite generic enough. I could pretend not to realize this and add a new test that expects the middle element to be found in a 5 long array, but TDD allows you to take bigger steps when you feel confident, so I replaced the constant 1 with the real index of the middle element which happens to be (lower+upper)/2:
class Search(object):
def search(self, sorted_array, value):
lower, upper = 0, len(sorted_array) - 1
if upper >= lower:
if sorted_array[lower] == value:
return lower
if sorted_array[(lower + upper) / 2] == value:
return (lower + upper) / 2
if sorted_array[upper] == value:
return upper
raise NotFound
However, since nor upper nor lower are changed in this function, this expression is still a fancy way of saying 1, at least in the case of the last test written sor far. Also, changing that explicit 1 to this more flexible formula allows the if statement in question to be moved higher inside the outer conditional, simply because it will never attempt to acces an array index out of bounds.
Next thing I did in the screencast was to give this expression a name, though, not the best name as I mentioned earlier. :-) Here I’m using the better name, middle instead of the i used in the screencast.
class Search(object):
def search(self, sorted_array, value):
lower, upper = 0, len(sorted_array) - 1
if upper >= lower:
middle = (lower + upper) / 2
if sorted_array[middle] == value:
return middle
if sorted_array[lower] == value:
return lower
if sorted_array[upper] == value:
return upper
raise NotFound
The next testcase was a tricky one:
self.assertEqual(2, search.search([ 1, 2, 3, 4 ], 3))
None of the inner if statements finds that 3 right now, however, after the first one fails to find it, we can force the second one to do it anyways. When the element in the middle is too small, we can simply set lower to 2, which will trigger the second if statement and bang, our test is green again! Of course we could write lower=2 but we know that this code wouldn’t live for a long time, so let’s use middle+1 instead, which seems to be more future-proof. Remember what TDD says about being confident. Also note that at this point, all our variables and expressions are just fancy ways of saying 0 or len(sorted_array), but for a given input, all of them behave like constants. It does not really matter at this point if you say 2, 1 + 1 or middle+1.
class Search(object):
def search(self, sorted_array, value):
lower, upper = 0, len(sorted_array) - 1
if upper >= lower:
middle = (lower + upper) / 2
if sorted_array[middle] == value:
return middle
if sorted_array[middle] < value:
lower = middle + 1
if sorted_array[lower] == value:
return lower
if sorted_array[upper] == value:
return upper
raise NotFound
The same idea leads to the fifth inner if statement after a new test:
class Search(object):
def search(self, sorted_array, value):
lower, upper = 0, len(sorted_array) - 1
if upper >= lower:
middle = (lower + upper) / 2
if sorted_array[middle] == value:
return middle
if sorted_array[middle] < value:
lower = middle + 1
if sorted_array[middle] > value:
upper = middle - 1
if sorted_array[lower] == value:
return lower
if sorted_array[upper] == value:
return upper
raise NotFound
Note that everything we did so far was either renaming some constants and parameters or choosing one element from the list of transformations!
But what to do now? First, let’s understand the code we did so far. This bunch of if statements can be divided into two parts. The first three inner if statements check one element near the middle of the array. This part of the code immediately returns the index when it finds the value it was looking for or changes either the lower or the upper boundary. What it means is that the array gets split into two parts: one that surely does not contain the value and the other that may do. This is true since the array is sorted. Then the second part, the last two inner if statements check the first and the last element of that latter subarray. What if we copy&paste-ed all those conditionals? There would be ten of them and they would either find the value or split the array again. Everytime we executed those five conditionals one after the other, the subarray that might contain the value we are looking for would become smaller and smaller, thus lower and upper would get closer and closer to each other. Actually, for iteratively splitting the array, repeating the first three if statements are just enough. Thinking through this finally makes it possible to eliminate the last two conditionals and safely change the outer if to while. Oh, how long I was waiting for being able to delete those if statements!
And voila, there is the binary search algorithm:
class Search(object):
def search(self, sorted_array, value):
lower, upper = 0, len(sorted_array) - 1
while upper >= lower:
middle = (lower + upper) / 2
if sorted_array[middle] == value:
return middle
if sorted_array[middle] < value:
lower = middle + 1
if sorted_array[middle] > value:
upper = middle - 1
raise NotFound
The Does it really work? The Transformation Priority Premise by athoshun, unless otherwise expressly stated, is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.
