TDD and the SkipList (part 3)

So here I am, with a SkipList implementation developed test-first. I have 100% test coverage (actually, more than 100% coverage), and didn't have to break encapsulation or pollute the class' interface to get it. Along the way, I wrote down some observations.

First: I remain convinced that test-first is the way to develop code, if only to ensure that you're doing what you think you are. In the case of the SkipList, this point was driven home early, when my tests caught a bug in the tier assignment method. It was a subtle bug: I knew that the size of the list determined the maximum tier for an element, so wrote the tier-assignment code to pass the current size into Random.nextInt(). My test however, kept failing. When I looked at the actual counts I discovered they were skewed — the bottom tier had about half the elements it should, and they were distributed to higher tiers. Without the tests, I never would have discovered the problem, nor been able to experiment with a solution (which was to pass a power of two).

And that leads to my second observation: it's really hard to avoid preconceived design. Although I wrote the test first, I already knew (or thought I knew) how I was going to implement the method. A pure TDD approach would have been to write separate tests for a variety of list sizes, and perhaps that would have led me directly to the “needs to be a power of two” solution.

Third: TDD is best accomplished in a single session, at least at the scale of a single method or group of methods. This one surprised me, because I thought that the tests would read like a story, leading me back to the point I had stopped. In reality, I put the half-finished code aside while attending the TDD training, and when I picked it up again I puzzled over some of the decisions that I'd made along the way.

On reflection, the storybook metaphor is actually the right one: you can't expect to put a novel down for a week and jump right back into it (at least, I can't). I think this may be one of the reasons for the XP practice of deleting uncommitted code before going home for the night. It's faster to start from scratch.

However, this observation concerns me, because it has direct bearing on the “code as specification” benefit of TDD. I find that the purist approach of small, limited test cases actually hinders comprehension, because the knowledge of how an object works is spread over many tests. I tend to write larger tests, such as testElementCreation() that explore multiple facets of a single behavior. Regardless of test size, this observation highlights the need for test clarity.

Fouth observation: implementation tends to be a quantum behavior. There are points at which you make a dramatic step in functionality that's impossible to break into smaller pieces. Either it works as expected, or it doesn't work at all. The SkipListManager.insert() method is an example: although I have a plethora of test scenarios, the code was pretty much complete (if slightly buggy) after the first. The only way to avoid this is to test something other than a SkipList.

And this brings me to a point that Uncle Bob made during the training: “TDD won't give you quicksort.” That statement seems to invalidate the entire approach: if a minimal failing test won't get you closer to your goal, why do it? The answer, I think, is that dogma inculcates discipline, and the TDD purists recognize that the real route to better code is disciplined programmers. Test-driven development mandates discipline: you have to to write the tests, and this will (hopefully) get you to thinking about the ways your code is used.

But this leads to my last observation: there were too many cases where the tests told me that I was fine, but my intuition said otherwise. I've developed that intuition over more than 30 years of writing code; many TDD proponents have been at it longer. An inexperienced programmer won't have that intuition, and could easily find him/herself at the end of a road with nowhere to turn.

TDD and the SkipList (part 2)

Several years have passed since my first attempt at implementing SkipList via TDD. I continue to do test-first development — for example, most of the Practical XML library was written in this manner. However, while I use tests to validate my design, and put me in the shoes of a person using the library, they don't drive that design.

For the SkipList, I tried very hard to take that next step, and let the tests show me where to go. I'm not sure that I was successful, and in some cases I didn't like the results. I won't blame you for skipping this post: it has a close resemblance to a fishing show (“yes, Billy-Bob, he's definitely got something on the hook, so lets watch him reel it in”). Not for everyone, but it does lay the groundwork for my next post.

In returning to the SkipList, I recognized that I would need a way to test the implementation separate from the public API. Java gave me a solution to the packaging issue: rather than using multiple top-level classes, or interface and implementation, I would use nested static classes. Everything lives in one source file. The choice of nested classes, rather than inner, was intentional: if TDD was going to drive me to independent collaborators, I wanted them to be truly independent.

The first question was where to draw the line between interface and implementation? I took what appeared to be the simplest: create a SkipListElement that knew only how to talk to its neighbors. The SkipList itself would know about the first element. Conceptually, this is how any linked list can be implemented, and it's very easy to test. In practice, of course, implementing a normal linked list with self-aware elements is a good way to blow up your stack from the recursive search operation (unless your language optimizes tail recursion). For SkipList, with its log2 access paths, it seemed like a workable idea.

As it turned out, while the tests remained simple, the implementation quickly became very complex. The find() method was particularly so: it had to work its way up through the tiers of links and then back down. After a lot of massaging, it turned into a half-dozen lines of code that still appeared to have O(log2) behavior. This exercise, however, was more test-first than test-driven: I made a lot of changes to the code, but only after pondering why the test was still failing; the test remained relatively unchanged.

Moreover, at this point my intuition was screaming “warning, Will Robinson!” but the tests remained silent. Looking at the tests, I realized that I wasn't actually validating that my search properly traversed the list, merely that it found the expected element. So I wrote a new test, one that recorded each invocation of the find() method, and discovered that I wasn't properly maintaining high-tier links. Even though I'd written a nice recursive method, I was doing a linear search.

Would a “pure” approach to TDD have made me write this test? On the one hand, I was validating core behavior; on the other, I already had a green bar, 100% coverage, and lots of tests that showed me what I expected to see.

As I looked at the code and thought about what would be required to make it work, I came to the conclusion that I had walked down a cul de sac. So, in good XP fashion, I deleted everything and started over.

In my next attempt I introduced another nested class, SkipListManager, and went having SkipListElement be a dumb data container. Well, almost a dumb data container: I made the decision that it should know about its neighbors.

This led to an interesting situation: to write my tests, I wanted to be able to connect two elements together at multiple tiers, so wrote an append() method to do so. As I moved forward with the implementation, I found that method leading me into a corner: because it existed, I wrote my manager to use it, and ended up with a findAndRemember() operation that was almost, but not quite the same as the find() operation. I couldn't find a good way out without a third object, a “find iterator.”

At this point, I debated whether or not I really needed the manager object. Its sole reason for existence was to provide a back door for testing; giving the list protected methods would do the same. This was a rehash of my original concerns about TDD: protected methods are part of the interface of a class, and can never be removed. I decided that I didn't want to pollute SkipList just to support testing.

As I was thinking about the manager-element interaction, I decided that the best way back was to delete a large chunk of code (unlike the former attempt, I wasn't willing to throw it all away). My tests certainly helped with this: I deleted the chunks of code that I didn't like, and my IDE told me what tests depended on them. The code that remained was still covered by tests, still worked, and still represented a design that I liked.

I dove back in, and again ran into trouble inserting elements. Once I had appended an element in a tier, it prevented me from properly traversing the lower tiers. Score one for the tests: they turned up this problem right away. I still needed to run in a debugger to figure out what was happening, but the tests gave me a controlled environment in which to walk the code.

The test for the manager's insert() function came in at nearly 100 lines of code, as I validated how different element values would work their way through the chains. Although I wrote this test one section at a time, I suspect a TDD purist would look at the length of the method and cringe (it was actually quite a bit longer, until I refactored the assertions). The TDD approach would be to break each of these scenarios into separate methods, but that seems like a lot of needless duplication to me: I would have to repeat code to configure the list for each test. By combining these tests I additionally validate that I'm not damaging other portions of the list. I will say, though, that my variable naming conventions left something to be desired.

The final hurdle came from remove(). After getting the manager to properly handle insertions, I started working through the public API in alphabetical order. When I hit removal, I realized belatedly that I just wasn't going to to get away with a singly-linked list. Should I have seen this coming? Probably yes, given that my element-only approach ran into a similar dead end. But it points out a very good point: with TDD, the order of tests matters. On the positive side, I was able to insert the backlinks by breaking one test at a time, and I was still testing the forward links.

Are you ready for “the codez”? You'll find the list class here, and the test class here. The name “SkipList1” should give you a hint that I'm still not happy with the implementation, but it's time to ship (ie, get this post up on the blog). Over the next few weeks I'll be tinkering with the implementation (I have an idea that will take me back to a forward-linked list), and once I'm happy with it (if ever), will post a link to the final code.

Next up: my thoughts about this experiment, and TDD in general.

TDD Training Debrief

I'm going to interrupt the postings on SkipList, because the TDD class is over. Did I learn anything?

I came into class thinking that I had a fairly good understanding of TDD, albeit as a skeptic that it could directly drive design. I left thinking the same thing. I'm sure there were some pieces of information that I picked up without realizing — it's impossible for that not to happen if you have a good instructor. And I was exposed to Fitnesse, a tool that will probably be more useful in a future career stop. But I came in test-infected, left test-infected, and didn't have a revelation in the middle. My thoughts may not have changed, but the class pushed me to think deeply about the subject again, and test those thoughts.

Where I thought the class was tremendously valuable was in interacting with Uncle Bob. He's a lot more pragmatic in person, admitting that there are places where test-driven design falls down (eg, TDD will give you bubble-sort, not quicksort). I can understand this difference in personality: written words have to stand on their own for all time, presentations are marketing (of ideas, if not of self), while the classroom is a place for discussion.

The biggest revelation, however, came from observing my fellow students. At any given time, about half of them were working on other things: responding to email, reviewing defects, writing code for their current projects, and generally ignoring what was happening around them. And to be honest, during the last example of the first day I joined them: a minor crisis had appeared in my inbox over lunch, and I decided that it was more important to respond to that crisis than to work through the example — after all, I already knew this stuff, right?

Uncle Bob finished the class with a talk on what he saw as the future of TDD. He used an interesting example: in the 1970s there was a lot of argument about the value of structured programming, yet today every mainstream language uses structured constructs — “goto” is no longer considered harmful, because it no longer exists. His opinion is that 30 years from now we won't be discussing TDD either, because it will be standard practice.

I think there's a flaw in this reasoning: computer languages are created by language designers, made whole by compiler writers, and are in effect handed down from on high for the rest of us. Even Fortran and Cobol have evolved: while there may be dusty decks filled with gotos, code written yesterday (and there is some) uses structured constructs. TDD won't follow that path, unless Eiffel becomes a mainstream languge, because of the commitment that it requires.

Anything that requires commitment also has costs: what do I have to invest to travel this path (direct cost), and what do I have to give up (opportunity cost)? In an economics classroom, choices are easy: you add the direct and opportunity costs, and take the low-cost option. In real life, it's often hard to identify those costs — most people consider staying in the same place to have zero cost. And given that, there's no reason to change.

I can't remember when I became test-infected: I know that I was writing test programs to isolate defects some 20 years ago. As I read the testing literature that started to appear around 1999, a lightbulb went on in my head, and I tried writing my mainline code with tests. And learned that no, it didn't take me any longer, and yes, I found problems very early. In other words, that TDD was in fact the low-cost option.