Part III: Testing and Timing (page 2)

Property-based testing

On the previous page, we developed a few unit tests for the reverseSort function, which we successfully passed. We did use randomized data, which is a good thing for testing, but then we had to resort to a so-called test oracle, namely isListReversed in order to check results. A more advanced form of unit testing is property-based testing, the advantage being that it will test functions with randomly generated inputs in an automated way. Whereas we created a few literal examples to test, as well as a few randomized inputs to test, the property-based testing process is geared to automatically generate inputs for testing. For this purpose we will be using FsCheck. A quote from a nice article on property-based testing

In some cases that is acceptable (see the use of “test oracles” in a following post), but in general, it’s a bad idea to have your tests duplicate the code that you are testing! It’s a waste of time and effort, and now you have two implementations to build and keep up to date.

So if you can’t test by using [equivalent code], how can you test?

The answer is to create tests that focus on the properties of the function — the “requirements”. These properties should be things that are true for any correct implementation.

The basic idea of a property-based tester is that test data is automatically generated, using a generator function, and properties of the function under test are tested. This is contrasted with simpler unit testing, wherein specific inputs are tested. The test generator function tries to create example inputs that tend to grow larger. There is also a shrinker function that works hand-in-hand with the generator such that when a failure is found, the input that caused the failure is then ‘shrunk’ trying to find a smaller input that also causes a failure — the idea being that it would be nice to present a small input that causes a test failure. The concepts of growing and shrinking inputs are abstract ideas and not necessarily strict in terms of particular input sizes. For typical input types, such as ints, floats, strings, lists, etal FsCheck provides generator and shrinker functions (which can be overridden), but for custom types you may need to create your own such functions.

So what are the properties that we can test, for reverseSort and later for the rest of the code created? Let’s dig in with a code listing:

  1: 
  2: 
  3: 
  4: 
  5: 
  6: 
  7: 
  8: 
  9: 
 10: 
 11: 
 12: 
 13: 
 14: 
 15: 
 16: 
 17: 
 18: 
 19: 
 20: 
 21: 
 22: 
 23: 
 24: 
 25: 
 26: 
 27: 
 28: 
 29: 
 30: 
 31: 
 32: 
 33: 
 34: 
 35: 
 36: 
 37: 
 38: 
 39: 
 40: 
 41: 
 42: 
 43: 
 44: 
 45: 
 46: 
 47: 
 48: 
 49: 
 50: 
 51: 
 52: 
 53: 
 54: 
 55: 
 56: 
 57: 
 58: 
 59: 
 60: 
 61: 
 62: 
 63: 
 64: 
 65: 
 66: 
 67: 
 68: 
 69: 
 70: 
 71: 
 72: 
 73: 
 74: 
 75: 
 76: 
 77: 
 78: 
 79: 
 80: 
 81: 
 82: 
 83: 
 84: 
 85: 
 86: 
 87: 
 88: 
 89: 
 90: 
 91: 
 92: 
 93: 
 94: 
 95: 
 96: 
 97: 
 98: 
 99: 
100: 
101: 
102: 
103: 
104: 
105: 
106: 
107: 
108: 
109: 
110: 
111: 
112: 
113: 
114: 
115: 
116: 
117: 
118: 
119: 
120: 
121: 
122: 
123: 
124: 
125: 
126: 
127: 
128: 
129: 
130: 
131: 
132: 
133: 
134: 
135: 
136: 
137: 
138: 
139: 
140: 
141: 
142: 
143: 
144: 
145: 
146: 
147: 
148: 
149: 
150: 
151: 
152: 
153: 
154: 
155: 
156: 
157: 
158: 
159: 
160: 
161: 
162: 
163: 
164: 

namespace BandBTest
open BandBapplication
open Xunit
open FsUnit.Xunit
open FsCheck
open FsCheck.Xunit
[<AutoOpen>]
module TestIsReversed =
let rec isListReversed li =
match li with
| [] | [_] -> true
| a::ls -> if a < ls.Head then false
else isListReversed ls
// isListReversed tests
[<Fact>]
let ``isListReversed ints []`` () = 
[] |> isListReversed |> should equal true
[<Fact>]
let ``isListReversed ints [7;0]`` () = 
[7;0] |> isListReversed |> should equal true
[<Fact>]
let ``isListReversed ints [0;7]`` () = 
[0;7] |> isListReversed |> should equal false
[<Fact>]
let ``isListReversed ints [7]`` () = 
[7] |> isListReversed |> should equal true
[<Fact>]
let ``isListReversed ints [2;3;1]`` () = 
[2;3;1] |> isListReversed |> should equal false
[<Fact>]
let ``isListReversed ints [3;2;1]`` () = 
[3;2;1] |> isListReversed |> should equal true
[<Fact>]
let ``isListReversed ints [3;2;-1]`` () = 
[3;2;-1] |> isListReversed |> should equal true
[<Fact>]
let ``isListReversed ints [3;3;-1]`` () = 
[3;3;-1] |> isListReversed |> should equal true
[<Fact>]
let ``isListReversed ints [-1;-1;3;3;-1]`` () = 
[-1;-1;3;3;-1] |> isListReversed |> should equal false
[<Property>]
let ``a pair out of order`` (xs:int list) =
// might we randomly find a pair of elements that are out of order?
let rnd = System.Random() // no seed
let revSorted = xs |> List.reverseSort |> List.toArray  // make it an array for indexed access
let sz = revSorted.Length
if sz >= 2 then 
let i1 = rnd.Next(sz)
let i2 = rnd.Next(i1,sz)  // ok if i1 = i2, but i1 <= i2 always!
revSorted.[i1] >= revSorted.[i2]
else
true    // test OK, all lists of zero or 1 length are reverseSorted!
[<AutoOpen>]
module TestReverseSort =
let randList count =
let rnd = System.Random(100)    // use a seed so that everytime we run we get the same values
List.init count (fun _ -> rnd.Next ())
// shuffle an array (in-place). adapted from: http://www.fssnip.net/L
// we leave this untested. 
let shuffle a =
let rand = new System.Random()
let swap (a: _[]) x y =
let tmp = a.[x]
a.[x] <- a.[y]
a.[y] <- tmp
Array.iteri (fun i _ -> swap a i (rand.Next(i, Array.length a))) a
let shuffleList l =
let a = List.toArray l
shuffle a  // in place
Array.toList (a)
// some property-based tests:
[<Property>]
let propRevForInts (xs:int list) = 
xs |> List.reverseSort |> isListReversed
[<Property>]
let propRevForStrings (xs:string list) = 
xs |> List.reverseSort |> isListReversed
// shuffle property test
[<Property>]
let propIsShuffledOKInt (xs:int list) = 
let xs_shuffled = shuffleList xs
(xs |> List.reverseSort) = (xs_shuffled |> List.reverseSort)
[<Property>]
let propIsShuffledOKString (xs:string list) = 
let xs_shuffled = shuffleList xs
(xs |> List.reverseSort) = (xs_shuffled |> List.reverseSort)
[<Property>]
let propIsRevOKInt (xs:int list) = 
let xs_rev = xs |> List.rev
(xs |> List.reverseSort) = (xs_rev |> List.reverseSort)
[<Property>]
let propIsRevOKString (xs:string list) = 
let xs_rev = xs |> List.rev
(xs |> List.reverseSort) = (xs_rev |> List.reverseSort)
module Main =
[<EntryPoint>]
let main argv = 
// FsCheck - same tests as above, but as executable code instead!
let revForInts (xs:int list) = xs |> List.reverseSort |> isListReversed
printf "int list isListReversed:        "
Check.Quick revForInts
let revForStrings (xs:string list) = xs |> List.reverseSort |> isListReversed
printf "string list isListReversed:     "
Check.Quick revForStrings
// shuffle property test
let isShuffledOKInt (xs:int list) = 
let xs_shuffled = shuffleList xs
(xs |> List.reverseSort) = (xs_shuffled |> List.reverseSort)
printf "int list isShuffledOKInt:       "
Check.Quick isShuffledOKInt
let isShuffledOKString (xs:string list) = 
let xs_shuffled = shuffleList xs
(xs |> List.reverseSort) = (xs_shuffled |> List.reverseSort)
printf "string list isShuffledOKString: "
Check.Quick isShuffledOKString
// shuffle property test
let isRevOKInt (xs:int list) = 
let xs_rev = xs |> List.rev
(xs |> List.reverseSort) = (xs_rev |> List.reverseSort)
printf "int list isRevOKInt:            "
Check.Quick isRevOKInt
let isRevOKString (xs:string list) = 
let xs_rev = xs |> List.rev
(xs |> List.reverseSort) = (xs_rev |> List.reverseSort)
printf "string list isRevOKString:      "
Check.Quick isRevOKString
printfn "\nDONE"
System.Console.ReadKey() |> ignore  // don't close the output window until a key is hit
0

First, I organized the tests a bit using modules. The TestIsReversed module is testing our ‘test oracle’ that determines if a list is in reverse order. These tests use our standard unit tests, as well as one property-based test ``a pair out of order`` on lines 56-67 (the result is shown as the first test output in the next image). This test takes the argument that is provided by FsCheck and sees if there is a random pair of elements that are out of order. Of course, we if instead of just checking one random pair we tested all such pairs than this would be a definitive test, but I leave implementing that as an exercise. Given the recursive structure of isListReversed, it isn’t hard to actually prove that it is correct using induction, but that is beyond our scope here. So I think that we are safe to conclude that this function is indeed correct.

We next look at some property-based testing in the TestReverseSort module. The first two tests use the isListReversed function that we just tested for int and string lists (on lines 91-97). The next tests check some general properties of a reverse sort. The first (applied to both int and string list arguments) checks if the reverse sort of the input array and the same array shuffled are equal (of course these should be). The shuffle code is from here, and we leave this untested. Similarly, the next two tests require that the reverse sort of the input list and this list reversed are the same. These are some general properties of a reverse sort that should be true for any correct reverse sort algorithm.

The results will look like this:

More test results

However, I also show how to use executable code for testing in the main module, lines 123-163. This code performs the same tests as the [<Property>] declared tests; its output is:

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 

int list isListReversed:        Ok, passed 100 tests.
string list isListReversed:     Ok, passed 100 tests.
int list isShuffledOKInt:       Ok, passed 100 tests.
string list isShuffledOKString: Ok, passed 100 tests.
int list isRevOKInt:            Ok, passed 100 tests.
string list isRevOKString:      Ok, passed 100 tests.
DONE