A Smackdown Tool for Overeager TDDers

smackdown!
Image source: https://commons.wikimedia.org/wiki/File:Cross_rhodes_on_gabriel.jpg

I’ve always prefaced my first test-driven development (TDD) exercises by saying something like, “Make sure you write no more code than necessary to pass your test. Don’t put in data structures you don’t need, for example.” This pleading typically comes on the tail of a short demo where I’ve mentioned the word incremental numerous times.

But most people don’t listen well, and do instead what they’ve been habituated to do.

With students in shu mode, it’s ok for instructors to be emphatic and dogmatic, smacking students upside the head when they break the rules for an exercise. It’s impossible to properly learn TDD if you don’t follow the sufficiency rule, whether deliberately or not. Trouble is, it’s tough for me to smack the heads of a half-dozen pairs all at once, and some people tend to call in HR when you hit them.

The whole issue of incrementalism is such an important concept that I’ve introduced a new starting exercise to provide me with one more opportunity to push the idea. The natural tendency of students to jump to an end solution is one of the harder habits to break (and a frequent cause of students’ negative first reaction when they actually try TDD).

I present a meaty first example (latest: the Soundex algorithm) where all the tests are marked as ignored or disabled, a great idea I learned from James Grenning. In Java, the students are to un-@Ignore tests one-by-one, simply getting them to pass, until they’ve gotten all tests to pass. The few required instructions are in the test file, meaning they can be hitting this exercise about two minutes after class begins.

Problem is, students have a hard time not breaking rules, and always tend to implement too much. As I walk around, I catch them, but it’s often a little too late. Telling them that they need to scrap their code and back up isn’t what they want to hear.

So, I built a custom test-runner that will instead fail their tests if they code too much, acting as a virtual head-smacking Jeff. (I built a similar tool for C++ that I’ve used successfully in a couple C++ classes.)

Here’s the (hastily built) code:

import org.junit.*;
import org.junit.internal.*;
import org.junit.internal.runners.model.*;
import org.junit.runner.*;
import org.junit.runner.notification.*;
import org.junit.runners.*;
import org.junit.runners.model.*;

public class IncrementalRunner extends BlockJUnit4ClassRunner {

   public IncrementalRunner(Class klass) 
         throws InitializationError {
      super(klass);
   }

   @Override
   protected void runChild(
         FrameworkMethod method, RunNotifier notifier) {
      EachTestNotifier eachNotifier = 
         derivedMakeNotifier(method, notifier);
      if (method.getAnnotation(Ignore.class) != null) {
         runIgnoredTest(method, eachNotifier);
         return;
      }

      eachNotifier.fireTestStarted();
      try {
         methodBlock(method).evaluate();
      } catch (AssumptionViolatedException e) {
         eachNotifier.addFailedAssumption(e);
      } catch (Throwable e) {
         eachNotifier.addFailure(e);
      } finally {
         eachNotifier.fireTestFinished();
      }
   }

   private void runIgnoredTest(
         FrameworkMethod method, EachTestNotifier eachNotifier) {
      eachNotifier.fireTestStarted();
      runExpectingFailure(method, eachNotifier);
      eachNotifier.fireTestFinished();
   }

   private EachTestNotifier derivedMakeNotifier(
         FrameworkMethod method, RunNotifier notifier) {
      Description description = describeChild(method);
      return new EachTestNotifier(notifier, description);
   }

   private void runExpectingFailure(
         final FrameworkMethod method, EachTestNotifier notifier) {
      if (runsSuccessfully(method)) 
         notifier.addFailure(
            new RuntimeException("You've built too much, causing " + 
                                 "this ignored test to pass."));
   }

   private boolean runsSuccessfully(final FrameworkMethod method) {
      try {
         methodBlock(method).evaluate();
         return true;
      } catch (Throwable e) {
         return false;
      }
   }
}

(Note: this code is written for JUnit 4.5 due to client version constraints.)

All the custom runner does is run tests that were previously @Ignored, and expect them to fail. (I think I was forced into completely overriding runChild to add my behavior in runIgnoredTest, but I could be wrong. Please let me know if you’re aware of a simpler way.) To use the runner, you simply annotate your test class with @RunWith(IncrementalRunner.class).

To effectively use the tool, you must provide students with a complete set of tests that supply a definitive means of incrementally building a solution. For any given test, there must be a possible implementation that doesn’t cause any later test to pass. It took me a couple tries to create a good sequence for the Soundex solution.

The tool is neither foolish-proof nor clever-proof; a small bit of monkeying about and a willingness to deliberately cheat will get around it quite easily. (There are probably a half-dozen ways to defeat the mechanism: For example, students could un-ignore tests prematurely, or they could simply turn off the custom test-runner.) But as long as they are not devious, the test failure from building too much gets in their face and smacks them when I’m not be around.

If you choose to try this technique, please drop me a line and let me know how it went!

My First TDD Exercise

Finding a good first exercise for TDD learners can be challenging. Some of the things I look for:

  • Not so simple that it’s trivial, e.g. Stack, lest students dismiss it as pointless. There should be opportunities for students to make a few simple mistakes, but…
  • …not so complex that students mire in the algorithm itself instead of focusing on technique.
  • Something students can relate to–not so obscure that students struggle with understanding the domain or problem.
  • Games and fluff (bowling, fizz-buzz, e.g.) can create a first impression–and first impressions can be very hard to break–that TDD is for trivialities only, despite what you say. These things can be fine as later exercises.
  • Not something that already exists in the library. (“Why am building a multi-map when C++ already has one?”)
  • Can be test-driven in 10 to 15 minutes by an experienced TDDer, meaning that it’s probably a 30-to-45-minute exercise for newbies pairing up.
  • Provides a good demonstration of the ability to incrementally grow a solution, including opportunities to spot and remove duplication.
  • Provides an opportunity to show how to deal with at least one exceptional case.

I’ve been demoing a stock portfolio tracker for some time–a simple collection class that allows purchases of stock symbols. With Java students, I follow up with a multi-map, a class that would be useful in most shops (though a similar jakarta implementation exists). Both have worked well.

The message an exercise sends can be damaging. As a second or third exercise, lately I’ve been using the Roman numeral converter kata. I think it’s a cool exercise that can show how you can build an elegant algorithm by following a simple, incremental approach. It’s had 99% effectiveness: Out of the past ~100 students, one guy–an algorithm specialist–took a completely negative view of TDD after it. His stance was that he could have derived the algorithm much more quickly using a top-down, non-test-driven approach. From that he dismissed TDD completely. During subsequent pairings, I think he saw some of its benefits (we talk a lot about algorithms and TDD), but it’s an uphill battle and it might have been too late.

Currently I’m experimenting with an exercise to implement the soundex algorithm. More on that in an upcoming blog post.

Dave Thomas’s PragProg CodeKata site is a great place to get ideas. You might also check out the TDD Problems site (to which I contributed a handful of problems).

TDD Kata: Roman number converter

I’ve introduced the whole-number-to-Roman-numeral kata in my test-driven development training, not out of sadistic interest, but because I think it offers some excellent lessons about TDD. I do find it a bit amusing that good developers often struggle badly with the derivation of the algorithm, even after I give them my guidelines for the exercise:

  • Don’t assume that your tests must go in order 1, 2, 3, 4, 5, 6, 7, … Seek the test that would make for the next simplest increment of code. Seek patterns–if you’ve figured out the pattern for 1, 2, 3, then what’s the next series of numbers that follows the same pattern?
  • When you refactor incrementally, make similar code look exactly alike, and then get rid of the duplication.
  • Do not prematurely optimize code. Avoid using code-expressiveness “optimizations:” use while loops and simple decrement constructs instead of for loops and post-decrement operators, and let them stand until your algorithm is complete.

After they complete the exercise, we discuss Uncle Bob’s Transformation Priority Premise (TPP), and I ask them to re-run the exercise for homework (and to get them used to the idea of a kata) with the TPP in mind.

The first time I attempted the Kata some years ago, I got lost in the weeds. I didn’t give up; I scrapped a good amount of code, thought a bit harder about the ordering of tests, and eventually made my way to the finish line. I noted at least a couple insights were required, and came up with the guidelines above as a result in order to help students keep on track.

“Let’s start at the beginning, a very good place to start:”

   @Test
   public void convertIntToRoman() {
      assertThat(convert(1), is("I"));
   }

The implementation is the topmost TPP transform, ({}->nil):

   String convert(int arabic) {
      return null;
   }

Quickly following, the passing implementation (nil->constant):

   String convert(int arabic) {
      return "I";
   }

Moving along to the next test:

assertThat(convert(2), is("II"));

There might be a way to get a higher-level transform, but (unconditional->if) seems simplest to me:

   String convert(int arabic) {
      if (arabic == 2) return "II";
      return "I";
   }

The conversion for 3 indicates a repeating pattern:

   assertThat(convert(3), is("III"));

…which begs for a loop (if->while):

   String convert(int arabic) {
      String roman = "";
      while (arabic-- > 0)
         roman += "I";
      return roman;
   }

Performance geeks: never mind the use of String vs StringBuilder/StringBuffer. I want to get the algorithm working first, and all that rot clutters up the code a bit.

Hmm. I didn’t follow my guideline, and used post-decrement where I probably should have just introduced a separate statement to decrement the arabic variable. (Oh and another sin, I’m manipulating the argument. Ah well.)

Now a bit of thought. One, two, three, ten! No, four sir! No, ten. I have support for I, II, III. If I seek a similar pattern, it’s likely to do the least to my code in terms of transforms required, so what if I head to X, XX, and XXX?

   assertThat(convert(10), is("X"));

I can get that to work with a simple (unconditional->if), but it’s horrid:

   String convert(int arabic) {
      if (arabic == 10) return "X";
      String roman = "";
      while (arabic-- > 0)
         roman += "I";
      return roman;
   }

That’s ok–adding a test for 20:

   assertThat(convert(20), is("XX"));

…starts to make things look better, as I introduce (if->while) again:

   String convert(int arabic) {
      String roman = "";
      while (arabic >= 10) {
         roman += "X";
         arabic -= 10;
      }
      while (arabic-- > 0)
         roman += "I";
      return roman;
   }

Those two while loops look an awful lot alike. I can make them look almost exactly alike–I replace my post-decrement (see, shouldn’t have introduced it yet) with a separate statement at the end of the loop body, and adjust my comparison expression:

  String convert(int arabic) {
      String roman = "";
      while (arabic >= 10) {
         roman += "X";
         arabic -= 10;
      }
      while (arabic >= 1) {
         roman += "I";
         arabic -= 1;
      }
      return roman;
   }

It’s clear that these while loops differ only by their data. A bit of insight suggests introducing a table-lookup, allowing the implementation to be factored to the following:

   static int[] ARABIC_DIGITS = { 10, 1 };
   static String[] ROMAN_DIGITS = { "X", "I" };

   String convert(int arabic) {
      String roman = "";
      for (int i = 0; i < ARABIC_DIGITS.length; i++) {
         while (arabic >= ARABIC_DIGITS[i]) {
            roman += ROMAN_DIGITS[i];
            arabic -= ARABIC_DIGITS[i];
         }
      }
      return roman;
   }

(In Java, I tried once building the above as a map, but since the algorithm demands traversing the digits in reverse order, it ends up being a good deal more code than the simple but slightly obnoxious paired arrays.)

Huh. Look at that. A test for 30 should pass too, and it does.

But is it a bit too much implementation? Maybe–now that I support I’s and X’s, I want to be able to combine them, yet it looks like the following tests will pass right off the bat:

   assertThat(convert(11), is("XI"));
   assertThat(convert(33), is("XXXIII"));

And they do! I wonder if there’s a way I could have coded so those tests failed first, but I’ve not thought about it much. Maybe I could have put the second loop in an else block. Ideas?

What about 5?

  assertThat(convert(5), is("V"));

It’s just another digit; adding support for 5 to the table gets this test to pass:

   static int[] ARABIC_DIGITS = { 10, 5, 1 };
   static String[] ROMAN_DIGITS = { "X", "V", "I" };

And now these little combinations involving 5 also pass:

   assertThat(convert(8), is("VIII"));
   assertThat(convert(27), is("XXVII"));

I have to imagine similar tests involving L, C, D, and M should all pass too.

Instead, I’ll hit that pesky one, 4:

   assertThat(convert(4), is("IV"));

The joy of four is that if I try to get there with subtraction, I’m in a world of hurt. This is where students usually go really, really wrong. But, wait… insight! What if I consider that “IV” is just another digit, like any other Roman digit, except that it requires two characters instead of one to represent?

   static int[] ARABIC_DIGITS = { 10, 5, 4, 1 };
   static String[] ROMAN_DIGITS = { "X", "V", "IV", "I" };

Voila. At this point, I’ve covered the various scenarios, now it’s just a matter of fleshing out the table with support for all of the Roman digits. How about I just write a couple tests that fire across all cylinders?

      assertThat(convert(2499), is("MMCDXCIX"));
      assertThat(convert(3949), is("MMMCMXLIX"));

The final “table:”

static int[] ARABIC_DIGITS =
{ 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
static String[] ROMAN_DIGITS =
{ "M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I" };

We haven’t had to touch the algorithm for a while. It still holds up!

   String convert(int arabic) {
      String roman = "";
      for (int i = 0; i < ARABIC_DIGITS.length; i++) {
         while (arabic >= ARABIC_DIGITS[i]) {
            roman += ROMAN_DIGITS[i];
            arabic -= ARABIC_DIGITS[i];
         }
      }
      return roman;
   }

I did a search for code that solves this challenge, and had to laugh at the ugliness of a number of the implementations. There were some clever but convoluted ones, some awful ones, and a few that had the same implementation here.

TDD can’t derive algorithms, so they say. I take a different view. An algorithm is simply a “step-by-step procedure for calculations,” per Wikipedia. And TDD is great at helping drive out the vast majority of step-by-step procedures.

Oh–they mean complex algorithms. I see. That’s ok: Most of what we must implement on a day-to-day basis can be done with reasonably simple algorithms. In fact, I’d warrant that far less than a percent of any given system requires anything but simple algorithms that any journeyman programmer can easily devise. (And I’ve seen some very “complex” systems, such as BaBar and the Sabre GDS.)

Complex algorithms do require leaps achieved often only by appropriate insights, sometimes gained only after extensive thought about the problem, and sometimes never reached by a given single mind. TDD will not necessarily help your mind achieve those insights. However, its incremental nature can in some cases give you enough pause and isolation on a small piece of the problem, to the point where the insight needed almost screams at you.

Atom