An important aspect of test-driven development: What’s my motivation?

Photo by Marc Kleen on Unsplash

A month ago, Fagner Brack published “This Is The One Thing Nobody Told You About TDD.” As someone who is still relatively new on the test-driven development (TDD) bandwagon, I definitely want to know what is that one thing nobody has told me about this programming philosophy I’m trying to adopt.

“The tests give you hints of what to do next. They drive you to build the code.” — Fagner Brack

Well, maybe I was luckier than most to have had an instructor, specifically Samah Majadla, who explained this to me. She didn’t use these exact words, but I think she got the point across to my classmates and I.

The tests motivate the production code. You write a simple test. Then you write the bare minimum necessary to make that test pass. Then you write a slightly more complicated test. And then write what’s needed to pass that test. And so on and so forth.

At each step of the process, to the best of your ability, don’t let the production code be more complex than strictly required to pass the tests. Because… the test drives the source.

The refactoring step of the TDD cycle gets very little attention. If there really is something about TDD that no one has ever told me, it’s likelier to be in the refactoring step.

But the thing about refactoring, though, is that it’s about simplifying the production code. If during refactoring you think of an improvement that’s not about simplifying what you wrote to pass the test, don’t make that change yet: write a test first.

I think the greatest common divisor (GCD) function provides a nice, simple and to-the-point example of how to do TDD.

Quick math refresher: the greatest common divisor of two integers is the greatest positive integer that divides them both. For instance, gcd(−91, −98) = 7, because both −91 and −98 are divisible by 7.

Also I think it’s better to demonstrate TDD in a programming language with a commonly preferred testing framework, like Java with JUnit, or C# with xUnit.

Because of the naming convention, you might think that JsUnit is the commonly preferred testing framework for JavaScript. But that’s a can of worms I better leave to someone else to tackle.

I like to start by writing a stub that will obviously fail the test. It doesn’t matter much if you’re writing your source code in a plain text editor and compiling on the command line, but in an integrated development environment (IDE) like NetBeans or IntelliJ, stubs help the IDE give you more pertinent errors and warnings.

So here’s our GCD stub that should obviously fail the first test:

For the first test, you might already be thinking of a pair of distinct numbers, like −27 and 18. But we can go simpler than that for our first test: how about gcd(n, n), where n is a positive integer?

Then obviously gcd(n, n) = n. So our first test then looks like this:

At this point, there are two valid ways to amend gcd() to pass the test. One way is:

The other way is to return b instead of a. Either way, the test should pass now.

At this point it might be too much to test if a == b, and it would certainly be too much to write a full-fledged implementation of an algorithm that derives lists of divisors from the prime factorizations of the integers and is equipped to handle the special case gcd(Integer.MIN_VALUE, Integer.MIN_VALUE) with a very elegant and informative custom exception.

We’ll get to that, but only after writing the relevant tests. No refactoring is needed at this point, because all we did was substitute one character for two characters on a function that was just a simple stub.

Can we do a test for two distinct numbers now? We could, but I think there is one other simpler thing we can do first: test for gcd(n, n) with n a negative integer. Let’s not use the MIN_VALUE of our numeric data type, though.

This should fail because it should give us −10 instead of +10. The fix to pass is easy.

Or we could also use Math.abs(b), either way it’s enough to pass the tests so far.

Okay, now let’s write a test with distinct numbers. At this point, it should be only positive numbers though, we should probably hold off on a test with one positive and one negative number.

Clearly this test will fail because the GCD is neither of the input numbers.

Now can we write the proper GCD implementation? We could, but it’s actually still quite easy to be a smart-aleck with this one. Notice that the GCD in this case is the difference of a and b. So…

At this point you’re probably ready to actually write an actual GCD function, so here’s a test that will hopefully require that.

We’re trying to steer well clear of numbers above 2³⁰, so as to not deal with overflow issues yet.

I suppose it’s still possible at this point to write an implementation that will pass this test but fail other simple tests with likely inputs, like gcd(336, −864) or gcd(245, 343).

But now the complexity of detecting what the wanted result might be vastly outweighs the complexity of actually writing a proper GCD implementation that works for all but a few unlikely edge cases.

There are at least three distinct algorithms we could use to find the GCD of two integers. If you know one I don’t mention, please let me know about it in the comments.

One way is to obtain the prime factorizations of both numbers and multiply the factors that they have in common. For example, 1050 = 2 × 3 × 5² × 7 and 1125 = 3² × 5³, so 3 × 5² = 75, and indeed gcd(1050, 1125) = 75.

The problem with this is that we would need to either write a new prime factorization function (which we’ll have to test and develop) or find one from a third party library.

We also need something to find the elements in common of two sets (what mathematicians call “intersection”). With this algorithm, we’re going to get sidetracked.

To me the most obvious algorithm is to list the positive divisors of each number and then find the largest one of them.

Using the same example as before, we see that the positive divisors of 1050 are 1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 25, 30, 35, 42, 50, 70, 75, 105, 150, 175, 210, 350, 525 and 1050 itself.

The positive divisors of 1125 are 1, 3, 5, 9, 15, 25, 45, 75, 125, 225, 375 and 1125 itself. The numbers in common to both sets are 1, 3, 5, 15, 25, 75, of which 75 is obviously the largest number, and thus the greatest common divisor.

In Scala this would be very easy to implement. Here is the example on the Scala REPL:

This might not be the most elegant way to do this in Scala, but for some quick and dirty experiments on the REPL, it’s just fine.

In Java, we’d have to write these things from scratch, or find a third party library. Though in Scala it would still be good form to write tests for a list of divisors function.

Regardless, both of these algorithms have the potential to sidetrack us from the objective of writing the bare minimum implementation that will pass all the tests we’ve written so far.

In this GCD scenario, our motivation is to write the simplest implementation that will meet the requirements expressed by the tests we have written. No more, no less.

So the Euclidean GCD algorithm here is the simplest and most direct way to get at our goal. However, let us take a brief moment to reflect on the mathematical principles at work here.

To use the Euclidean GCD algorithm, we need a Euclidean function f(n) such that f(n) is always a positive integer, except for f(0) = 0, and such that whenever d is a divisor of n, the inequality f(d) ≤ f(n) is true.

Almost always the absolute value function is chosen for this purpose, so much so that it gets taken for granted. And since Java comes with Math.abs() standard, we don’t have to reinvent the wheel on this one.

Then, to figure out gcd(a, b), if f(b) ≤ f(a) (swap a and b if necessary), we need to find numbers q and r such that a = qb + r and f(r) < f(b) (it must be less than, not less than or equal to).

If r = 0, we’re done, the gcd is b. If not, then we reset a to b and b to r, and go through the process of finding numbers q and r such that a = qb + r and f(r) < f(b) all over again.

To use the example gcd(1050, 1125) once more, we see that 1125 = 1 × 1050 + 75. Since our remainder is not 0, we go on to 1050 = 14 × 75 + 0. The remainder is now 0 and the GCD is 75.

I think this is enough information for you to implement a proper GCD function that passes the tests presented here so far, as well as other simple tests that you may devise.

It is a well known fact that the Euclidean GCD algorithm is the least efficient for consecutive Fibonacci numbers. Work out gcd(−144, 89) on paper, for example. By prime factorization it is much quicker to confirm your hunch that these two numbers are coprime.

However, computers are so fast that you won’t notice any performance penalty even for gcd(1134903170, 1836311903). You’d have to go well above the upper limits of int and long to notice any performance degradation.

If you do need to test for performance, I’d read up on timeouts in JUnit. The basic idea is that you allot a certain number of milliseconds for the test to run, and if it’s not done in that time, the test fails.

In Scala, we could implement gcd() in such a way that it can take a custom Euclidean function at runtime, but uses Math.abs() as the default Euclidean function if no Euclidean function is specified. It would go something like this:

Our TDD process would be the same as with Java, aside from superficial differences, and we could continue to use JUnit, at least for the time being.

Thanks to the implicit parameter (assuming I have the right syntax), we wouldn’t need to go back and add “, Math.abs” to the gcd() calls in the previous tests.

The crucial difference would be in testing that gcd() actually uses a custom function that we pass it during a test.

The way we would do that might be to pass an invalid Euclidean function (like one that returns negative integers) and seeing if it throws an exception or if it just uses the absolute value function and returns the right result anyway.

At that point, our draft of gcd() should be such that it uses Math.abs() regardless of what function we pass it. Then, once we have a test fail because our custom function is ignored, we go ahead and rework gcd() so that it does use the custom function.

Aside from these functional considerations, the TDD process in Scala is hardly different from the TDD process in Java.

Earlier I mentioned the case gcd(Integer.MIN_VALUE, Integer.MIN_VALUE), and that maybe this should cause a custom exception.

The GCD in that example is of course Integer.MAX_VALUE + 1, which obviously can’t be properly represented in a signed 32-bit int. We’d have much the same issue with Long.MIN_VALUE if we were using long instead of int, but at the signed 64-bit threshold instead.

But why write a custom exception (which we’ll have to take through the TDD process as well) when we can just use an existing exception in the standard Java library?

I think ArithmeticException makes sense for this purpose.

If you prefer the “old school” try-catch with fail, you can also have the test report the erroneous result (probably 0) if the exception is not triggered.

Once you have this test fail because gcd() did not throw new ArithmeticException for this edge case, you can go ahead and write where that actually happens.

Depending on how you actually implement gcd(), it could be the case that ArithmeticException arises for this edge case without your having to actually write a throw statement.

By writing the test first, you can then see if it really is necessary for you to make any changes to what you have so far. It might be, it might not be, the results of the test will tell you.

That’s the point of TDD: write the test, then, if necessary, write what’s needed to pass the test. Don’t write more than what is necessary, let the tests show you what is needed and what isn’t.

I hope someone has already told you this. I also hope my exposition here has made it clearer in your mind.

is a composer and photographer from Detroit, Michigan. He has been working on a Java program to display certain mathematical diagrams.