  
  [1X2 [33X[0;0YTutorial[133X[101X
  
  
  [1X2.1 [33X[0;0YUsing QuickCheck[133X[101X
  
  [33X[0;0YThe  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.[133X
  
  [33X[0;0YWhile  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.[133X
  
  [33X[0;0YAs  a first example, let's test if GAP's integers are commutative -- that is
  if [23Xa*b = b*a[123X. We first make a function which takes two arguments and returns
  [9Xtrue[109X  if  the  inputs are commutative. We test this using [10XQC_Check[110X. [10XQC_Check[110X
  has  two  mandatory  arguments,  firstly  the  types of the arguments of the
  functions we want to test, and secondly the function to test.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XtestFunc := function(a,b)[127X[104X
    [4X[25X>[125X [27X    return a*b = b*a;[127X[104X
    [4X[25X>[125X [27Xend;;[127X[104X
    [4X[25Xgap>[125X [27XQC_Check([IsInt, IsInt], testFunc);[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [33X[0;0YGreat! We can use the same function to test if other types are commutative:[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XQC_Check([IsPerm, IsPerm], testFunc);[127X[104X
    [4X[28XTest 60 of 500 failed:[128X[104X
    [4X[28X Input: [ (1,3), (1,3,2) ][128X[104X
    [4X[28X Output: false[128X[104X
    [4X[28Xfalse[128X[104X
  [4X[32X[104X
  
  [33X[0;0YTurns  out  multiplication  of permutations is not commutative! This isn't a
  surprise, of course...[133X
  
  [33X[0;0YIf  we  want  to  analyse  those  arguments,  we  can  access  them  through
  [10XQC_LastFailure[110X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XQC_LastFailure();[127X[104X
    [4X[28Xrec( args := [ (1,3), (1,3,2) ], func := function( a, b ) ... end )[128X[104X
  [4X[32X[104X
  
  [33X[0;0YRather  than  running  a single function and checking if it returns [9Xtrue[109X, 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:[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XslowIntersection := function(g,h)[127X[104X
    [4X[25X>[125X [27X     return Group(Filtered(g, p -> p in h));[127X[104X
    [4X[25X>[125X [27Xend;;[127X[104X
    [4X[25Xgap>[125X [27XQC_CheckEqual([IsPermGroup, IsPermGroup], Intersection, slowIntersection);[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [33X[0;0YCould  we be more efficient? How about if we just test which generators of [10Xg[110X
  are in [10Xh[110X?[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XgenIntersection := function(g,h)[127X[104X
    [4X[25X>[125X [27X   return Group(Filtered(GeneratorsOfGroup(g), p -> p in h), ());[127X[104X
    [4X[25X>[125X [27Xend;;[127X[104X
    [4X[25Xgap>[125X [27XQC_CheckEqual([IsPermGroup, IsPermGroup], Intersection, genIntersection);[127X[104X
    [4X[28XTest 97 of 500 failed:[128X[104X
    [4X[28X Input: [ Group( [ (1,2,3), (2,3,4) ] ), Group( [ (1,4)(2,3), (1,2)(3,4) ] ) ][128X[104X
    [4X[28X Output: Return values differ: Group( [ (1,4)(2,3), (1,2)(3,4) ] ) and Group( () )[128X[104X
    [4X[28Xfalse[128X[104X
  [4X[32X[104X
  
  [33X[0;0YNo,  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).[133X
  
  [33X[0;0YIn some cases, the inputs given might not make sense for the function we are
  testing. For example, imagine we want to test if [23Xb*(a/b) = a[123X. This statement
  isn't  valid for [23Xb=0[123X. We can skip invalid values by return the special value
  [10XQC_Skip[110X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XcheckDiv := function(a,b)[127X[104X
    [4X[25X>[125X [27X    if b = 0 then return QC_Skip; fi;[127X[104X
    [4X[25X>[125X [27X    return b*(a/b);[127X[104X
    [4X[25X>[125X [27Xend;;[127X[104X
    [4X[25Xgap>[125X [27XjustA := function(a,b)[127X[104X
    [4X[25X>[125X [27Xreturn a;[127X[104X
    [4X[25X>[125X [27Xend;;[127X[104X
    [4X[25Xgap>[125X [27XQC_CheckEqual([IsInt, IsInt], checkDiv, justA);[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [33X[0;0YIn  some  cases we might want to return an explanation of why a test failed.
  Rather  than returning [9Xfalse[109X from [10XQC_Equal[110X, you can instead return a string.
  Returning a string is treated as a failure, and the string is printed out to
  the user.[133X
  
  
  [1X2.2 [33X[0;0YValid argument types for QuickCheck[133X[101X
  
  [33X[0;0YThe  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.[133X
  
  [33X[0;0YThe currently allowed argument types for QuickCheck are:[133X
  
  [30X    [33X[0;6YIsInt : An integer[133X
  
  [30X    [33X[0;6YIsPosInt : A positive integer[133X
  
  [30X    [33X[0;6YIsNegInt : A negative integer[133X
  
  [30X    [33X[0;6YIsRat : Rational number[133X
  
  [30X    [33X[0;6YIsPosRat : Positive rational number[133X
  
  [30X    [33X[0;6YIsNegRat : Negative rational number[133X
  
  [30X    [33X[0;6YIsPerm : A permutation[133X
  
  [30X    [33X[0;6YIsTransformation : A transformation[133X
  
  [30X    [33X[0;6YIsPartialPerm : A partial permutation[133X
  
  [30X    [33X[0;6YIsPermGroup : A permutation group[133X
  
  [30X    [33X[0;6YIsDigraph : A digraph (requires the Digraph package)[133X
  
  [33X[0;0YThere is also a generic function to take a random member from a collection:[133X
  
  [30X    [33X[0;6YQC_ElementOf(x) : Return a random member of the list x[133X
  
  [33X[0;0YThis  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.[133X
  
  [33X[0;0YThere are also ways of defining lists or sets of arguments, recursively:[133X
  
  [30X    [33X[0;6YQC_ListOf(x) : A (possibly empty) list of items of type x[133X
  
  [30X    [33X[0;6YQC_SetOf(x) : A (possibly empty) set of items of type x[133X
  
  [30X    [33X[0;6YQC_PairOf(x) : A pair of items of type x[133X
  
  [30X    [33X[0;6YQC_FixedLengthListOf(x, len) : A list of length len of items of type x[133X
  
  [33X[0;0YIn  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.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xfunc := function(x)[127X[104X
    [4X[25X>[125X [27X    local a, s;[127X[104X
    [4X[25X>[125X [27X    if x < 2 then[127X[104X
    [4X[25X>[125X [27X        return QC_Skip;[127X[104X
    [4X[25X>[125X [27X    fi;[127X[104X
    [4X[25X>[125X [27X    a := AlternatingGroup(x);[127X[104X
    [4X[25X>[125X [27X    s := SymmetricGroup(x);[127X[104X
    [4X[25X>[125X [27X    if not IsSubgroup(s, a) then return "Not a subgroup"; fi;[127X[104X
    [4X[25X>[125X [27X    if s = a then return "Equal!"; fi;[127X[104X
    [4X[25X>[125X [27X    return true;[127X[104X
    [4X[25X>[125X [27Xend;;[127X[104X
    [4X[25Xgap>[125X [27XQC_Check([IsInt], func);[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  
  [1X2.3 [33X[0;0YAdding new types to QuickCheck[133X[101X
  
  [33X[0;0YQuickCheck  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.[133X
  
  [33X[0;0YAll  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).[133X
  
  [33X[0;0YFor example, here are generators for a positive integer and a permutation.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XmakePosInt := function(rs, limit)[127X[104X
    [4X[25X>[125X [27X   return Random(rs, [1..limit]);[127X[104X
    [4X[25X>[125X [27Xend;;[127X[104X
    [4X[25Xgap>[125X [27XmakePerm := function(rs, limit)[127X[104X
    [4X[25X>[125X [27X   return Random(rs, SymmetricGroup(limit));[127X[104X
    [4X[25X>[125X [27Xend;;[127X[104X
  [4X[32X[104X
  
  [33X[0;0YThese functions can be used immediately in QC_Check:[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XQC_Check([makePosInt, makePerm, makePerm], {r,p1,p2} -> (r^p1)^p2 = r^(p1*p2));[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [33X[0;0YThese functions can also be registered with the filter which they implement,
  using QC_RegisterFilterGen:[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xgap> QC_RegisterFilterGen(IsPosInt, makePosInt);[127X[104X
  [4X[32X[104X
  
