Diamond Kata – TDD with only Property-Based Tests


Diamond Kata – TDD with only Property-Based Tests
// Semaphore CI Community Tutorials

This article is brought with ❤ to you by Semaphore.

The Diamond Kata is a simple exercise that Seb Rose described in a blog post on recycling tests in TDD.

Seb describes the Diamond Kata as:

Given a letter, print a diamond starting with ‘A’ with the supplied letter at the widest point.

For example: print-diamond ‘C’ prints

 A B B C C B B A 

Seb used the exercise to illustrate how he “recycles” tests to help him work incrementally towards a full solution. Seb’s approach prompted Alastair Cockburn to write an article in response in which he argued for more thinking before programming. Alastair’s article shows how he approached the Diamond Kata with more up-front analysis. Ron Jeffries and George Dinwiddie responded to Alastair’s article, showing how they approached the Diamond Kata relying on emergent design to produce an elegant solution (“thinking all the time”, as Ron Jeffries put it). There was some discussion on Twitter, and several other people published their approaches. (You can find a list of other solutions at the end of this article).

This problem seemed to be a good fit for property testing. Below are the results of an attempt to test-drive a solution using only property-based tests and see what happens. The solution is written in Scala, and uses ScalaTest to run and organise the tests and ScalaCheck for property testing.

What follows is an unexpurgated, warts-and-all walkthrough of the progress, not just the eventual complete solution. There have been wrong turns and stupid mistakes along the way.

The walkthrough is pretty long, so if you want, you don’t want to follow through step by step, jump straight to the complete solution and/or conclusions on how the exercise went and what I learned. Alternatively, if you want to follow the walkthrough in more detail, the entire history is on GitHub, with a commit per TDD step (add a failing test, commit, make the implementation pass the test, commit, refactor, commit, … and repeat).

Walkthrough

Getting Started: Testing the Test Runner

The first thing you might want to do when starting a new project is make sure your development environment and test runner are set up right, that you can run tests, and that test failures are detected and reported. You can use Gradle to bootstrap a new Scala project with dependencies on the latest versions of ScalaTest and ScalaCheck, and import the Gradle project into IntelliJ IDEA.

ScalaTest supports several different styles of test and assertion syntax. The user guide recommends writing an abstract base class that combines traits and annotations for your preferred testing style and test runner, so that’s what we will do first:

@RunWith(classOf[JUnitRunner]) abstract class UnitSpec extends FreeSpec with PropertyChecks { } 

The test class extends UnitSpec:

class DiamondSpec extends UnitSpec { } 

Let’s add a test that explicitly fails to check that the test framework, IDE and build hang together correctly. When you see the test failure, you’re ready to write the first real test.

The First Test

Given that we’re writing property tests, we have to start with a simple property of the diamond function, not a simple example.

We come up with a simple property:

For all valid input character, the diamond contains one or more lines of text.

To turn that into a property test, we must define “all valid input characters” as a generator. The description of the Diamond Kata defines valid input as a single upper case character. ScalaCheck has a predefined generator for that:

val inputChar = Gen.alphaUpperChar 

At this point, we haven’t decided how we will represent the diamond. We do know that our test will assert on the number of lines of text, so we write the property with respect to an auxiliary function, diamondLines(c:Char):Vector[String], which will generate a diamond for input character c and return the lines of the diamond in a vector.

"produces some lines" in { forAll (inputChar) { c => assert(diamondLines(c).nonEmpty) } } 

The way that the test reads in ScalaTest/ScalaCheck is pretty much a direct translation of the English description of the property into code.

To make the test fail, we write diamondLines as:

def diamondLines(c : Char) : Vector[String] = { Vector() } 

The entire test class is:

import org.scalacheck._ class DiamondSpec extends UnitSpec { val inputChar = Gen.alphaUpperChar "produces some lines" in { forAll (inputChar) { c => assert(diamondLines(c).nonEmpty) } } def diamondLines(c : Char) : Vector[String] = { Vector() } } 

The simplest implementation that will make that property pass is to return a single string:

object Diamond { def diamond(c: Char) : String = { "A" } } 

Let’s make the diamondLines function in the test call the new function and split its result into lines:

def diamondLines(c : Char) = { Diamond.diamond(c).lines.toVector } 

The implementation can be used like this:

object DiamondApp extends App { import Diamond.diamond println(diamond(args.lift(0).getOrElse("Z").charAt(0))) } 

A Second Test, But It is Not Very Helpful

We now need to add another property, to more tightly constrain the solution. Note that the diamond always has an odd number of lines — let’s test that:

For all valid input character, the diamond has an odd number of lines.

This implies that the number of lines is greater than zero (because vectors cannot have a negative number of elements and zero is even), so we will change the existing test rather than adding another one:

"produces an odd number lines" in { forAll (inputChar) { c => assert(isOdd(diamondLines(c).length)) } } def isOdd(n : Int) = n % 2 == 1 

But this new test has a problem: the existing solution already passes it. The diamond function returns a single line, and 1 is an odd number. This choice of property is not helping drive the development forwards.

A Failing Test to Drive Development, But a Silly Mistake

The next simplest property we come up with is the number of lines of the diamond. If ‘ord(c)’ is the number of letters between ‘A’ and c, (zero for A, 1 for B, 2 for C, etc.) then:

For all valid input characters, c, the number of lines in a diamond for c is 2*ord(c)+1.

At this point we make a silly mistake. We write the property as:

"number of lines" in { forAll (inputChar) { c => assert(diamondLines(c).length == ord(c)+1) } } def ord(c: Char) : Int = c - 'A' 

Let’s leave the mistake in the code as an experiment to see if the property tests will detect the error by becoming inconsistent, and how long it will take before they do so.

This kind of mistake would easily be caught by an example test. It’s a good idea to have a few examples, as well as properties, to act as smoke tests.

Let’s make the test pass with the smallest amount of production code possible — move the ord function from the test into the production code and use it to return the required number of lines that are all the same.

def diamond(c: Char) : String = { "A\n" * (ord(c)+1) } def ord(c: Char) : Int = c - 'A' 

Despite sharing the ord function between the test and production code, there’s still some duplication. Both the production and test code calculate ord(c)+1. We will want to address that before writing the next test.

Refactor: Duplicated Calculation

Let’s replace ord(c)+1 with lineCount(c), which calculates number of lines generated for an input letter, and inline the ord(c) function, because it’s now only used in one place.

object Diamond { def diamond(c: Char) : String = { "A\n" * lineCount(c) } def lineCount(c: Char) : Int = (c - 'A')+1 } 

We’ll use lineCount in the test as well:

"number of lines" in { forAll (inputChar) { c => assert(diamondLines(c).length == lineCount(c)) } } 

On reflection, using the lineCount calculation from production code in the test feels like a mistake.

Squareness

The next property we’ll add is:

For all valid input character, the text containing the diamond is square

Where “is square” means:

The length of each line is equal to the total number of lines

In Scala, this is:

"squareness" in { forAll (inputChar) { c => assert(diamondLines(c) forall {_.length == lineCount(c)}) } } 

We can make the test pass like this:

object Diamond { def diamond(c: Char) : String = { val side: Int = lineCount(c) ("A" * side + "\n") * side } def lineCount(c: Char) : Int = (c - 'A')+1 } 

Refactor: Rename the lineCount Function

The lineCount is also being used to calculate the length of each line, so we’ll rename it to squareSide.

object Diamond { def diamond(c: Char) : String = { val side: Int = squareSide(c) ("A" * side + "\n") * side } def squareSide(c: Char) : Int = (c - 'A')+1 } 

Refactor: Clarify the Tests

We can now say that we have reason to be a little dissatisfied with the way the tests read:

"number of lines" in { forAll (inputChar) { c => assert(diamondLines(c).length == squareSide(c)) } } "squareness" in { forAll (inputChar) { c => assert(diamondLines(c) forall {_.length == squareSide(c)}) } } 

The “squareness” property does not stand alone. It doesn’t communicate that the output is square unless combined with “number of lines” property.

Let’s refactor the test to disentangle the two properties:

"squareness" in { forAll (inputChar) { c => val lines = diamondLines(c) assert(lines forall {line => line.length == lines.length}) } } "size of square" in { forAll (inputChar) { c => assert(diamondLines(c).length == squareSide(c)) } } 

The Letter on Each Line

The next property we will write specifies which characters are printed on each line. The characters of each line should be either a letter that depends on the index of the line, or a space.

Because the diamond is vertically symmetrical, we only need to consider the lines from the top to the middle of the diamond. This makes the calculation of the letter for each line much simpler.

We’ll need to add a property for the vertical symmetry once we have made the implementation pass this test.

"single letter per line" in { forAll (inputChar) { c => val allLines = diamondLines(c) val topHalf = allLines.slice(0, allLines.size/2 + 1) for ((line, index) <- topHalf.zipWithIndex) { val lettersInLine = line.toCharArray.toSet diff Set(' ') val expectedOnlyLetter = ('A' + index).toChar assert(lettersInLine == Set(expectedOnlyLetter), "line " + index + ": \"" + line + "\"") } } } 

To make this test pass, we’ll change the diamond function to:

def diamond(c: Char) : String = { val side: Int = squareSide(c) (for (lc <- 'A' to c) yield lc.toString * side) mkString "\n" } 

This repeats the correct letter for the top half of the diamond, but the bottom half of the diamond is wrong. This will be fixed by the property for vertical symmetry, which we’ll write next.

Vertical Symmetry

The property for vertical symmetry is:

For all input character, c, the lines from the top to the middle of the diamond, inclusive, are equal to the reversed lines from the middle to the bottom of the diamond, inclusive.

"is vertically symmetrical" in { forAll(inputChar) { c => val allLines = diamondLines(c) val topHalf = allLines.slice(0, allLines.size / 2 + 1) val bottomHalf = allLines.slice(allLines.size / 2, allLines.size) assert(topHalf == bottomHalf.reverse) } } 

The implementation is:

def diamond(c: Char) : String = { val side: Int = squareSide(c) val topHalf = for (lc <- 'A' to c) yield lineFor(side, lc) val bottomHalf = topHalf.slice(0, topHalf.length-1).reverse (topHalf ++ bottomHalf).mkString("\n") } 

But this fails the “squareness” and “size of square” tests! The properties are now inconsistent. The test suite has detected the erroneous implementation of the squareSide function.

The correct implementation of squareSide is:

def squareSide(c: Char) : Int = 2*(c - 'A') + 1 

With this change, the implementation passes all of the tests.

The Position Of The Letter In Each Line

Now we will add a property that specifies the position and value of the letter in each line, and that all other characters in a line are spaces. Like the previous test, we can rely on symmetry in the output to simplify the arithmetic. This time, because the diamond has horizontal symmetry, we only need specify the position of the letter in the first half of the line. We’ll add a specification for horizontal symmetry, and factor out generic functions to return the first and second half of strings and sequences.

"is vertically symmetrical" in { forAll (inputChar) { c => val lines = diamondLines(c) assert(firstHalfOf(lines) == secondHalfOf(lines).reverse) } } "is horizontally symmetrical" in { forAll (inputChar) { c => for ((line, index) <- diamondLines(c).zipWithIndex) { assert(firstHalfOf(line) == secondHalfOf(line).reverse, "line " + index + " should be symmetrical") } } } "position of letter in line of spaces" in { forAll (inputChar) { c => for ((line, lineIndex) <- firstHalfOf(diamondLines(c)).zipWithIndex) { val firstHalf = firstHalfOf(line) val expectedLetter = ('A'+lineIndex).toChar val letterIndex = firstHalf.length - (lineIndex + 1) assert (firstHalf(letterIndex) == expectedLetter, firstHalf) assert (firstHalf.count(_==' ') == firstHalf.length-1, "number of spaces in line " + lineIndex + ": " + line) } } } def firstHalfOf[AS, A, That](v: AS)(implicit asSeq: AS => Seq[A], cbf: CanBuildFrom[AS, A, That]) = { v.slice(0, (v.length+1)/2) } def secondHalfOf[AS, A, That](v: AS)(implicit asSeq: AS => Seq[A], cbf: CanBuildFrom[AS, A, That]) = { v.slice(v.length/2, v.length) } 

The implementation is:

object Diamond { def diamond(c: Char) : String = { val side: Int = squareSide(c) val topHalf = for (letter <- 'A' to c) yield lineFor(side, letter) (topHalf ++ topHalf.reverse.tail).mkString("\n") } def lineFor(length: Int, letter: Char): String = { val halfLength = length/2 val letterIndex = halfLength - ord(letter) val halfLine = " "*letterIndex + letter + " "*(halfLength-letterIndex) halfLine ++ halfLine.reverse.tail } def squareSide(c: Char) : Int = 2*ord(c) + 1 def ord(c: Char): Int = c - 'A' } 

It turns out the ord function, which we inlined into squareSide a while ago, is needed after all.

The implementation is now complete. Running the DiamondApp application prints out diamonds. But there’s plenty of scope for refactoring both the production and test code.

Refactoring: Delete the “Single Letter Per Line” Property

The “position of letter in line of spaces” property makes the “single letter per line” property superfluous, so we can delete “single letter per line”.

Refactoring: Simplify the Diamond Implementation

Let’s rename some parameters and simplify the implementation of the diamond function.

object Diamond { def diamond(maxLetter: Char) : String = { val topHalf = for (letter <- 'A' to maxLetter) yield lineFor(maxLetter, letter) (topHalf ++ topHalf.reverse.tail).mkString("\n") } def lineFor(maxLetter: Char, letter: Char): String = { val halfLength = ord(maxLetter) val letterIndex = halfLength - ord(letter) val halfLine = " "*letterIndex + letter + " "*(halfLength-letterIndex) halfLine ++ halfLine.reverse.tail } def squareSide(c: Char) : Int = 2*ord(c) + 1 def ord(c: Char): Int = c - 'A' } 

The implementation no longer uses the squareSide function. It’s only used by the “size of square” property.

Refactoring: Inline the squareSide Function

We’ll inline the squareSide function into the test.

"size of square" in { forAll (inputChar) { c => assert(diamondLines(c).length == 2*ord(c) + 1) } } 

The erroneous calculation probably would have been easier to notice if we had done this from the start.

Refactoring: Common Implementation of Symmetry

There’s one last bit of duplication in the implementation. The expressions that create the horizontal and vertical symmetry of the diamond can be replaced with calls to a generic function. We’ll leave that as an exercise for the reader…

Complete Tests and Implementation

Tests:

import Diamond.ord import org.scalacheck._ import scala.collection.generic.CanBuildFrom class DiamondSpec extends UnitSpec { val inputChar = Gen.alphaUpperChar "squareness" in { forAll (inputChar) { c => val lines = diamondLines(c) assert(lines forall {line => line.length == lines.length}) } } "size of square" in { forAll (inputChar) { c => assert(diamondLines(c).length == 2*ord(c) + 1) } } "is vertically symmetrical" in { forAll (inputChar) { c => val lines = diamondLines(c) assert(firstHalfOf(lines) == secondHalfOf(lines).reverse) } } "is horizontally symmetrical" in { forAll (inputChar) { c => for ((line, index) <- diamondLines(c).zipWithIndex) { assert(firstHalfOf(line) == secondHalfOf(line).reverse, "line " + index + " should be symmetrical") } } } "position of letter in line of spaces" in { forAll (inputChar) { c => for ((line, lineIndex) <- firstHalfOf(diamondLines(c)).zipWithIndex) { val firstHalf = firstHalfOf(line) val expectedLetter = ('A'+lineIndex).toChar val letterIndex = firstHalf.length - (lineIndex + 1) assert (firstHalf(letterIndex) == expectedLetter, firstHalf) assert (firstHalf.count(_==' ') == firstHalf.length-1, "number of spaces in line " + lineIndex + ": " + line) } } } def firstHalfOf[AS, A, That](v: AS)(implicit asSeq: AS => Seq[A], cbf: CanBuildFrom[AS, A, That]) = { v.slice(0, (v.length+1)/2) } def secondHalfOf[AS, A, That](v: AS)(implicit asSeq: AS => Seq[A], cbf: CanBuildFrom[AS, A, That]) = { v.slice(v.length/2, v.length) } def diamondLines(c : Char) = { Diamond.diamond(c).lines.toVector } } 

Implementation:

object Diamond { def diamond(maxLetter: Char) : String = { val topHalf = for (letter <- 'A' to maxLetter) yield lineFor(maxLetter, letter) (topHalf ++ topHalf.reverse.tail).mkString("\n") } def lineFor(maxLetter: Char, letter: Char): String = { val halfLength = ord(maxLetter) val letterIndex = halfLength - ord(letter) val halfLine = " "*letterIndex + letter + " "*(halfLength-letterIndex) halfLine ++ halfLine.reverse.tail } def ord(c: Char): Int = c - 'A' } 

Conclusions

In his article, “Thinking Before Programming”, Alastair Cockburn writes:

The advantage of the Dijkstra-Gries approach is the simplicity of the solutions produced.

The advantage of TDD is modern fine-grained incremental development.

Can we combine the two?

Property-based tests in the TDD process combined the two quite successfully in this exercise. It allowed us to record half-formed thoughts about the problem and solution as generators and properties while using “modern fine-grained incremental development” to tighten up the properties and grow the code that met them.

In Seb’s original article, he writes that when working from examples…

it’s easy enough to get [the tests for ‘A’ and ‘B’] to pass by hardcoding the result. Then we move on to the letter ‘C’.

The code is now screaming for us to refactor it, but to keep all the tests passing most people try to solve the entire problem at once. That’s hard, because we’ll need to cope with multiple lines, varying indentation, and repeated characters with a varying number of spaces between them.

We didn’t encounter this problem when driving the implementation with properties. Adding a new property always required an incremental improvement to the implementation to get the tests passing again.

Neither did we need to write throw-away tests for behaviour that was not actually desired of the final implementation, as Seb did with his “test recycling” approach. Every property we added applied to the complete solution. We only deleted properties that were implied by properties we added later, and so had become unnecessary duplication.

We took the approach of starting from very generic properties and incrementally adding more specific properties as we refined the implementation. Generic properties were easy to come up with, and helped us make progress in the problem. The suite of properties reinforced one another, testing the tests, and detected the mistake we made in one property that caused it to be inconsistent with the rest.

With a better knowledge of Scala, ScalaTest or ScalaCheck we could have written a minimisation strategy for the input character. This would have made test failure messages easier to understand.

We also didn’t address what the diamond function would do with input outside the range of ‘A’ to ‘Z’. Scala doesn’t let one define a subtype of Char, so we can’t enforce the input constraint in the type system. The Scala way would be to define diamond as a PartialFunction[Char,String].

Further Thoughts

Other Solutions

Mark Seeman has approached Diamond Kata with property-based tests, using F# and FsCheck.

Solutions to the Diamond Kata using exmaple-based tests include:

Post originally published on http://www.natpryce.com/. Modified and republished with author’s permission.

Related Articles in the Semaphore Community

This article is brought with ❤ to you by Semaphore.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s