Monday, September 21, 2009

Spy vs. Spy

A while ago Ravi Mohan wrote a blog entry having to do with TDD and sudoku solving and I wrote a response to it asserting that TDD is not an algorithm generator. I recently caught up with Ravi's blog and it turns out Peter Norvig indirectly referenced Ravi's original blog entry in an interview for the book Coders at Work. I've been thinking recently of writing a bit more on the subject of design and TDD to simplify and clarify what I said at the time so I figure I may as well take this opportunity to do so.

What is Design?

It strikes me that the big problem lies in the ambiguity of the word 'design' as it applies to programming. No one can envision how an entire application of any significance will be written ahead of time, so we break applications up into smaller problems which we can solve separately. Fundamentally that's what the word 'design' refers to: This process of cutting the thing up into smaller pieces: One wouldn't swallow an entire meal in one gulp. Instead there are separate courses and plates, and in turn we cut the food into bite-sized morcels.


One important part of this design process is separating the algorithm from the implementation. The 'algorithm' refers to the aspect of the solution to a problem that is independent from the code you need to write. It's even independent from any specific programming language. It's the over-all approach you're using to solve that problem. Let's say you want to write some code to fill a shape with a particular color, or sort a very large data-set, or encrypt a file, or calculate the odds of winning for a given poker hand. These tend to be the kinds of problems where you can't readily start writing code hoping to stumble toward the solution one step at a time. You have to start with some kind of plan. The algorithm is that plan. In some cases the algorithm has to be validated in a very formal mathematical kind of way. Cryptography is a good example. It doesn't matter that the average person can't decypher a scrambled message without the key. This kind of code generally has to stand up to a determined and sophisticated attacker and you have to know the boundaries where this algorithm will stop being effective. In other cases you just need to get the general idea and that's probably good enough to begin coding: A simple flood-fill may be a good example of that. In fact it's often the case that if you becom familiar enough with a given domain, you don't need to explicitely define algorithms ahead of time at all. If you have enough experience you know roughly what you'll need to do and you can be confident that you'll work out the details as you go along. It's important to realize that deep down you still usually have an algorithm in the back of your mind as you begin to write code, even though you may not be fully conscious of it.

Hill Climbing:

You want to climb to the top of a hill but you've never done it before. Instead of worrying about the entire route, you pick a place up the hill you're pretty sure you can reach. Once you get there, you have a look around and decide how to get a bit father up still, etc. Instead of solving the entire problem, you come up with a simpler version or part of the problem that you have some confidence you can deal with. You write some code to solve that aspect of the problem. Then you see if you can take the next step toward a solution. You may have to backtrack several times as you go along, but this can be an effective strategy. Hill-climbing has the advantage that solving a part of a problem may make the rest much clearer, and actually working on real code can free you from the mental paralysis that can come from simply staring too long at a piece of paper and thinking really hard. However, a hill-climbing approach can easily lead to a dead end: Once you've exhausted all of the code needed to develop the fairly obvious aspects of what you are trying to do, there is no clear way to take the next step. That's where algorithmic thinking is required, and the solution, once you have it, may be conceptually different enough that you may have to throw away much of the code you wrote earlier.

Where does TDD Fit?

TDD is a technique to help you write better code. Since TDD is about the code, it's important to realize that it is generally not about helping you to develop algorithms. It's mostly about the implementation part of the algorithm-implementation pairing at the heart of programming. That is what I meant when I wrote in my earlier post that TDD is not an algorithm generator. There's a lot more to writing an application than knowing about algorithms. Your code has to work correctly for one thing! Donald Knuth had a famous comment for a piece of code he wrote: Beware of bugs in the above code; I have only proved it correct, not tried it. It also has to be maintainable, which means the it should readable and as self-documenting as possible, and also that it should be a free as possible from duplication. Your implementation also has to to be reasonably efficient. If the way you implement your algorithm is too slow, that's also a problem (sometimes the algorithm itself is at fault and needs to be replaced too).

TDD allows you to write code one step at a time. The general idea is that you set up some initial conditions for your test, then you call a some function (which you haven't written yet), and finally you write some assertions to make sure that function did the right thing. Having done that much, you fill in the code for that function. This type of approach lets you think about the shape of your code without the distraction of worrying about the details of how to make it work. Shaping the code is also a part of the design process, and often that's where some confusion sets in. Some people are referring to the way the code is organized when they talk about design (the classes, methods, functions, data structures, etc) and other are focusing on the algorithmic aspects. If TDD means Test Driven Design, then it's the code-shaping meaning of design that it mainly refers to.

Backstopping each piece of code you write with a test allows you to achieve the following objectives: 1) Make sure your code is doing what you want it to - particularly to confirm edge cases are being handled properly; This lets you have more confidence in the code you're writing and prevents you from having to wait 'til an entire chunk of functionality is finished before testing it to see if it actually works; 2) Assist you in thinking about how you want your code organized without concomitantly worrying about implementation; 3) Develop a regression suite that will flag changes you may make later on that break the tests 4) Provide a form of executable documentation (one that won't go stale) that will help people (including yourself!) who read the code later on understand your intentions.

TDD and Hill Climbing:

If you don't understand a problem very well to begin with, hacking code naively one test at a time is not very likely to work, as can be seen in Ron Jeffries attempts to solve Sudoku using that very approach.


Hill climbing, writing the code so as to take one step toward the end goal at a time, works well enough when you have a pretty good idea of where you're going. However, for harder problems it's easy enough to reach a dead-end where there is no obvious next step. Undertaking a hill-climbing approach blindly without adequate preparation means you may spend a lot of time writing code that will only lead you to an impasse. In the domain of business programming there is not a lot of algorithmic complexity. Most of the time the complexity in business programming arises from requirements that are often rather arbitrary and from working with large amounts of data. Developing such applications successfully isn't easy, but the difficulty tends not to be mathematical in nature: It's more like tax law, if you will, with all of its intricacies and exceptions, than like quantum field theory. Using TDD to backstop a mostly hill-climbing strategy tends to work reasonably well for such applications. When problems become more algorithmic/mathematical, algorithmic thinking becomes necessary. You need to consider such problems as a whole and come up with an over-all strategy to solve them. A naive step-at-a-time approach usually doesn't work well in such cases, and it becomes necessary to work things out ahead of time. A combination of both approaches generally works best for most applications, though the balance between the two will obviously vary from one app to another. Success in developing good software lies in the ability to find this balance.


Ravi said...

I find myself agreeing with most fo what you say after reading your email, which did clarify some things.

Ravi said...

the latest version reads much better!

Surge said...

Trial and error is NOT the way to find yourself in the world. It is a good way to learn, if you have the time and patience for it but it is not for todays business world. Leave the hill-climbing to the kids that have the time for play. Good post, thanks.