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 Scala, we can test functions interactively using Scala's interactive mode:

> scala -i triangle.scala

The option -i tells Scala to load triangle1.scala and then enter the interactive mode.

> scala -i triangle.scala 
Loading triangle.scala...
triangle: (n: Int)Unit
size: Int = 5
*
**
***
****
*****

Welcome to Scala version 2.11.5 (OpenJDK 64-Bit Server VM, Java 1.7.0_75).
Type in expressions to have them evaluated.
Type :help for more information.

scala> triangle(7)
*
**
***
****
*****
******
*******

scala> 

Instead you can also use :load command inside Scala's interactive mode. This also allows you to reload your code after you have made changes to it:

> scala
Welcome to Scala version 2.11.5 (OpenJDK 64-Bit Server VM, Java 1.7.0_75).
Type in expressions to have them evaluated.
Type :help for more information.

scala> :load triangle.scala
Loading triangle.scala...
triangle: (n: Int)Unit
size: Int = 5
*
**
***
****
*****

scala> triangle(3)
*
**
***

scala> 

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.scala with the following contents:

def 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:

> scala -i collatz.scala 
Loading collatz.scala...
next: (n: Int)Int

Welcome to Scala version 2.11.5 (OpenJDK 64-Bit Server VM, Java 1.7.0_75).
Type in expressions to have them evaluated.
Type :help for more information.

scala> next(1)
res0: Int = 4

scala> next(4)
res1: Int = 2

scala> next(2)
res2: Int = 1

scala> next(5)
res3: Int = 16

scala> next(16)
res4: Int = 8

scala> next(52)
res5: Int = 26

scala> next(123417432)
res6: Int = 61708716

scala> next(123417431)
res7: Int = 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:

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

Again I test it on an example:

> scala 
Welcome to Scala version 2.11.5 (OpenJDK 64-Bit Server VM, Java 1.7.0_75).
Type in expressions to have them evaluated.
Type :help for more information.

scala> :load collatz.scala
Loading collatz.scala...
next: (n: Int)Int
collatz: (n0: Int)Unit

scala> collatz(5)
5 16 8 4 2 
scala> 

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

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

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

scala> :load collatz.scala
Loading collatz.scala...
next: (n: Int)Int
collatz: (n0: Int)Unit

scala> collatz(5)
5 16 8 4 2 1

scala> collatz(16)
16 8 4 2 1

scala> collatz(17)
17 52 26 13 40 20 10 5 16 8 4 2 1

scala> 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:

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

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

scala> :load collatz.scala
Loading collatz.scala...
next: (n: Int)Int
collatzCount: (n0: Int)Int

scala> collatz(5)
5 16 8 4 2 1

scala> collatzCount(5)
res6: Int = 5

scala> collatz(16); collatzCount(16)
16 8 4 2 1
res7: Int = 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:

def findMax(n: Int) {
  var maxCount = 0
  var maxStart = 1
  for (i <- 2 to n) {
    val count = collatzCount(i)
    if (count > maxCount) {
      maxCount = count
      maxStart = i
    }
  }
  printf("Starting at %d needs %d steps.\n", maxStart, maxCount)
}

Here is the result of testing this function:

scala> :load collatz.scala
Loading collatz.scala...
next: (n: Int)Int
collatzCount: (n0: Int)Int
findMax: (n: Int)Unit

scala> findMax(100)
Starting at 97 needs 118 steps.

scala> findMax(500)
Starting at 327 needs 143 steps.

scala> findMax(1000)
Starting at 871 needs 178 steps.

scala> findMax(2000)
Starting at 1161 needs 181 steps.

scala> findMax(4000)
Starting at 3711 needs 237 steps.

scala> findMax(10000)
Starting at 6171 needs 261 steps.

scala> findMax(20000)
Starting at 17647 needs 278 steps.

scala> findMax(40000)
Starting at 35655 needs 323 steps.

scala> 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.