Generating immutable instances in C# with FsCheck

If you do any functional programming in C# you’ll probably have lots of classes that look like this:

class Person {
    private readonly string name;
    private readonly DateTime dateOfBirth;

    public Person(string name, DateTime dateOfBirth) {
        this.name = name;
        this.dateOfBirth = dateOfBirth;
    }

    public string Name {
        get { return name; }
    }

    public DateTime DateOfBirth {
        get { return dateOfBirth; }
    }

    // equality members...
}

I.e. immutable classes, similar to F# records.
Now let’s say we want to test some property involving this Person class. For example, let’s say we have a serializer:

interface IPersonSerializer {
    string Serialize(Person p);
    Person Deserialize(string source);
}

Never mind the unsafety of this serializer, we want to test that roundtrip serialization works as expected. So we grab FsCheck and write:

Spec.ForAny((Person p) => serializer.Deserialize(serializer.Serialize(p)).Equals(p))
    .QuickCheckThrowOnFailure();

Only to be greeted with:

System.Exception: Geneflect: type not handled Person

Ok, so we write the generator explicitly:

var personGen =
    from name in Any.OfType<string>()
    from dob in Any.OfType<DateTime>()
    select new Person(name, dob);

Spec.For(personGen, p => serializer.Deserialize(serializer.Serialize(p)).Equals(p))
    .QuickCheckThrowOnFailure();

And all is fine.

But the generator code is trivially derivable from the class definition. And when you have lots of immutable classes, this boilerplate becomes really annoying. Couldn’t we automatize that somehow?

As it turns out, FsCheck already does this for F# records, using reflection. With a bit of code we can extend the reflection-based generator (built into FsCheck) to make it generate instances of immutable classes. With this change, we can go back to writing Spec.ForAny and FsCheck will automatically derive the generator for our Person class!

The restrictions on the classes to make them generable by FsCheck are:

• Must be a concrete class. No interfaces or abstract classes; FsCheck can’t guess a concrete implementation.
• It has to have only one public constructor. Otherwise, which one would FsCheck choose?
• All public fields and properties must be readonly. Otherwise, it creates the ambiguity of which ones to set and which ones not.
• Must not be recursively defined. FsCheck doesn’t generate recursively defined F# records by reflection either. I assume this is to keep the implementation simple.
• Must not have type parameters. This restriction could probably be relaxed, but since I haven’t needed it so far, I decided to play it safe. Left as an exercise for the reader :-)

This is available in FsCheck as of version 0.9.2.

Happy FsChecking in C# and VB.NET !

Optimizing with the help of FsCheck

Recently I needed a function to transpose a jagged array in F#. As I knew Haskell probably had this in its standard library and I'm lazy, I hoogled “transpose” and followed the link to its source code, then translated it to F#:

module List =
    let tryHead = 
        function
        | [] -> None
        | x::_ -> Some x

    let tryTail =
        function
        | _::xs -> Some xs
        | _ -> None

    let rec transpose =
        function
        | [] -> []
        | []::xs -> transpose xs
        | (x::xs)::xss -> (x::(List.choose tryHead xss))::transpose (xs::(List.choose tryTail xss))

The end.

Oh wait, I needed to process arrays, not lists. Well, I suppose we could convert the jagged array to a jagged list, and then back to an array:

let transpose x = x |> Seq.map Array.toList |> Seq.toList |> List.transpose |> Seq.map List.toArray |> Seq.toArray

It works, but it's a bit inefficient. For example, it does a lot of unnecessary allocations. Let's time it with a big array:

let bigArray = Array.init 3000 (fun i -> Array.init i id)
transpose bigArray |> ignore

Real: 00:00:01.369, CPU: 00:00:01.357, GC gen0: 79, gen1: 44, gen2: 1

We can do better. Since we're working with arrays, we could calculate the length of each array and preallocate it, then copy the correponding values. Problem is, that kind of code is very imperative, and tricky to get right.
Enter FsCheck. With FsCheck we can use the inefficient implementation as a model to ensure that the new, more efficient implementation is correct. It's very easy too:

let transpose2 (a: 'a[][]) = a // placeholder for the efficient implementation
FsCheck.Check.Quick ("transpose compare", fun (a: int[][]) -> transpose a = transpose2 a) 

Run this and FsCheck will generate jagged arrays to compare both implementations. As the new implementation is merely a placeholder for now, it won't take long to find a value that fails the comparison:

transpose compare-Falsifiable, after 1 test (0 shrinks) (StdGen (1547388233,295729162)):
[|[||]|]

Now that we have a simple but strong test harness we can confidently implement the optimized function. And many failed test runs later, this passes the 100 (by default) test cases generated by FsCheck:

let transpose2 (a: 'a[][]) =
    if a.Length = 0 then 
        [||]
    else
        let r = Array.zeroCreate (a |> Seq.map Array.length |> Seq.max)
        for i in 0 .. r.Length-1 do
            let c = Array.zeroCreate (a |> Seq.filter (fun x -> Array.length x > i) |> Seq.length)
            let mutable k = 0
            for j in 0 .. a.Length-1 do
                if a.[j].Length > i then
                    let v = a.[j].[i]
                    c.[k] <- v
                    k <- k + 1
            r.[i] <- c
        r

See, I told you it would be all imperative and messy! But is it more efficient?

transpose2 bigArray |> ignore

Real: 00:00:00.218, CPU: 00:00:00.218, GC gen0: 3, gen1: 2, gen2: 0

Yes it is (at least with this very unscientific benchmark).

BONUS: are you wondering why the original definition uses List.choose tryHead instead of List.map List.head ? That is:

let rec transpose =
    function
    | [] -> []
    | []::xs -> transpose xs
    | (x::xs)::xss -> (x::(List.map List.head xss))::transpose (xs::(List.map List.tail xss))

FsCheck can help with that too! Simply run this against the generated inputs and ignore the result (a trivial test):

FsCheck.Check.Quick("transpose", List.transpose >> ignore)

And watch it fail:

transpose-Falsifiable, after 1 test (6 shrinks) (StdGen (1278231111,295729178)):
[[true]; []]
with exception:
System.ArgumentException: The input list was empty.
Parameter name: list
   at Microsoft.FSharp.Collections.ListModule.Head[T](FSharpList`1 list)
   at Microsoft.FSharp.Primitives.Basics.List.map[T,TResult](FSharpFunc`2 mapping, FSharpList`1 x)

Note how FsCheck shrinks the value to the simplest possible failing case. This usage is great to find unwanted partial functions.

One last comment: none of this is specific for F#. FsCheck has a nice C# interface! You could also use it from Fuchu.

Fuchu: a functional test library for .NET

In my last two posts I showed how MbUnit supports first-class tests, and how you could use that to build a DSL in F# around it.

I explained how many concepts in typical xUnit frameworks can be more simply expressed when tests are first-class values, which is not the case for most .NET and Java test frameworks.

More concretely, test setup/teardown is a function over a test, and parameterized tests are... just data manipulation.

Since first-class tests greatly simplify things, why not dispense with the typical class-based, attribute-driven approach and build a test library around first-class tests? Well, Haskellers have been doing this for at least 10 years now, with HUnit.

HUnit organizes tests using this tree:

-- | The basic structure used to create an annotated tree of test cases. 
data Test 
    -- | A single, independent test case composed. 
    = TestCase Assertion 
    -- | A set of @Test@s sharing the same level in the hierarchy. 
    | TestList [Test] 
    -- | A name or description for a subtree of the @Test@s. 
    | TestLabel String Test 

Where Assertion is simply an alias for IO (). This is all you need to organize tests in suites and give them names.

We can trivially translate this to F# :

type TestCode = unit -> unit

type Test = 
    | TestCase of TestCode
    | TestList of Test seq
    | TestLabel of string * Test

Let's see an example:

let testA = 
    TestLabel ("testsuite A", TestList 
                         [
                            TestLabel ("test A", TestCase(fun _ -> Assert.AreEqual(4, 2+2)))
                            TestLabel ("test B", TestCase(fun _ -> Assert.AreEqual(8, 4+4)))
                         ])

It's quite verbose, but we can define the same DSL as I defined earlier for MbUnit tests, so this becomes:

let testA = 
    "testsuite A " =>> [
        "test A" => 
            fun _ -> Assert.AreEqual(4, 2+2)
        "test B" =>
            fun _ -> Assert.AreEqual(8, 4+4)
    ]

Actually, I first ported HUnit (including this DSL), then discovered that MbUnit has first-class tests and later wrote the DSL around MbUnit. Everything I described in those posts (setup/teardown as higher-order functions, parameterized tests as simple data manipulation, arbitrary nesting of test suites) applies here in the exact same way.

In fact, MbUnit's class hierarchy of Test/TestSuite/TestCase can be read as the following algebraic data type:

type Test =
| TestSuite of string * Test list
| TestCase of string * Action

which turns out to be very similar to the tree we translated from HUnit, only the names are embedded instead of being a separate case.

I called this HUnit port Fuchu (it doesn't mean anything), it's on github.

Assertions

Fuchu doesn't include any assertion functions, or at least not yet. (EDIT: assertions were added in 0.2.0) It only gives you tools to organize and run tests, but you're free to use NUnit, MbUnit, xUnit, NHamcrest, etc, or more F#-ish solutions like Unquote or FsUnit or NaturalSpec for assertions.

Tighter integration with FsCheck is planned. (EDIT: it was added in the first release of Fuchu)

Runner/Tooling

As with HUnit, the test assembly is the runner itself. That is, as opposed to having an external test runner as with most test frameworks, your test assembly is an executable (a console application). This is because it's more of a library instead of a framework. As a consequence, there is no need of installing any external tool to run tests (just hit CTRL-F5 in Visual Studio) or debug tests (just set your breakpoints and hit F5 in Visual Studio). Here's a clear signal of why this matters:

How does one run a #fsharp unit test project in #vs11?

— Community for F# (@c4fsharp) March 23, 2012

So how do you run tests with Fuchu? Given a test suite testA like the one defined above, you can run it like this:

[<EntryPoint>]
let main _ = run testA // or runParallel

But this is quite inconvenient, as it's common to split tests among different modules/files and this would mean having to list all tests somewhere, to feed them to the run function. HUnit works around this using Template Haskell, and OUnit (OCaml's port of HUnit) users generate the boilerplate code by parsing the tests' source code.

In .NET we can just decorate the tests with an attribute and then use reflection to fetch them:

[<Tests>]
let testA = 
    "2+2=4" => 
        fun _ -> Assert.AreEqual(4, 2+2)

[<Tests>]
let testB = 
    "2*3=6" => 
        fun _ -> Assert.AreEqual(7, 2*3)

[<EntryPoint>]
let main args = defaultMainThisAssembly args

This function defaultMainThisAssembly does exactly what it says on the tin. Notice that it also takes the command-line args, so if you call it with "/m" it will run the tests in parallel. (Curiously, you can't say let main = defaultMainThisAssembly, it won't be recognized as the entry point).

By the way, this is just an example, you wouldn't normally annotate every single test with the Tests attribute, only the top-level test group per module.

Run this code and you get an output like this:

2*3=6: Failed: 
  Expected: 7
  But was:  6

  G:\prg\Test.fs(15,1): SomeModule.testB@15.Invoke(Unit _arg1)
 (00:00:00.0017681)

2 tests run: 1 passed, 0 ignored, 1 failed, 0 errored (00:00:00.0058780)

If you run this within Visual Studio with F5 you can navigate to the failing assertion by clicking on the line that looks like a mini stack trace.

REPL it!

Since running tests is as easy as saying "run test", it's also convenient sometimes to do so from the F# REPL.

Pros:

• You can directly load the source code under tests in the REPL, which cuts down compilation times.
• Easy to cherry-pick one or a few tests to run instead of running all tests (with the provided Test.filter function)

Cons:

• Having to manually load all dependencies to the tests. It may be possible to work around this using a variant of this script by Gustavo Guerra.
• If you reference the assembly under test in the REPL, fsi.exe blocks the DLLs, so you have to reset the REPL session to recompile. But if you're testing F# code, you can work around this by loading source code instead of referencing the assembly.

You can see an example of running tests from the REPL here.

Other tools

Integrating with other tools is not simple. Most tools out there seem to assume that tests are organized in classes, and each test corresponds to a method or function. This also happens with MbUnit's StaticTestFactory: for example in ReSharper or TestDriven.Net you can't single out tests. Still, they can be made to run let-bound tests (which may be a test suite), so it should be possible to have some support within this limitation.

Also, no immediate support for any continuous test runner. I checked with Greg Young, he tells me that MightyMoose/AutoTest.NET can be configured to use an arbitrary executable (with limitations). Remco Mulder, of NCrunch, suggested wrapping the test runner in a test from a known test framework as a workaround. Maybe executing the tests after compilation (with a simple AfterBuild msbuild target) is enough. I haven't looked into this yet.

Coverage tools should have no problem, it makes no difference where the executable comes from.

Build tools should have no issues either; obviously FAKE is the more direct option, but I see no problems integrating this with other build tools.

C# support

I threw in a few wrapper functions to make this library usable in C# / VB.NET. Of course, it will never be as concise as F#, but still usable. I'm not going to fully explain this (it's just boring sugar) but you can see an example here.

NUnit/MbUnit test loading

Even though it may seem very different, Fuchu is still built on xUnit concepts. And since tests are first-class values, it's very easy to map tests written with other xUnit framework to Fuchu tests. For example, building Fuchu tests from NUnit test classes takes less than 100 LoC (it's already built into Fuchu)

This lets you use Fuchu as a runner for existing tests, and to write new tests. I'm planning to use this soon in SolrNet to replace Gallio (for example, Gallio doesn't work on Mono).

There is a limitation here: Fuchu can't express TestFixtureTearDowns. It can do TestFixtureSetups (and obviously SetUp/TearDown, as explained in previous posts), but not TestFixtureTearDowns (or at least not unless you treat that test suite separately). Give it a try and see for yourself :) . Is it a real downside? I don't think so (for example, TestFixtureTearDowns make parallelization harder), but it's something to be aware of. Also I haven't looked into test inheritance yet, but it should be pretty easy to support it.

Conclusions

Does .NET really need yet another test framework? Absolutely not. The current test frameworks are "good enough" and hugely popular. But since they don't treat tests as first-class values, extending them results in more and more complexity. Consider the lifecycle of a test in a typical unit testing framework. Inheritance and multiple marker attributes make it so complex that it reminds me of the ASP.NET page lifecycle. 

What I propose with Fuchu is a hopefully simpler, no-magic model. Remember KISS?

Code is here. Binaries on NuGet.

Zipping with applicative functors in F#

In my last post I briefly described functors from a F# perspective. Now it's the turn of applicative functors. Since there were few to none concrete examples in my previous post, this time I'll start with an example. Hopefully everyone remembers Seq.zip. Remember also Seq.zip3 ? Just to recap, they combine sequences into sequences of pairs and triples respectively. The signatures are:

Seq.zip : seq<'a> -> seq<'b> -> seq<'a * 'b>
Seq.zip3 : seq<'a> -> seq<'b> -> seq<'c> -> seq<'a * 'b * 'c>

Now let's say we want zip5:

Seq.zip5 : seq<'a> -> seq<'b> -> seq<'c> -> seq<'d> -> seq<'e> -> seq<'a * 'b * 'c * 'd * 'e>

We could implement it with a nested zip3 and a flattening map:

let zip5 a b c d e = 
    Seq.zip3 a b (Seq.zip3 c d e) |> Seq.map (fun (n,m,(o,p,q)) -> n,m,o,p,q)

Or we could write it using an applicative functor, like this:

let zip5 a b c d e =
    puree (fun n m o p q -> n,m,o,p,q) <*> a <*> b <*> c <*> d <*> e

I think you'll agree that the latter looks much cleaner, so let's see how we get there.

Applicative functors are defined by two operations: pure and <*> (actually but we can't write that in ASCII!). Again we can't express these generically in .NET's type system due to the lack of type constructor abstraction, but this is how their signatures would look like:

pure : 'a -> 't<'a> 
(<*>) : 't<'a -> 'b> -> 't<'a> -> 't<'b>

I prefer the bracket-less ML way of expressing types, whenever possible:

pure : 'a -> 'a 't 
(<*>) : ('a -> 'b) 't -> 'a 't -> 'b 't

Intuitively, pure lifts a value (usually a function) inside the domain of the applicative functor, and <*> applies the function inside the applicative to an applicative value, yielding another applicative value.

At this point, it might not be immediately clear that <*> is an application, but compare its signature with the regular function application operator (<|) and you'll see the similarity:

(<|) : ('a -> 'b) -> 'a -> 'b

Since pure is a reserved keyword in F# (it doesn't do anything yet, though) we'll use puree in our code instead.

The applicative functor that enables the zip5 implementation above is known as ZipList:

module ZipList = 
    let puree v = Seq.initInfinite (fun _ -> v)
    let (<*>) f a = Seq.zip f a |> Seq.map (fun (k,v) -> k v)

The signatures for ZipList:

puree : 'a -> 'a seq 
(<*>) : ('a -> 'b) seq -> 'a seq -> 'b seq

In plain English, <*> in a ZipList applies a sequence of functions to a sequence of values, pairwise; while puree creates an infinite sequence of values (usually functions) ready to be applied to another sequence of values using <*>.

Functors and applicatives

Since we're always using this ZipList in the form "puree function <*> value" we might as well wrap that in an operator:

let (<!>) f a = puree f <*> a

Sow now we can write zip5 a bit shorter:

let zip5 a b c d e =  
    (fun n m o p q -> n,m,o,p,q) <!> a <*> b <*> c <*> d <*> e

Let's take a moment to see the signature of <!>

(<!>) : ('a -> 'b) -> 'a seq -> 'b seq

This signature should look familiar to you. Yes, it's Seq.map. Applicative functors are also functors, which is quite obvious from its name but we hadn't seen it until now. So we can write a map (a.k.a. lift) function for every applicative functor exactly as the <!> operator above.

Observing the law

Applicative functors, just as regular functors, need to satisfy some laws. Just as the last time, we'll use FsCheck, and again we'll have to cheat a little to get comparable types (we can't compare infinite sequences).

open System.Linq
// limited comparison for infinite sequences
let toListFrom r a = Enumerable.Take(a, List.length r) |> Seq.toList

type ApplicativeLaws<'a,'b,'c when 'a:equality and 'b:equality>() =
    static member identity (v: 'a list) = 
        let x = puree id <*> v
        toListFrom v x = v
    static member composition (u: ('a -> 'b) list) (v: ('c -> 'a) list) (w: 'c list) = 
        let toList = toListFrom u
        let a = puree (<<) <*> u <*> v <*> w
        let b = u <*> (v <*> w)
        toList a = toList b
    static member homomorphism (f: 'a -> 'b) x = 
        let toList a = Enumerable.Take(a, 10000) |> Seq.toList
        let a = puree f <*> puree x
        let b = puree (f x)
        toList a = toList b
    static member interchange (u: ('a -> 'b) list) (y: 'a) = 
        let toList = toListFrom u
        let a = u <*> puree y
        let b = puree ((|>) y) <*> u
        toList a = toList b

FsCheck.Check.QuickAll<ApplicativeLaws<_,_,_>>()

In the next post, we'll see how applicative functors relate to monads, with a parsing example.