Extreme Enthusiasm

Know your stuff

A while ago we had a fun evening at the Milano XPUG writing a Sudoku solver. I blogged about my solution. I’m not particularly proud of it, in retrospect. The code and the tests are not obvious. I can’t read any of it and be certain that it works. It does not speak.

It is true that solving puzzles like Sudoku is quite different from what application programmers do everyday at work. Why is it that? The problems that we solve in business applications do not have that mathematical crispness that puzzles have. Perhaps it’s because we’re not good enough at analyzing them and expressing them abstractly. That would explain why business code is so long, convoluted and expensive.

Anyway, the point I want to make is that it is not satisfying to use the tests in TDD as a crutch for constructing hapazard code that, with a kick here and a few hammer blows there seem to work. The point of TDD is to *design* code; and a good design shows how and why a solution works.

I often see people doing katas that involve problems with well-known solutions. We usually disregard, forget, or ignore the well-known solution! And we keep writing tests and production code until we rig together something that passes the tests. It’s painful. I know. I too did some of that.

TDD does not work well when we don’t know what we’re doing. Some high-profile XPers failed to ship when TDDing their way with unfamiliar APIs or disregarding known solutions. TDD is no substitute for analyzing a problem, and finding abstractions that make it easy to solve. TDD without thinking and analyzing and abstracting is not fun!.

It’s for this reason that there is the XP practice of “spiking solutions”, that is, take time to learn how to do something, make experiments, then apply what you learned. If you know how to do things, you will not spend hours discussing with your pair; you and your pair will grab the keyboard from each other, as Francesco Cirillo often says.

A better way

Consider Sudoku again. Peter Norvig solves it in two different ways by using known techniques. The first solution is depth-first search, which is gueranteed to terminate as the graph of Sudoku states is acyclic. The other is by constraint propagation. If I were to do the exercise again, I would try to make the analysis apparent from the code.

Say we want to solve it by depth-first search. That entails two sub-problems:

• a) writing a depth-first algorithm
• b) writing something that enumerates legal moves in a given Sudoku board

I would start by testing the depth-first search algorithm. I would drive it with an abstract “tree” implementation. This means I could concentrate on the search algorithm without being distracted by the complex details of the Sudoku rules.

Then I would test-drive the generation of next-moves from a Sudoku position. That could also be done incrementally. Can we imagine a simplified Sudoku board? The full Sudoku is too complex for the first test! A year ago I would have started by defining a 9 by 9 array of numbers, but now the sheer boredom of defining it would stop me. Is there a better way?

Relax. Think. Dream.

Think about the game terminology. As Norvig says, the game is about units (either a row, a column or a box). A unit with no empty spaces has no descendant moves. A unit where a number is missing has the full unit as a descendant move. A unit where two numbers are missing… You get the point.

Then work out how to combine descendant moves of two units that share a square. Think a row and a column. If the common square is empty, than valid solutions for that square must be valid for both units…

The point is to work the problem incrementally. Try smaller scales first. Try 2×2 boards. Make the size of units and the board parametric. Add the constraint rules one by one, so that you can test them separately.

Conclusions

One important principle to apply is “separation of concerns”. Enumerating moves is a problem, and search strategy is another. By solving them separately, our tests become more clear and to the point. We gain confidence that we know how and why our code works.

Another way to see this is to decompose a problem in smaller problems; prove with tests that you can solve the subproblems, then prove with tests that you can solve the composition of the subproblems.

When you have a problem that is of fixed size 42, turn that constant into a parameter and solve the problem for N=1, N=2, … Imagine if the Sudoku board was 100×100 instead of 9×9; would you define a 100×100 matrix in your tests? Turning these constants into parameters make your code more general, your tests more clear, while making the problem *easier* to solve!

To summarize, what I think is important is

• Learn data structures, algorithms, known solutions, the proper way of doing things.
• Apply separation of concerns.
• Solving a slightly more general problem sometimes is much easier than solving the actual problem
• It’s more fun to work when you know what you’re doing!

Update

Charlie Poole recently posted this on the TDD mailing list (Emphasis is mine):

I’ve written elsewhere that I believe attempting to get TDD to “drive” the invention of a new algorithm reflects an incorrect understanding of what TDD is for.

TDD allows us to express intent (i.e. design) in a testable manner and to move from intention to implementation very smoothly – I know of no better way.

OTOH, you have to start out with an intent. In this context, I think that means you need to have some idea of the algorithm you want to implement. TDD will help you implement it and even refine the details of the idea. Writing tests may also inspire you to have further ideas, to deepen the ones you started with or to abandon ideas that are not working out.

Vlad Levin blogs thoughtfully:

one of the first rules I teach my students when I am doing a TDD workshop or teaching a course is precisely that TDD is not an algorithm generator! Solving sudoku is just the kind of problem you want to find an algorithm for first, then implement that algorithm

[…]

So what is the purpose of TDD then? One goal of TDD is to reduce the need to determine ahead of time which classes and methods you’re going to implement for an entire story. There’s a large body of shared experience in the developer community that trying to anticipate such things tends to lead to paralysis where nothing useful gets done and/or produces bloated, over-designed code. Instead, you can develop one aspect of the story at a time, using each test to keep yourself moving forward and refactoring the design as you go along

In a comment to my post about testing data serialization, Jacopo says:

well, if you’re lucky enough, both client and webservice will be under your control, so yes: focus on data (structure) sent/received, to be sure they’re as expected.

but is far more common a scenario where webservice aren’t under your control, they represent and integration point with external systems: that is, XML document syntax _is_ what you’re trying to test. for example, (I can think of at least 2 cases that happened to me in the last 6 months) switching from one parsing library to another or simply testing interoperabily (such as Java/.NET).

of course, not as much domain logic there ;) but still, webservices aren’t supposed to encapsulate domain knowledge, so focusing on syntax would be good enough.

Hi Jacopo,

Even in your case, the users of your service will be interested in doing something with your data, not in its syntax.

Consider this modified test: there’s an error in it, but it’s not easy to see.

@Test public static void serializesToCorrectXml() {
  DataStructure structure = new ....;
  XmlSerializer s = new XmlSerializer();
  String xml = s.serialize(structure);
  assertEquals("<?xml version=\"1.0\"><foo><bar>zot</bar></foo>",
    xml);
}

Can you see it? The xml prolog is broken. Now if your code passes this test, it will break in production with your paying customers.

Consider this other test:

@Test public static void serializesArray() {
  XmlSerializer s = new XmlSerializer();
  String xml = s.serialize(new String[] {"A", "B"});
  assertEquals("<list><el>A</el><el>A</el></list>", xml);
}

this one is also wrong, for a different reason. It’s syntactically valid, but does not contain the right information.

Even when I am not writing the client side, I would still write a client for my tests. The client should do something with my data that is similar to what a typical real client would do. At the very least, it should parse the XML to make sure it’s valid! That would take care of the first broken test. Then I would make the client extract the information from the serialized form, and make sure it contains the same information.

@Test public static void serializesArray() {
  String [] anArray = { "A", "B" };
  XmlSerializer s = new XmlSerializer();
  XmlClient c = new XmlClient();
  String xml = s.serialize(anArray);
  
  assertArrayEquals(anArray, c.parse(xml).toStringArray());
}

Another thing that happened when I was last coaching a team on XP techniques. We were working on a real application, and one thing that we had to do was to serialize a data structure to XML for publishing on a web service. There are a ton of different ways to do that, but whatever you do, don’t write tests like this:

@test public static void serializesToCorrectXml() {
  DataStructure structure = new ....;
  XmlSerializer s = new XmlSerializer();
  String xml = s.serialize(structure);
  assertEquals("<?xml version=\"1.0\"?><foo><bar>zot</bar></foo>", 
    xml);
}

Can you see what’s bad with this code?

I can name a few things:

• It doesn’t scale. When the data structure grows, the xml string becomes big and difficult to handle
• It’s brittle. A tiny, insignificant difference in white space will break the test.
• It does not express intent. Look at the name of the test. We could not come up with anything better than this.

The crux of the matter is that we don’t care at all what the xml string is. What really matters is what we do with it, and in this case what we do is build the XML in one process, and reconstruct an equivalent data structure in another process. We should test that the behaviour works, not the details of an intermediate structure.

@test public static void serializesAndRebuildsFoobars() {
  DataStructure structure = new DataStructure("foo", "bar");
  XmlSerializer s = new XmlSerializer();
  XmlParser p = new XmlParser();
  
  assertEquals(structure, p.parse(s.serialize(structure)));
}

Now this tests the behaviour we’re interested in. Note that this test is robust, as changes of the intermediate representation will not break it. We don’t really even care what the serialized data type is: we could change it to byte array, or anything else, with no need to change this test.

This sort of tests supports incremental development. If my data structure was, for instance, a list, I could write a nice sequence of tests:

• serializesAndRebuildsEmptyLists
• serializesAndRebuildsSingletonLists
• serializesAndRebuildsListsOfManyElements
• …

One final note: let the pair who writes the serializer also write the parser. This will save a lot of arguments :-) Vertical slices of functionality always work best.

Last week I was traning a team on XP techniques. We tried the following exercise:

I want you people to build me a Swing application that computes the area of a square with a given side length.

I asked for an estimate. The devs were nervous, someone said “impossible!” :-) someone said 5 hours. I played the part of the project-manager-who-was-once-a-developer and said “come on, five hours?? I could do that in 10 minutes in my sleep. What’s so difficult about it”? Then I reasoned with them that if we keep our estimates too comfortable, our business opportunities may fly out of the window. They agreed on a 2 hours estimate.

They proceeded to implement the feature. The three devs rotated every 7 minutes. This was a good slot size; everyone was involved, even the junior one who is rarely given the keyboard. The feature was done in one and a half hour. Then I said

Cool. Now we need to compute the area of a triangle of a given base and height. How much time for this?

The devs estimated 1.5 hours. It was delivered on time. Now the fun part started. The team wrote the application in the “usual” way, by writing new code for the new window. No effort was spent, at this time, to reduce duplication. I pointed out that

We’re going to need to implement many more of these geometry formulae. Make it so that it is trivial to add others.

The team came up with a design where the Swing window object is generic and can be customized to support the input for any formula that requires a variable number of inputs with different names. They thought they could do it in 2 hours. It took 4. At some point we wasted a lot of time on Swing layouts, trying to fathom the mysteries of GroupLayout. I gave some help here. Then we were done! Stepping again in my role of customer I said

Very well. The next feature we need is to compute the area of a circle from the radius.

It was done in 10 minutes. The customer was very satisfied, and so were the devs.

What have we learned?

• I have learned the power of letting the team come up with their own design. It’s difficult for me, an xp-trainer-who-was-once-a-developer, to give up giving guidance on design. But time and again, I have seen the damage of doing so: the team follows my design, gets bogged down, does not learn.
• We have learned how hard it is to make the code easy to change. It would have been easy to declare we were “done” after the area of triangle was working. But we were not really “done” from the point of view of TDD. Remember, the cycle is red-green-REFACTOR, and by “refactor” what is really meant is “remove duplication”.
• Once you get to clean, refactored code, the cost of changes drops. And it’s a pleasure to work with!
• The decision to invest time in making the code generic might seem difficult. After all, you can get skilled at copy-pasting Swing code and writing many copies of the Swing form class. But then you are left with gobs of code. And good luck applying a different graphic layout to them all! My answer is that we should get skilled at writing flexible code. It took us 4 hours to make the code generic. Next time they have to do something similar, it will take less.

  Copying-and-pasting is a dead end; there is a limit at how skilled you can become at it, and there is certainly a big problem in the quality of the code you deliver. Learning to do good, clean, flexible code never ends. It’s a path where you can get to write better and better code. Which path would you rather be on?

Very cool, guys. This geometry app rocks!!

This is a subset of the Back to the Checkout kata by Dave Thomas, which I used many times as a TDD training exercise.

Suppose you have a PriceRules object that knows that the prices of items. Its responsibility is to know the following table:

Item	Unit Price	Special Price
A	50	3 for 130
B	30	2 for 45
C	20
D	15

Then you have a Cart object that knows which items a customer is trying to buy. For instance, a given cart could contain the list [A, A, C, A, D].

The problem is to compute the total that the customer has to pay, out of a collaboration between (at least) the cart and the pricerRules objects. It seems easy, but there is a catch: you are forbidden to use getters. All methods must return “void”, in Java terms. Design the messages that are exchanged between the objects and produce the desired result. (In the example, it would be 165). Have fun!

Bruno Rossi of the Bozen University will organize a followup to XP2010 on September 15 this year. I think this is a great opportunity for those who could not attend XP2010 in Norway. This conference will be much smaller and affordable.

I will submit something about Extreme Programming engineering techniques; nothing terribly new, just sharing some of my current understanding of these techniques.

I hope I will see you in Bolzano!

You learn math by solving problems. Problems frame the way you learn, give you a tangible proof that you’re progressing, give you a sense of meaning and achievement. How do you learn physics? By studying the books of course, but then solving physics problems is very important. How do you learn to play deep games such as chess or go? By playing, mostly. And then by pondering and solving problems. Electronics? Chemistry? Building science? Genetics? The books on these subjects are full of problems.

How do you learn good software design? I don’t know. The books that I’ve read explain principles, and provide examples. Rarely I’ve seen books that contain problems, exercises, or challenges. (Notable exceptions: William Wake’s Refactoring Workbook and Ka Iok Tong’s Essential Skills for Agile Development.)

I propose that we assemble a collection of problems meant to develop and discuss software design. A good problem for this goal would problem *not* have a single correct answer, for design and engineering are always a matter of compromises. A good problem should be a means to discuss the various choices and tradeoff, and worse and better ways to solve it. A good problem should be a small framework.

Let’s start! Here is a problem that I find interesting. The good old Fizz-Buzz problem goes like this:

Write a program that prints the numbers in order from 1 to 100, with the exception that when a number is a multiple of 3, it prints “Fizz”. When a number is a multiple of 5, it prints “Buzz”. And when a number is multiple of both, it prints “FizzBuzz”. In all other cases, it just prints the decimal representation of the number.

There is an obvious way to solve this exercise, of course. It’s a very simple problem, from the point of view of programming. I would have the student solve it however they like. Most solutions contain a 3-way IF. I would then ask students to remove duplication. Early XP books were strong on removing duplication, for a good reason. It takes a bit of training to see how much duplication can creep in even such a small bit of programming.

The usual objection I get at this point is that it makes no sense to go this deep in removing duplication for such a small and trivial example. They also will say that the 3-IFs version is more readable than any version where duplication is removed. This is the crux of the matter.

I then continue the exercise by adding the requirement that

For multiples of 7, the program prints “Bang”.

Easy, they say. Add a fourth IF. Not so fast, I say :-)

For multiples of 7 and 3, the program prints “FizzBang”. For multiples of 5 and 7, the program prints “BuzzBang”. For multiples of 3, 5, 7, the program prints “FizzBuzzBang”!

Now we have an exploding number of IFs. If the next requirement is of the same sort as this one, we see how the IF-chain solution becomes untenable :-) Now solve this!

Update:

• I got the idea of using FizzBuzz as a design example from Giordano Scalzo, who presented it at the Milano XPUG and posted a solution on slideshare
• Other sources of problems, in no particular order: the Refactoring to patterns book by Joshua Kerievsky. The list of katas by Dave Thomas. The Refactoring in Ruby book by William Wake and Mike Rutherford. The Ruby Quiz site. I’m not merely looking for programming problems. I’m looking for design problems. The difference is that I don’t just want a problem that requires a correct or efficient solution. I want a problem that requires a solution that is easy to understand and change.

I read this interview by Bill Wake to an Ukrainian coach, and he raises a very important point that I find it difficult to get right :-)

WW – I’m interested in things you do, behaviors you have, whether you think of them as coaching or programming.

AK – I was at a position in my life where I stopped being a traditional team lead and turned myself into a ScrumMaster. It’s hard to do, because you get used to proposing your ideas and believing that you’re smarter than other people. Instead you have to start believing that the team can make up better ideas themselves. You make yourself stop talking and just ask questions. This is a hard thing to achieve.

Alexey Krivitsky, interviewed by William Wake