TDD Basics : TDD Cycle : Red, Green, Refactor

Objectives


  • What is a Starter Test? When to use it?
  • Focus on getting it to work first, cleanup by refactoring and then focus on optimization.
  • When refactoring, start green and end in green.
  • Learn recursive solution and optimize the execution by using non-recursive solution.
  • Using existing tests as regression tests when making major changes to existing code.

alt text

Problem Statement


Generate Fibonacci sequence for a given number.

Problem Domain Analysis


In mathematics, the Fibonacci numbers are the numbers in the following integer sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 ... By definition, the first two numbers in the Fibonacci sequence are 0 and 1 and each subsequent number is the sum of the previous two.

alt text

Algebraic Equation

In mathematical terms, the sequence fibonacci(n) of Fibonacci numbers is defined by the recurrence relation :

fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) 

with seed values

fibonacci(0) = 0
fibonacci(1) = 1

alt text

Visual Representation

alt text

Sample Input Output

Each input output set is an example. Make each example executable.

Input  : 0, 1, 2, 3, 4, 5
Output : 0, 1, 1, 2, 3, 5 

alt text

alt text

The final solution should be able to take any random number and calculate the Fibonacci number without any modification to the production code.

Initial Conditions

First two numbers are given (not calculated).

Solution Domain Analysis


alt text

Steps


Step 1

In this step, we set up the environment.

require 'test/unit'

class FibonacciTest < Test::Unit::TestCase
  def test_fibonacci_of_zeror_is_zeror
    fail 'fail'
  end
end

In this step, we got the proper require statement to execute the test. The test also follows the proper naming convention for tests. This example illustrates how to go from Requirements to Examples to Executable Specs. Each test for this problem takes an argument, does some computation and returns a result. It illustrates Direct Input and Direct Output. This is called State Based Testing. In State Based Testing, there are no side effects. Side effect free functions are easy to test.

See the appendix of the Essential TDD book for definition of Direct Input, Direct Output and Side Effects.

Step 2

In this step, we will discover the public API. Here is the fibonacci_test.rb

require 'test/unit'

class Fibonacci
  def self.of(number)
    0
  end
end

class FibonacciTest < Test::Unit::TestCase
  def test_fibonacci_of_zero_is_zero
    fib_of_zero = Fibonacci.of(0)
    assert_equal(fib_of_zero, 0)
  end
end

Starter Test

Start by testing a variant of an operation that doesn't do anything. If you write a realistic test first, then you will find yourself solving a bunch of problems at once. Realistic test will leave you too long without feedback. You want the red/green/refactor loop to take just minutes. You can shorten the loop by choosing inputs and outputs that are trivially easy to discover. Pick a Starter Test that will teach you something but that you are certain you can quickly get to work.
----- Kent Beck (Test-driven Development: By Example)

Starter Test is helpful when you are implementing something unfamiliar or complicated. You don't need the Starter Test when you are confident, you can pick a test that will require a non-trivial operation.

Step 3

Don't change the test code and code under test at the same time.

require 'test/unit'

class Fibonacci
  def self.of(number)
    0
  end
end

class FibonacciTest < Test::Unit::TestCase
  def test_fibonacci_of_zero_is_zero
    fib_of_zero = Fibonacci.of(0)
    assert_equal(0, fib_of_zero)
  end
end

In this step, I found the right assertion to use. You can see the order of the parameters for assert_equal matters. I overcame the temptation to change the test code and code under test at the same time. Thereby test driving the development of the production code. I got the test to pass quickly by using a fake implementation. The fake implementation returns a constant.

Step 4

Here is the dirty implementation that makes fib(1) = 1 pass very quickly using a dirty implementation.

require 'test/unit'

class Fibonacci
  def self.of(number)
    number
  end
end

class FibonacciTest < Test::Unit::TestCase
  def test_fibonacci_of_zero_is_zero
    fib_of_zero = Fibonacci.of(0)
    assert_equal(0, fib_of_zero)
  end

  def test_fibonacci_of_one_is_one
    fib_of_one = Fibonacci.of(1)
    assert_equal(1, fib_of_one)
  end
end

Step 5

In this step, we force the implementation to change via tests. The broken test forced the implementation to change. Here is the dirty implementation that passes the test.

require 'test/unit'

class Fibonacci
  def self.of(number)
    if number == 2
      return 1
    else
      return number
    end
  end
end

class FibonacciTest < Test::Unit::TestCase
  # First two specs are same as before

  def test_fibonacci_of_two_is_one
    fib_of_two = Fibonacci.of(2)
    assert_equal(1, fib_of_two)
  end
end

Step 6

This step is about refactoring in the green state. The new test broke the implementation. Commented out the new test to refactor the test in green state.

require 'test/unit'

class Fibonacci
  def self.of(number)
    if number == 0
      return 0
    elsif number <= 2
      return 1
    end
  end
end  

class FibonacciTest < Test::Unit::TestCase

  def test_fibonacci_of_zero_is_zero
    fib_of_zero = Fibonacci.of(0)
    assert_equal(0, fib_of_zero)
  end

  def test_fibonacci_of_one_is_one
    fib_of_one = Fibonacci.of(1)
    assert_equal(1, fib_of_one)
  end

  def test_fibonacci_of_two_is_one
    fib_of_two = Fibonacci.of(2)
    assert_equal(1, fib_of_two)
  end

  def xtest_fibonacci_of_three_is_two
    fib_of_three = Fibonacci.of(3)
    assert_equal(2, fib_of_three)
  end

end

Step 7

In this step we are going to use fake implementation.

require 'test/unit'

class Fibonacci
  def self.of(number)
    if number == 0
      return 0
    elsif number <= 2
      return 1
    end
    return 2
  end
end  

class FibonacciTest < Test::Unit::TestCase

  def test_fibonacci_of_zero_is_zero
    fib_of_zero = Fibonacci.of(0)
    assert_equal(0, fib_of_zero)
  end

  def test_fibonacci_of_one_is_one
    fib_of_one = Fibonacci.of(1)
    assert_equal(1, fib_of_one)
  end

  def test_fibonacci_of_two_is_one
    fib_of_two = Fibonacci.of(2)
    assert_equal(1, fib_of_two)
  end

  def test_fibonacci_of_three_is_two
    fib_of_three = Fibonacci.of(3)
    assert_equal(2, fib_of_three)
  end

end

Step 8

Let's now look at recursive solution. When you look at the input and output for the Fibonacci sequence:

Input  : 0 1 2 3
Output : 0 1 1 2

We see that the pattern emerges and we see the result is the sum of previous two Fibonacci numbers. So

return 2

is actually return 1 + 1 which from the above same data set is :

fib(n-1) + fib(n-2)

This is the generic solution to this problem.

require 'test/unit'

class Fibonacci
  def self.of(number)
    if number == 0
      return 0
    elsif number <=2
      return 1
    end
    return of(number - 1) + of(number - 2)
  end
end

class FibonacciTest < Test::Unit::TestCase

  def test_fibonacci_of_zero_is_zero
    fib_of_zero = Fibonacci.of(0)
    assert_equal(0, fib_of_zero)
  end

  def test_fibonacci_of_one_is_one
    fib_of_one = Fibonacci.of(1)
    assert_equal(1, fib_of_one)
  end

  def test_fibonacci_of_two_is_one
    fib_of_two = Fibonacci.of(2)
    assert_equal(1, fib_of_two)
  end

  def test_fibonacci_of_three_is_two
    fib_of_three = Fibonacci.of(3)
    assert_equal(2, fib_of_three)
  end

end

We now have the generalized solution that uses recursion.

Step 9

Let's clean up the solution.

require 'test/unit'

class Fibonacci
  def self.of(n)
    return 0 if n == 0
    return 1 if n == 1
    return of(n-1) + of(n-2)
  end
end

# Specs same as previous steps

Before starting refactoring you must be in green state. After refactoring is done you should still be in green state. You can see that the variables are expressive of the domain.

Step 10

Let's now add a new test that is a large number to make sure our solution is good.

def test_fibonacci_of_ten_is_fifty_five
  fib_of_ten = Fibonacci.of(10)
  assert_equal(55, fib_of_ten)
end

This is a story test. It gives us the confidence that our solution is complete. So we don't have to write any more tests and we are done.

Step 11

Let's us now optimize the solution.

require 'test/unit'

class Fibonacci
  def self.of(n)
    current, successor = 0, 1
    n.times do
      current, successor = successor, current + successor
    end
    return current
  end
end

# Tests are same as before.

This version illustrates using existing tests as safety net when making major changes to the code. Notice that we only focus on one thing at a time. The focus can shift from one version to the other.

alt text

Code Mutation we discussed in a previous article is also part of the TDD Cycle. Regression is one of the goals of TDD and we have seen how to use existing test suite as a safety net for catching regression bugs.

TDD Cycle

alt text

In this example we saw how we go about repeating the TDD cycle many times to form a rhythm. We wrote a failing test, we quickly made it pass with a quick and dirty implementation and then we refactored to cleanup the code. The focus is on the design during the refactor step.

Exercises


1) Run the mini-test based Fibonacci and sure all tests pass.

$ruby fibonacci_test.rb

2) Move the Fibonacci class into its own file and make all the tests pass.
3) Get the output of the mini-test in color.
4) Convert the given mini-test to rspec version fibonacci_spec.rb. You can refer the solution in the appendix of the Essential TDD book.


Related Articles


Ace the Technical Interview

  • Easily find the gaps in your knowledge
  • Get customized lessons based on where you are
  • Take consistent action everyday
  • Builtin accountability to keep you on track
  • You will solve bigger problems over time
  • Get the job of your dreams

Take the 30 Day Coding Skills Challenge

Gain confidence to attend the interview

No spam ever. Unsubscribe anytime.