Forty Six and Two

FsCheck 0.6.3 for Visual Studio 2010 RC and F# February 2010 CTP

2010-02-15T12:08:00.000-08:00

A new release of F# means a new release of FsCheck.

Removed the dependency on the F# PowerPack. This makes FsCheck easier to use, especially since the PowerPack is now separately distributed. Besides, it was only used to pretty print functions.
Cleaned up reflective generators a bit.
All projects are upgraded to build with Visual Studio 2010 now. For backwards compatibility, I’ve added an FsCheck2008.sln solution which allows you to build in Visual Studio 2008 with the February 2010 CTP. You’ll get a warning from MSBuild saying that ToolsVersion 4.0 is not supported and that it is treating the build as a 3.5 build. Good – that’s exactly what you want. FsCheck is still targeting .NET3.5 until .NET4 is out.

Enjoy.

Technorati: FsCheck,random testing,F#

Visug presentation in Leuven, Belgium on 8 Feb 2010

2010-02-11T12:54:00.001-08:00

Thanks to everyone who attended – hope you got something out of it (besides the free food and drinks…).

Here are the slides I used, as well as the (completed) demo project. There are some extra slides and some extra parts to the demo which I didn’t present. Apparently the whole thing will also appear on MSDN chopsticks, at which point I’ll update this post with the link.

On Understanding Data Abstraction, Revisited

2009-12-22T08:57:00.000-08:00

I’m not in the habit of posting links, but this essay by Willam R. Cook on the difference between ADTs and objects made such an excellent and humbling read... Humbling because in my arrogance I had assumed that I knew the difference – after all this is basic stuff. Excellent because despite the humbling experience, it’s a very enjoyable read.

Enjoy.

Technorati: ADT,objects,data abstraction

Share this post :

How to get hg-git working with Mercurial without installing Python on Windows

2009-12-08T11:51:00.000-08:00

Sorry for the horrendous search keyword-driven title, but I’ve been trying to get this to work for ages.

Here’s a step by step guide, along with some potential pitfalls.

1) Download TortoiseHg. I used 0.9.1.1. with Mercurial 1.4.1. Do not use the windows Mercurial command line only distribution – we’ll need to modify a zip file later and for some reason the zip file with the command line distribution cannot be modified with either WinRar, Winzip or 7-zip.

2) Install TortoiseHg as usual.

3) Download dulwich 0.4.0.

4) Add the directory called ‘dulwich’ inside the dulwich download (the one with the file __init__.py in it) to the library.zip file in the TortoiseHg folder (normally just C: \Program Files\TortoiseHg) using your favorite zip utility.

5) Download the tip of an up to date hg-git fork. I used http://bitbucket.org/gwik/hg-git/.

6) Put the hg-git directory in the TortoiseHg directory.

7) Add the following lines to your Mercurial.ini file:

bookmarks =

hggit = C:\Program Files\TortoiseHg\hg-git\hggit

That’s it. I finally managed to clone the ClojureClr repository with the above install:

> hg clone git://github.com/richhickey/clojure-clr.git
destination directory: clojure-clr.git
importing Hg objects into Git
Counting objects: 4001, done.
Compressing objects: 100% (1816/1816), done.
Total 4001 (delta 3153), reused 2774 (delta 2148)
importing Git objects into Hg
at:   0/307
at: 100/307
at: 200/307
at: 300/307
updating to branch default
313 files updated, 0 files merged, 0 files removed, 0 files unresolved

And with this we’re back to functional programming languages ;)

I didn’t test this any further.

Good luck!

Technorati: mercurial, hg, hg-git, git

Share this post :

FsCheck 0.6.2: F# October 2009 CTP/2010 Beta 2

2009-10-26T03:10:00.000-07:00

FsCheck is updated for the new F# release! Conversion was fairly straightforward, some name changes and indentation changes mostly. Furthermore, the following smaller changes:

A nice set of new default generators contributed by Howard Mansell. FsCheck can now generate any Enum instance, as well as generators for DateTime, arrays, positive and negative ints and so on. Check out the Arbitrary.fs file for a complete overview.
Some more examples
registerInstances and overwriteInstances now throws an exception if it cannot find any instances in the given type.

Happy FsChecking!

Simple and Fair Backtracking Computations

2009-09-19T06:53:00.000-07:00

Translated to F# from the fair and terminating backtracking monad and monad transformer by Oleg Kiselyov.

Sequence expressions in F# can be seen as backtracking computations. For example,

let backtrack =
    seq {   for i in 1..10 do
            for j in 1..10 do
            if i*j > 10 then yield (i,j) }

will yield one by one (i.e. lazily) all the tuples i,j that satisfy the guard i*j>10. In Haskell, you would use list comprehensions to much the same effect. Once the values of j are exhausted for a given i, the computation backtracks, takes the next value for i and retries all values for j. Don’t mistake the syntactic sugar for nested loops – there is really a computation builder behind this that translates to something like

1..10 >>= (fun i –> 1..10 >>= (fun j –> …))

where (>>=) represents monadic bind. This translations shows more clearly that the binds are really doing backtracking. It’s just F#’s syntactic sugar for computation expressions that makes the computation look like a nested loop.

Unfortunately, this simplicity has some drawbacks.

let infinite =
    seq {   for i in 1..10 do
            for j in Seq.initInfinite id do
            if i > 5 then yield (i,j) }

will never return any results, although there is an infinite number of solutions. The reason is that generation gets stuck on j – an infinite stream that will never yield a solution as long as the computation does not backtrack and tries new values for i. The computation is unfair in its choice of values to try – it always chooses the last stream until that is exhausted.

The thing to realize is that, if viewed as a backtracking computation, there are basically two operations that are important: choice and bind.

Choice gives the computation a range of elements to choose from. In the example above, we have an element i that can be chosen from the interval [1,10] and an element j that can be chosen from the interval [0,Infinity]. It can be viewed as logical disjunction: for i, choose 1 or 2 or 3 or 4 or…

Bind gives the computation a number of sub-computations that all need to return a value if the complete computation is to return a value. It can be understood as logical conjunction: in the example above, i should be chosen from [1,10] and j should be chosen from [0,Infinity] and i should be > 5.

Theoretically, it does not matter in which order these kinds of generate-and-test computations are executed. However, for performance and once you start using infinite streams, it becomes important that the computation is fair – in the sense that the choices it makes give every option consideration, even if once choice has not been exhausted yet. The results of all backtracking computations should be equivalent modulo the order in which the results are returned.

So, can we make an alternative computation builder for which this kind of computation returns results?

Fair streams

Let’s start by making a new datatype of streams, that we can use to make fairer choices, and that also can be suspended so that infinite streams can be supported:

type Stream<'a> = 
    | Nil                               //empty
    | One of 'a                         //one element
    | Choice of 'a * Stream<'a>         //one element, and maybe more
    | Incomplete of Lazy<Stream<'a>>    //suspended stream

Using this stream, we can code a fair choice function:

let rec choice r r' = 
    match r with
    | Nil -> r' //first empty-> try the second
    | One a -> Choice (a,r') //Put in front of the new stream
    | Choice (a,rs) -> Choice (a,choice r' rs) //interleave r and r' here
    | Incomplete i ->
        match r' with
        | Nil -> r
        | One b -> Choice (b,r)
        | Choice (b,rs') -> Choice (b,choice r rs') 
        | Incomplete j -> Incomplete (lazy (choice i.Value j.Value))

The important thing here is the switch of argument order in the recursive call to choice in the third case. This ensures that, in contrary to normal sequences, a choice will choose alternatively from the first and second stream (and so on, recursively, for more streams). Choice is actually somewhat equivalent to concatenate on sequences, only it interleaves the elements so that the choice is fair.

Bind is more straightforward:

let rec bind m f =
    match m with
        | Nil -> Nil
        | One a -> (f a)
        | Choice (a,r) -> choice (f a) (Incomplete (lazy bind r f))
        | Incomplete i -> Incomplete (lazy bind i.Value f)

This is what you would expect from a normal monadic bind on a list like type: a variant of map – concat on each element of the first stream. Note in the third case that we take care to encode the resulting stream as a number of choices that we can choose from fairly.

We now have the important elements to make a computation builder:

type FairStream() =
    member x.Return a = One a
    member x.Yield a = One a
    member x.Bind (m, f) = bind m f
    member x.Zero() = Nil
    member x.Combine (r,r') = choice r r'
    member x.Delay (f:unit->Stream<_>) = Incomplete (Lazy.Create f)

   
let bt = FairStream()

I called it bt, short for backtracking. Now we need a function to run our computation:

let rec run d st =
    match (d,st) with
    | _,Nil -> Seq.empty
    | _,One a -> seq { yield a }
    | _,Choice (a,r) -> seq { yield a; yield! run d r }
    | Some 0,Incomplete i -> Seq.empty //exhausted depth
    | d,Incomplete (Lazy r) -> let d' = Option.map ((-) 1) d in run d' r

The run function takes an optional parameter to bound the number of backtracking steps, which may be useful to help with termination.

A few examples

First, let’s define a stream of numbers [0,Infinity]:

let rec number() = bt { yield 0
                        let! n = number() in yield n+1 }

Nothing really amazing here – you could do something similar with sequences as well. However, if we use the choice constructor explicitly, we can define number as a left-recursive function:

let rec number() = choice (bt { let! n = number() in return n+1 }) (bt {return 0})

Both number functions yield the same results.

Now for something a bit more spectacular.

let guard assertion = 
    bt { if assertion then return () }

let pythagoreanTriples =
    bt{ let! i = number()
        do! guard (i > 0)
        let! j = number()
        do! guard (j > 0) 
        let! k = number()
        do! guard (k > 0)
        do! guard (i*i + j*j = k*k)
        return (i,j,k) }

This computation will never yield any results in a standard sequence expression, but with the fair streams it works, even if you leave off the guards.

The discerning reader might wonder why we can’t write:

let rec number() = 
    bt { let! n = number() in return n+1
         return 0 }

which is a left recursive version in a computation expression style. I don’t know the answer myself – some details are lost in the translation to the methods on the computation builder, but I’m guessing it has something to do with the bind not being lazy enough, and/or the choice function not getting inserted in the appropriate place. I’ve tried various approaches, but couldn’t get it to work. So I guess there’s some homework for you :) In the mean time, I think I’m going to work through Backtracking, Interleaving, and Terminating Monad Transformers by Kiselyov et al…

Technorati: F#,computation builder,backtracking,monads

Share this post :

More fun with data structures, continuations and call/cc

2009-06-27T04:32:00.000-07:00

Last time I showed a few ways of implementing insert into an unbalanced binary tree, as an implementation of a set data structure. This post adds an implementation that is similar in functionality to the example that uses call/cc, but using the more familiar exceptions to avoid allocating elements needlessly:

let insertExc x t =
    try
        let rec insertRec x t =
            match t with
            | Empty ->  cont { return Elem(empty,x,empty) }
            | Elem (left,e,right) when x < e -> 
                cont {  let! t' = insertRec x left
                        return Elem(t',e,right) }
            | Elem (left,e,right) when x > e -> 
                cont {  let! t' = insertRec x right
                        return Elem(left,e,t') }
            | Elem _ -> failwith "alreadyExists"
        insertRec x t id
    with e –> t

Performance shootout

A comment on the last post indicated that exceptions should be much slower (on .NET, at least) than the callCC approach. Furthermore, I said that callCC was necessary to avoid re-allocating elements needlessly on the search path to an already existing element. Let’s put these claims to the test with a simple benchmark:

let longList = 
    let r = new System.Random()
    let l = 100000
    [ for i in 1..l -> r.Next(0,l) ]

let insertALot f nbRuns =
    for i in 1..nbRuns do
        longList |> List.fold (fun t elem -> f elem t) empty

How many duplicates are in the long list (i.e. how much can we expect to gain by using callCC/exceptions):

> longList |> Seq.distinct |> Seq.length;;
val it : int = 63362

So about 35% duplicates. The results:

> insertALot insert 100;;
Real: 00:01:38.717, CPU: 00:01:37.516, GC gen0: 2247, gen1: 520, gen2: 8
val it : unit = ()
> insertALot insert' 100;;
Real: 00:01:44.583, CPU: 00:01:37.251, GC gen0: 4050, gen1: 1444, gen2: 18
val it : unit = ()
> insertALot insertM 100;;
Real: 00:02:35.101, CPU: 00:02:29.792, GC gen0: 12698, gen1: 1875, gen2: 24
val it : unit = ()
> insertALot insertCallCC 100;;
Real: 00:01:09.410, CPU: 00:01:02.540, GC gen0: 12149, gen1: 7, gen2: 0
val it : unit = ()
> insertALot insertExc 100;;

- Interrupt

Observe that:

the readability of computation expressions comes with a cost;
even with that cost, the callCC code is still significantly faster;
Exceptions are indeed horribly slow – I interrupted after about an hour.

Share this post :

Fun with data structures, continuations and call/cc

2009-06-24T13:00:00.000-07:00

Prompted by exercise 2.3 in Purely Functional Data Structures, by Chris Okasaki.

type Tree<'a> = Empty | Elem of 'a Tree * 'a * 'a Tree

let empty = Empty

Recursive

let rec insert x t =
    match t with
    | Empty ->  Elem(empty,x,empty)
    | Elem (left,e,right) when x < e -> Elem (insert x left,e,right)
    | Elem (left,e,right) when x > e -> Elem (left,e, insert x right)
    | Elem _ –> t

Tail Recursive

let insert' x t =
    let rec cont x t k =
        match t with
        | Empty -> k (Elem(empty,x,empty))
        | Elem (left,e,right) when x < e -> cont x left (fun t' -> k <| Elem (t',e,right))
        | Elem (left,e,right) when x > e -> cont x right (fun t' -> k <| Elem (left,e,t'))
        | Elem _ -> k t
    cont x t id

Using a continuation monad

type Cont<'a,'r> = ('a -> 'r) -> 'r

type ContBuilder() =
    member x.Return (a):Cont<'a,'r> = fun k -> k a
    member x.Bind (c:Cont<'a,'r>, f:'a -> Cont<'b,_>) =
        (fun k -> c (fun a -> f a k))
    member this.Delay(f) = f()

let cont = ContBuilder()

let insertM x t =
    let rec insertRecM x t =
        match t with
        | Empty ->  cont { return Elem(empty,x,empty) }
        | Elem (left,e,right) when x < e -> 
            cont {  let! t' = insertRecM x left
                    return Elem(t',e,right) }
        | Elem (left,e,right) when x > e -> 
            cont {  let! t' = insertRecM x right
                    return Elem(left,e,t') }
        | Elem _ -> cont { return t }
    insertRecM x t id

Using call with current continuation

let callCC (f:('a -> Cont<'b,'r>) -> Cont<'a,'r>) : Cont<'a,'r> = fun k -> f (fun a _ -> k a) k

let insertCallCC x t =
    callCC (fun alreadyExists ->
        let rec insertRecCallCC x t =
            match t with
            | Empty ->  cont { return Elem(empty,x,empty) }
            | Elem (left,e,right) when x < e -> 
                cont {  let! t' = insertRecCallCC x left
                        return Elem(t',e,right) }
            | Elem (left,e,right) when x > e -> 
                cont {  let! t' = insertRecCallCC x right
                        return Elem(left,e,t') }
            | Elem _ -> alreadyExists t
        insertRecCallCC x t
    ) id

Please note that the complexity of the last implementation is not obfuscation – it avoids recreating nodes on the path to an already existing element (exercise 2.3 actually asks to do it using exceptions, which works just as well).

Share this post :

Traversing and transforming F# quotations: A guided tour

2009-06-13T07:25:00.000-07:00

There seems to be some lack of information about quotations – most is either short, a specific example, or is a bit outdated. The most comprehensive example is probably Tomáš Petříček’s Quotations Visualizer in the F# samples. His site is also one of the better resources about quotations that I’ve found. Another one with some recent activity is Alex Pedenko’s blog. Furthermore, even the otherwise excellent Expert F# book has little to say about it, and predates the major changes that were made in the September CTP.

Here I’ll focus on the important general patterns of using quotations. That is, I’m going to show how to traverse and transform quotations, independent of any specific example. I’m going to focus more on the API and programming aspects, than on introductory concepts, so this assumes some intermediate-level knowledge of F#. Basic knowledge about quotations doesn’t hurt either, as I‘ll make explanations terse.

Either way, this post represents some knowledge that took me a while to figure out on my own, piecing together scattered sources.

I would like to point out that once you get over the learning curve, working with quotations is actually enjoyable. I’ve been refraining from using them because I was put off by some bad experiences with System.Reflection (I think System.Reflection truly sucks as an API) and because I felt that to do anything useful, you’d almost be forced to support (i.e. at the very least provide default implementations of) every single construct in F#. It turns out that the quotations API is very enjoyable to work with and that there are built-in means to start small and focus on the things that are interesting to you.

The basics

In short, a quotation is metadata that represents the code of a particular function or code snippet, that gets compiled into the dll (along with the actual executable code, in some cases) by the F# compiler. To those of you who are familiar with LINQ Expression trees, it’s the same concept only F#’s quotations cover the entire reach of the F# language.

There are three ways to obtain a quotation:

1) Use the <@ @> operation around a code snippet to get a typed quotation of type Expr<’a>, where ‘a is the type of the actual value you put into the snippet. The Expr “wrapper” essentially indicates that we’re not dealing with an actual value of type ‘a, but instead with a reified representation of that value – the quotation:

let typedExpr = <@ 1 + 5 @>

let typedExpr2 = <@ fun i -> i + 5 @>

Sending these to FSI gives:

val typedExpr : Quotations.Expr<int> =
  Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
      [Value (1), Value (5)])
val typedExpr2 : Quotations.Expr<(int -> int)> =
  Lambda (i,
        Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
              [i, Value (5)]))

First notice the types: the first is Expr<int> because 1 + 5 of course is an int value. The second example illustrates a function value, of type Expr<int->int>.

FSI has printed the values of the quotations: a representation of the code! In fact, as we’ll soon see, the Expr type is nothing more than a discriminated union with one case for each possible language construct in F# (it’s not actually a discriminated union under the covers, but that’s how it’s abstracted, and the abstraction is very clean. It doesn’t hurt to think about it that way.)

2) Use the <@@ @@> operator around a code snippet to get an untyped quotation, of type Expr. Expr<’a> is a subtype of Expr, and every Expr<’a> can be converted to an Expr by calling .Raw:

let untypedExpr = <@@ 1 + 5 @@>

let untypedExpr2 = <@@ fun i -> i + 5 @@>

Sending to FSI gives:

val untypedExpr : Quotations.Expr =
  Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
      [Value (1), Value (5)])
val untypedExpr2 : Quotations.Expr =
  Lambda (i,
        Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
              [i, Value (5)]))

Pretty much exactly the same information, except for the type. For library writers, the Expr type does all the heavy lifting of inspecting and transforming quotations: since in a library you almost always want to write some code for any quotation, you cannot write this code in a generic way with typed quotations.

3) Using the ReflectedDefinition attribute on a top level function gives you the best of both worlds: the function can be called and executed as normal, but it can also be inspected as a quotation:

[<ReflectedDefinitionAttribute>]
let quotation i = i + 5

Based on a MethodInfo, the Expression.TryGetReflectedDefinition method allows you to get to the Expr associated with the function. The necessary metadata is actually marshaled into the dll when this function is compiled.

The Microsoft.FSharp.Quotations namespace

This namespace in the FSharp core libraries contains three modules and three types. The types are Expr, Expr<’a> and Var. The first two we’ve discussed already, the third one is just the representation of a variable.

The meat of quotations processing is in the module Quotations.Patterns and the static methods on Expr. If you compare these two, you’ll notice that for every active pattern in the Patterns modules, there is a static method on Expr. For example, you have Patters.Call(…) and Expr.Call(…), with equivalent signatures. This is no coincidence: the Patterns module contains all the patterns you’ll need to deconstruct a quotation expression. Together, these patterns can traverse any F# abstract syntax tree. It contains 32 active patterns (that’s a lot, but don’t despair yet: it gets better. ).

Its dual, the static methods on the Expr type, construct quotation expressions programmatically.

If you know F#, it shouldn’t be too hard to figure out what the arguments mean. For example:

Expr.Call : obj:Expr * methodInfo:MethodInfo * arguments:Expr list –> Expr

constructs an expression that represents a method call (defined by a methodInfo) on a target object (i.e. it’s an instance method), taking the given arguments. Conversely,

( |Call|_| ) : Expr -> (Expr option * MethodInfo * Expr list) option

is an active pattern that matches a method call, with an (optional) target, methodinfo and a list of arguments.

This duality makes it fairly easy to get started with constructing and deconstructing quotations. Try to make some quotations and print them using fsi – it will give you a good idea of what code constructs the patterns represent. Alternatively, use the quotation visualizer mentioned above.

Another module, Quotations.DerivedPatterns, contains additional active patterns that are not needed in the strict sense, but that represent some common use cases for deconstructing a quotation. An example is

( |SpecificCall|_| ) : Expr -> (Expr -> (Type list * Expr list) option)

which is a variant of Call that takes an expression and matches if the quotation is the given method or function call. The beauty of this particular active pattern is that you can use quotations to match on the given quotation:

let recognizePlus quotation =
    match quotation with
    | SpecificCall <@ (+) @> (types,exprs) -> printfn "Plus! types=%A  exprs=%A" types exprs
    | _ -> printfn "something else"

> recognizePlus <@ 1 + 2 @>;;
Plus! types=[System.Int32; System.Int32; System.Int32]  exprs=[Value (1); Value (2)]

Come on, this is still a lot of work, isn’t it?

That last example has one major shortcoming, which will hit you pretty hard when you’re trying to do anything useful with quotations. Even when you’re only interested in one particular kind of node (say, you’re interested in doing something with all (+) calls), you still have to walk the whole expression tree in order to be sure that you’ve seen all the method calls. Consider:

> recognizePlus <@ 1 * (2 + 3) @>;;
something else

Why? Because the tree looks like:

Call (None, Int32 op_Multiply[Int32,Int32,Int32](Int32, Int32),
      [Value (1),
       Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
             [Value (2), Value (3)])])

so we’re calling multiply first – and our function doesn’t do anything with that. In order to find all plus calls, we need to look through the whole tree recursively – including the multiply call’s children. But doesn’t that mean that we’ll have to rewrite our recognizePlus function to incorporate a match on all of the 32 active patterns in Quotations.Patterns (or at least those that return child expressions, which is pretty much all of them) just to be able to traverse the whole expression tree looking for a plus call?

Luckily, no. This is were the third module in the Quotations namespace comes in.

The secret sauce: Quotations.ExprShape

This module is really the workhorse of pretty much anything you’ll do with quotations. Now, I believe this will come as a surprise to most people – in fact, it took me a bit of luck (when I saw it being used in passing, in a post on hubfs) to really understand what this module was all about. It was one of those moments for which a beautiful German word exists: Aha-Erlebnis.

This module’s mystery is in no small part thanks to its“terse” documentation. In fact, it’s so short I’ll reproduce it completely here:

val RebuildShapeCombination : obj * Expr list -> Expr	Re-build combination expressions. The first parameter should be an object returned by the ShapeCombination case of the active pattern in this module.
val ( \|ShapeVar\|ShapeLambda\|ShapeCombination\| ) : Expr -> Choice<Var,(Var * Expr),(obj * Expr list)>	An active pattern that performs a complete decomposition viewing the expression tree as a binding structure.

First, look at the active pattern. The key thing is that this active pattern is complete: every quotation will match with one of the three cases of the active pattern: either it is a variable (ShapeVar), a lambda (ShapeLambda) or a “combination” (ShapeCombination). So, we now have a general and complete decomposition of any quotation, and it is short:

let workhorse quotation =
    match quotation with
    | ShapeVar v -> ()
    | ShapeLambda (v,expr) -> ()
    | ShapeCombination (o, exprs) -> ()

Notice if you paste this in an .fs file that the compiler does not complain about any missing match cases, reinforcing my point. So, now we can do this recursively, which gives us:

let rec traverse quotation =
    match quotation with
    | ShapeVar v -> ()
    | ShapeLambda (v,expr) -> traverse expr
    | ShapeCombination (o, exprs) -> List.map traverse exprs |> ignore

Here’s the beauty: this simple function traverses all the expressions and sub-expressions in any quotation. You don’t have to deal with all 32 cases in order to do something with one node. This function should be the basis of all your work with traversing quotations: anything you want to do, as far as inspecting the tree goes, can be built on top of this simple structure. Let’s revisit our earlier example:

let rec recognizePlus' quotation =
    match quotation with
    | SpecificCall <@ (+) @> (types,exprs) -> 
        printfn "Plus! types=%A  exprs=%A" types exprs
        List.map recognizePlus' exprs |> ignore
    | ShapeVar v -> ()
    | ShapeLambda (v,expr) -> recognizePlus' expr
    | ShapeCombination (o, exprs) -> List.map recognizePlus' exprs |> ignore

Let’s run this on our failing example of earlier:

> recognizePlus' <@ 1 * (2 + 3) @>;;
Plus! types=[System.Int32; System.Int32; System.Int32]  exprs=[Value (2); Value (3)]

It sure found the plus now.

Transforming quotations

So far, we’ve just been inspecting the quotation. Now let’s actually do something with it. Again, the ExprShape module will be a big win: the workhorse here is the ShapeCombination and RebuildShapeCombination duality.

You might have noticed the o parameter in the ShapeCombination; this is an opaque marker that stores how the sub-expressions in a shape combination can be put back together , i.e. whether it is a function call, a let binding, or anything else that has child expressions. This is were the function RebuildShapeCombination comes into play: given an o marker and the right number and type of child expressions, it can put an expression deconstructed by ShapeCombination back together . So, whereas above we wrote a general traversal function for quotations, a general transformation function looks like:

let rec transform quotation =
    match quotation with
    | ShapeVar v -> Expr.Var v
    | ShapeLambda (v,expr) -> Expr.Lambda (v,transform expr)
    | ShapeCombination (o, exprs) -> RebuildShapeCombination (o,List.map transform exprs)

This function takes any quotation and transforms it into itself, visiting, deconstructing and reconstructing every node in the expression tree along the way.

If you’re familiar with a zipper data structure, this reminds me of it: the active patterns “open the zipper” and the RebuildShapeCombination function “closes the zipper”. (Actually, I’m not sure that the sub-expressions get reused or are made anew, but it seemed familiar anyway.)

So, let’s do some transformation: let’s replace all calls to (+) with calls to (-). (Maniacal laugh and organ playing):

let rec evilTransform quotation =
    let minus l r = <@@ %%l - %%r @@>
    match quotation with
    | SpecificCall <@ (+) @> (types,l::r::[]) -> 
        minus (evilTransform l) (evilTransform r)
    | ShapeVar v -> Expr.Var v
    | ShapeLambda (v,expr) -> Expr.Lambda (v,evilTransform expr)
    | ShapeCombination (o, exprs) -> RebuildShapeCombination (o,List.map evilTransform exprs)

Ignoring the specifics of the actual transformation, which I’ll get to in a moment, notice that the structure of the transformation is exactly the same as above, except now we’ve added one pattern to deal with the case we’re interested in: a call to addition. Essentially, this is saying: do something special for addition, and just traverse the tree, leaving it unchanged, for all the rest.

Splicing

Now, I know I said earlier that the Expr.Call static method is the dual of the Call active pattern, so you’d expect that I would have used that in the result of the SpecificCall match above. I could have done that, but instead I chose to demonstrate another useful technique for constructing expressions: splicing, denoted by the % or %% operator, for typed and untyped splicing respectively. All this operator does is insert an expression in a certain place (or places) into a quotation. So the minus function constructs a quotation that represents the subtraction of two given expressions (this doesn’t always make sense – in that case we’ll get a runtime exception with untyped quotations). Splicing is a very readable and versatile way of constructing expressions, because you can actually write your expressions in F# instead of using Expr.Call and friends.

The proof of the pudding

In the F# powerpack, there are some useful (but somewhat experimental) functions to actually compile and evaluate any F# quotation. The process is somewhat convoluted: the quotation trees are first translated to .NET Expressions, and then that API is used to compile them. This comes with a significant performance hit: code compiled using that route can be a factor of 5 slower. So don’t use it for optimization. So far, I haven’t run into any limitations yet, and it’s a nice way to check whether everything works:

let before = <@ 1 + 2 * 3 + 5 @>
let after = evilTransform <@ 1 + 2 * 3 + 5 @>
printfn "%A" <| before.EvalUntyped()
printfn "%A" <| after.EvalUntyped()

Shows:

12
-10

val evilTransform : Expr -> Expr
val before : Expr<int> =
  Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
      [Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
             [Value (1),
              Call (None, Int32 op_Multiply[Int32,Int32,Int32](Int32, Int32),
                    [Value (2), Value (3)])]), Value (5)])
val after : Expr =
  Call (None, Int32 op_Subtraction[Int32,Int32,Int32](Int32, Int32),
      [Call (None, Int32 op_Subtraction[Int32,Int32,Int32](Int32, Int32),
             [Value (1),
              Call (None, Int32 op_Multiply[Int32,Int32,Int32](Int32, Int32),
                    [Value (2), Value (3)])]), Value (5)])

Pretty cool, and it opens up all kinds of interesting possibilities. For example, you can write a lazy transformer, which inserts lazy and force in the appropriate places to simulate call-by-need semantics in F#. You can add side-effects to print the result of each call as it is evaluated. Or you can transform the expression in something completely different – SQL, PHP, FPGA instructions, whatever you want.

Conclusions

The three main things you should know about the quotations API:

Quotations.Expr and Quotations.Patterns are each other’s dual: they are used for constructing and deconstructing Expr types respectively;
Quotations.ExprShape contains the workhorse of any quotations-using implementation: a zipper-like pattern for traversing and transforming any quotation in a straightforward way;
Splicing is used to effectively and readably construct parameterized expressions as an alternative to Expr.Whatever calls.

Like I said before, I think the API strikes an excellent balance between simplicity and abstraction. F#’s features come together nicely to provide a clean development experience. I was somewhat afraid of quotations before, because I had an image in my mind that it would be messy, lots of work, and lots of special cases. Turns out it isn’t, and I hope this post will do its part in getting some more attention to this aspect of F#.

Download the example .fs file. Don’t forget to add references to FSharp.PowerPack and FSharp.PowerPack.Linq, if you want to run the dynamic compilation examples.

Technorati: F# quotations

Share this post :

Announcing FsCheck 0.6.1

2009-05-23T09:36:00.000-07:00

No functional changes, just an update as a result of the May CTP released by the F# team.

Get it here.

Change log:

Many name changes as a result of name changes in the F# API
Used the new formatting API, which gets rid of a bunch of obsolete warnings
Tried to solve issues resulting from changed initialization order
Added a standalone version of the FsCheck binary, to accommodate C#/VB users better
Added a contributors file. Want your name in there? Then contribute ;)

Enjoy the new CTP!

Share this post :

How to test DSLs (and: FsChecking FsCheck)

2009-05-12T13:50:00.001-07:00

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:

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.
Generate the actual representation in your compiler or interpreter from the symbolic representation.
Specify the semantics of the symbolic representation.
Rely on FsCheck’s built-in generators, or make your own generator to generate the symbolic representation.
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 :

Announcing FsCheck 0.6: Dot is the new pipe

2009-05-12T13:17:00.000-07:00

It is about time to release a new version of FsCheck, and here it is.

What’s new in this release?

A fluent interface for C# and VB

This is in prototype stage at the moment, and has some limitations with respect to the F# interface, but I would say it’s about 90% functional. An example of a property in C#:

Spec.ForAny<int, int[]>((x, xs) => xs.Insert(x).IsOrdered())
                .When((x, xs) => xs.IsOrdered())
                .Classify((x, xs) => new int[] { x }.Concat(xs).IsOrdered(), "at-head")
                .Classify((x, xs) => xs.Concat(new int[] { x }).IsOrdered(), "at-tail")
                .QuickCheck("InsertClassify");

This property is the equivalent of the following in F#:

let prop_InsertClassify (x:int) xs = 
    ordered xs ==> (ordered (insert x xs))
    |> classify (ordered (x::xs)) "at-head"
    |> classify (ordered (xs @ [x])) "at-tail" 
quickCheck prop_InsertClassify

As you can see, it’s about the same amount of code, but because of the fluent interface I have to add a class for each number of type arguments - currently limited to three. Ideally, I’d like to generate some code for classes up to six or nine, but for the moment it’s all copy-paste and you can only write properties with up to three parameters this way. For the rest, almost everything should be working: you can register generators, provide configuration, add shrinkers, and write generators using some combinators and LINQ:

var gen = from x in Any.OfType<int>()
          from y in Any.IntBetween(5, 10)
          where x > 5
          select new { Fst = x, Snd = y };

Pretty neat.

Incidentally, there is no C# code in FsCheck itself, and the fluent interface is all pure F# code. This was a good test to see how interoperable F# really is. Overall, the experience has been great, with just a few minor hiccups.

I translated most of the F# examples from the documentation to C# as well, you can find those in the F# source distribution.

Possibility to replay a test run. FsCheck now displays the seed it used to start a test run when it fails. You can give this seed to a configuration parameter, so that FsCheck will repeat the run with exactly the same generated values:

check { quick with Name="Counter-replay"; Replay = Some <| Random.StdGen (395461793,1) } (asProperty spec)

Various bug fixes and updates to xml docs.
I’m making headway in testing FsCheck using FsCheck itself. It’s an interesting experience, and I have a blog post lined up about it.

The C#/VB “mainstream” support is something that I hope to continue to improve – I also plan to add reflective object generators and Gallio integration, mainly as a means to get some more attention for FsCheck. It’s also an interesting exercise to compare approaches. So far, if you know F#, I’d stick with it, but you can see that LINQ is occasionally very elegant for defining generators.

Happy FsChecking!

Share this post :

Tests are not specifications

2009-05-06T13:03:00.000-07:00

There seems to be some consensus in the TDD and BDD community that the tests (or behaviors) for a given software system constitute an (executable) specification of the system.

Wrong.

A specification is an unambiguous and complete description of a system or subsystem. Or at least it should be a heroic attempt.

A test, whether written as a traditional unit test, or as an executable scenario in BDD is neither unambiguous nor complete. Worse, it’s not even trying.

A test is almost always written as one specific example of how a subsystem should behave. An implementation that can fail on other examples will pass the test, and so still fulfill the non-specification. Furthermore, there are many implementations with wildly differing behavior that can pass the test.Doesn't sound like a specification to me, or at least not a good one.

In fact, if TDD/BDD advocates would really follow their advice to program no more than what the tests test, then given the following test:

Assert.Equal (Reverse [1,2,3] , [3,2,1])

they should implement the pseudo function:

Reverse list = [3,2,1]

Compare with what FsCheck's properties look like (again, in pseudo-code):

Reverse [x] = [x]

Reverse (x::xs) = Reverse xs @ [x]

That's what I call a specification: unambiguous, and complete. So TDD talks the talk, but does not walk the walk.

Before you start commenting, foam at the mouth, I’m not saying testing is bad – on the contrary. It’s just that you should stop kidding yourself by calling tests specifications. It’s like saying that “8” is an algorithm for adding two numbers, because it happens to work for 3 and 5.

Using frameworks and tools such as Code Contracts, Pex and FsCheck (I’m being completely unbiased here, of course), you will take a big step towards writing real specifications, not tests. That’s where their real value is.

Share this post :

FsChecking dnAnalytics – Part 3

2009-03-13T08:37:00.000-07:00

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 :

FsCheck on Ohloh

2009-03-06T12:14:00.000-08:00

I found out about Ohloh recently and decided to play around with it by adding FsCheck. From FsCheck’s Ohloh page we learn that:

it’s mostly written in Make. Uhm, what?
it has a short source control history (that’s right: I do all my local development using Mercurial, and only export to codeplex on release)
it has a single active developer (I’m not single, I have a lovely wife!)
it has very few source code comments (I didn’t put any comments in the Makefile. Sorry.)

It seems that the appraisal of an open source project can not be replaced by a small shell script…

Anyway, it’s nice to see how many related projects there are (and how many projects in general). If you’re in the neighborhood, come say hi, add a rating, add a user, whatever…

Technorati: fscheck,ohloh

FsCheck 0.5.1

2009-03-01T03:54:00.001-08:00

Just a short note to announce v0.5.1 of FsCheck, which fixes some bugs in 0.5 and includes one improvement in the category I-can't-believe-I-didn't-see-this-earlier.

Bug fix: no more escaping exceptions when using lazy
Bug fix: no extra initialization (init.Value) necessary when registering generators 'early'
check (and quickCheck, verboseCheck) now take a simple value 'a instead of a function value 'a->'b as argument, so you can just write 'quickCheck <| forAll ...' instead of 'quickCheck (fun () -> forAll ...)'.

I don't see any reason not to update if you're using 0.5.

Technorati: F#,FsCheck

FsChecking dnAnalytics Part 2

2009-02-27T15:10:00.000-08:00

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

2009-02-23T14:06:00.000-08:00

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

Announcing FsCheck 0.5

2009-02-19T13:19:00.000-08:00

Another month has gone by, another release of FsCheck is a fact. (No, I won't keep this up). Check out the goodies.

Major:

Shrinking, which was introduced in FsCheck 0.4, is now fully customizable per type. This concludes the integration of Neil Mitchell's shrinking code (modulo the extra bugs I introduced, obviously)
Combining properties using and, or, and giving a name to subproperties, similar to functionality in a port of QuickCheck to Scala: scalacheck
Model based testing for stateful types, another shameless scalacheck rip-off. A surprisingly small extension to FsCheck that allows you to check stateful object types.
Thanks to some excellent feedback from Ganesh (from the Crédit Suisse team, which has been generous with contributions; thanks!) property combinators have become more general, in particular any Lazy<property> can now be tested (as opposed to only Lazy<bool> in 0.4).

Minor

New property combinators: throws (expect an exception), within (expect a result within some time). The latter is from QuickCheck 2.
New generator combinators: listOf, constant, suchThat, suchThatMaybe, again from QuickCheck 2.
Pretty printing and shrinking of function values. You guessed it, ported from QuickCheck 2.
Added support to TypeClass.fs to define typeclasses of arrays (this needs to be special cased since an array is not an ordinary generic type. Hurray for the consistencies of language design). FsCheck now also knows how to generate and shrink arrays.
Added makefile for Mono users, thanks to toyvo. I've tried to keep it up to date, but have not tested it so let me know if you have any problems.
Various bug fixes and smaller improvements.Notably the generator for discriminated unions should now produce "bigger" values, and the float generator now generates NaN, Infinity and Epsilon fairly often.

With these changes, I can safely say that FsCheck 0.5 has reached near feature parity with the combination(!) of both QuickCheck 2.1.0.1 and Scalacheck 1.5. Not bad for half a release on a technology preview platform.

I plan to let this stabilize over the next few months, and finally adding those FsChecks to FsCheck itself - FsCheck is fornicating priestware at the moment (*). I have however used FsCheck fairly frequently in private projects and I must say it has helped me a lot. Hopefully I'll have time to blog more about my experiences soon.

As usual, let me know if you have any feedback, always a pleasure to hear from you!

(*) i.e. it does not practice what it preaches

Technorati: F#,FsCheck,quickcheck,scalacheck

How to deal with out parameters in F#

2009-01-24T06:28:00.000-08:00

This is the third installment of my modest 'how to' series, where I try to highlight some in my opinion unappreciated (or under-marketed) gems of F#: little language features that pleasantly surprised me when I first learned about them.

Don't you hate out parameters? It's such a chore to use them: you need to declare a variable, pass it in the method with the out parameter modifier, and then check the results. Out parameters suck: they're just a poor excuse for not having to add a decent tuple type to your language. Unfortunately, some methods in the .NET framework use out parameters, and you might be dealing with some legacy code that uses them (some developers, apparently, think out parameters are the greatest idea since sliced bread).

Luckily, calling methods with out parameters is very easy in F#: they are converted to a tuple type automatically. For example, the Math.DivRem method has the following signature:

public static int DivRem( int a, int b, out int result )

which calculates the quotient of two numbers and also returns the remainder in an output parameter (in F#, this is a byref parameter).

Using this method in F# is simple:

let (q,r) = Math.DivRem(n,d)

The out parameter has been automatically converted to the second element of the resulting tuple.

Technorati: F#,out parameters

Announcing FsCheck 0.4

2009-01-14T14:18:00.000-08:00

It's been a month and a half since the last release of FsCheck. Time for an update!

Major changes:

Rewrote the back end using typeclasses. The result: much less reflection, cleaner code, and improved flexibility in the property combinators. In particular, the 'prop' and 'propl' combinators can now be omitted. Properties can take any nunber of arguments, that do not need to be tupled. Generators can now be more easily defined, and function generators are also derived based on type.
Two major new features were contributed generously by Howard Mansell and team at Credit Suisse. Most of the implementation was done by Neil Mitchell, who has also helped me a lot in integrating the changes in the main FsCheck branch. Thank you both!
The features are:
- Automatic generation of records, discriminated unions (including recursive ones), arrays and tuples. So once you define a generator for a type, FsCheck can now automatically generate lists, arrays, record types, functions, discriminated unions and options involving that type.
- Shrinking. Especially with recursive datatypes, counter examples can become quite large. FsCheck now automatically shrinks these examples to a smaller one, making bug finding lots easier.

Minor changes:

Some performance improvements
Improvements in FsCheck's output.
Factored out the function that prints the result of a test, so you can use it in your IRunner implementation if necessary
Because FsCheck uses less reflection, stack traces of exceptions when a test case fails are shorter and clearer

Breaking changes:

quickCheck no longer checks types; instead use quickCheckAll, verboseCheckAll or checkAll. quickCheck is the preferred way to check properties: it is faster, clearer and more flexible.
You'll need to redefine some of your custom generators; the mechanism to define and register generators has changed. See the manual for details, an don't hesitate to ask questions.

This is a bit of an intermediary release - for v0.5 I'd like to integrate shrinking better, so you can define your own shrinkers for a given datatype. Should be straightforward now that I've reworked the back-end, but I wanted to get this release out first - I think shrinking and the reflective datatype generators by themselves are worth a new release. Most of the churn should be over now, I'm finally happy now with the way a user can define new properties and generators.

Enjoy!

Technorati: FsCheck,quickcheck,F#

A poor man's typeclass

2009-01-13T12:43:00.000-08:00

This post contains a surprisingly short library which allows you to emulate Haskell's typeclasses in F#, except the type-safety. You might think that takes a lot away from the concept, but there is still plenty usefulness left. Not in the least it allows you to use an almost one-to-one translation of Haskell code including typeclasses to F#. At runtime both behave identically. In addition, since this is a library, its functionality can be extended beyond Haskell's typeclasses. Finally, if nothing else, you might be interested in how typeclasses work: this post shows you an implementation.

What is a typeclass, really?

If you don't know what typeclasses are, I recommend reading this chapter in the excellent Real World Haskell book. Let's look at a simple example of a typeclass from that chapter:

class BasicEq a where
isEqual :: a -> a -> Bool

This defines a typeclass BasicEq. All instances (which are defined later) will need to provide a function isEqual, which compares two values of the instance a. An example of such an instance is:

instance BasicEq Bool where
    isEqual True True = True
    isEqual False False = True
    isEqual _     _     = False

This example provides an instance of BasicEq for the type Bool. A lot of people coming from an OO background compare this with an abstract class BasicEq with a subclass Bool, when in fact it is nothing like that. There is absolutely no subtyping of any kind going on. The only relevant type here is Bool; after the instance definition Haskell just knows what isEqual function to call when applied to type Bool. There is absolutely no abstract class. Even more, although Bool is an already defined type, we are adding it as an instance of BasicEq after the fact, something which is not possible in any mainstream statically typed OO language with subtyping.

Typeclasses are a form of so called ad-hoc polymorphism. It has much more in common with operator overloading as it is known in F#, than with subclassing. In fact, the type of isEqual is:

isEqual :: (BasicEq a) => a -> a -> Bool

This indicates that isEqual can be called on any instance a of the typeclass BasicEq. In fact, Haskell only knows the specific function to call when it knows the type a: then, it just looks up the functions associated with that type. So, in fact, the (BasicEq a) => in front of the arguments can (besides as a type annotation) be seen as a dictionary that maps types a to functions implementing the BasicEq typeclass functions for a. The great thing about this is that because of type inference, the actual type a is inferred without any programmer annotation. So Haskell can choose the correct function to call automatically.

So, in the end, what is a typeclass? It's just a dictionary from type to a record of functions, where on each application of a typeclass function Haskell passes along the dictionary to it's calling function implicitly (i.e. without requiring the caller to pass it in). Because of type inference, this sometimes looks like pulling a function or value out of thin air.

The idea

If a typeclass at runtime is nothing more than using type information to pass in an implicit parameter to a function, then in F# we can use respectively reflection and side effects to emulate much the same thing:

Using reflection, we can obtain the type arguments with which a function is called
Using side effects, we can build a globally accessible dictionary of types to functions, that can be accessed "transparently", without needing the caller to thread it in calls.

The rest is some syntactic sugar.

Let's first look at how we can use the library, before diving into it's internals. Usage is remarkably similar to that of typeclasses. First, we define the typeclass:

type IListOf<'a> =
    abstract ListOf : list<'a>

This looks like a traditional class or interface type definition, that represents the functions in the typeclass. This type should have exactly one type parameter, which represents the type that we'll be defining instances for.

Now, let's register this new typeclass with our library:

newTypeClass<IListOf<_>>

newTypeClass takes one generic parameter, of which only the generic type definition part is important; this registers IListOf<'a> as a typeclass with which instances for certain types 'a can be registered.

Now, let's make some instances:

type IListOfInstances() =
    static member Unit() = 
        { new IListOf<unit> with
            override x.ListOf = [()]}
    static member Bool() = 
        { new IListOf<bool> with
            override x.ListOf = [true;false] }
    static member Int() = 
        { new IListOf<int> with
            override x.ListOf = [1..20] }

That defined instances for our typeclass IListOf with three instances for types unit, bool and int. As you can see, the corresponding interface implementations should be returned as the result of static members.

These instances must now be registered with the typeclass:

registerInstances<IListOf<_>,IListOfInstances>()

A function that we need to give two type arguments: the typeclass we're registering instances for, and the the type with the static members which return the instances.

Now we can get a specific IListOf implementation for a specific type:

getInstance (typedefof<IListOf<_>>,typeof<unit>)

However, this returns an obj - not nice. We'd like a typed listOf function that can be used whenever we want a list of some typeclass instance. Let's define such a function:

let listOf<'a> = getInstance (typedefof<IListOf<_>>,typeof<'a>) |> unbox<IListOf<'a>> |> (fun l -> l.ListOf)

The function takes only a type argument - which is used to get the instance, unbox the result (if the implementation of the typeclass library is correct, the unbox should always succeed), and then call the ListOf property which should return the correct list. This function can now be used just like an overloaded function:

printfn "%A" (listOf |> List.map (fun x -> x+5))
printfn "%A" (listOf |> List.map (fun x -> if x then "pos" else "neg"))

What is going on? The first listOf returns a list of ints, while the second returns a list of bools, although it seems we're not passing it any argument or hint as to what list to produce. Magic? Of course not.

We are passing listOf information - in its type argument. The reason we don't have to explicitly mention this argument is because F# infers it for us. So this is a great way to let type inference do some work at runtime.

The implementation

The library maintains an internal dictionary of typeclass names to instances of that typeclass:

let private typeClasses = new Dictionary<_,_>()

Defining a new typeclass prepares the one value of that dictionary to hold another dictionary which will map the actual instance types to their implementation of the typeclass functions:

let newTypeClass<'typeClass> = typeClasses.Add((typeof<'typeClass>).GetGenericTypeDefinition(), new Dictionary<_,_>())

The following method then uses some reflection to find all the instances of a given typeclass, which should be defined as static members on a given class type:

let private findInstances (typeClass:Type) = 
    let addMethods l (t:Type) =
        t.GetMethods((BindingFlags.Static ||| BindingFlags.Public)) |>
        Seq.fold (fun l m ->
            match m.ReturnType with
                | GenericTypeDef typeClass args -> 
                    if (args.Length <> 1) then
                        failwithf "Typeclasses must have exactly one generic parameter. Typeclass %A has %i" typeClass args.Length
                    else
                        let instance = args.[0]
                        if instance.IsGenericType 
                            && (instance.GetGenericArguments() |> Array.for_all (fun t -> t.IsGenericParameter)) then
                            (args.[0].GetGenericTypeDefinition(), m) :: l   
                        else
                            (args.[0], m) :: l
                | _ -> l
            ) l
    addMethods []

///Register instances in a given class as instances of the given type class. 
let registerInstancesByType typeClass instance =
    findInstances typeClass instance |> Seq.iter (typeClasses.[typeClass].Add)

///Register instances in a given class as instances of the given type class.
let registerInstances<'typeClass,'instance>() = 
    registerInstancesByType (typedefof<'typeClass>) (typeof<'instance>)

The final ingredient is the lookup function, to get the implementation of a typeclass given a type:

let getInstance   =
    memoize (fun (typeClass:Type, instance:Type) ->
        let instances = typeClasses.[typeClass]
        let mi =
            match instances.TryGetValue(instance) with
            | (true, res) -> res
            | _ when instance.IsGenericType -> //exact type is not known, try the generic type
                match instances.TryGetValue(instance.GetGenericTypeDefinition()) with
                | (true, mi') -> if mi'.ContainsGenericParameters then (mi'.MakeGenericMethod(instance.GetGenericArguments())) else mi'
                | _ -> failwithf "No instances of class %A for type %A" typeClass instance 
            | _ -> failwithf "No instances of class %A for type %A" typeClass instance 
        mi.Invoke(null, Array.empty))

There is some heavy reflection going on here, which I'll let you figure out in your own time. The memoize function I took from the Expert F# book. Full implementation is downloadable below.

Conclusions

This posts shows how to get all the advantages of typeclasses in F#, except the static checking. I've found these advantages considerable:

The use of reflection is heavy, but it is very nicely encapsulated: all the un-typesafeness goes on strictly inside the library and definition. What goes in and what comes out is strongly typed, and from a user point of view, the reflection is completely behind the scenes.
Although reflection is involved, it is actually fast: there is some manipulation of Types, but this is highly optimized in .NET. There is one reflective invocation per instance that is looked up, but the result is memoized so this can be considered startup cost. Finally, there are two constant time dictionary lookups.
To give a real world example, in FsCheck 0.4 (which will be out real soon) I have been able to use this simple library to translate the Arbitrary and Testable typeclasses from QuickCheck directly into F#, making property combinators more powerful. For one, there is no longer a need for the 'prop' and 'propl' functions, a feat which I was not able to accomplish using reflection alone (and I did try!). So the typeclass abstraction is a nice way to structure your code around overloading.
It has also allowed me to reduce the amount of reflection code in FsCheck and other projects - which is a Good Thing as reflection is always a pain to use.
It's a great way to let type inference work for you, also at run time.

Finally, some things for the future:

This library is not thread safe, although it could be made thread safe at the cost of some locking.
Are multi-parameter type classes possible using this technique?
...

Anyway, I hope that this post has shown that with some imagination and a little work, you can do great things with F#, not in the least thanks to a lot of infrastructure in the form of .NET libraries, without which this would not have been possible.

Download the full implementation. It will also be distributed with FsCheck 0.4 (soon, I promise :).

Technorati: F#,typeclass,haskell

How to change the accessibility of a constructor using implicit object construction

2008-12-20T08:54:00.001-08:00

The recommended way to define a class in F# is by using so-called implicit object construction. The more traditional (for C# programmers, that is) but typically more tedious explicit object construction syntax feels distinctly less "functional". In short, implicit construction relieves you of writing an explicit constructor for your class, and also allows you to use let and do clauses in the body of your class that take the place of static or instance initializers. Check out Robert Pickering's F# wiki for a nice overview.

The other day I was writing a class that needs only factory methods to construct it, a not so uncommon pattern. In C#, I wouldn't think twice about how to do this: just add a private or internal constructor, and a few public factory methods. This is also straightforward to do using F#'s explicit object construction syntax, but I wondered if it is possible using implicit construction. Turns out it is!

The trick is simple:

type Foo internal()=

static member FactoryMethod = new Foo()

Notice the position of the 'internal' modifier. Modifying the accessibility of the 'Foo' class proper is done in the usual way, by putting the modifier right after the 'type' keyword. You can even mix these up:

type internal Foo private()=

This defines an internal class with a private constructor.

Thanks to Brian and Tomas for helping me out on this one!

Technorati: F#,implicit object construction,syntax,accessibility modifier

Announcing FsCheck 0.3

2008-12-03T14:28:00.000-08:00

I am very pleased to announce a new release of FsCheck, for the first time on codeplex! Here is a short description.

FsCheck is a port of Haskell's QuickCheck: it is a tool for testing F# programs automatically. The programmer provides a specification of the program, in the form of properties which functions, methods or objects should satisfy, and FsCheck then tests that the properties hold in a large number of randomly generated cases. While writing the properties, you are actually writing a testable specification of your program. Specifications are expressed in F#, using combinators defined in the FsCheck library. FsCheck provides combinators to define properties, observe the distribution of test data, and define test data generators.

This release brings FsCheck about up to par with QuickCheck 0.1, and adds some smaller features. An overview:

Added feature to derive a generator from the type of arguments. You can add your own generators for custom types. Radically reduces the use of forAll.
Added feature to reduce use of prop and propl. For example: "quickCheck (fun a -> a+a = 2*a)" just works.
Added feature to group related properties in a class, and check it at once. Can also be used to check all toplevel properties in a module.
FsChecks no longer dies when a property throws an exception, but reports a test failure.
Bug fixes and suggestions received through this blog, email and hubfs implemented. Thanks Neil, Chance, Mat and Anton, and everyone who emailed me!
Some extension points to use FsCheck with whateverUnit frameworks.
Updated examples, and documentation, the whole codeplex thing.

It was a lot of work, but I hope it was worth it.

I plan to devote more of my time to other projects from now on, at least for the next coming months. That said, your contributions to FsCheck are more than welcome. Besides, this release should keep you quiet for a while ;).

I will be posting some suggestions for features and improvements soon, should you run out of ideas.

[Update: check out the FsCheck issue tracker for some ideas on how to contribute]

Technorati: F#,FsCheck,random testing

Future plans for FsCheck

2008-11-15T06:18:00.000-08:00

Because of a recent question on HubFS, I made my future plans for FsCheck public. I'm re-iterating them here:

smaller bug fixes, some cleaning (mostly done)
adding FsCheck.fsi module declaration & comments
Feature: derive generators from types of arguments (mostly done)
Feature: ability to group properties in classes, and check the class with one command (mostly done)
Investigate using FsCheck with unit testing frameworks like MbUnit & co, or generally how to use it in practice (currently active)
putting the project on codeplex + clarifying license . I'm checking compatibility with the QuickCheck license, but I'm aiming for a permissive license, like the new BSD license.

I intend to finalize this before the end of the year.

Finally, you can help by answering the following question. How are you using FsCheck? Do you have a separate console app that you run that contains your properties, or do you use F# interactive with the properties inline, or something else?

Technorati: F#,random testing,FsCheck