Agile Zone is brought to you in partnership with:

I am a programmer and architect (the kind that writes code) with a focus on testing and open source; I maintain the PHPUnit_Selenium project. I believe programming is one of the hardest and most beautiful jobs in the world. Giorgio is a DZone MVB and is not an employee of DZone and has posted 637 posts at DZone. You can read more from them at their website. View Full User Profile

TDD for algorithms: the state of the art

01.13.2011
| 11814 views |
  • submit to reddit

Uncle Bob's recent formalization of the Transformation Priority Premise may improve the ability to build an algorithm with Test-Driven Development.

In his example, Uncle Bob follows strict rules of evolution in his code for implementing sorting, and finally reaches quicksort instead of bubblesort. If you don't remember, a criticism of TDD is that it accepts naive solutions like bubblesort: it is normal trying to Test-Driven Development an ordering algorithm, and ending up with bubblesort or insertion sort, which have O(n^2) computational complexity, far from the optimum O(N logN), the boundary for comparison sorts.

I've yet to apply the Transformation Priority Premise on a real world problem however, and I'm waiting for independent confirmations. Today we will discuss about what goals you can reach with Test-Driven Development, by also citing some insightful references. We are trying to learn if TDD is useful for creating algorithms, or only as a discipline for coding something we already know how to do.

There has been a recent comparison of the two different Test-Driven Development schools: The Classic versus London TDD describes the classic school as an attempt to discover algorithms with incremental testing, while the London school always starts from a big picture, like an entire application.

When Classic TDD is illustrated, it's usually an example where an algorithm is fleshed out one test at a time. For example, if test-driving an implementation of, say, a program that converts integers into roman numerals, we might start with the simplest test "roman numeral for 1 is I". The simplest solution might be to return the hardcoded literal value "I". Then we move on to the next easiest failing test.

The dichotomy has been described as a fallacy as both styles are necessary during development: the Classic style for small, reusable parts, the London one for acceptance and integration testing.

However, it has been pointed out that practitioners of the Classic style often draws on tacit design knowledge, for example in the article Making too much of TDD by Michael Feathers:

The emergent design meme, for better or worse, became intimately woven into Test Driven Development.  We found that, in the small, you could start developing a system without having a plan for its design, and, through the application of a set of rules and some reflection, arrive at very good designs.  When I think back about this, I call this the "Look ma, no hands!" era of TDD.  Critics would rightly point out that people who were doing this well were drawing on a lot of tacit knowledge of good design.  For the most part, we agreed.  We just felt that this knowledge of good design could be taught, and people could make continuous decisions across the development cycle to grow good design organically.  You do have to bring your design knowledge to the table.  Red/Green/Refactor is a generative process, but it is extremely dependent upon the quality of our input.

My take on this is that actually producing reusable algorithms is the job of the computer scientist or operations researcher; our job is to implement published algorithms, and to reuse existing implementations if they are too complicated (@xpmatteo would make the example of cryptography), without tying too much our design to libraries and frameworks.

What if we don't know how to make a test pass?

A personal experience of mine, for example, comes from Matlab and algorithms for multimedia algorithms like Harris or Canny feature detection, used to find interesting points on images. Apart from the difficulty of testing their results and defining them beforehand, they're difficult to code by incremental improvements too; however, when you can, you learn why the algorithms works in this way. A much better choice than barely memorizing it. The same could be said of sorting algorithms: after that old lesson in college, we often forget why quicksort and mergesort are faster.

Thus TDD is a tool for design, because it forces to define and focus on an interface rather than an implementation. But if you do not know how to design, listening to your tests will be painful as they would scream and either be ignored, or halt the development because you do not know how to fix the situation, and return to easy tests.

A hammer (what an overused metaphor) is useful, but if you start throwing it around, not knowing how to hit the nail, you will make more harm than benefit. That's why I write and write about patterns both for the production code and the testing code: they're a step above the single class in design. With TDD you can easily develop a single class, but won't feel pain very much even after having put some hundred lines in it. When it comes to divide the work in multiple classes, your spidey design sense should be start tickling, and instantly see if some pattern applies or it would be a bad idea.

Uncle Bob made the right point again on TDD a while ago, in a quote which I printed and hanged in my office:

Look, TDD is not my religion, it is one of my disciplines. It’s like dual entry bookkeeping for accountants, or sterile procedure for surgeons. Professionals adopt such disciplines because they understand the theory behind them, and have directly experienced the benefits of using them.

Like Jack in Lost, you can operate without the right environment in emergency conditions or when time is very short (for example, a bomb will go off if you do not compile something in the next minute). But will it be less or more difficult? Will it be safer? Will it be desiderable for the patient?

Surgeons follow strict procedures due to the risks involved, without inventing as they go along (I dare you to accept an emergent design for your bypass). But should you invent when doing development? I mean, how can you estimate how long will it take to prepare an application if you do not know how to code it? You do not know which pattern you will be using, how many classes there will be in this package, or what fields should the objects have. And that's right: it's far more flexible to decide this constraints after having got feedback from the code. But usually you have all the knowledge and experience necessary for making these choices.

Now imagine you're told to prepare an application that performs face recognition. Will you start from a test? Maybe, but it will stay red for a long time. In that case, after defining what I want with some informal user stories, I will start doing spikes, exploratory testing and walking skeletons to learn more about the problem.

Spikes are not test-driven, while walking skeletons have tests written on a very high-level and to test a design which is already fleshed out (in fact, they're used to discover if an architecture can work).

Only when I'm confident that I can make a test pass, I write it. But I have a rule: anything that goes under source control should be tested.

Conclusion

My final thought is that during development, the solution space is very large and there is an infinite amount of code which solves your problem. TDD drives us towards a solution which is maintainable, presents a good Api (since the test is its first example of client code) and minimal because you can easily try to delete a line of code and see if the tests are still green. TDD is desiderable, but you cannot think that by following blindly the Red-Green-Refactor cycle you will end up with a full-fledged application. It's only the basic workflow: you still have to do the thinking, and to gain the knowledge necessary.

In short, this is the line I would try to follow: to make this test pass. should I use a Map or a List? Uhm, first I have to learn what a Map and a List are, and the difference between them. Let's open a data structures book. I don't know how to make this test pass, and maybe after some experimentations and research I will have learned more; I will be able to write a better test, and to actually get to green.

Let me know what you think about developing algorithms with or without TDD in the comments.

Published at DZone with permission of Giorgio Sironi, author and DZone MVB.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Ronald Miura replied on Thu, 2011/01/13 - 6:46pm

The problem with Uncle Bob is that, although he says TDD is not his religion, when he talks about TDD it sounds too much like religious preaching.

He uses the analogy of surgeons washing their hands, but the way he talks about TDD, it's as if mastering 'the art of washing hands' is the single most important skill you could ever acquire as a surgeon.

I'd rather pick one skilled with the scalpel.

Giorgio Sironi replied on Fri, 2011/01/14 - 4:34am in response to: Ronald Miura

Thank for your feedback, there is much controversy on what TDD can be used for lately. I find the washing hands comparison fine: even if you have a skilled surgeon, which operates you perfectly, if he is not clean you'll eventually get an infection. I did not gone to medical school, but if I remember correctly washing hands (intended as overall hygiene on the surgery) is a simple practice which has highly raised the safety of surgery in the last centuries.

Loren Kratzke replied on Fri, 2011/01/14 - 2:45pm in response to: Giorgio Sironi

I still maintain that tests are best for locking down functionality as opposed to implementing functionality. TDD is totally cart-before-the-horse.

In the past I used a test harness to bootstrap a code module belonging to a larger system. In electronics manufacturing I used a test jig designed to test circuit boards that were already manufactured. In music I used a metronome and scratch tracks as opposed to designing an album cover. In construction I used concrete forms as opposed to hanging curtains in a vacant lot and noting that I needed more building materials. In masonry I stretched a string to lay bricks level as opposed to using a level that told me I needed more bricks. In accounting I would enter numbers into the books (at the END of the day as opposed to the begining of the day). In the sign shop I would prep the sign for lettering on a bench as opposed to 20 feet in the air and standing in a parking lot saying the sign needs more letters.

I am telling you, TDD is not a sustainable pattern. It is little more than a fetish and is downright moronic when applied to anything real-world in my experience.

Roger Lindsjö replied on Fri, 2011/01/14 - 5:01pm in response to: Loren Kratzke

Aren't most of these examples of TDD? Metronome: A test that helps you follow the correct beat. An other option would be to record without it and the check if you kept the beat.
In construction: The concrete form is your test that makes it (very) easy to shape your result. Did any of your final customers order a form? Or just a specific shape out of concrete?
The stretched string in masonry is also a test first, you first stretch the string to guide you in laying the bricks.

I think TDD is a very useful tool, but of course it does not make a bad developer good. Referring to your previous examples, have you ever seen a mason lay more than a handful of brick with out using a tight string to guide the work? However, using a tight string does in no way guarantee that the result will be good.

Loren Kratzke replied on Fri, 2011/01/14 - 7:55pm in response to: Roger Lindsjö

Well, I can't prevent you from making these correlations but one must admit that they are a stretch :-) That being said, what isn't a test? Perhaps this question will yeild a shorter list.

Giorgio Sironi replied on Sun, 2011/01/16 - 6:41am

In my mind, TDD is about getting immediate feedback on the code we write, by defining an executable specification even before we start writing it (in order to get feedback also on the Api). It broke down in some of my examples because while developing new algorithms, you don't yet know what they can do (for example, detection of lines in an image) and so preparing a concise specification like a unit test is... tricky.

Roger Lindsjö replied on Wed, 2011/01/19 - 3:24am in response to: Loren Kratzke

They might be a stretch, always hard to compare different fields. However, what i tried to convey was that in many fields some kind of "test" is set up before doing the implementation to guide and to prevent going to far astray.
My father is a mechanic and I don't ever see him working for long period of times without testing of some sort (measuring, fitting etc), and in many cases fixtures are made before producing the end result. Still, I see developers that never do tests before the fact, and if they do the tests after, the tests are infrequent. Coding can be going on for hours (even days) before checking if the code does what was expected. And at that point often quite a bit of more work is needed even though the code was "done".

As for what isn't a test, not much I think. Our whole life is built around tests, but again, for some reason even professional programmers put off testing even though we are working in environment where testing can be inexpensive. If you were building a house, could you imagine cutting wood and nailing it together for hours or days, looking at the blueprint, but never once bringing out your measuring tape?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.