In the previous post, we talked about some of the basics of functional programming unit testing. That post mostly focused around HUnit, which is a traditional xUnit testing framework. This time, let's focus on type-based property testing, which is to create specs which assert logical properties about a function, and then to generate data to test in an attempt to falsify these assertions, through the use of a tool called QuickCheck.
Much like the traditional xUnit frameworks, this tool helps us flush out the specifications of our software through the use of tests. Unlike the xUnit frameworks, however, this framework allows us to create generators to help flush out our behaviors and capture our edge cases as we look for ways to falsify our tests. These generators could use either random data or well structured data that you can craft. Let's dive a little deeper into what that means.
But, before we continue, let's get caught up to where we are today:
Introducing QuickCheck
Testing in the functional programming world is important, especially when precision in algorithms leave little room for error. With the use of QuickCheck, and property-based testing, we are able to write functions that should satisfy universally, with the actual test data to be generated by QuickCheck in such a way that we specify. This way, we can literally run thousands of variations that would be pretty unreasonable to write by hand, or by using the RowTest from the MbUnit world. Doing so, we are able to find subtle edge cases that we may not find otherwise.
Let's first walk through a simple example of how QuickCheck works before we move onto some more interesting ones. First, let's do a simple check on a reverse statement. We'll use the standard prop_ notation to mark our property-based tests from here on out.
prop_RevRev :: [Int] -> Bool
prop_RevRev xs = (reverse . reverse) xs == xs
What this code does is say that when calling reverse on a given list twice, it should equal the original list, in this case, an integer list. We can then use a built-in integer generator to give us our input. Once the property-based test has been written, we can use the GHCi to run our example:
We can then notice that it tried 100 values against our given function and found that there are no errors. Had I made a mistake in my property-based test, it would have exited prematurely with the data that caused the particular error. For example, I could be careless about my input and expect always to take 5 items from a list.
prop_TakeFive :: [Int] -> Bool
prop_TakeFive xs = (length . take 5) xs == 5
Now, what we did wrong is assume that our lists were always going to be greater than 5 in length, which could be an issue, and QuickCheck easily alerts us to that fact as shown below:
One thing to remember is that creating property-based tests can be hard and we need to be careful how we specify them. It takes time to refine them and get them right, but luckily the Haskell community is great for learning either through IRC, Haskell-Cafe or other places.
Let's walk through another example of a ROT13 implementation and perform property-based testing on it. A ROT13 is a simple cipher which rotates a given letter by 13 places and when applied twice, will undo itself. The input handles only alphabetic characters and case does matter. The question is, how do we test something like this? Let's look at the basic proof for this:
ROT13(ROT13(x)) = ROT26(x) = x where x is any given text.
How do I express that in property-based tests? Well, let's lay out four basic cases with the given input of data from upper and lower case letters only, and then implement each one.
- A ROT13 of a given string should equal a ROT13 of the same string
- A ROT13 of a given string should not equal the original string
- A ROT13 applied twice to the original string should equal the original string
- A ROT13 of a given string should have the same distribution shape as the original. For example, "foo" when sorted and grouped should be ["f", "oo"] and then mapped to [1,2]. The shape of its translation to "sbb" should follow the same grouping as well of [1,2].
Now that we've deduced our criteria for success for this algorithm, let's define the property tests.
module EncryptionTests where
import Data.List
import Encryption(rot13)
-- Equal
prop_rot13_equals s =
not (null s) ==> rot13 s == rot13 s
-- Single is inequal to original
prop_rot13_single_notEquals s =
not (null s) ==> rot13 s /= s
-- Double is equal to original
prop_rot13_double_equals s =
not (null s) ==> (rot13 . rot13) s == s
-- Distribution shapes should be equal
prop_rot13_group_equals s =
not (null s) ==> getDistro (rot13 s) == getDistro s
where getDistro = sort . map length . group . sort
We need to define now what data we will be giving to the function in order to create the strings for our property tests. In order to define the data, we need to create an instance of the Arbitrary typeclass. Below, we'll define the Char version which includes both upper and lower case letters.
instance Arbitrary Char where
arbitrary = elements (['A'..'Z'] ++ ['a'..'z'])
coarbitrary n = variant (ord n)
Now that the rules and data are defined, how might we implement the rot13 function? Remembering that case does matter, we'll have to handle each one differently. The implementation would look something like the following:
module Encryption(rot13) where
import Data.Char(chr, ord)
rot13 :: String -> String
rot13 =
map mapRot
where mapRot :: Char -> Char
mapRot c | c >= 'A' && c <= 'Z' = rot 'A' c
| c >= 'a' && c <= 'z' = rot 'a' c
| otherwise = c
rot :: Char -> Char -> Char
rot b c = chr $ (ord c - ord b + 13) `mod` 26 + ord b
We can now run our property tests through QuickCheck through the GHCi console, such as the following:
quickCheck (prop_rot13_group_equals :: String -> Property)
Then we'll be able to see the results as shown below:
This seems great, but you may be wondering why you would use this. The answer is simple, for functionally pure algorithmic work in a functional language, use QuickCheck to formulate the specs. Else, if there are side effects, state or other behaviors that aren't easily captured using QuickCheck, then the traditional xUnit frameworks apply better. Even still, if having IO in the code, it's best to refactor the code to separate the pure function from the IO interaction.
As I mentioned in a previous post, there are other versions out there for us to use. What about the F# world?
QuickCheck in F#?
Kurt Schelfthout has been working on a port of the Haskell QuickCheck library to F# called FsCheck, now available on CodePlex. Today, Kurt released version 0.3 of the product which puts it on par with the QuickCheck 1.0 library, which is well short of the version 2.1.0.1 of QuickCheck now available for Haskell. But, how do I use it?
Let's look at some simple examples of some of the above code in F# this time to gain a better understanding of how it works in F#. First, let's do a translation of the simple reverse function as we did above.
#light
open FsCheck
let prop_RevRev (xs:int list) =
(List.rev >> List.rev) xs = xs
quickCheck prop_RevRev
After running this code, we see that 100 tests pass nicely. Now, a quick example of doing the ROT13 implementation. Just one test should suffice to show how it works.
#light
open FsCheck
open FsCheck.Generator
let rec rot13 =
List.map mapRot
and mapRot = function
| c when c >= 'A' && c <= 'Z' -> rot 'A' c
| c when c >= 'a' && c <= 'z' -> rot 'a' c
| c -> c
and rot b c = char ((int c - int b + 13) % 26 + int b)
type CharGenerator() =
static member Chars = elements(['A'..'Z'] @ ['a'..'z'])
overwriteGenerators (typeof<CharGenerator>)
let prop_rot13_equals s =
(rot13 >> rot13) s = s
quickCheck prop_rot13_equals
Once you run the code, you'll find that it passes the 100 tests easily just as it did in the Haskell version. I hope that the FsCheck project will continue, and I don't see why not. After all, it's up to the community to pick it up and run with it. I'd like to see continued work on the test framework plugins such as xUnit.net, MbUnit and NUnit. That would make a more integrated story, and that's part of the next post to bring it all together.
There is a lot more to be covered as I've just touched a very small portion of what QuickCheck can do. There is a lot of good documentation to be read on the subject on the Haskell Wiki as always.
Conclusion
As always, it's important to stress design and specification of your functional programming code. With such toolsets as QuickCheck, we can use this to not only flush out our design, but test our code in many ways through generated data, to help ease the edge cases that might not have been found if coding straight by hand. Learning these techniques are not always easy and careful consideration must be given when crafting these property tests.
There is still much to cover in this section, which includes extending HUnit, tying our tests together, and code coverage, so stay tuned.