Incremental testing

When you write a program, it is tempting to write the whole program, and then start debugging it.

In general, this is very bad strategy. It is much more effective to test every function immediately after you have written it.

Continue working on the next function only after the first one works correctly.

In Kotlin, we can test functions interactively using the interactive mode. We use the :load command inside the interactive mode. The same command allows us to reload our code after we have made changes to it:

$ ktc
Welcome to Kotlin version 1.0.1-2 (JRE 1.7.0_95-b00)
Type :help for help, :quit for quit
>>> :load triangle.kts
>>> triangle(3)
*
**
***
>>> triangle(5)
*
**
***
****
*****

A worked out example: the Collatz problem

Let's practice incremental testing on an example, the so-called Collatz problem.

Consider a sequence of integers following the rule:

If you provide a starting value \(n_0\), this determines an entire sequence. Here are a few examples, with starting values 5, 34, 7, and 672:

5 16 8 4 2 1
34 17 52 26 13 40 20 10 5 16 8 4 2 1
7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
672 336 168 84 42 21 64 32 16 8 4 2 1

You can notice that all four example sequences reach the number 1 (and then of course the sequence starts cycling: 1 4 2 1 4 2 1 4 2 1...).

It is conjectured that this is always true: for any starting value, the sequence arrives at 1.

We want to do some experiments with this conjecture, for instance to determine experimentally which starting value gives long chains. So we want to write functions that, given the starting value, can print out the entire sequence, and can print the number of steps until 1 is reached.

Let's start with the basic function: Given \(n_i\), compute the next number \(n_{i+1}\). I create a file collatz.kts with the following contents:

fun next(n: Int): Int = 
  if (n % 2 == 0)
    n / 2
  else
    3 * n + 1

We test this function by loading the file and checking that it correctly handles both the even and the odd case:

$ ktc
Welcome to Kotlin version 1.0.1-2 (JRE 1.7.0_95-b00)
Type :help for help, :quit for quit
>>> :load collatz.kts
>>> next(1)
4
>>> next(4)
2
>>> next(2)
1
>>> next(5)
16
>>> next(16)
8
>>> next(52)
26
>>> next(123417432)
61708716
>>> next(123417431)
370252294

The functions seems to work, so the next step is to write a function that prints the entire sequence starting from a given starting value. We add the function collatz to our file:

fun collatz(n0: Int) {
  var n = n0
  while (n != 1) {
    print(n)
    print(" ")
    n = next(n)
  }
}

I reload the file and test it on an example:

>>> :load collatz.kts
>>> collatz(5)
5 16 8 4 2

And already I notice my mistake: the loop doesn't print the final 1. So I change my function as follows (collatz.kts):

fun collatz(n0: Int) {
  var n = n0
  while (n != 1) {
    print(n)
    print(" ")
    n = next(n)
  }
  println(1)
}

And I can continue testing by reloading the file and trying again:

>>> :load collatz.kts
>>> collatz(5)
5 16 8 4 2 1
>>> collatz(16)
16 8 4 2 1
>>> collatz(17)
17 52 26 13 40 20 10 5 16 8 4 2 1
>>> collatz(27)
27 82 41 124 62 31 94 47 142 71 214 107 322 161 484 242 121 364 182 91
274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186
593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425
1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644
1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732
866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160
80 40 20 10 5 16 8 4 2 1

Now it seems to work well.

The next function will count the number of steps done from a given starting value until we reach 1:

fun collatzCount(n0: Int): Int {
  var n = n0
  var count = 0
  while (n != 1) {
    n = next(n)
    count += 1
  }
  return count
}

I test this by comparing the result with the output of collatz:

>>> :load collatz.kts
>>> collatz(5)
5 16 8 4 2 1
>>> collatzCount(5)
5
>>> collatz(16); collatzCount(16)
16 8 4 2 1
4

Finally, I'll write a function that tries all starting values between 2 and a given maximum \(n\), and reports the starting value with the longest sequence (collatz3.kts):

fun findMax(n: Int) {
  var maxCount = 0
  var maxStart = 1
  for (i in 2 .. n) {
    val count = collatzCount(i)
    if (count > maxCount) {
      maxCount = count
      maxStart = i
    }
  }
  println("Starting at $maxStart needs $maxCount steps.")
}

Here is the result of testing this function:

>>> :load collatz3.kts
>>> findMax(100)
Starting at 97 needs 118 steps.
>>> findMax(500)
Starting at 327 needs 143 steps.
>>> findMax(1000)
Starting at 871 needs 178 steps.
>>> findMax(2000)
Starting at 1161 needs 181 steps.
>>> findMax(4000)
Starting at 3711 needs 237 steps.
>>> findMax(10000)
Starting at 6171 needs 261 steps.
>>> findMax(20000)
Starting at 17647 needs 278 steps.
>>> findMax(40000)
Starting at 35655 needs 323 steps.
>>> findMax(80000)
Starting at 77031 needs 350 steps.

Unit testing

For a large program, it is common to write a separate test program for every function or class. These test programs are called unit tests.

Some programmers even write the tests before the code!

The unit tests remain useful even when the program is finished. All software needs to be maintained. Whenever a change is made to the software, we can run the unit tests again to get confidence that we didn’t break anything.

On many software projects, unit tests are automated and run every night, to ensure that the changes made during the day didn’t create any new bugs.

We will not ask you to write unit tests in CS109, but you should get in the habit of testing your functions. Often you can test by hand, interactively. But when you need more than two or three lines of code to test a function, it makes sense to write extra testing functions. Keep those in your code, so that you can use them again later to check your program when you have made changes.