MyStack isn’t a great name, but it avoided the name collision. Now that MyStack is declared in the stack package, let’s change it back to Stack. That took 15 seconds. The tests still pass.

Click here to view code image

// T:01:09 StackTest.java
public class StackTest {
  @Test
  public void canCreateStack() throws Exception {
    Stack stack = new Stack();
  }
}

// T: 01:09 Stack.java
package stack;

public class Stack {
}

Here we see another rule: red → green → refactor. Never miss an opportunity to clean things up.

Rule 2: Make it fail. Make it pass. Clean it up.

Writing code that works is hard enough. Writing code that works and is clean is even harder. Fortunately, we can break the effort up into two steps. We can write bad code that works. Then, if we have tests, we can easily clean up the bad code while keeping it working.

Thus, every circuit around the TDD loop, we take the opportunity to clean up any little messes we might have made.

You may have noticed that our test does not actually assert any behavior. It compiles and passes but asserts nothing at all about the newly created stack. We can fix that in 15 seconds:

Click here to view code image

// T: 01:24 StackTest.java
public class StackTest {
  @Test
  public void canCreateStack() throws Exception {
    Stack stack = new Stack();
    assertTrue(stack.isEmpty());
  }
}

The second law kicks in here, so we’d better get this to compile:

Click here to view code image

// T: 01:49
import static junit.framework.TestCase.assertTrue;

public class StackTest {
  @Test
  public void canCreateStack() throws Exception {
    Stack stack = new Stack();
    assertTrue(stack.isEmpty());
  }
}

// T: 01:49 Stack.java
public class Stack {
  public boolean isEmpty() {
    return false;
  }
}

Twenty-five seconds later, it compiles but fails. The failure is intentional: isEmpty is specifically coded to return false because the first law says that the test must fail—but why does the first law demand this? Because now we can see that our test fails when it ought to fail. We have tested our test. Or rather, we have tested one half of it. We can test the other half by changing isEmpty to return true:

// T: 01:58 Stack.java
public class Stack {
  public boolean isEmpty() {
    return true;
  }
}

Nine seconds later, the test passes. It has taken 9 seconds to ensure that the test both passes and fails.

When programmers first see that false and then that true, they often laugh because it looks so foolish. It looks like cheating. But it’s not cheating, and it’s not at all foolish. It has taken mere seconds to ensure that the test both passes and fails as it should. Why in the world would we not do this?

What’s the next test? Well, we know we need to write the push function. So, by Rule 1, we write the test that forces us to write the push function:

Click here to view code image

// T 02:24 StackTest.java
@Test
public void canPush() throws Exception {
  Stack stack = new Stack();
  stack.push(0);
}

This doesn’t compile. By the second law, then, we must write the production code that will make it compile:

Click here to view code image

// T: 02:31 Stack.java
public void push(int element) {

}

This compiles, of course, but now we have another test without an assertion. The obvious thing to assert is that, after one push, the stack is not empty:

Click here to view code image

// T: 02:54 StackTest.java
@Test
public void canPush() throws Exception {
  Stack stack = new Stack();
  stack.push(0);
  assertFalse(stack.isEmpty());
}

This fails, of course, because isEmpty returns true, so we need to do something a bit more intelligent—like create a Boolean flag to track emptiness:

Click here to view code image

// T: 03:46 Stack.java
public class Stack {
  private boolean empty = true;

  public boolean isEmpty() {
    return empty;
  }

  public void push(int element) {
    empty=false;
  }
}

This passes. It has been 2 minutes since the last test passed. Now, by Rule 2, we need to clean this up. The duplication of the stack creation bothers me, so let’s extract the stack into a field of the class and initialize it:

Click here to view code image

// T: 04:24 StackTest.java
public class StackTest {
  private Stack stack = new Stack();

  @Test
  public void canCreateStack() throws Exception {
    assertTrue(stack.isEmpty());
  }

  @Test
  public void canPush() throws Exception {
    stack.push(0);
    assertFalse(stack.isEmpty());
  }
}

This requires 30 seconds, and the tests still pass.

The name canPush is a pretty bad name for this test.

Click here to view code image

  // T: 04:50 StackTest.java
  @Test
  public void afterOnePush_isNotEmpty() throws Exception {
    stack.push(0);
    assertFalse(stack.isEmpty());
  }

That’s better. And, of course, it still passes.

Okay, back to the first law. If we push once and pop once, the stack should be empty again:

Click here to view code image

// T: 05:17 StackTest.java
@Test
public void afterOnePushAndOnePop_isEmpty() throws Exception {
  stack.push(0);
  stack.pop()
}

The second law kicks in because pop doesn’t compile, so

// T: 05:31 Stack.java
public int pop() {
  return -1;
}

And then the third law allows us to finish the test:

Click here to view code image

// T: 05:51
@Test
public void afterOnePushAndOnePop_isEmpty() throws Exception {
  stack.push(0);
  stack.pop();
  assertTrue(stack.isEmpty());
}

This fails because nothing sets the empty flag back to true, so

// T: 06:06 Stack.java
public int pop() {
  empty=true;
  return -1;
}

And, of course, this passes. It has been 76 seconds since the last test passed.

Nothing to clean up, so back to the first law. The size of the stack should be 2 after two pushes.

Click here to view code image

// T: 06:48 StackTest.java
@Test
public void afterTwoPushes_sizeIsTwo() throws Exception {
  stack.push(0);
  stack.push(0);
  assertEquals(2, stack.getSize());
}

The second law kicks in because of the compile errors, but they are easy to fix. We add the necessary import to the test and the following function to the production code:

// T: 07:23 Stack.java
public int getSize() {
  return 0;
}

And now everything compiles, but the tests fail.

Of course, getting the test to pass is trivial:

// T: 07:32 Stack.java
public int getSize() {
  return 2;
}

This looks dumb, but we have now seen the test fail and pass properly, and it took only 11 seconds. So, again, why wouldn’t we do this?

But this solution is clearly naive, so by Rule 1, we modify a previous test in a manner that will force us to write a better solution. And, of course, we screw it up (you can blame me):

Click here to view code image

// T: 08:06 StackTest.java
@Test
public void afterOnePushAndOnePop_isEmpty() throws Exception {
  stack.push(0);
  stack.pop();
  assertTrue(stack.isEmpty());
  assertEquals(1, stack.getSize());
}

Okay, that was really stupid. But programmers make dumb mistakes from time to time, and I am no exception. I didn’t spot this mistake right away when I first wrote the example because the test failed just the way I expected it to.

So, now, secure in the assumption that our tests are good, let’s make the changes that we believe will make those tests pass:

Click here to view code image

// T: 08:56
public class Stack {
  private boolean empty = true;
  private int size = 0;

  public boolean isEmpty() {
    return size == 0;
  }

  public void push(int element) {
    size++;
  }

  public int pop() {
    --size;
    return -1;
  }

  public int getSize() {
    return size;
  }
}

I was surprised to see this fail. But after composing myself, I quickly found my error and repaired the test. Let’s do this:

Click here to view code image

// T: 09:28 StackTest.java
@Test
public void afterOnePushAndOnePop_isEmpty() throws Exception {
  stack.push(0);
  stack.pop();
  assertTrue(stack.isEmpty());
  assertEquals(0, stack.getSize());
}

And the tests all pass. It has been 3 minutes and 22 seconds since the tests last passed.

For the sake of completeness, let’s add the size check to another test:

Click here to view code image

// T: 09:51 StackTest.java
@Test
public void afterOnePush_isNotEmpty() throws Exception {
  stack.push(0);
  assertFalse(stack.isEmpty());
  assertEquals(1, stack.getSize()); 
}

And, of course, that passes.

Back to the first law. What should happen if we pop an empty stack? We should expect an underflow exception:

Click here to view code image

// T: 10:27 StackTest.java
@Test(expected = Stack.Underflow.class)
public void poppingEmptyStack_throwsUnderflow() {
}

The second law forces us to add that exception:

Click here to view code image

// T: 10:36 Stack.java
public class Underflow extends RuntimeException {
}

And then we can complete the test:

Click here to view code image

// T: 10:50 StackTest.java
@Test(expected = Stack.Underflow.class)
public void poppingEmptyStack_throwsUnderflow() {
  stack.pop();
}

This fails, of course, but it is easy to make it pass:

// T: 11:18 Stack.java
public int pop() {
  if (size == 0)
    throw new Underflow();
  --size;
  return -1;
}

That passes. It has been 1 minute and 27 seconds since the tests last passed.

Back to the first law. The stack should remember what was pushed. Let’s try the simplest case:

Click here to view code image

// T: 11:49 StackTest.java

@Test
public void afterPushingX_willPopX() throws Exception {
  stack.push(99);
  assertEquals(99, stack.pop());
}

This fails because pop is currently returning -1. We make it pass by returning 99:

// T: 11:57 Stack.java
public int pop() {
  if (size == 0)
    throw new Underflow();
  --size;
  return 99;
}

This is obviously insufficient, so by Rule 1, we add enough to the test to force us to be a bit smarter:

Click here to view code image

// T: 12:18 StackTest.java
@Test
public void afterPushingX_willPopX() throws Exception {
  stack.push(99);
  assertEquals(99, stack.pop());
  stack.push(88);
  assertEquals(88, stack.pop());
}

This fails because we’re returning 99. We make it pass by adding a field to record the last push:

Click here to view code image

// T: 12:50 Stack.java
public class Stack {
  private int size = 0;
  private int element;

  public void push(int element) {
    size++;
    this.element = element;
  }

  public int pop() {
    if (size == 0)
      throw new Underflow();
    --size;
    return element;
  }
}

This passes. It has been 92 seconds since the tests last passed.

At this point, you are probably pretty frustrated with me. You might even be shouting at these pages, demanding that I stop messing around and just write the damned stack. But actually, I’ve been following Rule 3.

Rule 3: Don’t go for the gold.

When you first start TDD, the temptation is overwhelming to tackle the hard or interesting things first. Someone writing a stack would be tempted to test first-in-last-out (FILO) behavior first. This is called “going for the gold.” By now, you have noticed that I have purposely avoided testing anything stack-like. I’ve been focusing on all the ancillary stuff around the outside of the stack, things like emptiness and size.

Why haven’t I been going for the gold? Why does Rule 3 exist? Because when you go for the gold too early, you tend to miss all the details around the outside. Also, as you will soon see, you tend to miss the simplifying opportunities that those ancillary details provide.

Anyway, the first law has just kicked in. We need to write a failing test. And the most obvious test to write is FILO behavior:

Click here to view code image

// T: 13:36 StackTest.java
@Test
public void afterPushingXandY_willPopYthenX() {
  stack.push(99);
  stack.push(88);
  assertEquals(88, stack.pop());
  assertEquals(99, stack.pop());  
}

This fails. Getting it to pass will require that we remember more than one value, so we should probably use an array. Let’s rename the field to elements and turn it into an array:

Click here to view code image

// T: 13:51 Stack.java
public class Stack {
  private int size = 0;
  private int[] elements = new int[2];

  public void push(int element) {
    size++;
    this.elements = element;
  }

  public int pop() {
    if (size == 0)
      throw new Underflow();
    --size;
    return elements;
  }
}

Ah, but there are compile errors. Let’s tackle them one by one. The elements variable in push needs brackets:

Click here to view code image

  // T: 14:01 Stack.java  
  public void push(int element) {
    size++;
    this.elements[] = element;
  }

We need something to put into those braces. Hmmm. There’s that size++ from the previous snippets:

Click here to view code image

  // T: 14:07 Stack.java  
  public void push(int element) {
    this.elements[size++] = element;
  }

There’s the elements variable in pop too. It needs braces:

  // T: 14:13  
  public int pop() {
    if (size == 0)
      throw new Underflow();
    --size;
    return elements[];
  }

Oh look! There’s that nice --size we could put in there:

  // T: 14:24  
  public int pop() {
    if (size == 0)
      throw new Underflow();
    return elements[--size];
  }

And now the tests pass again. It has been 94 seconds since the tests last passed.

And we’re done. Oh, there’s more we could do. The stack holds only two elements and does not deal with overflows, but there’s nothing left that I want to demonstrate in this example. So, consider those improvements an exercise for you, my reader.

It has taken 14 minutes and 24 seconds to write an integer stack from scratch. The rhythm you saw here was real and is typical. This is how TDD feels, regardless of the scope of the project.

Exercise

Implement a first-in-first-out queue of integers using the technique shown previously. Use a fixed-sized array to hold the integers. You will likely need two pointers to keep track of where the elements are to be added and removed. When you are done, you may find that you have implemented a circular buffer.

Prime Factors

Watch related video: Prime Factors

Access video by registering at informit.com/register

The next example has a story and a lesson. The story begins in 2002 or thereabouts. I had been using TDD for a couple of years by that time and was learning Ruby. My son, Justin, came home from school and asked me for help with a homework problem. The homework was to find the prime factors of a set of integers.

I told Justin to try to work the problem by himself and that I would write a little program for him that would check his work. He retired to his room, and I set my laptop up on the kitchen table and started to ponder how to code the algorithm to find prime factors.

I settled on the obvious approach of using the sieve of Eratosthenes to generate a list of prime numbers and then dividing those primes into the candidate number. I was about to code it when a thought occurred to me: What if I just start writing tests and see what happens?

I began writing tests and making them pass, following the TDD cycle. And this is what happened.

First watch the video if you can. It will show you a lot of the nuances that I can’t show in text. In the text that follows, I avoid the tedium of all the timestamps, compile-time errors, and so on. I just show you the incremental progress of the tests and the code.

We begin with the most obvious and degenerate case. Indeed, that follows a rule:

Rule 4: Write the simplest, most specific, most degenerate² test that will fail.

2. The word degenerate is used here to mean the most absurdly simple starting point.

The most degenerate case is the prime factors of 1. The most degenerate failing solution is to simply return a null.

Click here to view code image

public class PrimeFactorsTest {
  @Test
  public void factors() throws Exception {
    assertThat(factorsOf(1), is(empty()));
  }
  private List<Integer> factorsOf(int n) {
    return null;
  }
}

Note that I am including the function being tested within the test class. This is not typical but is convenient for this example. It allows me to avoid bouncing back and forth between two source files.

Now this test fails, but it is easy to make it pass. We simply return an empty list:

Click here to view code image

private List<Integer> factorsOf(int n) {
  return new ArrayList<>();
}

Of course, this passes. The next most degenerate test is 2.

Click here to view code image

assertThat(factorsOf(2), contains(2));

This fails; but again, it’s easy to make it pass. That’s one of the reasons we choose degenerate tests: they are almost always easy to make pass.

Click here to view code image

private List<Integer> factorsOf(int n) {
  ArrayList<Integer> factors = new ArrayList<>();
  if (n>1)
    factors.add(2);
  return factors;
}

If you watched the video, you saw that this was done in two steps. The first step was to extract the new ArrayList<>() as a variable named factors. The second step was to add the if statement.

I emphasize these two steps because the first follows Rule 5.

Rule 5: Generalize where possible.

The original constant, new ArrayList<>(), is very specific. It can be generalized by putting it into a variable that can be manipulated. It’s a small generalization, but small generalizations often are all that are necessary.

And so, the tests pass again. The next most degenerate test elicits a fascinating result:

Click here to view code image

assertThat(factorsOf(3), contains(3));

This fails. Following Rule 5, we need to generalize. There is a very simple generalization that makes this test pass. It might surprise you. You’ll have to look closely; otherwise you’ll miss it.

Click here to view code image

private List<Integer> factorsOf(int n) {
  ArrayList<Integer> factors = new ArrayList<>();
  if (n>1)
    factors.add(n);
  return factors;
}

I sat at my kitchen table and marveled that a simple one-character change that replaced a constant with a variable, a simple generalization, made the new test pass and kept all previous tests passing.

I’d say we were on a roll, but the next test is going to be disappointing. The test itself is obvious:

Click here to view code image

assertThat(factorsOf(4), contains(2, 2));

But how do we solve that by generalizing? I can’t think of a way. The only solution I can think of is to test whether n is divisible by 2, and that just isn’t very general. Nevertheless,

Click here to view code image

private List<Integer> factorsOf(int n) {
  ArrayList<Integer> factors = new ArrayList<>();
  if (n>1) {
    if (n%2 == 0) {
      factors.add(2);
      n /= 2;
    }
    factors.add(n);
  }
  return factors;
}

Not only is this not very general; it also fails a previous test. It fails the test for the prime factors of 2. The reason should be clear. When we reduce n by a factor of 2, it becomes 1, which then gets put into the list.

We can fix that with some even less general code:

Click here to view code image

private List<Integer> factorsOf(int n) {
  ArrayList<Integer> factors = new ArrayList<>();
  if (n > 1) {
    if (n % 2 == 0) {
      factors.add(2);
      n /= 2;
    }
    if (n > 1)
      factors.add(n);
  }
  return factors;
}

At this point, you might fairly accuse me of just tossing in various if statements to make the tests pass. That’s not far from the truth. You might also accuse me of violating Rule 5, because none of this recent code is particularly general. On the other hand, I don’t see any options.

But there’s a hint of a generalization to come. Notice that the two if statements have identical predicates. It’s almost as if they were part of an unwound loop. Indeed, there’s no reason that second if statement needs to be inside the first.

Click here to view code image

private List<Integer> factorsOf(int n) {
  ArrayList<Integer> factors = new ArrayList<>();
  if (n > 1) {
    if (n % 2 == 0) {
      factors.add(2);
      n /= 2;
    }
  }
  if (n > 1)
    factors.add(n);
  return factors;
}

This passes and looks very much like an unwound loop.

The next three tests pass without any changes:

Click here to view code image

assertThat(factorsOf(5), contains(5));
assertThat(factorsOf(6), contains(2,3));
assertThat(factorsOf(7), contains(7));

That’s a pretty good indication that we are on the right track, and it makes me feel better about those ugly if statements.

The next most degenerate test is 8, and it must fail because our solution code simply cannot put three things into the list:

Click here to view code image

assertThat(factorsOf(8), contains(2, 2, 2));

The way to make this pass is another surprise—and a powerful application of Rule 5. We change an if to a while:

Click here to view code image

private List<Integer> factorsOf(int n) {
  ArrayList<Integer> factors = new ArrayList<>();
  if (n > 1) {
    while (n % 2 == 0) {
      factors.add(2);
      n /= 2;
    }
  }
  if (n > 1)
    factors.add(n);
  return factors;
}

I sat at my kitchen table and once again I marveled. It seemed to me that something profound had happened here. At that time, I didn’t know what it was. I do now. It was Rule 5. It turns out the while is a general form of if, and if is the degenerate form of while.

The next test, 9, must also fail because nothing in our solution factors out 3:

Click here to view code image

assertThat(factorsOf(9), contains(3, 3));

To solve it, we need to factor out 3s. We could do that as follows:

Click here to view code image

private List<Integer> factorsOf(int n) {
  ArrayList<Integer> factors = new ArrayList<>();
  if (n > 1) {
    while (n % 2 == 0) {
      factors.add(2);
      n /= 2;
    }
    while (n % 3 == 0) {
      factors.add(3);
      n /= 3;
    }
  }
  if (n > 1)
    factors.add(n);
  return factors;
}

But this is horrific. Not only is it a gross violation of Rule 5, but it’s also a huge duplication of code. I’m not sure which rule violation is worse!

And this is where the generalization mantra kicks in:

As the tests get more specific, the code gets more generic.

Every new test we write makes the test suite more specific. Every time we invoke Rule 5, the solution code gets more generic. We’ll come back to this mantra later. It turns out to be critically important for test design and for the prevention of fragile tests.

We can eliminate the violation of duplication, and Rule 5, by putting the original factoring code into a loop:

Click here to view code image

private List<Integer> factorsOf(int n) {
  ArrayList<Integer> factors = new ArrayList<>();
  int divisor = 2;
  while (n > 1) {
    while (n % divisor == 0) {
      factors.add(divisor);
      n /= divisor;
    }
    divisor++;
  }
  if (n > 1)
    factors.add(n);
  return factors;
}

Once again, if you watch the video, you will see that this was done in several steps. The first step was to extract the three 2s into the divisor variable. The next step was to introduce the divisor++ statement. Then the initialization of the divisor variable was moved above the if statement. Finally, the if was changed into a while.

There it is again: that transition from if->while. Did you notice that the predicate of the original if statement turned out to be the predicate for the outer while loop? I found this to be startling. There’s something genetic about it. It’s as though the creature that I’ve been trying to create started from a simple seed and gradually evolved through a sequence of tiny mutations.

Notice that the if statement at the bottom has become superfluous. The only way the loop can terminate is if n is 1. That if statement really was the terminating condition of an unwound loop!

Click here to view code image

private List<Integer> factorsOf(int n) {
  ArrayList<Integer> factors = new ArrayList<>();
  int divisor = 2;
  while (n > 1) {
    while (n % divisor == 0) {
      factors.add(divisor);
      n /= divisor;
    }
    divisor++;
  }
  return factors;
}

Just a little bit of refactoring, and we get this:

Click here to view code image

private List<Integer> factorsOf(int n) {
  ArrayList<Integer> factors = new ArrayList<>();

  for (int divisor = 2; n > 1; divisor++)
    for (; n % divisor == 0; n /= divisor)
      factors.add(divisor);

  return factors;
}

And we’re done. If you watch the video, you’ll see that I added one more test, which proves that this algorithm is sufficient.

Sitting at my kitchen table, I saw those three salient lines and I had two questions. Where did this algorithm come from, and how does it work?

Clearly, it came from my brain. It was my fingers on the keyboard after all. But this was certainly not the algorithm I had planned on creating at the start. Where was the sieve of Eratosthenes? Where was the list of prime numbers? None of it was there!

Worse, why does this algorithm work? I was astounded that I could create a working algorithm and yet not understand how it functioned. I had to study it for a while to figure it out. My dilemma was the divisor++ incrementer of the outer loop, which guarantees that every integer will be checked as a factor, including composite factors! Given the integer 12, that incrementer will check whether 4 is a factor. Why doesn’t it put 4 in the list?

The answer is in the order of the execution, of course. By the time the incrementer gets to 4, all the 2s have been removed from n. And if you think about that for a bit, you’ll realize that it is the sieve of Eratosthenes—but in a very different form than usual.

The bottom line here is that I derived this algorithm one test case at a time. I did not think it through up front. I didn’t even know what this algorithm was going to look like when I started. The algorithm seemed to almost put itself together before my eyes. Again, it was like an embryo evolving one small step at a time into an ever-more-complex organism.

Even now, if you look at those three lines, you can see the humble beginnings. You can see the remnants of that initial if statement and fragments of all the other changes. The breadcrumbs are all there.

And we are left with a disturbing possibility. Perhaps TDD is a general technique for incrementally deriving algorithms. Perhaps, given a properly ordered suite of tests, we can use TDD to derive any computer program in a step-by-step, determinative, manner.

In 1936, Alan Turing and Alonzo Church separately proved that there was no general procedure for determining if there was a program for any given problem.³ In so doing, they separately, and respectively, invented procedural and functional programming. Now TDD looks like it might be a general procedure for deriving the algorithms that solve the problems that can be solved.

3. This was Hilbert’s “decidability problem.” He asked whether there was a generalized way to prove that any given Diophantine equation was solvable. A Diophantine equation is a mathematical function with integer inputs and outputs. A computer program is also a mathematical function with integer inputs and outputs. Therefore, Hilbert’s question can be described as pertaining to computer programs.

The Bowling Game

In 1999, Bob Koss and I were together at a C++ conference. We had some time to kill, so we decided to practice this new idea of TDD. We chose the simple problem of computing the score of a game of bowling.

A game of bowling consists of ten frames. In each frame, the player is given two attempts to roll a ball toward ten wooden pins in order to knock them down. The number of pins knocked down by a ball is the score for that ball. If all ten pins are knocked down by the first ball, it is called a strike. If knocking all ten pins down requires both balls, then it is called a spare. The dreaded gutter ball (Figure 2.3) yields no points at all.

The scoring rules can be stated succinctly as follows:

• If the frame is a strike, the score is 10 plus the next two balls.

• If the frame is a spare, the score is 10 plus the next ball.

• Otherwise, the score is the two balls in the frame.

The score sheet in Figure 2.4 is a typical (if rather erratic) game.

On the player’s first attempt, he knocked down one pin. On his second attempt, he knocked down four more, for a total of 5 points.

In the second frame, he rolled a 4 followed by a 5, giving him a 9 for the frame and a total of 14.

In the third frame, he rolled a 6 followed by a 4 (a spare). The total for that frame cannot be computed until the player begins the next frame.

In the fourth frame, the player rolls a 5. Now the score can be computed for the previous frame, which is 15, for a total of 29 in the third frame.

The spare in the fourth frame must wait until the fifth frame, for which the player rolls a strike. The fourth frame is therefore 20 points for a total of 49.

The strike in the fifth frame cannot be scored until the player rolls the next two balls for the sixth frame. Unfortunately, he rolls a 0 and a 1, giving him only 11 points for the fifth frame and a total of 60.

And on it goes until the tenth and final frame. Here the player rolls a spare and is thus allowed to roll one extra ball to finish out that spare.

Now, you are a programmer, a good object-oriented programmer. What are the classes and relationships you would use to represent the problem of computing the score of a game of bowling? Can you draw it in UML?⁴

4. The Unified Modeling Language. If you don’t know UML, don’t worry—it’s just arrows and rectangles. You’ll work it out from the description in the text.

Perhaps you might come up with something like what is shown in Figure 2.5.

The Game has ten Frames. Each Frame has one or two Rolls, except the TenthFrame subclass, which inherits the 1..2 and adds one more roll to make it 2..3. Each Frame object points to the next Frame so that the score function can look ahead in case it has to score a spare or a strike.

The Game has two functions. The roll function is called every time the player rolls a ball, and it is passed the number of pins the player knocked down. The score function is called once all the balls are rolled, and it returns the score for the entire game.

That’s a nice, simple object-oriented model. It ought to be pretty easy to code. Indeed, given a team of four people, we could divide the work into the four classes and then meet a day or so later to integrate them and get them working.

Or, we could use TDD. If you can watch the video, you should do that now. In any case, please read through the text that follows.

Watch related video: Bowling Game

Access video by registering at informit.com/register

We begin, as always, with a test that does nothing, just to prove we can compile and execute. Once this test runs, we delete it:

Click here to view code image

public class BowlingTest {
  @Test
  public void nothing() throws Exception {
  }
}

Next, we assert that we can create an instance of the Game class:

Click here to view code image

@Test
public void canCreateGame() throws Exception {
  Game g = new Game();


}

Then we make that compile and pass by directing our IDE to create the missing class:

public class Game {
}

Next, we see if we can roll one ball:

Click here to view code image

@Test
public void canRoll() throws Exception {
  Game g = new Game();
  g.roll(0);
}

And then we make that compile and pass by directing the IDE to create the roll function, and we give the argument a reasonable name:

Click here to view code image

public class Game {
  public void roll(int pins) {
  }

}

You’re probably already bored. This should be nothing new to you by now. But bear with me—it’s about to get interesting. There’s a bit of duplication in the tests already. We should get rid of it, so we factor out the creating of the game into the setup function:

Click here to view code image

public class BowlingTest {
  private Game g;

  @Before
  public void setUp() throws Exception {
    g = new Game();
  }
}

This makes the first test completely empty, so we delete it. The second test is also pretty useless because it doesn’t assert anything. We delete it as well. Those tests served their purpose. They were stairstep tests.

Stairstep tests: Some tests are written just to force us to create classes or functions or other structures that we’re going to need. Sometimes these tests are so degenerate that they assert nothing. Other times they assert something very naive. Often these tests are superseded by more comprehensive tests later and can be safely deleted. We call these kinds of tests stairstep tests because they are like stairs that allow us to incrementally increase the complexity to the appropriate level.

Next, we want to assert that we can score a game. But to do that, we need to roll a complete game. Remember that the score function can be called only after all the balls in a game are rolled.

We fall back on Rule 4 and roll the simplest, most degenerate game we can think of:

Click here to view code image

@Test
public void gutterGame() throws Exception {
  for (int i=0; i<20; i++)
    g.roll(0);
  assertEquals(0, g.score());
}

Making this pass is trivial. We just need to return zero from score. But first we return -1 (not shown) just to see it fail. Then we return zero to see it pass:

Click here to view code image

public class Game {
  public void roll(int pins) {
  }

  public int score() {
    return 0;
  }
}

Okay, I said this was about to get interesting, and it is. Just one more little setup. The next test is another example of Rule 4. The next most degenerate test I can think of is all ones. We can write this test with a simple copy paste from the last test:

Click here to view code image

@Test
public void allOnes() throws Exception {
  for (int i=0; i<20; i++)
    g.roll(1);
  assertEquals(20, g.score());
}

This creates some duplicate code. The last two tests are virtually identical. When we refactor, we’ll have to fix that. But first, we need to make this test pass, and that’s really easy. All we need to do is add up all the rolls:

Click here to view code image

public class Game {
  private int score;

  public void roll(int pins) {
    score += pins;
  }

  public int score() {
    return score;
  }
}

Of course, this is not the right algorithm for scoring bowling. Indeed, it is hard to see how this algorithm could ever evolve into becoming the rules for scoring bowling. So, I’m suspicious—I expect squalls in the coming tests. But for now, we must refactor.

The duplication in the tests can be eliminated by extracting a function called rollMany. The IDE’s Extract Method refactoring helps immensely with this and even detects and replaces both instances of the duplication:

Click here to view code image

public class BowlingTest {
  private Game g;


  @Before
  public void setUp() throws Exception {
    g = new Game();
  }


  private void rollMany(int n, int pins) {
    for (int i = 0; i < n; i++) {
      g.roll(pins);
    }
  }


  @Test
  public void gutterGame() throws Exception {
    rollMany(20, 0);
    assertEquals(0, g.score());
  }


  @Test
  public void allOnes() throws Exception {
    rollMany(20, 1);
    assertEquals(20, g.score());
  }
}

Okay, next test. It’s hard to think of something degenerate at this point, so we might as well try for a spare. We’ll keep it simple though: one spare, with one extra bonus ball, and all the rest gutter balls.

Click here to view code image

@Test
public void oneSpare() throws Exception {
  rollMany(2, 5); // spare
  g.roll(7);
  rollMany(17, 0);
  assertEquals(24, g.score());
}

Let’s check my logic: This game has two balls in each frame. The first two balls are the spare. The next ball is the ball after the spare, and the 17 gutter balls complete the game.

The score in the first frame is 17, which is 10 plus the 7 rolled in the next frame. The score for the whole game, therefore, is 24 because the 7 is counted twice. Convince yourself that this is correct.

This test fails, of course. So how do we get it to pass? Let’s look at the code:

Click here to view code image

public class Game {
  private int score;
  public void roll(int pins) {
    score += pins;
  }


  public int score() {
    return score;
  }
}

The score is being calculated in the roll function, so we need to modify that function to account for the spare. But that will force us to do something really ugly, like this:

Click here to view code image

 public void roll(int pins) {
    if (pins + lastPins == 10) { // horrors!
      //God knows what…
    }
    score += pins;
  }

That lastPins variable must be a field of the Game class that remembers what the last roll was. And if the last roll and this roll add up to 10, then that’s a spare. Right? Ew!

You should feel your sphincter muscles tightening. You should feel your gorge rise and a tension headache beginning to build. The angst of the software craftsman should be raising your blood pressure.

This is just wrong!

We’ve all had that feeling before, haven’t we? The question is, what do you do about it?

Whenever you get that feeling that something is wrong, trust it! So, what is it that’s wrong?

There’s a design flaw. You might rightly wonder how there could be a design flaw in two executable lines of code. But the design flaw is there; it’s blatant, and it’s deeply harmful. As soon as I tell you what it is you’ll recognize it and agree with me. Can you find it?

Jeopardy song interlude.

I told you what the design flaw was at the very start. Which of the two functions in this class claims, by its name, to calculate the score? The score function, of course. Which function actually does calculate the score? The roll function. That’s misplaced responsibility.

Misplaced responsibility: A design flaw in which the function that claims to perform a computation does not actually perform the computation. The computation is performed elsewhere.

How many times have you gone to the function that claims to do some task, only to find that function does not do that task? And now you have no idea where, in the system, that task is actually done. Why does this happen?

Clever programmers. Or rather, programmers who think they are clever.

It was very clever of us to sum up the pins in the roll function, wasn’t it? We knew that function was going to be called once per roll, and we knew that all we had to do was sum up the rolls, so we just put that addition right there. Clever, clever, clever. And that cleverness leads us to Rule 6.

Rule 6: When the code feels wrong, fix the design before proceeding.

So how do we fix this design flaw? The calculation of the score is in the wrong place, so we’re going to have to move it. By moving it, perhaps we’ll be able to figure out how to pass the spare test.

Moving the calculation means that the roll function is going to have to remember all the rolls in something like an array. Then the score function can sum up the array.

Click here to view code image

public class Game {
  private int rolls[] = new int[21];
  private int currentRoll = 0;


  public void roll(int pins) {
    rolls[currentRoll++] = pins;
  }


  public int score() {
    int score = 0;
    for (int i = 0; i < rolls.length; i++) {
      score += rolls[i];
    }
    return score;
  }
}

This fails the spare test, but it passes the other two tests. What’s more, the spare test fails for the same reason as before. So, although we’ve completely changed the structure of the code, the behavior remains unchanged. By the way, that is the definition of refactoring.

Refactoring: A change to the structure of the code that has no effect upon the behavior.⁵

5. Martin Fowler, Refactoring: Improving the Design of Existing Code, 2nd ed. (Addison-Wesley, 2019).

Can we pass the spare case now? Well, maybe, but it’s still icky:

Click here to view code image

  public int score() {
    int score = 0;
    for (int i = 0; i < rolls.length; i++) {
      if (rolls[i] + rolls[i+1] == 10) { // icky
        // What now?
      }
      score += rolls[i];
    }
    return score;
  }

Is that right? No, it’s wrong, isn’t it? It only works if i is even. To make that if statement actually detect a spare, it would have to look like this:

Click here to view code image

if (rolls[i] + rolls[i+1] == 10 && i%2 == 0) { // icky

So, we’re back to Rule 6—there’s another design problem. What could it be?

Look back to the UML diagram earlier in this chapter. That diagram shows that the Game class should have ten Frame instances. Is there any wisdom in that? Look at our loop. At the moment, it’s going to loop 21 times! Does that make any sense?

Let me put it this way. If you were about to review the code for scoring bowling—code that you’d never seen before—what number would you expect to see in that code? Would it be 21? Or would it be 10?

I hope you said 10, because there are 10 frames in a game of bowling. Where is the number 10 in our scoring algorithm? Nowhere!

How can we get the number 10 into our algorithm? We need to loop through the array one frame at a time. How do we do that?

Well, we could loop through the array two balls at a time, couldn’t we? I mean like this:

Click here to view code image

public int score() {
  int score = 0;
  int i = 0;
  for (int frame = 0; frame<10; frame++) {
    score += rolls[i] + rolls[i+1];
    i += 2;
  }
  return score;
}

Once again, this passes the first two tests and fails the spare test for the same reason as before. So, no behavior was changed. This was a true refactoring.

You might be ready to tear this book up now because you know that looping through the array two balls at a time is just plain wrong. Strikes have only one ball in their frame, and the tenth frame could have three.

True enough. However, so far none of our tests has used a strike, or the tenth frame. So, for the moment, two balls per frame works fine.

Can we pass the spare case now? Yes. It’s trivial:

Click here to view code image

public int score() {
  int score = 0;
  int i = 0;
  for (int frame = 0; frame < 10; frame++) {
    if (rolls[i] + rolls[i + 1] == 10) { // spare
     score += 10 + rolls[i + 2];
      i += 2;
    } else {
      score += rolls[i] + rolls[i + 1];
      i += 2;
    }
  }
  return score;
}

This passes the spare test. Nice. But the code is pretty ugly. We can rename i to frameIndex and get rid of that ugly comment by extracting a nice little method:

Click here to view code image

public int score() {
  int score = 0;
  int frameIndex = 0;
  for (int frame = 0; frame < 10; frame++) {
    if (isSpare(frameIndex)) {
      score += 10 + rolls[frameIndex + 2];
      frameIndex += 2;
    } else {
      score += rolls[frameIndex] + rolls[frameIndex + 1];
      frameIndex += 2;
    }
  }
  return score;
}


private boolean isSpare(int frameIndex) {
  return rolls[frameIndex] + rolls[frameIndex + 1] == 10;
}

That’s better. We can also clean up the ugly comment in the spare test by doing the same:

Click here to view code image

private void rollSpare() {
  rollMany(2, 5);
}


@Test
public void oneSpare() throws Exception {
  rollSpare();
  g.roll(7);
  rollMany(17, 0);
  assertEquals(24, g.score());
}

Replacing comments with pleasant little functions like this is almost always a good idea. The folks who read your code later will thank you.

So, what’s the next test? I suppose we should try a strike:

Click here to view code image

@Test
public void oneStrike() throws Exception {
  g.roll(10); // strike
  g.roll(2);
  g.roll(3);
  rollMany(16, 0);
  assertEquals(20, g.score());
}

Convince yourself that this is correct. There’s the strike, the 2 bonus balls, and 16 gutter balls to fill up the remaining eight frames. The score is 15 in the first frame and 5 in the second. All the rest are 0 for a total of 20.

This test fails, of course. What do we have to do to make it pass?

Click here to view code image

public int score() {
  int score = 0;
  int frameIndex = 0;
  for (int frame = 0; frame < 10; frame++) {
    if (rolls[frameIndex] == 10) { // strike
      score += 10 + rolls[frameIndex+1] + 
                    rolls[frameIndex+2];
      frameIndex++;
    }
    else if (isSpare(frameIndex)) {
      score += 10 + rolls[frameIndex + 2];
      frameIndex += 2;
    } else {
      score += rolls[frameIndex] + rolls[frameIndex + 1];
      frameIndex += 2;
    }
  }
  return score;
}

This passes. Note that we increment frameIndex only by one. That’s because a strike has only one ball in a frame—and you were so worried about that, weren’t you?

This is a very good example of what happens when you get the design right. The rest of the code just starts trivially falling into place. Pay special attention to Rule 6, boys and girls, and get the design right early. It will save you immense amounts of time.

We can clean this up quite a bit. That ugly comment can be fixed by extracting an isStrike method. We can extract some of that ugly math into some pleasantly named functions too. When we’re done, it looks like this:

Click here to view code image

public int score() {
  int score = 0;
  int frameIndex = 0;
  for (int frame = 0; frame < 10; frame++) {
    if (isStrike(frameIndex)) {
      score += 10 + strikeBonus(frameIndex);
      frameIndex++;
    } else if (isSpare(frameIndex)) {
      score += 10 + spareBonus(frameIndex);
      frameIndex += 2;
    } else {
      score += twoBallsInFrame(frameIndex);
      frameIndex += 2;
    }
  }
  return score;
}

We can also clean up the ugly comment in the test by extracting a rollStrike method:

Click here to view code image

@Test
public void oneStrike() throws Exception {
  rollStrike();
  g.roll(2);
  g.roll(3);
  rollMany(16, 0);
  assertEquals(20, g.score());
}

What’s the next test? We haven’t tested the tenth frame yet. But I’m starting to feel pretty good about this code. I think it’s time to break Rule 3 and go for the gold. Let’s test a perfect game!

Click here to view code image

@Test
public void perfectGame() throws Exception {
  rollMany(12, 10);
  assertEquals(300, g.score());
}

We roll a strike in the first nine frames, and then a strike and two 10s in the tenth frame. The score, of course, is 300—everybody knows that.

What’s going to happen when I run this test? It should fail, right? But, no! It passes! It passes because we are done! The score function is the solution. You can prove that to yourself by reading it. Here, you follow along while I read it to you:

Click here to view code image

For each of the ten frames
   If that frame is a strike,
     Then the score is 10 plus the strike bonus 
      (the next two balls). 
   If that frame is a spare,
     Then the score is 10 plus the spare bonus 
      (the next ball).
   Otherwise,
     The score is the two balls in the frame.

The code reads like the rules for scoring bowling. Go to the beginning of this chapter and read those rules again. Compare them to the code. And then ask yourself if you’ve ever seen requirements and code that are so closely aligned.

Some of you may be confused about why this works. You look at the tenth frame on that scorecard and you see that it doesn’t look like any of the other frames; and yet there is no code in our solution that makes the tenth frame a special case. How can that be?

The answer is that the tenth frame is not special at all. It is drawn differently on the score card, but it is not scored differently. There is no special case for the tenth frame.

And we were going to make a subclass out of it!

Look back at that UML diagram. We could have divvied out the tasks to three or four programmers and integrated a day or two later. And the tragedy is that we’d have gotten it working. We would have celebrated the 400⁶ lines of working code, never knowing that the algorithm was a for loop and two if statements that fits into 14 lines of code.

6. I know it’s 400 lines of code because I’ve written it.

Did you see the solution early? Did you see the for loop and two if statements? Or did you expect one of the tests to eventually force me to write the Frame class? Were you holding out for the tenth frame? Is that where you thought all the complexity would be found?

Did you know we were done before we ran the tenth frame test? Or did you think there was a lot more to do? Isn’t it fascinating that we can write a test fully expecting more work ahead, only to find, to our surprise, that we are done?

Some folks have complained that if we’d followed the UML diagram shown earlier, we’d have wound up with code that was easier to change and maintain. That’s pure bollocks! What would you rather maintain, 400 lines of code in four classes or 14 lines with a for loop and two if statements?

Conclusion

In this chapter, we studied the motivations and basics of TDD. If you’ve gotten this far, your head may be spinning. We covered a lot of ground. But not nearly enough. The next chapter goes significantly deeper into the topic of TDD, so you may wish to take a little rest before turning the page.