leancheck-0.5.0: doc/tutorial.md
Introduction to property-based testing (with LeanCheck)
=======================================================
This document introduces property-based testing. The reader only needs to be
familiar with Haskell. No previous knowledge of property-based testing is
assumed. This document focuses on LeanCheck, but skills are transferable to
[other property-based testing tools](#other-property-based-testing-tools-for-haskell).
(If you are already familiar with property-based testing and just want to learn
how to use LeanCheck, you might be best served by reading
[LeanCheck's README file](../README.md).
The learning outcomes of each section are:
* [What is property-based testing?](#what-is-property-based-testing)
--- what is property-based testing;
* [Example 1: testing `sort`](#example-1-testing-a-sort-implementation)
--- how to use a property-based testing library (LeanCheck);
* [Example 2: testing `insert`](#example-2-testing-conditional-properties)
--- how to test conditional properties
* [Example 3: testing `Stack`](#example-3-testing-user-defined-datatypes)
--- how to apply property-based testing to functions over user-defined
datatypes by declaring [`Listable`] typeclass instances;
What is property-based testing?
-------------------------------
In property-based testing, properties are defined as Haskell functions
returning a boolean value which should be `True` for all possible choices of
argument values. These properties are applied enumerated or random argument
values in search for a counterexample. This is perhaps better illustrated in
an example (see Example 1).
### Terminology
Property-based testing might be known with other names:
* property testing;
* [parameterized unit tests]: in the context of C# ([NUnit]) or Java ([JUnit]),
properties are viewed with unit tests with
arguments.
Example 1: testing a sort implementation
----------------------------------------
Lets imagine that we want to test an implementation of a (not-so-quick) `sort`
function:
sort :: Ord a => [a] -> [a]
sort [] = []
sort (x:xs) = sort lesser ++ [x] ++ sort greater
where
lesser = filter (< x) xs
greater = filter (> x) xs
### In contrast --- unit testing
We can *unit test* the above implementation:
testsPass :: Bool
testsPass = and
[ [] == sort ([]::[Int])
, [1] == sort [1]
, [1,2,3] == sort [1,2,3]
, [1,2,3] == sort [3,2,1]
, [1..100] == sort [100,99..1]
]
If we evaluate `testsPass` on ghci, we will get `True` --- our implementation
of `sort` passes all our unit tests.
### Declaring properties
Alternatively, we use *property-based testing* to test the above
implementation. We first declare a few properties:
prop_elem :: Ord a => a -> [a] -> Bool
prop_elem x xs = elem x (sort xs) == elem x xs
prop_ordered :: Ord a => [a] -> Bool
prop_ordered xs = ordered (sort xs)
where
ordered (x:y:xs) = x <= y && ordered (y:xs)
ordered _ = True
prop_length :: Ord a => [a] -> Bool
prop_length xs = length (sort xs) == length xs
Those properties are similar to unit tests, but are parameterized. Instead of
defining the behavior of sort for specific values, each property defines the
behavior of `sort` for a range of values.
### Testing properties
By binding those properties to specific types and passing those properties as
arguments to the [`check`] function, we get:
$ ghci
> import Test.LeanCheck
> check (prop_elem :: Int -> [Int] -> Bool)
+++ OK, passed 200 tests.
> check (prop_ordered :: [Int] -> Bool)
+++ OK, passed 200 tests.
Internally, the function [`check`] enumerates arguments to those functions and
test whether properties hold.
### Finding and fixing bugs
But what happens when the function does not follow the properties?
> check (prop_length :: [Int] -> Bool)
*** Failed! Falsifiable (after 3 tests):
[0,0]
The `check` function reports a failing counterexample. We get a `False` value
when evaluating `prop_length [0,0]`. We can investigate on GHCi:
> prop_length [0,0]
False
> length (sort [0,0]) == length [0,0]
False
> length (sort [0,0])
1
> sort [0,0]
[0]
If we look back at our definition of `sort`, we can see that we forgot to
account for repeated elements. We should change `>` to `>=`:
greater = filter (>= x) xs
After fixing that bug, `prop_length` will pass:
> check (prop_length :: [Int] -> Bool)
+++ OK, passed 200 tests.
Example 2: testing conditional properties
-----------------------------------------
The boolean operator [`==>`] can be used to construct conditional properties.
The function [`insert`] defined in [`Data.List`] inserts an element into a list
at the first position where it is less than or equal to the next element.
*If the list is already ordered, the resulting list will still be ordered:*
prop_insertOrd x xs = ordered xs ==> ordered (insert x xs)
Example 3: testing user-defined datatypes
-----------------------------------------
Consider the following implementation of a `Stack`:
data Stack a = Stack a (Stack a)
| Empty
deriving (Show,Eq)
push :: a -> Stack a -> Stack a
push x s = Stack x s
pop :: Stack a -> (a, Stack a)
pop (Stack x s) = (x,s)
We might want to test the following property:
prop_popush :: a -> Stack a -> Bool
prop_popush x s = pop (push x s) == (x,s)
However, if we provide this property on ghci, we get an error:
> check (prop_popush :: Int -> Stack Int -> Bool)
<interactive>:x:1:
No instance for (Listable (Stack Int))
Our `Stack` type should be made an instance of the [`Listable`] typeclass.
This way LeanCheck will have a way to know how to list values to be tested by
the property. See [`Listable`] documentation for more. In this case, the
instance is:
instance Listable a => Listable (Stack a) where
tiers = cons2 Stack
\/ cons0 Empty
Now:
> check (prop_popush :: Int -> Stack Int -> Bool)
+++ OK, passed 200 tests.
LeanCheck also provides the function [`deriveListable`] to automatically derive
[`Listable`] instances for types that do not follow a data invariant (precondition).
Advantages of property-based testing
------------------------------------
Property-based testing has a few advantages over unit-testing:
* (+) scalability:
after making a small change to a program, we might [`checkFor`] `50` tests;
before making a major release, we may [`checkFor`] `1000` tests.
A continuous integration system can be configured to run more test than what
is usual on developers machines.
* (+) documentation:
properties serve as a clear documentation of behaviour;
* (+) tool support:
in Haskell there are several different property-based testing tools to choose
from.
The disadvantage is:
* (-) Properties are comparatively harder to write than simple input and output
test cases. (+) However, it might be easier to define good properties than a good
selection of unit test cases.
See "[Ranking programs using Black-Box testing (2010)]".
If you are unsure, you can always use *both* PBT and UT.
Other property-based testing tools for Haskell
----------------------------------------------
* [QuickCheck] : randomized
* [SmallCheck] : enumerative, depth-bounded
* [Lazy SmallCheck] : enumerative, depth-bounded, lazy, demand-driven
* [Feat] : enumerative, size-bounded
* [LeanCheck] : enumerative, size-bounded
Further reading
---------------
* [Using LeanCheck on functions over types with a data invariant](data-invariant.md)
* [Testing and tracing using QuickCheck and Hat](https://www.cs.kent.ac.uk/pubs/2003/1896/content.pdf)
* [QuickCheck's seminal paper (2000)](https://dl.acm.org/citation.cfm?id=1988046)
* [SmallCheck's paper (2008)](http://dl.acm.org/citation.cfm?id=1411292)
[`Listable`]: https://hackage.haskell.org/package/leancheck/docs/Test-LeanCheck.html#t:Listable
[`check`]: https://hackage.haskell.org/package/leancheck/docs/Test-LeanCheck.html#v:check
[`checkFor`]: https://hackage.haskell.org/package/leancheck/docs/Test-LeanCheck.html#v:checkFor
[`==>`]: https://hackage.haskell.org/package/leancheck/docs/Test-LeanCheck.html#v:-61--61--62-
[`deriveListable`]: https://hackage.haskell.org/package/leancheck/docs/Test-LeanCheck.html#v:deriveListable
[QuickCheck]: https://hackage.haskell.org/package/QuickCheck
[SmallCheck]: https://hackage.haskell.org/package/smallcheck
[Lazy SmallCheck]: https://hackage.haskell.org/package/lazysmallcheck
[Feat]: https://hackage.haskell.org/package/testing-feat
[LeanCheck]: https://hackage.haskell.org/package/leancheck
[parameterized unit tests]: http://research.microsoft.com/apps/pubs/default.aspx?id=77419
[NUnit]: http://www.nunit.org/index.php?p=parameterizedTests&r=2.5
[JUnit]: http://www.mkyong.com/unittest/junit-4-tutorial-6-parameterized-test/
[`insert`]: https://hackage.haskell.org/package/base/docs/Data-List.html#v:insert
[`Data.List`]: https://hackage.haskell.org/package/base/docs/Data-List.html
[Ranking programs using Black-Box testing (2010)]: http://www.cse.chalmers.se/~nicsma/papers/ranking-programs.pdf