Blog

Haskell provides QuickCheck a domain-specific language widely used for testing and adapted to many other languages. Like Parsec, QuickCheck takes time to learn, but is a worthwhile tool to have available.

What QuickCheck does is ingenious. Let’s assume that we’ve written a function and would like to test that a property holds for a set of arbitrary inputs to that function. As a concrete example, let’s define a function `f x = x * x`

and a property `p v = v >= 0`

. `f`

is the *function under test* and `p`

is the *property being tested*. Note the signatures of `f`

and `p`

:

```
f::Int -> Int
f x = (x * x)
p::Int -> Bool
p v = v >= 0
```

If we want to say that `p`

holds for all `f`

, we would prove the following property:

This tells us that for every integer $x$, $p$ holds for $f x$. (This isan easy proof, but for discussion let’s assume we only have testing available to us.)

To test `p`

we can write a function:

```
\x -> (p (f x))
```

and call that function with numerous random values of `x`

. The more tests run, the more confident we are in the result.

This is exactly what QuickCheck does:

```
quickCheck (\x -> (p (f x)))
```

will generate 100 arbitrary `Int`

values and call `(\x -> (p (f x)))`

on each. In this case, the square of every integer is greater than or equal to zero, and we get the result:

```
+++ OK, passed 100 tests.
```

Alternatively, choosing a test that is false for some integers:

```
p' v = (v /= 100)
```

causes QuickCheck to display a counterexample:

```
quickCheck (\x-> (p' (f x)))
*** Failed! Falsifiable (after 18 tests and 1 shrink):
10
```

In this case, 100 random tests were enough to discover that 100 is the square of 10 and the test condition is thus false.

The magic of QuickCheck is the ability to generate random test cases. In this example, QuickCheck must generate random `Int`

values. Because `Int`

is a commonly used type, the ability to generate random `Int`

values is built-in to QuickCheck. In contrast `AE`

is a custom, user-defined type that is not built-in.

QuickCheck requires that the domain of any function it is called on be an instance of class `Arbitrary`

providing a function `arbitrary`

that generates an arbitrary value of that type. We must make `AE`

and instance of `Arbitrary`

:

```
instance Arbitrary AE where
arbitrary = ...
```

The type signature of `arbitrary`

tells us what direction we need to follow:

```
arbitrary :: Arbitrary a => Gen a
```

The `arbitrary`

operator is of type `Gen a`

where `a`

is also an instance of `Arbitrary`

. `Gen`

is a *generator*.

Let’s start by generating an arbitrary `Num`

. The `genNumFirst`

function does this by returning an arbitrary number:

```
genNumFirst =
do t <- arbitrary
return (Num t)
```

There is quite a bit going on here. First note that `Arbitrary`

is a monad allowing use of the `do`

notation to bind identifiers and sequence generators. Using `do`

, `genNumFirst`

calls `arbitrary`

, binds the result to `t`

, and then returns `(Num t)`

. Now we see `arbitrary`

at work. The `Num`

constructor in the `return`

statement constrains `t`

to be of type `Int`

. This is how the correct `arbitrary`

instance is identified for `t`

. `Int`

is an instance of `Arbitrary`

and its associated `arbitrary`

function is used to generate a value for `t`

. `genNumFirst`

generates arbitrary `Num`

values ofby lifting arbitrary `Int`

values into our AST.

Suppose we don’t want to look at all `Int`

values, but a range. The built in `choose`

operation does this by restricting the range of `arbitrary`

. `genNum`

uses `choose`

to generate arbitrary `Num`

values over a subrange of `Int`

:

```
genNum =
do t <- choose (0,100)
return (Num t)
```

We could stop now and define `AE`

to be an instance of `Arbitrary`

as follows:

```
instance Arbitrary AE where
arbitrary = genNum
```

Our arbitrary values of `AE`

are not arbitrary as they will only include number values ranging from 0 to 100. We need terms that involve `Plus`

and `Minus`

if our intent is testing an interpreter.

Let’s start with `Plus`

and think about how we might generate arbitrary terms. The simplest approach is to generate `Plus`

terms over arbitrary numbers:

```
genPlusFirst =
do t1 <- genNum
t2 <- genNum
return (Plus t1 t2)
```

This generator gets us part way there, but only generates terms of the form `(Plus (Num v1) (Num v2))`

where `v1`

and `v2`

are arbitrary `Int`

values. A term of the form `(Plus (Plus (Num 1) (Num 2)) (Num 3))`

would never be generated. What we need is to generate terms recursively in the `Plus`

generator. Unfortunately we don’t have a generator for terms yet. We’ll have to set this aside and use `genPlusFirst`

.

`Minus`

is identical to `Plus`

modulo the constructor name, thus we’ll defer that generator and assume we have `genMinusFirst`

available.

Now let’s put our generators together to generate a more complete set of terms using `genAE`

. The simplest way to compose generators for our individual terms is to use the `oneof`

operator that chooses one generator arbitrarily from a list of generators:

```
genAEFirst = oneof [genNum,genPlus,genMinus]
```

If we use `genAEFirst`

we arbitrarily generate a `Num`

, `Plus`

or `Minus`

. Getting closer, but not quite there. Remember that `genPlusFirst`

and `genMinusFirst`

only build terms from `Num`

. With a generator for `AE`

we can fix that now by using `genAEFirst`

where we used `genNum`

:

```
genPlusSecond =
do s <- genAEFirst
t <- genAEFirst
return (Plus s t)
```

If we do the same thing with `genMinusSecond`

we will now generate arbitrary `AE`

terms. Unfortunately, those arbitrary `AE`

terms are of *arbitrary size*. Mathematically this is perfectly fine as huge things don’t bother us in the symbolic world. Pragmatically this is not perfectly fine as `genAEFirst`

can now generate arbitrarily huge test cases. If you want to see what this does, use `sample`

to generate a few test cases and be prepared to terminate your Haskell process!

How do we make our generator for `AE`

not go into the weeds generating huge test cases? The easiest way is to add a size limit to the `AE`

generator function by adding a size parameter to `genAE`

that is decremented on each call to `genAE`

.

Let’s start with `genAE`

by adding a size parameter, `n`

and a base case when `n`

hits zero:

```
genAE :: Int -> Gen AE
genAE 0 =
do term <- genNum
return term
genAE n =
do term <- oneof [genNum,(genPlus (n-1)),(genMinus (n-1))]
return term
```

This new function takes a size counter and produces a generator. If the size counter is zero, then the generator will produce a number and will not recurse. If the size counter is not zero, the generator will produce an arbitrary term while decrementing the size counter. `genPlus`

and `genMinus`

must be similarly extended to include the size counter:

```
genPlus n =
do s <- genAE n
t <- genAE n
return (Plus s t)
```

The counter is passed to `genAE`

where it will be decremented in any mutually recursive call to `genPlus`

or `genMinus`

. Note that it is always an option to call `genNum`

when the counter is not zero. This allows for any term whose size is less than the counter, not just equal to it.

Now we make `AE`

and instance of `Arbitrary`

by using `genAE`

to define the `arbitrary`

function:

```
instance Arbitrary AE where
arbitrary =
sized $ \n -> genAE (rem n 10)
```

What’s going on here is obfuscated by underlying construction of generators, but let’s see if we can make sense of it. `sized`

is a function that accepts an argument of type `Int -> Gen a`

. `sized`

then chooses an arbitrary positive integer and calls its argument on that value to produce a generator. In effect, the parameter `n`

is an arbitrary value that we can use to produce a generator. We could just use `n`

as an argument to `genAE`

. What I’ve done is use the `rem`

function to convert `n`

into an arbitrary value less than 10. This is overkill, but demonstrates how we can use `sized`

to arbitrarily size a structure. Another alternative would define `arbitrary`

this way:

```
arbitrary = sized $ \n -> genAE (rem n 10) + 10
```

In this case the arbitrary values would have a maximum size ranging from 10 to 19. There are all kinds of games one can play to generate interesting arbitrary cases.

Before we go on, here’s all the code for our generators and making `AE`

and instance of `Abitrary`

in one place:

```
instance Arbitrary AE where
arbitrary =
sized $ \n -> genAE (rem n 10)
genNum =
do t <- choose (0,100)
return (Num t)
genPlus n =
do s <- genAE n
t <- genAE n
return (Plus s t)
genMinus n =
do s <- genAE n
t <- genAE n
return (Minus s t)
genAE :: Int -> Gen AE
genAE 0 =
do term <- genNum
return term
genAE n =
do term <- oneof [genNum,(genPlus (n-1)),(genMinus (n-1))]
return term
```

An idiom is emerging even in this simple interpreter that merits attention. We defined our parser, interpreter, generator, and pretty printer the same way. Define the function for each individual case, then put the cases together to define the overall function. Remember this. It will serve you well.

Now that we can generate arbitrary `AE`

values, we can start our testing. Like many things in Haskell, once the preparatory work is done, using what we built is rather simple.

Before we can run QuickCheck, we need to determine what it is we’re going to test for. For a traditional test case, we provide an input and an expected output. QuickCheck performs *random testing* meaning that we need to express correctness in terms of an unknown test case. We can’t find `eval n`

and compare it to a known value.

Let’s first look at our parser for ideas. If the parser and pretty printer are working correctly, pretty printing an `AE`

structure and parsing the result, should give us the same `AE`

structure. Formally:

To turn this into an input for QuickCheck we remove the universal quantifier and pass in a value for $t$. The Haskell representation is:

```
\t -> parseAE (pprint t) == t
```

Calling QuickCheck on this function generates 100 arbitrary `AE`

values and test each one:

```
quickCheck (\t -> parseAE (pprint t) == t)
+++ OK, passed 100 tests.
```

We can play with parameters to QuickCheck that adjust the number of test cases to a larger or smaller set of test cases:

```
quickCheckWith stdArgs {maxSuccess=500} (\t -> parseAE (pprint t) == t)
+++ OK, passed 500 tests.
```

and define a utility function that can be used during development quickly run a set of tests on a parser instance:

```
testParser :: Int -> IO ()
testParser n = quickCheckWith stdArgs {maxSuccess=n}
(\t -> parseAE (pprint t) == t)
```

This final function is included in the source for `AE`

as an example test function. Note the type of `testParser`

taking an `Int`

and generating something that is printed.

Lets move forward and test the evaluator in a similar way. Again, what to test? There’s not much to work with here. Let’s test another property that is interesting, but does not represent correctness:

```
\t -> interp . pprint t == eval t
```

What this property says is evaluating an `AE`

structure gives us the same thing as pretty printing and then interpreting the same structure. Let’s embed that property in a test function for the evaluator:

```
testEval :: Int -> IO ()
testEval n = quickCheckWith stdArgs {maxSuccess=n}
(\t -> (interp $ pprint t) == (eval t))
```

Not much of a test, but if any of our components crashed QuickCheck will help find those cases.