Towards a Theory of Test-Driven Development

Red, Green, RefactorThis post examines how well we really understand the practice of Test-Driven Development (TDD).

Red, Green, Refactor

By now we all know that Test-Driven Development (TDD) follows a simple cycle consisting of these steps:

  1. Start by writing a test. Since there is no code, it will fail (Red)
  2. Write just enough code to make the test pass (Green)
  3. Clean up the code (Refactor)

The beauty of this division is that we can focus on one thing at a time.

Specify, Transform, Refactor

Although simple, TDD isn’t easy. To execute the TDD cycle well, we need a deeper understanding that we can only get from experience.

For instance, after doing TDD for a while we may look at the steps as:

  1. Specify new required functionality
  2. Improve the functionality while keeping the design constant
  3. Improve the design while keeping the functionality constant

When we look at the TDD cycle in this light, we see that the Green and Refactor phases are each others opposite.

Refactorings and Transformations

In the Refactor phase, we use Martin Fowler‘s refactorings to clean up the code.

TransformationRefactorings are standard alterations of the code that change its internal structure without changing its external behavior.

Now, if the Green and Refactor phases are each others opposite, then you might think that there are “opposite refactorings” as well. You would be right.

Robert Martin‘s transformations are standard alterations of the code that change its external behavior without changing its internal structure.

Automated Transformations?

Most of us use powerful IDEs to write our code. These IDEs support refactorings, which means that they can do the code alteration for you in a manner that is guaranteed to be safe.

So do we need something similar for transformations? I think not.

Some transformations are so simple in terms of the changes to code, that it wouldn’t actually save any effort to automate them. I don’t see a lot of room for improving the change from if to while, for instance.

Other transformations simply have an unspecified effect. For example, how would you automate the statement->statements transformation?

RefactoringThe crux is that refactorings keep the external behavior the same, and the tools depend on that to properly implement the refactorings. However, transformations don’t share that property.

Standardized Work

In the Specify/Transform/Refactor view of TDD, we write our programs by alternating between adding tests, applying transformations, and applying refactorings.

In other words, if we look at the evolution of our non-test code through a series of diffs, then each diff shows either a transformation or a refactoring.

It seems we are getting closer to the Lean principle of Standardized Work.

What’s still missing, however, is a deeper insight into the Red/Specify phase.

How to Write Tests

The essential part of the Red/Specify phase is obviously to write a test. But how do we do that?

For starters, how do we select the next test to implement?

Unit test failureThere is almost always more than one test to write for a given requirement.

And the order in which you introduce tests makes a difference for the implementation.

But there is very little advice on how to pick the next test, and this is sorely needed.

Kent Beck has a kata for experimenting with test order, which helps in gaining understanding. But that’s a far cry from a well-developed theory like we have for refactorings.

So what do you think? If we understood this phase better, could we come up with the test writing equivalent of transformations and refactorings?

Please share your thoughts in the comments.

TDD and the Transformation Priority Premise

TransformationLast time, we looked at the Red/Green/Refactor phases of Test-Driven Development (TDD).

This time we’ll take a detailed look at the transformations applied in the Green phase.

The Transformation Priority Premise

Most of you will have heard of the refactorings we apply in the last TDD phase, but there are corresponding standardized code changes in the Green phase as well. Uncle Bob Martin named them transformations.

The Transformation Priority Premise (TPP) claims that these transformations have an inherent order, and that picking transformation that are higher on the list leads to better algorithms.

Anecdotal evidence is provided by the example of sorting, where violating the order leads to bubble sort, while the correct order leads to quicksort.

After some modifications based on posts by other people, Uncle Bob arrived at the following ordered list of transformations:

Transformation Description
{}–>nil no code at all->code that employs nil
nil->constant
constant->constant+ a simple constant to a more complex constant
constant->scalar replacing a constant with a variable or an argument
statement->statements adding more unconditional statements
unconditional->if splitting the execution path
scalar->array
array->container ??? this one is never used nor explained
statement->tail-recursion
if->while
statement->recursion
expression->function replacing an expression with a function or algorithm
variable->assignment replacing the value of a variable
case adding a case (or else) to an existing switch or if

Applying the TPP to the Roman Numerals Kata

Roman numeral symbolsReading about something gives only shallow knowledge, so let’s try out the TPP on a small, familiar problem: the Roman Numerals kata.

For those of you who are unfamiliar with it: the objective is to translate numbers into Roman. See the table at the left for an overview of the Roman symbols and their values.

As always in TDD, we start off with the simplest case:

public class RomanNumeralsTest {

  @Test
  public void arabicToRoman() {
    Assert.assertEquals("i", "i", RomanNumerals.arabicToRoman(1));
  }

}

We get this to compile with:

public class RomanNumerals {

  public static String arabicToRoman(int arabic) {
    return null;
  }

}

Note that we’ve already applied the first transformation on the list: {}->nil. We apply the second transformation, nil->constant, to get to green:

public class RomanNumerals {

  public static String arabicToRoman(int arabic) {
    return "i";
  }

}

Now we can add our second test:

public class RomanNumeralsTest {

  @Test
  public void arabicToRoman() {
    assertRoman("i", 1);
    assertRoman("ii", 2);
  }

  private void assertRoman(String roman, int arabic) {
    Assert.assertEquals(roman, roman, 
        RomanNumerals.arabicToRoman(arabic));
  }

}

The only way to make this test pass, is to introduce some conditional (unconditional->if):

  public static String arabicToRoman(int arabic) {
    if (arabic == 2) {
      return "ii";
    }
    return "i";
  }

However, this leads to duplication between the number 2 and the number of is returned. So let’s try a different sequence of transformations. Warning: I’m going into baby steps mode now.

First, do constant->scalar:

public static String arabicToRoman(int arabic) {
  String result = "i";
  return result;
}

Next, statement->statements:

public static String arabicToRoman(int arabic) {
  StringBuilder result = new StringBuilder();
  result.append("i");
  return result.toString();
}

Now we can introduce the if without duplication:

public static String arabicToRoman(int arabic) {
  StringBuilder result = new StringBuilder();
  if (arabic >= 1) {
    result.append("i");
  }
  return result.toString();
}

And then another statement->statements:

public static String arabicToRoman(int arabic) {
  StringBuilder result = new StringBuilder();
  if (arabic >= 1) {
    result.append("i");
    arabic -= 1;
  }
  return result.toString();
}

And finally we do if->while:

public static String arabicToRoman(int arabic) {
  StringBuilder result = new StringBuilder();
  while (arabic >= 1) {
    result.append("i");
    arabic -= 1;
  }
  return result.toString();
}

Our test now passes. And so does the test for 3, by the way.

With our refactoring hat on, we spot some more subtle duplication: between the number 1 and the string i. They both express the same concept (the number 1), but are different versions of it: one Arabic and one Roman.

We should introduce a class to capture this concept:

public class RomanNumerals {

  public static String arabicToRoman(int arabic) {
    StringBuilder result = new StringBuilder();
    RomanNumeral numeral = new RomanNumeral("i", 1);
    while (arabic >= numeral.getValue()) {
      result.append(numeral.getSymbol());
      arabic -= numeral.getValue();
    }
    return result.toString();
  }

}

public class RomanNumeral {

  private final String symbol;
  private final int value;

  public RomanNumeral(String symbol, int value) {
    this.symbol = symbol;
    this.value = value;
  }

  public int getValue() {
    return value;
  }

  public String getSymbol() {
    return symbol;
  }

}

Now it turns out that we have a case of feature envy. We can make that more obvious by extracting out a method:

public static String arabicToRoman(int arabic) {
  StringBuilder result = new StringBuilder();
  RomanNumeral numeral = new RomanNumeral("i", 1);
  arabic = append(arabic, result, numeral);
  return result.toString();
}

private static int append(int arabic, StringBuilder builder,
    RomanNumeral numeral) {
  while (arabic >= numeral.getValue()) {
    builder.append(numeral.getSymbol());
    arabic -= numeral.getValue();
  }
 return arabic;
}

Now we can move the append() method to RomanNumeral:

public class RomanNumerals {

  public static String arabicToRoman(int arabic) {
    StringBuilder result = new StringBuilder();
    RomanNumeral numeral = new RomanNumeral("i", 1);
    arabic = numeral.append(arabic, result);
    return result.toString();
  }

}

public class RomanNumeral {

  private final String symbol;
  private final int value;

  public RomanNumeral(String symbol, int value) {
    this.symbol = symbol;
    this.value = value;
  }

  public int getValue() {
    return value;
  }

  public String getSymbol() {
    return symbol;
  }

  public int append(int arabic, StringBuilder builder) {
    while (arabic >= getValue()) {
      builder.append(getSymbol());
      arabic -= getValue();
    }
    return arabic;
  }

}

We can further clean up by inlining the getters that are now only used in the RomanNumeral class:

public class RomanNumeral {

  private final String symbol;
  private final int value;

  public RomanNumeral(String symbol, int value) {
    this.symbol = symbol;
    this.value = value;
  }

  public int append(int arabic, StringBuilder builder) {
    while (arabic >= value) {
      builder.append(symbol);
      arabic -= value;
    }
    return arabic;
  }

}

There is one other problem with this code: we pass in arabic and builder as two separate parameters, but they are not independent. The former represents the part of the arabic number not yet processed, while the latter represents the part that is processed. So we should introduce another class to capture the shared concept:

public class RomanNumerals {

  public static String arabicToRoman(int arabic) {
    ArabicToRomanConversion conversion
        = new ArabicToRomanConversion(arabic);
    RomanNumeral numeral = new RomanNumeral("i", 1);
    numeral.append(conversion);
    return conversion.getResult();
  }

}

public class RomanNumeral {

  private final String symbol;
  private final int value;

  public RomanNumeral(String symbol, int value) {
    this.symbol = symbol;
    this.value = value;
  }

  public void append(ArabicToRomanConversion conversion) {
    while (conversion.getRemainder() >= value) {
      conversion.append(symbol, value);
    }
  }

}

public class ArabicToRomanConversion {

  private int remainder;
  private final StringBuilder result;

  public ArabicToRomanConversion(int arabic) {
    this.remainder = arabic;
    this.result = new StringBuilder();
  }

  public String getResult() {
    return result.toString();
  }

  public int getRemainder() {
    return remainder;
  }

  public void append(String symbol, int value) {
    result.append(symbol);
    remainder -= value;
  }

}

Unfortunately, we now have a slight case feature envy in RomanNumeral. We use conversion twice and our own members three times, so it’s not too bad, but let’s think about this for a moment.

Does it make sense to let the roman numeral know about an conversion process from Arabic to Roman? I think not, so let’s move the code to the proper place:

public class RomanNumerals {

  public static String arabicToRoman(int arabic) {
    ArabicToRomanConversion conversion
        = new ArabicToRomanConversion(arabic);
    RomanNumeral numeral = new RomanNumeral("i", 1);
    conversion.process(numeral);
    return conversion.getResult();
  }

}

public class RomanNumeral {

  private final String symbol;
  private final int value;

  public RomanNumeral(String symbol, int value) {
    this.symbol = symbol;
    this.value = value;
  }

  public String getSymbol() {
    return symbol;
  }

  public int getValue() {
    return value;
  }

}

public class ArabicToRomanConversion {

  private int remainder;
  private final StringBuilder result;

  public ArabicToRomanConversion(int arabic) {
    this.remainder = arabic;
    this.result = new StringBuilder();
  }

  public String getResult() {
    return result.toString();
  }

  public void process(RomanNumeral numeral) {
    while (remainder >= numeral.getValue()) {
      append(numeral.getSymbol(), numeral.getValue());
    }
  }

  private void append(String symbol, int value) {
    result.append(symbol);
    remainder -= value;
  }

}

We had to re-introduce the getters for RomanNumeral‘s fields to get this to compile. We could have avoided that rework by introducing the ArabicToRomanConversion class first. Hmm, maybe refactorings have an inherent order too!

OK, on to our next test: 4. We can make that pass with another series of transformations. First, scalar->array:

public static String arabicToRoman(int arabic) {
  ArabicToRomanConversion conversion
      = new ArabicToRomanConversion(arabic);
  RomanNumeral[] numerals = new RomanNumeral[] {
    new RomanNumeral("i", 1)
  };
  conversion.process(numerals[0]);
  return conversion.getResult();
}

Next, constant->scalar:

public static String arabicToRoman(int arabic) {
  ArabicToRomanConversion conversion
      = new ArabicToRomanConversion(arabic);
  RomanNumeral[] numerals = new RomanNumeral[] {
    new RomanNumeral("i", 1)
  };
  int index = 0;
  conversion.process(numerals[index]);
  return conversion.getResult();
}

Now we need an if:

public static String arabicToRoman(int arabic) {
  ArabicToRomanConversion conversion
      = new ArabicToRomanConversion(arabic);
  RomanNumeral[] numerals = new RomanNumeral[] {
    new RomanNumeral("i", 1)
  };
  int index = 0;
  if (index < 1) {
    conversion.process(numerals[index]);
  }
  return conversion.getResult();
}

And another constant->scalar:

public static String arabicToRoman(int arabic) {
  ArabicToRomanConversion conversion
      = new ArabicToRomanConversion(arabic);
  RomanNumeral[] numerals = new RomanNumeral[] {
    new RomanNumeral("i", 1)
  };
  int index = 0;
  if (index < numerals.length) {
    conversion.process(numerals[index]);
  }
  return conversion.getResult();
}

You can probably see where this is going. Next is statement->statements:

public static String arabicToRoman(int arabic) {
  ArabicToRomanConversion conversion
      = new ArabicToRomanConversion(arabic);
  RomanNumeral[] numerals = new RomanNumeral[] {
    new RomanNumeral("i", 1)
  };
  int index = 0;
  if (index < numerals.length) {
    conversion.process(numerals[index]);
    index++;
  }
  return conversion.getResult();
}

Then if->while:

public static String arabicToRoman(int arabic) {
  ArabicToRomanConversion conversion
      = new ArabicToRomanConversion(arabic);
  RomanNumeral[] numerals = new RomanNumeral[] {
    new RomanNumeral("i", 1)
  };
  for (RomanNumeral numeral : numerals) {
    conversion.process(numeral);
  }
  return conversion.getResult();
}

And finally constant->constant+:

public static String arabicToRoman(int arabic) {
  ArabicToRomanConversion conversion
      = new ArabicToRomanConversion(arabic);
  RomanNumeral[] numerals = new RomanNumeral[] {
    new RomanNumeral("iv", 4),
    new RomanNumeral("i", 1)
  };
  for (RomanNumeral numeral : numerals) {
    conversion.process(numeral);
  }
  return conversion.getResult();
}

Now we have our algorithm complete and all we need to do is add to the numerals array. BTW, this should be a constant:

public class RomanNumerals {

  private static final RomanNumeral[] ROMAN_NUMERALS 
      = new RomanNumeral[] {
    new RomanNumeral("iv", 4),
    new RomanNumeral("i", 1)
  };

  public static String arabicToRoman(int arabic) {
    ArabicToRomanConversion conversion
        = new ArabicToRomanConversion(arabic);
    for (RomanNumeral romanNumeral : ROMAN_NUMERALS) {
      conversion.process(romanNumeral);
    }
    return conversion.getResult();
  }

}

Also, it looks like we have another case of feature envy here that we could resolve as follows:

public class RomanNumerals {

  public static String arabicToRoman(int arabic) {
    return new ArabicToRomanConversion(arabic).getResult();
  }

}

public class ArabicToRomanConversion {

  private static final RomanNumeral[] ROMAN_NUMERALS 
      = new RomanNumeral[] {
    new RomanNumeral("iv", 4),
    new RomanNumeral("i", 1)
  };

  private int remainder;
  private final StringBuilder result;

  public ArabicToRomanConversion(int arabic) {
    this.remainder = arabic;
    this.result = new StringBuilder();
  }

  public String getResult() {
    for (RomanNumeral romanNumeral : ROMAN_NUMERALS) {
      process(romanNumeral);
    }
    return result.toString();
  }

  private void process(RomanNumeral numeral) {
    while (remainder >= numeral.getValue()) {
      append(numeral.getSymbol(), numeral.getValue());
    }
  }

  private void append(String symbol, int value) {
    result.append(symbol);
    remainder -= value;
  }

}

Retrospective

Magnifying glassThe first thing I noticed, is that following the TPP led me to discover the basic algorithm a lot quicker than in some of my earlier attempts at this kata.

The next interesting thing is that there seems to be an interplay between transformations and refactorings.

You can either perform a transformation and then clean up with refactorings, or prevent the need to refactor by using only transformations that don’t introduce duplication. Doing the latter is more efficient and also seems to speed up discovery of the required algorithm.

Certainly food for thought. It seems like some more experimentation is in order.

Update: Here is a screencast of a slightly better version of the kata: