## QuickCheck - property based testing in Haskell and JavaScript

By
Kamil Ciemniewski

March 16, 2016

In my last article, I presented a functional programming pattern. The goal was to reach out to the developers who werenâ€™t familiar with advanced type systems like the one found in Haskell and make them a bit curious. This time Iâ€™d like to take a step further and present a testing approach coming from the same world, that can be used with mainstream languages with a great success.

### Many ways to test the code

The importance of testing is almost a clichĂ© nowadays. Out of this relevance, a large number of testing frameworks and paradigms have been created. On the paradigm level we have notions like TDD and BDD. On the level of implementations we have hundreds of projects for each language like RSpec in Ruby and Jasmine or Mocha in JavaScript.

The ideas behind the libraries donâ€™t differ that much. All of them are based on the idea of providing code examples with assertions on how the code should behave in these particular cases.

A bit more revolutionary in its approach was the Cucumber project. In its essence, it allows business people to express the system logic by stating it in specially formed, plain English. An example taken from the Cucumberâ€™s website reads:

```
Feature: Refund item
Scenario: Jeff returns a faulty microwave
Given Jeff has bought a microwave for $100
And he has a receipt
When he returns the microwave
Then Jeff should be refunded $100
```

In this article, Iâ€™d like to present an approach that was conceived in the realm of Haskellâ€”â€‹the purely functional, statically typed language. Though it started just as a Haskell library, today it could be broadly named an â€śapproachâ€ť. We now have implementations for almost every major language. This approach is what is known as **QuickCheck**.

### Code testing limitations

Having a good test coverage is a sign of a potentially stable code. However, even well-tested software needs to be improved occasionally as new bugs are discovered. This happens even in the projects with the largest test suites. Moreover, the tests are code tooâ€”â€‹they also are prone to being invalid. But do we have a really valid solution when all our tests are valid and the code passes all assertions? Realistically, we can only provide a few examples per use case at most. The best we can do is to choose the most probable use cases and the ones we have a hunch that might go wrong.

This implies that for the tests suite to be guarding us against bugs, we need to have an insight as to where the potential bugs may be before even testing. Isnâ€™t a definition of a bug telling the other story though? If we knew where to find them, we would fix them in the first place. In reality the systems grow so complex that we only can have *a feeling* of what might go wrong.

In 1969, Edsger W. Dijkstra said at the â€śNato Software Engineering Conferenceâ€ť:

Testing shows the presence, not the absence of bugs.

### Iâ€™ve got lots of ammo, give me a machine gun for killing bugs!

What if we could ask the computer to come up with many different use cases for us? Instead of having 2 or 3 cases per some code aspect, weâ€™d have 100 of them including the ones weâ€™d never consider ourselves. We could describe **properties** of the code weâ€™d like to hold for all of the randomly chosen cases. That is exactly the idea behind the QuickCheck. In its functional - Haskell form, it takes advantage of the supreme type system and generates a random set of function parameters based on their types. It then runs the property check for all of them and stops if itâ€™s able to find a counter example making the property falsifiable.

If weâ€™d compare coming up with traditional test cases to shooting with a pistol, the **QuickCheck** approach had to be called firing with a machine gun. The reason is that weâ€™re not focusing on a specific use case, but weâ€™re focusing on certain properties of the code that have to hold for any argument from the accepted domain.

One of the most basic examples we could show, could be ensuring that the *reverse* function applied twice returns the original array (pseudo-code):

```
arr1 == reverse(reverse(arr1))
```

The idea here is to make sure this property holds against a large number of randomly selected arguments from the domain. In this example the checker would randomly generate e. g 100 arrays and test if the assertion evaluates to true for every one of them.

### Working example â€” the Haskell way

Letâ€™s take a look at how the approach is being used in its original environment. Later on we'll see how the pattern can be used when coding in JavaScript. For this, letâ€™s imagine that weâ€™re developing a graph data structure, to be used in some e-commerce project weâ€™re working on. Hereâ€™s the basic very incomplete draft:

```
module BlogGraph where
import Data.Map as Map
import Data.List as List
-- Graph as an adjacency list as described here:
-- https://en.wikipedia.org/wiki/Adjacency_list
data Graph a = Graph (Map a [a]) deriving (Show)
empty :: Graph a
empty = Graph Map.empty
insertNode :: (Ord a) => a -> Graph a -> Graph a
insertNode node (Graph m) = Graph $ Map.insert node [] m
removeNode :: (Ord a) => a -> Graph a -> Graph a
removeNode node (Graph m) = Graph $ Map.delete node m
insertEdge :: (Ord a) => a -> a -> Graph a -> Graph a
insertEdge parent child (Graph m) =
Graph $ Map.insertWithKey update parent [child] m
where
update _ _ old = List.nub $ child:old
nodes :: Graph a -> [a]
nodes (Graph m) = Map.keys m
```

If youâ€™re not proficient yet in reading Haskell code, weâ€™re just using a Map where keys are integers and values are arrays of integers to implement the graph as an Adjacency List. So each node has its representation in a map as one of its keys. Also, each edge has its representation as a child stored in the parentâ€™s array in the map.

You might be able to find a silly bug in the **removeNode** function. It doesnâ€™t remove the node from the edge definitions of other nodes. Weâ€™ll use **QuickCheck** to show how this could be found automatically.

Before doing that, letâ€™s have a warm up, by adding two simple properties:

```
prop_insert_empty :: Int -> Bool
prop_insert_empty i =
nodes (insertNode i BlogGraph.empty) == [i]
prop_insert_existing :: Int -> Bool
prop_insert_existing i =
nodes (insertNode i $ insertNode i BlogGraph.empty) == [i]
```

Properties are just simple functions returning true or false. They take arguments which are randomly provided later on by the QuickCheck library.

The first property says that adding a node to an empty graph will always produce a one-node graph. The second one, that adding a node to a graph that already has this node will always return the same unmodified graph.

We can successfully run these cases:

```
quickCheck prop_insert_empty
quickCheck prop_insert_existing
```

Now we should add a property stating that for all removals of a node from the graph, all references of this node in edge definitions for other nodes are always also being removed:

```
prop_remove_removes_edges :: Graph Int -> Bool
prop_remove_removes_edges (Graph m) =
List.null (nodes graph) || List.notElem node elemsAfter
where
graph = Graph m
node = List.head $ BlogGraph.nodes graph
elemsAfter = List.concat $ Map.elems mapAfter
mapAfter =
case removeNode node graph of
(Graph m) -> m
```

As I wrote before, these property testing functions are being run by the **QuickCheck** framework repeatedly with randomly generated values as arguments. Out of the box weâ€™re able to generate random examples for many simple typesâ€”â€‹including e.g Int. Thatâ€™s the reason we were able to just specify properties depending on random Int variablesâ€”â€‹without any additional code. But with the last example, weâ€™re asking QuickCheck to generate a set of random **graphs**. We need to tell it how to construct a random graph first:

```
arbitrarySizedIntGraph :: Int -> Gen (Graph Int)
arbitrarySizedIntGraph s = do
nodes <- vectorOf s $ choose (0, 32000)
edges <- edges nodes
let withNodes = List.foldr insertNode BlogGraph.empty nodes
return $ List.foldr addEdge withNodes edges
where
addEdge (parent, child) = insertEdge parent child
edges nodes = do
parents <- sublistOf nodes
let children = nodes List.\\ parents
return [ (parent, child) | parent <- parents, child <- children ]
instance Arbitrary (Graph Int) where
arbitrary = sized arbitrarySizedIntGraph
```

The above generator will be good enough for our case. It generates variable length graphs. A sublist of all nodes are made parents in edges and all parents are connected to the rest of non-parental nodes.

When we try to run the test we get:

```
Failed! Falsifiable (after 3 tests):
Graph (fromList [(10089,[]),(25695,[10089])])
```

QuickCheck shows that the property doesnâ€™t hold for the whole domainâ€”â€‹it failed after 3 examples. It also prints the example for which our property did not hold.

We can now reexamine the code for the removeNode function and fix it as per the propertyâ€™s specification:

```
removeNode :: (Ord a) => a -> Graph a -> Graph a
removeNode node (Graph m) =
Graph $ Map.map remNode $ Map.delete node m
where
remNode = List.delete node
```

Now running the test again we can see that it works.

### Another working example â€” the JavaScript land

As I stated before, this pattern became implemented for many different mainstream languagesâ€”â€‹this includes JavaScript. Iâ€™d like to show you the version of the above process for this language now. This might end up being helpful if youâ€™d like to use it in your project but don't know much Haskell yet.

As a start, letâ€™s make sure we have the following packages:

```
npm install jsverify
npm install lodash
```

We can now create a JS file with what might resemble the Haskell draft implementation:

```
var jsc = require("jsverify");
var _ = require("lodash");
var Graph = function() {
var self = this;
self._map = {};
self.insertNode = function(node) {
if(self._map[node] === undefined) {
self._map[node] = [];
}
return self;
};
self.removeNode = function(node) {
self._map.delete(node);
return self;
};
self.insertEdge = function(a, b) {
if(self._map[a] === undefined) {
self.insertNode(a);
}
self._map[a].push(b);
return self;
};
self.nodes = function() {
return _.keys(self._map);
};
}
Graph.empty = function() {
return new Graph();
}
```

To reproduce the first propertyâ€”â€‹for all integers, inserting one as a node to an empty graph results in a graph with one node:

```
var propInsertEmpty =
jsc.forall("nat", function(i) {
return _.isEqual(Graph.empty().insertNode(i).nodes(), [i]);
});
jsc.assert(propInsertEmpty);
```

The jsVerify DSL takes some time to get used to. It cannot take advantage of the type system as in the Haskell example so aspects like generation of random data based on types requires some documentation reading.

Running *jsc.assert* we might have expected to get a success, but this time weâ€™re getting:

```
Error: Failed after 1 tests and 5 shrinks. rngState: 001d40a68297fbce35; Counterexample: 0;
```

We can see that jsVerify has found 0 as a counterexample. Letâ€™s see whatâ€™s happening by running the code by hand passing 0 as a parameter:

```
console.log(Graph.empty().insertNode(0).nodes());
```

Result:

```
[ '0' ]
```

Aha! Itâ€™s quite easy to shoot your own foot in JavaScript. We can fix it really fast with the following:

```
self.nodes = function() {
return _.map(_.keys(self._map), function(i){ return parseInt(i, 10); });
};
```

Running the code again doesnâ€™t show any errors which means that all assertions were valid. What about the bug we saw in the Haskell version? Letâ€™s provide a property for that too:

```
var propRemoveRemovesEdges =
jsc.forall(graphG, function(g) {
if(g.nodes().length === 0){
return true;
}
else {
var numNodes = g.nodes().length;
var index = _.random(0, numNodes - 1);
var node = g.nodes()[index];
return !_.includes(_.flattenDeep(_.values(g.removeNode(node)._map)), node);
}
});
jsc.assert(propRemoveRemovesEdges);
```

We will still need to specify how to generate a random graph. We can use the notion of a Functor that's coming from the functional programming world and turn a random array into a random graph:

```
var graphG = jsc.array(jsc.nat).smap(
function(arr) {
var ins = function(g, i) {
return g.insertNode(i);
};
var graph = _.reduce(arr, ins, Graph.empty());
var numParents = Math.floor(arr.length / 2);
var parents = _.take(arr, numParents);
var children = _.difference(arr, parents);
var insEd = function(g, parent) {
var insF = function(r, c) {
return r.insertEdge(parent, c);
};
return _.reduce(children, insF, g);
};
return _.reduce(parents, insEd, graph);
},
function(graph) {
return graph.nodes();
}
);
```

When running the assert for that property weâ€™re getting an error:

```
Error: Failed after 1 tests and 1 shrinks. rngState: 085f6c82ea10439d7b; Counterexample: {"_map":{"21":[44]}}; Exception: self._map.delete is not a function
```

This isnâ€™t the issue we were expecting though. Still itâ€™s great to find a problem before showing the code to the client. We can iron it out with:

```
self.removeNode = function(node) {
delete self._map[node];
return self;
};
```

When running again, weâ€™re getting an error we were expecting:

```
Error: Failed after 8 tests and 2 shrinks. rngState: 8c97e25bc36f41da08; Counterexample: {"_map":{"2":[7]}};
```

The jsVerify has found a counterexample falsifying our property. Itâ€™s also worth noting that it took 8 tests to find this issue. We can notice that for the event of removing a node that is a child and doesnâ€™t have any children itself the property isnâ€™t true. Letâ€™s reexamine our removeNode function:

```
self.removeNode = function(node) {
delete self._map[node];
return _.mapValues(self._map, function(children) {
return _.without(children, node);
});
};
```

And now it works!

### Not only Haskell and JavaScript

The QuickCheck style testing is available for many different languages. The Wikipedia says:

Re-implementations of QuickCheck exist for C, C++, Chicken Scheme, Clojure, Common Lisp, D, Elm, Erlang, F# (and C#, VB.NET), Factor, Io, Java, JavaScript, Node.js, Objective-C, OCaml, Perl, Prolog, PHP, Python, R, Ruby, Rust, Scala, Scheme, Smalltalk, Standard ML and Swift.

You can find many useful links about the approach on Wikipedia. If youâ€™re into Haskell, a good place to start reading about the library is the Haskell Wiki as well as the documentation found on the Hackage.

The JavaScript counterpart can be found on GitHub. Itâ€™s important to note that jsVerify isnâ€™t the only JavaScript library implementing the QuickCheck approach.

functional-programming haskell javascript testing

## Comments