Personal tools

Introduction to QuickCheck1

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
m (Testing take5)
m (Going further: - typo)
(27 intermediate revisions by 14 users not shown)
Line 1: Line 1:
A quick introduction to QuickCheck, and testing Haskell code.
+
A quick introduction to QuickCheck, and testing Haskell code. See [[Introduction_to_QuickCheck2| Introduction to QuickCheck2]] for the QC2 version
   
 
== Motivation ==
 
== Motivation ==
   
In September 2006, Bruno Mart�nez
+
In September 2006, Bruno Martínez
 
[http://www.haskell.org/pipermail/haskell-cafe/2006-September/018302.html asked]
 
[http://www.haskell.org/pipermail/haskell-cafe/2006-September/018302.html asked]
 
the following question:
 
the following question:
Line 22: Line 22:
 
-- would use a istringstream. I couldn't find a function that returns a
 
-- would use a istringstream. I couldn't find a function that returns a
 
-- Handle from a String. The closer thing that may work that I could find
 
-- Handle from a String. The closer thing that may work that I could find
-- was making a pipe and convertind the file descriptor. Can I simplify
+
-- was making a pipe and converting the file descriptor. Can I simplify
 
-- that function to take it out of the IO monad?
 
-- that function to take it out of the IO monad?
 
</haskell>
 
</haskell>
Line 36: Line 36:
 
Such a mixture is not good for reasoning about code.
 
Such a mixture is not good for reasoning about code.
   
Let's untangle that, and then test the the referentially transparent
+
Let's untangle that, and then test the referentially transparent
 
parts simply with QuickCheck. We can take advantage of lazy IO firstly,
 
parts simply with QuickCheck. We can take advantage of lazy IO firstly,
 
to avoid all the unpleasant low-level IO handling.
 
to avoid all the unpleasant low-level IO handling.
Line 46: Line 46:
 
-- A thin monadic skin layer
 
-- A thin monadic skin layer
 
getList :: IO [Char]
 
getList :: IO [Char]
getList = take5 `fmap` getContents
+
getList = fmap take5 getContents
   
 
-- The actual worker
 
-- The actual worker
Line 62: Line 62:
   
 
<haskell>
 
<haskell>
import Data.Char
+
import Data.Char
import Test.QuickCheck
+
import Test.QuickCheck
   
instance Arbitrary Char where
+
instance Arbitrary Char where
arbitrary = choose ('\32', '\128')
+
arbitrary = choose ('\32', '\128')
coarbitrary c = variant (ord c `rem` 4)
+
coarbitrary c = variant (ord c `rem` 4)
 
</haskell>
 
</haskell>
   
Line 75: Line 75:
   
 
<haskell>
 
<haskell>
*A> quickCheck ((\s -> s == s) :: [Char] -> Bool)
+
*A> quickCheck ((\s -> s == s) :: [Char] -> Bool)
OK, passed 100 tests.
+
OK, passed 100 tests.
 
</haskell>
 
</haskell>
   
Line 86: Line 86:
   
 
<haskell>
 
<haskell>
*A> quickCheck ((\s -> (reverse.reverse) s == s) :: [Char] -> Bool)
+
*A> quickCheck ((\s -> (reverse.reverse) s == s) :: [Char] -> Bool)
OK, passed 100 tests.
+
OK, passed 100 tests.
 
</haskell>
 
</haskell>
   
Line 108: Line 108:
 
Which we can then run in QuickCheck as:
 
Which we can then run in QuickCheck as:
 
<haskell>
 
<haskell>
*A> quickCheck (\s -> length (take5 s) == 5)
+
*A> quickCheck (\s -> length (take5 s) == 5)
Falsifiable, after 0 tests:
+
Falsifiable, after 0 tests:
""
+
""
 
</haskell>
 
</haskell>
   
Line 121: Line 121:
 
this:
 
this:
 
<haskell>
 
<haskell>
*A> quickCheck (\s -> length (take5 s) <= 5)
+
*A> quickCheck (\s -> length (take5 s) <= 5)
OK, passed 100 tests.
+
OK, passed 100 tests.
 
</haskell>
 
</haskell>
   
Line 134: Line 134:
   
 
We can specify that as:
 
We can specify that as:
  +
<math>\forall~s~.~\forall~e~.~e~\in~take5~s~\to~e~\in~[abcde] </math>
  +
  +
And in QuickCheck:
 
<haskell>
 
<haskell>
*A> quickCheck (\s -> all (`elem` ['a'..'e']) (take5 s))
+
*A> quickCheck (\s -> all (`elem` ['a'..'e']) (take5 s))
OK, passed 100 tests.
+
OK, passed 100 tests.
 
</haskell>
 
</haskell>
   
 
Excellent. So we can have some confidence that the function neither
 
Excellent. So we can have some confidence that the function neither
 
returns strings that are too long, nor includes invalid characters.
 
returns strings that are too long, nor includes invalid characters.
  +
  +
== Coverage ==
  +
  +
One issue with the default QuickCheck configuration, when testing
  +
[Char], is that the standard 100 tests isn't enough for our situation.
  +
In fact, QuickCheck never generates a String greater than 5 characters
  +
long, when using the supplied Arbitrary instance for Char! We can confirm
  +
this:
  +
  +
<haskell>
  +
*A> quickCheck (\s -> length (take5 s) < 5)
  +
OK, passed 100 tests.
  +
</haskell>
  +
  +
QuickCheck wastes its time generating different Chars, when what we
  +
really need is longer strings. One solution to this is to modify
  +
QuickCheck's default configuration to test deeper:
  +
  +
<haskell>
  +
deepCheck p = check (defaultConfig { configMaxTest = 10000}) p
  +
</haskell>
  +
  +
This instructs the system to find at least 10000 test cases before
  +
concluding that all is well. Let's check that it is generating longer
  +
strings:
  +
  +
<haskell>
  +
*A> deepCheck (\s -> length (take5 s) < 5)
  +
Falsifiable, after 125 tests:
  +
";:iD^*NNi~Y\\RegMob\DEL@krsx/=dcf7kub|EQi\DELD*"
  +
</haskell>
  +
  +
We can check the test data QuickCheck is generating using the
  +
'verboseCheck' hook. Here, testing on integers lists:
  +
  +
<haskell>
  +
*A> verboseCheck (\s -> length s < 5)
  +
0: []
  +
1: [0]
  +
2: []
  +
3: []
  +
4: []
  +
5: [1,2,1,1]
  +
6: [2]
  +
7: [-2,4,-4,0,0]
  +
Falsifiable, after 7 tests:
  +
[-2,4,-4,0,0]
  +
</haskell>
   
 
== Going further ==
 
== Going further ==
Line 148: Line 199:
 
those you've seen here to be tested. Some sources for further reading
 
those you've seen here to be tested. Some sources for further reading
 
are:
 
are:
* [http://www.cse.unsw.edu.au/~dons/data/QuickCheck.html The QuickCheck source]
+
* [http://code.haskell.org/QuickCheck/stable/Test/ The QuickCheck source]
* [http://haskell.org/ghc/docs/latest/html/libraries/QuickCheck/Test-QuickCheck.html Library documentation]
+
* [http://hackage.haskell.org/package/QuickCheck-2.4.2 QuickCheck Library documentation]
* [http://www.cse.unsw.edu.au/~dons/code/fps/tests/Properties.hs A large testsuite of QuickCheck code]
+
* [http://www.cse.chalmers.se/~rjmh/QuickCheck/manual.html QuickCheck v1 Manual]
* Paper [http://www.cs.chalmers.se/~koen/pubs/icfp00-quickcheck.ps QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs], Koen Claessen and John Hughes. In Proc. of International Conference on Functional Programming (ICFP), ACM SIGPLAN, 2000.
+
* [http://hackage.haskell.org/trac/ghc/browser/libraries/bytestring/tests?rev=bc96abdb6d3777bdc4eaaccf37494f535405d4e1 A large testsuite of QuickCheck code]
* Paper [http://www.math.chalmers.se/~koen/pubs/entry-fop-quickcheck.html Specification Based Testing with QuickCheck], Koen Claessen and John Hughes. In Jeremy Gibbons and Oege de Moor (eds.), The Fun of Programming, Cornerstones of Computing, pp. 17--40, Palgrave, 2003.
 
* Paper [http://www.math.chalmers.se/~koen/pubs/entry-tt04-quickcheck.html QuickCheck: Specification-based Random Testing], Koen Claessen. Presentation at Summer Institute on Trends in Testing: Theory, Techniques and Tools, August 2004.
 
* Paper [http://www.cs.chalmers.se/~rjmh/Papers/QuickCheckST.ps Testing Monadic Programs with QuickCheck], Koen Claessen, John Hughes. SIGPLAN Notices 37(12): 47-59 (2002):
 
* More [http://haskell.org/haskellwiki/Research_papers/Testing_and_correctness research on correctness and testing] in Haskell
 
 
* Tutorial: [[QuickCheck as a test set generator]]
 
* Tutorial: [[QuickCheck as a test set generator]]
 
* Tutorial: [[QuickCheck / GADT]]
 
* Tutorial: [[QuickCheck / GADT]]
  +
* More [[Research_papers/Testing_and_correctness | research on correctness and testing]] in Haskell
  +
  +
* 2012 Blog article: [http://ics.p.lodz.pl/~stolarek/blog/2012/10/code-testing-in-haskell/ Code testing in Haskell]
  +
* 2009 Blog article: [http://koweycode.blogspot.com/2009/07/some-ideas-for-practical-quickcheck.html some ideas for practical QuickCheck]
  +
* 2004 Paper [http://dl.acm.org/citation.cfm?doid=351240.351266 QuickCheck: Specification-based Random Testing], Koen Claessen. Presentation at Summer Institute on Trends in Testing: Theory, Techniques and Tools, August 2004.
  +
* 2003 Paper [http://www.cs.utexas.edu/~ragerdl/fmcad11/slides/tutorial-a.pdf Specification Based Testing with QuickCheck], Koen Claessen and John Hughes. In Jeremy Gibbons and Oege de Moor (eds.), The Fun of Programming, Cornerstones of Computing, pp. 17--40, Palgrave, 2003.
  +
* 2002 Paper [http://www.cse.chalmers.se/~rjmh/Papers/QuickCheckST.ps Testing Monadic Programs with QuickCheck], Koen Claessen, John Hughes. SIGPLAN Notices 37(12): 47-59 (2002):
  +
* 2000 Paper [http://www.eecs.northwestern.edu/~robby/courses/395-495-2009-fall/quick.pdf QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs], Koen Claessen and John Hughes. In Proc. of International Conference on Functional Programming (ICFP), ACM SIGPLAN, 2000.
  +
  +
Note, QuickCheck doesn't need to just be an embedded domain specific language for testing ''Haskell'' code. By making instances of Arbitrary for FFI types you can use Haskell and QuickCheck to check code in other languages.
   
 
[[Category:Tutorials]]
 
[[Category:Tutorials]]

Revision as of 07:43, 25 October 2012

A quick introduction to QuickCheck, and testing Haskell code. See Introduction to QuickCheck2 for the QC2 version

Contents

1 Motivation

In September 2006, Bruno Martínez asked the following question:

-- I've written a function that looks similar to this one
 
getList = find 5 where
     find 0 = return []
     find n = do
       ch <- getChar
       if ch `elem` ['a'..'e'] then do
             tl <- find (n-1)
             return (ch : tl) else
           find n
 
-- I want to test this function, without hitting the filesystem.  In C++ I
-- would use a istringstream.  I couldn't find a function that returns a
-- Handle from a String.  The closer thing that may work that I could find
-- was making a pipe and converting the file descriptor.  Can I simplify
-- that function to take it out of the IO monad?

So the problem is: how to effectively test this function in Haskell? The solution we turn to is refactoring and QuickCheck.

2 Keeping things pure

The reason your getList is hard to test, is that the side effecting monadic code is mixed in with the pure computation, making it difficult to test without moving entirely into a "black box" IO-based testing model. Such a mixture is not good for reasoning about code.

Let's untangle that, and then test the referentially transparent parts simply with QuickCheck. We can take advantage of lazy IO firstly, to avoid all the unpleasant low-level IO handling.

So the first step is to factor out the IO part of the function into a thin "skin" layer:

-- A thin monadic skin layer
getList :: IO [Char]
getList = fmap take5 getContents
 
-- The actual worker
take5 :: [Char] -> [Char]
take5 = take 5 . filter (`elem` ['a'..'e'])

3 Testing with QuickCheck

Now we can test the 'guts' of the algorithm, the take5 function, in isolation. Let's use QuickCheck. First we need an Arbitrary instance for the Char type -- this takes care of generating random Chars for us to test with. I'll restrict it to a range of nice chars just for simplicity:

import Data.Char
import Test.QuickCheck
 
instance Arbitrary Char where
    arbitrary     = choose ('\32', '\128')
    coarbitrary c = variant (ord c `rem` 4)

Let's fire up GHCi (or Hugs) and try some generic properties (its nice that we can use the QuickCheck testing framework directly from the Haskell prompt). An easy one first, a [Char] is equal to itself:

*A> quickCheck ((\s -> s == s) :: [Char] -> Bool)
OK, passed 100 tests.

What just happened? QuickCheck generated 100 random [Char] values, and applied our property, checking the result was True for all cases. QuickCheck generated the test sets for us!

A more interesting property now: reversing twice is the identity:

*A> quickCheck ((\s -> (reverse.reverse) s == s) :: [Char] -> Bool)
OK, passed 100 tests.

Great!

4 Testing take5

The first step to testing with QuickCheck is to work out some properties that are true of the function, for all inputs. That is, we need to find invariants.

A simple invariant might be:

   \forall~s~.~length~(take5~s)~=~5

So let's write that as a QuickCheck property:

\s -> length (take5 s) == 5

Which we can then run in QuickCheck as:

*A> quickCheck (\s -> length (take5 s) == 5)
Falsifiable, after 0 tests:
""

Ah! QuickCheck caught us out. If the input string contains less than 5 filterable characters, the resulting string will be less than 5 characters long. So let's weaken the property a bit:

   \forall~s~.~length~(take5~s)~\le~5

That is, take5 returns a string of at most 5 characters long. Let's test this:

*A> quickCheck (\s -> length (take5 s) <= 5)
OK, passed 100 tests.

Good!

5 Another property

Another thing to check would be that the correct characters are returned. That is, for all returned characters, those characters are members of the set ['a','b','c','d','e'].

We can specify that as: \forall~s~.~\forall~e~.~e~\in~take5~s~\to~e~\in~[abcde]

And in QuickCheck:

*A> quickCheck (\s -> all (`elem` ['a'..'e']) (take5 s))
OK, passed 100 tests.

Excellent. So we can have some confidence that the function neither returns strings that are too long, nor includes invalid characters.

6 Coverage

One issue with the default QuickCheck configuration, when testing [Char], is that the standard 100 tests isn't enough for our situation. In fact, QuickCheck never generates a String greater than 5 characters long, when using the supplied Arbitrary instance for Char! We can confirm this:

*A> quickCheck (\s -> length (take5 s) < 5)
OK, passed 100 tests.

QuickCheck wastes its time generating different Chars, when what we really need is longer strings. One solution to this is to modify QuickCheck's default configuration to test deeper:

deepCheck p = check (defaultConfig { configMaxTest = 10000}) p

This instructs the system to find at least 10000 test cases before concluding that all is well. Let's check that it is generating longer strings:

*A> deepCheck (\s -> length (take5 s) < 5)
Falsifiable, after 125 tests:
";:iD^*NNi~Y\\RegMob\DEL@krsx/=dcf7kub|EQi\DELD*"

We can check the test data QuickCheck is generating using the 'verboseCheck' hook. Here, testing on integers lists:

*A> verboseCheck (\s -> length s < 5)
0: []
1: [0]
2: []
3: []
4: []
5: [1,2,1,1]
6: [2]
7: [-2,4,-4,0,0]
Falsifiable, after 7 tests:
[-2,4,-4,0,0]

7 Going further

QuickCheck is effectively an embedded domain specific language for testing Haskell code, and allows for much more complex properties than those you've seen here to be tested. Some sources for further reading are:

Note, QuickCheck doesn't need to just be an embedded domain specific language for testing Haskell code. By making instances of Arbitrary for FFI types you can use Haskell and QuickCheck to check code in other languages.