GAP (quickcheck) - Chapter 2: Tutorial

The idea behind QuickCheck is to write functions which should always return true, or two functions which should always return the same value. We then feed those functions many different inputs, and see if that behaviour holds.

While this cannot detect all bugs, it can catch many issues. In particular, the code can catch issues with small inputs, or edge conditions. This tutorial will walk through the major functionality of the QuickCheck package through examples.

As a first example, let's test if GAP's integers are commutative -- that is if \(a*b = b*a\). We first make a function which takes two arguments and returns true if the inputs are commutative. We test this using QC_Check. QC_Check has two mandatory arguments, firstly the types of the arguments of the functions we want to test, and secondly the function to test.

gap> testFunc := function(a,b)
>     return a*b = b*a;
> end;;
gap> QC_Check([IsInt, IsInt], testFunc);
true

gap> QC_Check([IsPerm, IsPerm], testFunc);
Test 60 of 500 failed:
 Input: [ (1,3), (1,3,2) ]
 Output: false
false

Turns out multiplication of permutations is not commutative! This isn't a surprise, of course...

If we want to analyse those arguments, we can access them through QC_LastFailure.

gap> QC_LastFailure();
rec( args := [ (1,3), (1,3,2) ], func := function( a, b ) ... end )

Rather than running a single function and checking if it returns true, we can run two functions and test if they produce the same output. For example, let's compare two methods of intersecting groups -- GAP's optimised implementation and a "brute force" method which just finds the elements in both groups:

gap> slowIntersection := function(g,h)
>      return Group(Filtered(g, p -> p in h));
> end;;
gap> QC_CheckEqual([IsPermGroup, IsPermGroup], Intersection, slowIntersection);
true

Could we be more efficient? How about if we just test which generators of g are in h?

gap> genIntersection := function(g,h)
>    return Group(Filtered(GeneratorsOfGroup(g), p -> p in h), ());
> end;;
gap> QC_CheckEqual([IsPermGroup, IsPermGroup], Intersection, genIntersection);
Test 97 of 500 failed:
 Input: [ Group( [ (1,2,3), (2,3,4) ] ), Group( [ (1,4)(2,3), (1,2)(3,4) ] ) ]
 Output: Return values differ: Group( [ (1,4)(2,3), (1,2)(3,4) ] ) and Group( () )
false

No, unfortunately not! You may be surprised it took until test 97 to find this bug (you may also get different results). This is because QuickCheck starts by making many very small tests, which are fast to execute (finding this bad example takes less than a tenth of a second).

In some cases, the inputs given might not make sense for the function we are testing. For example, imagine we want to test if \(b*(a/b) = a\). This statement isn't valid for \(b=0\). We can skip invalid values by return the special value QC_Skip.

gap> checkDiv := function(a,b)
>     if b = 0 then return QC_Skip; fi;
>     return b*(a/b);
> end;;
gap> justA := function(a,b)
> return a;
> end;;
gap> QC_CheckEqual([IsInt, IsInt], checkDiv, justA);
true

In some cases we might want to return an explanation of why a test failed. Rather than returning false from QC_Equal, you can instead return a string. Returning a string is treated as a failure, and the string is printed out to the user.

2.2 Valid argument types for QuickCheck

The set of elements which can be given to QuickCheck tests is listed below. The list is always growing, and please submit an issue on GitHub if you have any specific requests.

This can be used to take a random element of a small list of options ( like [1,2,3] ), or a random element of a collection which is not explicitly listed above (like AlternatingGroup(7) ). The disadvantage of using QC_ElementOf is that it does not handle 'limit' well, but will instead take a random element from x.

In some cases this may not be sufficient, for example an algorithm may require an integer which is not prime. The function can return the special value QC_Skip, which skips this test. If too many tests are skipped, the tester will eventually stop generating new arguments. For example, if we want to check the AlternatingGroup(n) is a strict subgroup of the SymmetricGroup(n) for n > 2.

gap> func := function(x)
>     local a, s;
>     if x < 2 then
>         return QC_Skip;
>     fi;
>     a := AlternatingGroup(x);
>     s := SymmetricGroup(x);
>     if not IsSubgroup(s, a) then return "Not a subgroup"; fi;
>     if s = a then return "Equal!"; fi;
>     return true;
> end;;
gap> QC_Check([IsInt], func);
true

2.3 Adding new types to QuickCheck

QuickCheck takes a list of the arguments for the function to be tested, so it needs to know how to generate values of any given type. There is a built-in list of types and new ones can be easily added.

All value generators are a function which takes two arguments -- the first is a RandomSource, and the second is a positive integer representing the maximum "size" of the value created (each type can choose how to interpret this).

gap> makePosInt := function(rs, limit)
>    return Random(rs, [1..limit]);
> end;;
gap> makePerm := function(rs, limit)
>    return Random(rs, SymmetricGroup(limit));
> end;;

gap> QC_Check([makePosInt, makePerm, makePerm], {r,p1,p2} -> (r^p1)^p2 = r^(p1*p2));
true

These functions can also be registered with the filter which they implement, using QC_RegisterFilterGen:

gap> gap> QC_RegisterFilterGen(IsPosInt, makePosInt);

2 Tutorial

2.1 Using QuickCheck

2.2 Valid argument types for QuickCheck

2.3 Adding new types to QuickCheck