TDD should be an algorithm generator

TDD should be an algorithm generator 23:37 Tuesday the 22nd of May 2007 8 Comments

It all began when Ravi Mohan invited his readers to compare Ron Jeffries and Peter Norvigs attempts at building a Soduku solver. You really should read both attempts, as they are very educational, but to save time its pretty clear that Norvig wins by a wide margin. Many Test Driven Development fans took umbrage at the comparison and rushed to Rons defence. The most eloquent argument in Rons defense I have found is Vlad Levins "TDD is not an algorithm generator". While well written Vlads argument rings hollow to me, he seems to believe that an "Algorithm" is not normal code, that it is some sort of special case, and as such TDD is not the tool of choice as it is everywhere else.

Well, first lets ask , what is an algorithm?

Wikipedia's definition of Algorithm:

In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a defined end-state.

A finite list of well-defined instructions, this sounds like software. The definition is all embracing with little room for exceptions and special cases . There are well known and commonly used algorithms, such as QuickSort, that get taught in "Algorithms" Courses in "Algorithms" text books. But the truth of the matter is all code implements an algorithm of some sort. Those found in the text books are simply a list of algorithms that are generally useful in many projects, and so are worth teaching and passing on. When we develop something new, we take some of the well known algorithms, and mix them with something new, algorithms of our own creation.

TDD is presented as resulting in better more reliable code, which translates to better more reliable algorithms. And the contrast between Norvigs and Jeffries results shows that this is simply not the case. The cry of "Not an algorithm generator" is equivalent to saying you should not use TDD to write code if you don't already know how you are going to write it, if you are trying to solve a difficult problem for the first time do not use TDD.

I do not actually believe this to be the case. I am a fan of TDD and use it whenever possible, However I am also not adverse to sitting back and mulling over a problem for an hour or two in the middle of coding, call that design up front if you will, but Norvigs solution proves that this can also generate good results.

The real problem here is that TDD generated obviously inferior results in this case, and while Norvig did well, he did not provide a Methodology, after reading Norvigs article I know how to solve sodoku, but I dont think I can solve a completely different problem in a Norvig like fashion.

This is a challenge not only to TDD, but to the Norvigs of this world too. If TDD on its own cannot be relied upon to provide great results then there is something we are missing. Perhaps Agile needs a new practice, perhaps the Norvigs of this world need to document their thinking practices. I don't care where the answer comes from, but I want someone to teach me to think like Norvig.

Add Comment

Comments

Hoping for TDD to be an algorithm generator is saying that there should be some mechanical way to make problem solving in general easy. There's obviously *no* known way to do this, else we would all be geniuses. The best one can hope for now is to learn heuristics and get more experience in one's area of work.

Vladimir Levin 17:38 Wednesday the 23rd of May 2007

Oh, as for algorithm, an algorithm is really the knowledge of how to solve a given problem. Code ought to be written so it is maintainable, which is different from just solving a problem. Would you enjoy maintaining a piece of code if you only had the binary? Of course the binary has all the information you need, but for any reasonable problem is is effectively useless. That's the essential difference.

Vladimir Levin 17:39 Wednesday the 23rd of May 2007

Hi Vladimir, Nice to see you here. As regards a mechanical way to make problem solving in general easy, it would be smashing wouldn't it? I believe its fair to say that TDD and other methodologies do present themselves as the heuristics in question (and as they go , its a pretty good heuristic). I am not anti TDD, I simply believe that we have a long way to go. I am not quite sure that I am following you with regard to your point on maintainability. If you are suggesting that code is not an algorithm because you can implement "An Algorithm" several different ways in code, Then there is certainly something to be said for that. But I would wonder if they really counted as the same algorithm, the different implementations would strike me as separate members of the same family of algorithm.

Sean O'Donnell 17:40 Wednesday the 23rd of May 2007

Hi Sean! Hmmm, I guess we are getting into philosophy a little bit. Maybe it's just a matter of terminology. To my way of seeing things, an algorithm is a rather platonic sort of thing. It is the essence of how to solve a problem. For example, You can implement a quicksort algorithm, and so can I. Our code, even if it's written in the same programming language, would not be identical, but it would still be recognizable as quicksort, no?

Vladimir Levin 17:41 Wednesday the 23rd of May 2007

I do believe that we are descending into the dark and muddy waters of philosophy, but its good fun so lets carry on :) I think I am understanding where you are coming from now. If I follow you correctly, your argument is that the structure of code can be completely separated from its function. And TDDs value lies in giving good structure to code. I hope I am not setting up a straw man by expressing it so, but thats my interpretation of what you are saying so far. There is a certain amount of truth to it. But I don't think the separation can be made so cleanly. Even the tests we write reveal the truth of the matter. They do not test structure, modularity and separation of concerns as often as they test raw functionality, the results of executing the algorithm. The average test will not check if a sorting algorithm is nicely refactored I would agree that two pieces of code could be both be regarded as a quicksort, but then to take it higher up in abstraction, two pieces of code can be regarded as web browsers. I think the number of expressions of quicksort that result in an identical series of instructions being executed would be small, and if the instructions executed are different, then while the solutions may belong the the quicksort family, they are unique in their own right. If you regard such distinctions as being irrelevant, then fair enough.

Sean O'Donnell 17:42 Wednesday the 23rd of May 2007

My Blog seems to be having some troubles with long comments at the moment, so I am continuing here. I believe TDD will usually make a good coder better. But I would rather be a Norvig learning TDD than vice versa. Norvig unfortunately is like a stage magician, he dazzles and then disappears in a puff of smoke leaving the audience unable to replicate his feat. Ron has at least allowed us a peek in his bag of tricks.

Sean O'Donnell 17:43 Wednesday the 23rd of May 2007

Hi Sean, I guess the way I generally look at it, an algorithm is to code as a recipe is to a cake. Having the recipe is important, but you still have to bake the cake. I figure coding using TDD is analogous to actually preparing ingredients and doing all of the work of baking.

Vladimir Levin 17:44 Wednesday the 23rd of May 2007

I've been known to write my fair share of TDD code, but in the 1% of times when I need a funky algorithm, I just ask the smart guy on the team to design a funky algorithm - not via TDD. Works for me.

Steve Q 17:46 Wednesday the 23rd of May 2007