How to test DSLs (and: FsChecking FsCheck)

There are two causes for this post.

First, I’ve been watching videos from Lang.NET and DSL DevCon, so I’m in language-mode. It occurred to me that (domain specific) languages seem difficult to test using traditional unit tests: after all, the usage possibilities are far greater for a language than for, say, a typical user interface (maybe this means that typical user interfaces suck - you decide). The word “combinator library”, which are internal DSLs avant la lettre, says it all: the usage possibilities are combinatorial. Classic, example based unit testing thus becomes combinatorially expensive as well.

Second, I’ve been saying in the last release announcement of FsCheck that I wanted to write some FsChecks for FsCheck itself. So far, this effort is about 60% complete. As a sort of challenge, I want to check as much as possible from FsCheck without any traditional example-based unit testing – in other words, I want to test FsCheck using only FsCheck (and maybe some Pex and Code Contracts later on).

FsCheck itself consists of basically two internal DSLs: one for constructing random value generators for whatever value it is your tests need, and one for constructing properties: basically assertions augmented with property combinators for adding labels, classifying generated values and such. It’s the latter DSL that I’m going to test, and draw some general conclusions that may apply to testing other DSLs or even general purpose languages as well.

To see what we’re dealing with, here’s an example of using the property DSL:

let prop_InsertCombined (x:int) xs = 
    ordered xs ==> (ordered (insert x xs))
        |> classify (ordered (x::xs)) "at-head"
        |> classify (ordered (xs @ [x])) "at-tail"
        |> collect (List.length xs)
quickCheck prop_InsertCombined

This property asserts that the insert function maintains the invariant that the list is ordered. The classify and collect property combinators are used to gather some information about the generated data. So in this test, there are three property combinators at work: implies (==>), classify and collect. Also, the arguments to the property (x and xs) are implicitly universally quantified using the forAll property combinator. These and more combinators in FsCheck can be combined an arbitrary ways, so testing this using example-based testing can be quite tedious. Can FsCheck do better?

The property DSL’s syntax tree

First, we’re going to need to generate an arbitrary property, i.e. an arbitrary combination of property combinators. To do that, I made a symbolic representation of the property language – a sort of abstract syntax tree of the language. It’s no secret that discriminated unions are great for this, and this case is not different:

type SymProp =  | Unit | Bool of bool | Exception
                | ForAll of int * SymProp
                | Implies of bool * SymProp
                | Classify of bool * string * SymProp
                | Collect of int * SymProp

So, a property can consist of, respectively:

• A function that returns the unit value;
• A function that returns a bool value;
• A function that throws an exception;
• A function that uses the implies combinator, which needs two arguments: a boolean condition and another property;
• A function that classifies the generated values, which needs three arguments: a boolean condition, the name to classify with if the condition is true and another property;
• A function that collects values, which takes two arguments: the value to collect, and another property.

Note that I’ve made some simplifications here: in fact forAll takes a generator that generates values of an arbitrary type – but since we’re not testing generators here, I’ve assumed the forAll always generates a constant int value. Also, collect would normally collect a (function of a) generated value, but it’s here constrained to collecting a constant int value.

We can build an actual property from this symbolic representation:

let rec private toProperty prop =
        match prop with
        | Unit -> property ()
        | Bool b -> property b
        | Exception -> property (lazy (raise <| InvalidOperationException()))
        | ForAll (i,prop) -> forAll (constant i) (fun i -> toProperty prop)
        | Implies (b,prop) -> b ==> (toProperty prop)
        | Classify (b,stamp,prop) -> classify b stamp (toProperty prop)
        | Collect (i,prop) -> collect i (toProperty prop)

The simplifications are plainly visible here.

Defining the semantics of properties

Now, let’s define a specification of what a symbolic property means, in terms of what it should produce as Result. Result is an internal datatype used by FsCheck to track the result of one execution of a property. This is the gist of it:

type Outcome = 
    | Timeout of int
    | Exception of exn
    | False
    | True
    | Rejected

type Result = 
    {   Outcome     : Outcome
        Stamp       : list<string>
        Labels      : Set<string>
        Arguments   : list<obj> }

So, a result tracks the outcome of a property: timed out, raised exception, returned false or true, or value rejected. The latter means a generated value did not pass the condition of an implies combinator. Furthermore, it also tracks the generated arguments, the stamps applied using classify and collect, as well as labels which are not tested here.

And here is a formal, executable specification of a subset of the FsCheck property DSL:

let rec private determineResult prop =
        let addStamp stamp res = { res with Stamp = stamp :: res.Stamp }
        let addArgument arg res = { res with Arguments = arg :: res.Arguments }
        match prop with
        | Unit -> succeeded
        | Bool true -> succeeded
        | Bool false -> failed
        | Exception  -> exc <| InvalidOperationException()
        | ForAll (i,prop) -> determineResult prop |> addArgument i
        | Implies (true,prop) -> determineResult prop
        | Implies (false,_) -> rejected
        | Classify (true,stamp,prop) -> determineResult prop |> addStamp stamp
        | Classify (false,_,prop) -> determineResult prop
        | Collect (i,prop) -> determineResult prop |> addStamp (any_to_string i)

You can check this definition with the FsCheck documentation. For example, it shows that an assertion that returns unit or true is interpreted as succeeded, false as failed and so on. The succeeded function and friends are defined in FsCheck and just construct basic Result instances:

let private result =
  { Outcome     = Rejected
  ; Stamp       = []
  ; Labels       = Set.empty
  ; Arguments   = []
  }

let internal failed = { result with Outcome = False }

The test

Armed with these functions, we can write our test:

let SymProperty (symprop:SymProp) = 
        let expected = determineResult symprop 
        let (MkRose (Common.Lazy actual,_)) = generate 1 (Random.newSeed()) (toProperty symprop) 
        areSame expected actual
        |> label (sprintf "expected = %A - actual = %A" expected actual)
        |> collect symprop

Ignore the specifics of the “actual” symbol definition – it executes an actual property and extracts the Result from it. The gist of the property is the comparison between the actual Result of the execution of the property (that was built from the symbolic property representation), and compare that with our expected semantics. Just to see what kind of properties we’re testing, I’ve also added a collect combinator, as well as a label to see what’s wrong if the test should fail. Thanks to FsCheck’s built-in discriminated union generator, running this gives:

Property.SymProperty-Ok, passed 100 tests.
22% Exception.
12% Unit.
6% Bool true.
6% Bool false.
4% Classify (false,"",Unit).
2% Implies (false,Exception).
2% Classify (true,"",Unit).
2% Classify (true,"",Exception).
2% Classify (false,"",Exception).
1% Implies (true,Exception).
1% Implies (true,Collect (2,Bool true)).
1% Implies (true,Collect (0,Unit)).
1% Implies (true,Collect (0,Collect (0,Bool false))).
(and so on)

Generating more interesting properties

This leaves something to be desired: the depth of combinations isn’t very high, and almost half of the generated properties are the trivial bool, unit or exception cases. One way of increasing this depth is by increasing the size of the generator, but that didn’t work very well: it mostly increased the length of the generated strings, without increasing the depth too much. The reason is that three of the seven options are “leaf” nodes, where generation ends. So I wrote my own generator for the SymProp type:

let rec private symPropGen =
        let rec recGen size =
            match size with
            | 0 -> oneof [constant Unit; liftGen (Bool) arbitrary; constant Exception]
            | n when n>0 ->
                let subProp = recGen (size/2)
                oneof   [ liftGen2 (curry ForAll) arbitrary (subProp)
                        ; liftGen2 (curry Implies) arbitrary (subProp)
                        ; liftGen2 (curry Collect) arbitrary (subProp)
                        ; liftGen3 (fun b s p -> Classify (b,s,p)) arbitrary arbitrary (subProp)]
            | _ -> failwith "symPropGen: size must be positive"
        sized recGen

If you’re somewhat familiar with FsCheck’s generator combinators, this shouldn’t be hard to read. The idea is that we only generate one of the leaf nodes if the size equals zero, and halve the size if we generate a “real” property combinator to ensure the generation ends at some point. Let’s change the property to incorporate this generator:

let Property = 
        forAllShrink symPropGen shrink (fun symprop ->
            let expected = determineResult symprop 
            let (MkRose (Common.Lazy actual,_)) = generate 1 (Random.newSeed()) (toProperty symprop) 
            areSame expected actual
            |> label (sprintf "expected = %A - actual = %A" expected actual)
            |> collect (depth symprop)

I added a depth function that calculates the depth of the generated symbolic property (i.e. depth of Unit, Bool and Exception is zero, and the rest adds one to the depth of it’s subproperty). Running this gives:

Property.get_Property-Ok, passed 100 tests.
26% 5.
26% 4.
18% 3.
12% 2.
7% 6.
6% 0.
4% 1.

which shows that FsCheck is now generating more properties with greater depth (4-5), and trivial properties only 6% of the time.

Conclusion

This post showed an approach for testing DSLs, combinator libraries or “language-oriented” programs, whatever you’d like to call it:

1. Write a symbolic representation of the abstract syntax tree of the language you want to test. This symbolic representation is used to abstract from details you don’t want to test, to define semantics of the language later on, and it to generate output for counter-examples that FsCheck may find.
2. Generate the actual representation in your compiler or interpreter from the symbolic representation.
3. Specify the semantics of the symbolic representation.
4. Rely on FsCheck’s built-in generators, or make your own generator to generate the symbolic representation.
5. Write an FsCheck property to compare the actual with the expected semantics.

This approach may even be usable for testing compilers of general purpose programming languages. The effort involved will be much larger, but it’s easy to start small.

Want more of this? Also check out the Checks.fs file in the FsCheck distribution for a complete test of the FsCheck property language.

Share this post :

Technet!

del.icio.us it!

del.iri.ous!

digg it!

dotnetkicks it!

reddit!

technorati!

FsChecking dnAnalytics – Part 3

Thanks to Marcus Cuda, coordinator of the dnAnalytics project, I can end my little series (part 1 – part 2) with a nice result: the dnAnalytics team  have decided to incorporate FsCheck in their testing. Cool! So next time, I’ll probably choose another project to “experiment” with (all in the interest of science), but this post I had lined up already.

Last time I described one kind of property based on invariants that hold over two or more related functions or methods. The example I gave was mathematically oriented (i.e. directly originating from the problem domain). Today I’ll show a property that should be familiar to many of you, and is applicable for quite a few of your types.

It happens that the Complex type in dnAnalytics can be constructed by parsing it from a string such as “1 + 3.0i”. On the other hand, calling ToString() on a Complex object produces a similar string. So, we specify that the ToString of a Complex value can be parsed, and produces the original value again:

let prop_ParseToString (c:Complex) =
    let actual = Complex.Parse(c.ToString(CultureInfo.InvariantCulture), CultureInfo.InvariantCulture)
    if Complex.IsInfinity(c) then Complex.IsInfinity(actual)
    elif Complex.IsNaN(c) then Complex.IsNaN(actual)
    else equalsUpTo 12 c actual

The only thing to watch out for is again the special values infinity and NaN. Also, since the ToString of a complex does not return a representation of Complex value up to its complete precision, we’re just checking equality up to a certain number of significant digits by using the equalsTo function.

In dnAnalytics version 0.3, running this property produces:

Parse ToString-Falsifiable, after 4 tests (0 shrinks):
0 + 1,79769313486232E+308i
with exception:
System.FormatException: One of the identified items was in a bad format

This bug was due to the fact that the string is split on the basis of the ‘+’ character – which is also used when a floating point number is printed in scientific notation – clearly visible in the counter example given by FsCheck. This is a confirmed bug that is solved by now. Apparently the same property also detected a bug when parsing NaN and Infinity values.

This again shows that writing properties, or specifications, for your code in FsCheck is easy, short, and most importantly, finds bugs!

The kind of property that is described here you can write for any pair of functions or methods that convert a representation A to a representation B and back (in this case, a Complex value to a string and back). It can be generalized as follows:

let toAndFro x transformTo transformFrom equals =
    x |> transformTo |> transformFrom |> equals x

Applied to the example:

let prop_ParseToString (c:Complex) =
    toAndFro c 
        (fun c -> c.ToString(CultureInfo.InvariantCulture)) 
        (fun s -> Complex.Parse(s, CultureInfo.InvariantCulture)) 
        (fun c actual -> 
            if Complex.IsInfinity(c) then Complex.IsInfinity(actual)
            elif Complex.IsNaN(c) then Complex.IsNaN(actual)
            else equalsUpTo 12 c actual)

This kind of property is fairly common: think about Parse/ToString, serializing/deserializing, and all kinds of conversion and formatting functions.

(I was at TechDays 2009 in Antwerp this week, and watched a presentation about Pex by Peli de Halleux. He showed a similar pattern when using Pex to write parameterized unit tests. In fact, a lot of the patterns and scenarios he described sounded very recognizable to my ears. If you like FsCheck, definitely check out Pex as well.)

Conclusion

One project converted, a gazillion to go. If you maintain an open source project and are unsure or even better, skeptical! how FsCheck can be used for testing in your project, contact me and you’ll probably get me crazy enough to write some tests for you. I choose a scientific domain because F# is targeted towards that, but the applicability goes far beyond that, as I hope to have showed in this post. On the other hand, I am also curious for what kind of projects or domains you are already using FsCheck. Did you encounter testing patterns like “toAndFro” that you’d like to share? Got any wishes? Don’t hesitate to let me know. Or even better, spread the word and blog about FsCheck yourself.

Happy FsChecking!

Technorati: fscheck,dnanalytics,random testing,F#

del.icio.us Tags: fscheck,dnanalytics,random testing,F#

Share this post :

FsChecking dnAnalytics Part 2

In part 1, I started out with defining some FsCheck properties on dnAnalytics' Complex class. The properties I showed were fairly straightforward: break the complex number in its real and imaginary part, apply the definition of the operation and compare that to the result of the actual operation under test.

A possible critique on this kind of property is that it partly duplicates the implementation of the operation under test. In my experience, it almost never does completely: there is of course some overlap, but the property is invariably simpler, takes into account less detail, and is easier to understand. The property is mostly unusable for an actual implementation, for example because it is inefficient, is not tail recursive, causes more rounding errors etc.  The only important thing about such a property is that is simple, so that you are sure it is correct (in fact, FsCheck will verify that it is correct...). So this critique is not justified.

But anyway, such definition properties are not the only kind that can be written using FsCheck. Today we'll look at properties that relate different operations (functions, methods) of the same class or module together.

As an example, we'll test that the complex numbers form a field over addition and multiplication, i.e. the field C+,*.

Now, the first thing to realize here is that instances of type Complex do not form an actual field, due to the presence of NaN, Infinity, rounding errors and overflow. So, for the purpose of this property we're about to write, we need to be able to generate Complex instances where these values are not generated.

There is a nice trick to define a custom generator that filters or otherwise manipulates values from another generator but keeps the other generator's type. First define a wrapper union type and define a generator for that:

type NoSpecials = NoSpecials of Complex

type Generators =
    static member NoSpecials() =
        { new Arbitrary<NoSpecials>() with
            override x.Arbitrary = 
                arbitrary 
                |> suchThat (fun (C (r,i) as a) -> 
                    not (Complex.IsInfinity(a)) && 
                    not (Complex.IsNaN(a))      && 
                    r > 1e-16  && r < 1e16      &&
                    i > 1e-16  && i < 1e16  )  
                |> fmapGen NoSpecials
            override x.Shrink (NoSpecials c) = shrink c |> Seq.map NoSpecials
        }

Notice how special values like NaN, and very low and high values are filtered out in the generator using the suchThat generator combinator.

Now, we can write a property with a signature like:

let prop_ComplexField (NoSpecials a,NoSpecials b,NoSpecials c) =

which will generate "non-special" complex values in a, b and c. F#'s pattern matching and FsCheck's type directed value generation come together nicely here. (The alternative for this style is to use an explicit generator using forAll or forAllShrink).

Our property should check that both addition and multiplication are commutative, associative, distributive and have an an identity. So, the following functions will be useful:

let (=~=) (expected:Complex) actual = 
    try TestHelper.TestRelativeError(expected, actual, 2e-10); true with _ -> false

let commutative f (a,b) = f a b =~= f b a 
let associative f (a,b,c) = f (f a b) c =~=  f a (f b c) //e.g. (a+b)+c = a+(b+c)
let rightdistributive f g (a,b,c) =  g (f a b) c =~= f (g a c) (g b c) //e.g. (a+b)c = ac+bc
let leftdistributive f g (a,b,c) = g c (f a b) =~= f (g c a) (g c b) // e.g. c(a+b) = ca+cb
let identity f id a = f a id = a

Armed with these, our property can be written as:

let prop_ComplexField (NoSpecials a,NoSpecials b,NoSpecials c) =
    commutative (+) (a,b)               |@ "+ commutative"      .&.
    commutative (*) (a,b)               |@ "* commutative"      .&.
    associative (+) (a,b,c)             |@ "+ associative"      .&.
    associative (*) (a,b,c)             |@ "* associative"      .&.
    rightdistributive (+) (*) (a,b,c)   |@ "right distributive" .&.
    leftdistributive (+) (*) (a,b,c)    |@ "left distributive"  .&.
    identity (+) Complex.Zero a         |@ "0 is identity of +" .&.
    identity (*) Complex.One a          |@ "1 is identity of *" 
quickCheckN "Complex numbers are a field"  prop_ComplexField  

Which produces:

Complex numbers are a field-Ok, passed 100 tests.

It should be clear that the possibilities for coming up with such properties are almost limitless, and that you'll never have to repeat any part of your implementation to express them.

Conclusion

FsCheck makes it easy to test whether relations between a set of related methods or functions hold. This technique is in my experience sometimes neglected when unit testing, because of the focus on the unit. Nevertheless, such properties can have great value in documentation and testing.

In this post I took a few shortcuts to avoid having to deal with the "specials", and so in that sense this specification could be called misleading because indeed, instances of Complex do not form a field. I did this for two reasons. First, I wanted to show the wrapper type/pattern match technique to define derived generators that generate a subset of the values of an original generator. Second, I wanted to show that FsCheck makes you work  if you want to ignore these special values - in other words, you have to make a very conscious decision to ignore them. In contrast, using unit tests the default is that you forget about these values until it's too late.

A third point I wanted to show is that with a little refactoring and common sense, you can write elegant and very readable properties that could conceivably be part of your documentation - in other words, true executable specifications.

Download fs file

Technorati: F#,fscheck case study,fscheck,dnAnalytics

FsChecking dnAnalytics

I've been thinking lately what I can do to make FsCheck more widely used. Whenever I write "regular" unit tests, I feel like I'm back in the stone ages. It just feels so clumsy and tedious. Why don't more people see this? Is it because there's a learning curve? Surely that's part of it, but the benefit is so huge that this can't be the whole story. I came across this question on stackoverflow, and read a lot of misunderstandings about random testing (luckily the chosen answer was well-informed, and even mentions FsCheck). I could respond to each of those, but I'll keep that to a later post; instead, I'm resolved to convert the world to FsCheck, even if I have to do it one project at a time ;)

Today's candidate: dnAnalytics. dnAnalytics makes a good candidate for FsChecking because  it is in the mathematical field - finding properties for the functionality to satisfy should be straightforward: there's millennia of mathematical knowledge to choose from. Secondly, dnAnalytics already has some tests that I can trash later. Also, dnAnalytics  has an F# interface which I won't be using in this post, but at least the maintainers are familiar with F#, so I have some hope of "converting" them. Finally, dnAnalytics has quite a few downloads (over a 1000), so hopefully this can raise visibility of FsCheck outside the F# community.

Without further ado, let's go find bugs!  (I'll give it away now to keep you interested, as this has become a long post: I found a bug...read on.)

For my first experiment, I choose to test the Complex class, which represents a complex number a+bi, along with some operations. Fairly straightforward stuff that even a mathematically challenged person like myself can follow.

For education and amusement, I'll give an overview of how the tests I wrote revolved over time - errors and imperfections included.

The complex number generator

To test a type, typically the first step to take when using FsCheck is writing a generator for a type. In this case, we'll just be using a generator for a tuple of two floats, and map that to a complex number:

type Generators =
    static member Complex() =
        { new Arbitrary<Complex>() with
            override x.Arbitrary = two arbitrary |> fmapGen ( fun (a,b) -> new Complex(a,b))
            override x.Shrink (C (r,i)) = 
                shrink (r,i)  
                |> Seq.map (fun (r,i) -> new Complex(r,i))
        }
registerGenerators<Generators>()

Pretty easy. The shrink function also exploits the relation between a complex number and a pair of floats. In case you're wondering, I added an active pattern C to deal with the Complex class, it's just:

let (|C|) (c:Complex) = (c.Real, c.Imaginary)

The Absolute of a complex number

I started out with testing the Complex type's Absolute method. It's supposed to return the Absolute value of the Complex instance it's applied to. Here's the property I wrote:

let prop_Absolute (C (r,i) as c) = 
    let lhs = c.Absolute
    let rhs = Math.Sqrt( r*r + i*i)
    sprintf "lhs=%O, rhs=%O" lhs rhs @| (lhs = rhs)

Basically this just checks that the outcome of the Absolute method is equal to the mathematical definition of the absolute value of a complex number. The sprintf and the label operator @| are there to display the intermediate values should the property fail. And failing it does:

Absolute-Falsifiable, after 6 tests (1 shrink):
Label of failing property: lhs=NaN (Niet-een-getal), rhs=NaN (Niet-een-getal)
NaN

Classic mistake: NaN is a special case; NaN is never equal to NaN. That's easily solved:

let prop_Absolute (C (r,i) as c) = 
    let lhs = c.Absolute
    let rhs = Math.Sqrt( r*r + i*i)
    sprintf "lhs=%O, rhs=%O" lhs rhs @|
    (if Complex.IsNaN(c) then Double.IsNaN(lhs) else lhs = rhs)

produces

Absolute-Falsifiable, after 10 tests (2 shrinks):
Label of failing property: lhs=7,00446286306095, rhs=7,00446286306095
7 + 0,25i

Hmm. Instead of looking up how I could see all  of a float's significant digits, I just assumed a rounding error. I explored dnAnalytics existing tests and found just the thing to deal with that: a method to test equality taking into account a relative error. Using that method in the property results in:

let prop_Absolute (C (r,i) as c) = 
    let lhs = c.Absolute
    let rhs = Math.Sqrt( r*r + i*i)
    sprintf "lhs=%O, rhs=%O" lhs rhs @|
    (   if Complex.IsNaN(c) then Double.IsNaN(lhs) 
        else TestHelper.TestRelativeError(lhs, rhs, 2e-16);true)

And yes:

Absolute-Ok, passed 100 tests.

Notice that FsCheck works nicely with NUnit here; suppose we introduce a "bug" by adding 1 to the right hand side:

let prop_Absolute (C (r,i) as c) = 
    let lhs = c.Absolute
    let rhs = Math.Sqrt( r*r + i*i)
    sprintf "lhs=%O, rhs=%O" lhs rhs @|
    (   if Complex.IsNaN(c) then Double.IsNaN(lhs) 
        else TestHelper.TestRelativeError(lhs, rhs+1.0, 2e-16);true)

produces:

Absolute-Falsifiable, after 1 test (0 shrinks):
0 + 0i
with exception:
NUnit.Framework.AssertionException:   Expected: less than 2E-16.0d
  But was:  1.0d

   at NUnit.Framework.Assert.That(Object actual, Constraint constraint, String message, Object[] args)
   at NUnit.Framework.Assert.Less(Double arg1, Double arg2, String message, Object[] args)
   at NUnit.Framework.Assert.Less(Double arg1, Double arg2)
   at dnAnalytics.Tests.TestHelper.TestRelativeError(Double expected, Double approx, Double acceptableError) in c:\Documents and Settings\Kurt\My Documents\dnAnalytics\0.3\src\dnAnalytics.Tests\TestHelper.cs:line 53
   at Complex.prop_Absolute(Complex _arg1) in C:\Documents and Settings\Kurt\MyDocuments\dnAnalytics\0.3\src\dnAnalytics.FsCheck\Complex.fs:line 32
   at FsCheck.Property.evaluate[T,U](FastFunc`2 body, T a) in C:\Documents and Settings\Kurt\My Documents\FsCheck\FsCheck\Property.fs:line 162

But wait! Why aren't our labels displayed? We've found a bug...in FsCheck :) Hold on, I didn't con you earlier, I really did find a bug in dnAnalytics as well.

People can get a bit nervous now because they're not actually seeing what values FsCheck is generating. Let's find out:

let prop_Absolute (C (r,i) as c) = 
    let lhs = c.Absolute
    let rhs = Math.Sqrt( r*r + i*i)
    sprintf "lhs=%O, rhs=%O" lhs rhs @|
    if Complex.IsNaN(c) then Double.IsNaN(lhs) 
    else TestHelper.TestRelativeError(lhs, rhs, 2e-16);true
    |> classify (Complex.IsNaN(c)) "NaN"
    |> classify (Complex.IsInfinity(c)) "Infinity"
    |> classify (c = Complex.Zero) "Zero"
    |> classify (c = Complex.One) "One"

Absolute-Ok, passed 100 tests.
17% Infinity.
8% NaN.
2% Zero.

As you can see, using the classify combinator you can make FsCheck print out the ratio of test cases that fulfill a certain criterion. Here we learn that One is never generated; and infinity quite a bit. This is due to the fact that the built in generator for floats generates these special values with preference. We can change this behavior by changing the generator. Suppose we'd like to generate the value One also:

override x.Arbitrary = 
  frequency   [ (98,two arbitrary |> fmapGen ( fun (a,b) -> new Complex(a,b)))
              ; (2, constant Complex.One) ]

Absolute-Ok, passed 100 tests.
10% Infinity.
9% NaN.
4% Zero.
2% One.
1% Infinity, NaN.

Easy enough. Our generator now indeed generates One as well.

But hold on: we see also that a Complex number can be both Infinity and NaN. That doens't make sense. Let's write a property to check this:

let prop_NaNInfinity (c:Complex) =
    not ( Complex.IsInfinity(c) &&  Complex.IsNaN(c))
checkName  "Both NaN and Infinity" { quick with MaxTest = 1000} prop_NaNInfinity 

Note that I didn't use the usual quickCheckN function to run the tests, because the Absolute test indicated that only one test in a hundred exhibited the behavior. So I made FsCheck run this test a bit more, 1000 times to be exact. Running this sure enough produces:

Both NaN and Infinity-Falsifiable, after 418 tests (0 shrinks):
NaN

and this find was confirmed as a bug by the dnAnalytics team. A small victory for FsCheck.

The conjugate of a complex number

Let's do one more: finding the conjugate.

let prop_Conjugate (C (r,i) as c) =
    let lhs = c.Conjugate
    let rhs = new Complex(r,-i)
    sprintf "lhs=%O, rhs=%O" lhs rhs @|
    if Complex.IsNaN(c) then Complex.IsNaN(lhs) 
    else lhs = rhs

Since the Absolute property, I've become a bit wiser and factored in the possibility of NaN from the start. Running this gives:

Conjugate-Ok, passed 100 tests.

And all is well. Except one thing: our tests like a bit ugly, because we had to duplicate some code.

Red, green, refactor!

We're going to refactor two things.

First, all the classify's we've added to the Absolute property are actually common to every property where we use our Complex generator. These kinds of "tests" are not uncommon when writing a new FsCheck generator - for example, it ensures that our generator does not throw an exception when generating values (which can happen when certain objects are constructed). I've taken the habit of separating these kinds of tests into a single separate property:

let prop_ComplexGen c = 
    ()
    |> classify (Complex.IsNaN(c)) "NaN"
    |> classify (Complex.IsInfinity(c)) "Infinity"
    |> classify (c = Complex.Zero) "Zero"
    |> classify (c = Complex.One) "One"

And we leave these classify's out of the other properties. (Note that a property that returns unit or true is interpreted as succeeded by FsCheck. An exception or false indicates failure.)

Then, we add the following helper method to abstract out the labeling of left and right hand side; cleaning it up in the process:

let compare expected actual prop = 
      sprintf "expected=%O, actual=%O" expected actual @| (prop expected actual)

Now our two properties can be written:

let prop_Absolute (C (r,i) as c) = 
    compare (Math.Sqrt(r*r + i*i)) c.Absolute (fun expected actual ->
        if Complex.IsNaN(c) then Double.IsNaN(actual) 
        else TestHelper.TestRelativeError(expected, actual, 2e-16);true)

let prop_Conjugate (C (r,i) as c) =
    compare (Complex(r,-i)) c.Conjugate (fun expected actual ->
        if Complex.IsNaN(c) then Complex.IsNaN(actual) 
        else expected = actual)

A successful experiment

In my eyes, the FsCheck based tests are hugely superior to the original tests, for the following reasons.

First, we've replaced 2 x 100 hand-written tests with presumably manually calculated values in dnAnalytics with just a few lines of code.  An excerpt from the original tests:

[Test]
public void Absolute()
{
  TestHelper.TestRelativeError(ComplexMath.Absolute(new Complex(0.0, 1.19209289550780998537e-7)), 1.19209289550780998537e-7, 2e-016);
  TestHelper.TestRelativeError(ComplexMath.Absolute(new Complex(0.0, -1.19209289550780998537e-7)), 1.19209289550780998537e-7, 2e-016);
  TestHelper.TestRelativeError(ComplexMath.Absolute(new Complex(0.0, 5.0e-1)), 5.0e-1, 2e-016);
  TestHelper.TestRelativeError(ComplexMath.Absolute(new Complex(0.0, -5.0e-1)), 5.0e-1, 2e-016);

(Note that these are actually tests for a static method on ComplexMath, but Complex.Absolute calls this method directly without further ado. In any case we could easily rewrite our properties to call this method directly as well.)

These must've been a pain to write. Probably someone generated a little script to apply the definition of Absolute in each of these cases. That should be the work of a computer! Using FsCheck, it is.

Second, the original tests do not reveal the intent of the Absolute or Conjugate methods. Basically you just see a bunch of values going in, and the expected values coming out. In a normal program, you would call these "magic numbers" and call the developer that wrote them names. In unit tests, this is commonly tolerated.

FsCheck's specification on the other hand reveals the intent of the tested methods directly - in fact, I just looked up the mathematical definition of these operators to come up with the properties, and this definition is still readily apparent.

Third, FsCheck forced us to make the specification complete, and factor in NaN values. I could not find any test using NaN in the original dnAnalytics tests. This led directly to the discovery of a previously unknown bug.

In conclusion; FsCheck's tests are shorter, clearer and more complete than the original tests.

To boot, I dare say they are faster to write: I downloaded dnAnalytics, explored the code, choose a type to test, wrote the above properties, reported the bug, and typed in the bulk of this blog post in the course of about 4 hours yesterday. I spent another hour or two today cleaning up the post itself.

Technorati: FsCheck,dnAnalytics,FsCheck case study