4. Generating test cases

The QuickCheck tool for Haskell uses type classes so that arbitrary values of various types may be generated behind the scenes. In SML, we need to be more explicit, but the same holds true in Haskell if we don't want the default generator (positive integers only, for example). The Gen module holds a wide range of tools for creating random values of various structured types and, yes, even functions!

We begin with the raw random number generator. The new function generates a seed based on the current time. The range function produces random integers between those in the given pair, inclusive. The generator is applicative, in the sense that it returns the new state of the random number generator.

type rand
val new : unit → rand
val range : int * int → rand → int * rand

The generator for a type takes a random number stream and produces a value of that type, along with the new state of the stream.

type 'a gen = rand → 'a * rand
type ('a, 'b) co = 'a → 'b gen → 'b gen

4.1 Random-value combinators

lift v is a generator that always produces the given value. select picks uniform randomly from the values in the vector, while choose picks uniform randomly from the generators in the vector, to produce a value. For example:

   Gen.choose #[Gen.lift 42, Gen.Int.int]

will return the number 42 with 50% probability, and a random integer otherwise (but recall that Gen.Int.int is biased toward zero and the extrema). The primed version pairs each generator with an integer weight to bias the choice (making it non-uniform).

val lift : 'a → 'a gen
val select : 'a vector → 'a gen
val choose : 'a gen vector → 'a gen
val choose' : (int * 'a gen) vector → 'a gen

The functions ending in L are the same, except they operate on lists instead of vectors.

val selectL : 'a list → 'a gen
val chooseL : 'a gen list → 'a gen
val chooseL' : (int * 'a gen) list → 'a gen

Here are some basic map and filtering functions over generators.

val filter : ('a → bool) → 'a gen → 'a gen
val zip : ('a gen * 'b gen) → ('a * 'b) gen
val zip3 : ('a gen * 'b gen * 'c gen) →
           ('a * 'b * 'c) gen
val zip4 : ('a gen * 'b gen * 'c gen * 'd gen) →
           ('a * 'b * 'c * 'd) gen
val map : ('a → 'b) → 'a gen → 'b gen
val map2 : ('a * 'b → 'c) → ('a gen * 'b gen) →
           'c gen
val map3 : ('a * 'b * 'c → 'd) →
           ('a gen * 'b gen * 'c gen) → 'd gen
val map4 : ('a * 'b * 'c * 'd → 'e) →
           ('a gen * 'b gen * 'c gen * 'd gen) →
           'e gen

flip is just like flipping a fair coin. With flip', the coin is biased by the pair of integers given: flip' (3,5) will choose true three-eights of the time, and false five-eights.

val flip : bool gen
val flip' : int * int → bool gen

These produce lists or optional values by consulting the boolean generator about when to produce the nil list or NONE.

val list : bool gen → 'a gen → 'a list gen
val option : bool gen → 'a gen → 'a option gen

The following function produces any kind of sequential collection type, you just provide the tabulate function as the first parameter. The integer generator then determines how many elements the collection will have.

val vector : (int * (int → 'a) → 'b) →
             int gen * 'a gen → 'b gen

Here is an example, showing how we can generate strings with vector:

    Gen.vector CharVector.tabulate
               (Gen.range(6,10), Gen.select #[#"a", #"b", #"c"])

Here is a sample of the strings it generated in one test:

 › "abbacccbbb" : CharVector.vector
 › "bccbaabacb" : CharVector.vector
 › "aacbbbaba" : CharVector.vector
 › "aabbaca" : CharVector.vector
 › "acaacbb" : CharVector.vector
 › "cbbbccab" : CharVector.vector
 › "bbcaccca" : CharVector.vector

val variant : (int,'b) co
val arrow : ('a, 'b) co * 'b gen → ('a → 'b) gen
val cobool : (bool, 'b) co
val colist : ('a, 'b) co → ('a list, 'b) co
val coopt : ('a, 'b) co → ('a option, 'b) co

These turn generators into a stream of values. You can limit them by a given integer, or just use the default maximum number of values from the Settings.

type stream
val start : rand → stream
val limit' : int → 'a gen → ('a,stream) reader
val limit : 'a gen → ('a,stream) reader

4.2 Basis types

In addition to the general combinators, practically all of the SML Basis types have associated generators in sub-structures. The following generators can be instantiated for whatever character and string types your implementation provides, such as Gen.WideText.charByType. For the default character and string types, however, these are found in the top-level of the Gen structure.

type char                                       
type string                                     
type substring                                  
val char : char gen                             
val charRange : char * char → char gen         
val charFrom : string → char gen               
val charByType : (char → bool) → char gen     
val string : (int gen * char gen) → string gen 
val substring : string gen → substring gen     
val cochar : (char, 'b) co                      
val costring : (string, 'b) co                  
val cosubstring : (substring, 'b) co            

The functions in Gen.Int (and Gen.Int32, Gen.IntInf, etc.) generate integers in various ranges. They can easily be instantiated for whatever integer types your implementation provides. They are biased so that zero, maxInt, and minInt (if they exist) are generated much more often than other integers.

eqtype int                              
val int : int gen                       
val pos : int gen                       
val neg : int gen                       
val nonpos : int gen                    
val nonneg : int gen                    
val coint : (int, 'b) co                

The functions generating unsigned words are in structures such as Gen.Word, Gen.Word8, Gen,Word32, etc., depending on your implementation.

eqtype word                             
val word : word gen                     
val coword : (word, 'b) co              

These are in Gen.Real structure. Currently, real numbers are generated from strings of (decimal) digits, rather than from bits. So some valid reals will never be generated. This may not be sufficient for testing numerical code.

type real                               
val real : real gen                     
val frac : real gen                     
val pos : real gen                      
val neg : real gen                      
val nonpos : real gen                   
val nonneg : real gen                   
val finite : real gen                   

Generate dates and times from Gen.DateTime. The dateFromYear function uses the given generator to produce the year, but then it comes up with a month, day, hour, minute, and second itself. A few days are more likely than others because we do not bother to generate the correct number of days based on the month. This makes May 1st more likely than May 2nd, because it could also have been generated as April 31st. (The Basis Date.date normalizes the dates though, so you will never see April 31st.)

val weekday : Date.weekday gen              
val month : Date.month gen                  
val dateFromYear : int gen → Date.date gen 
val time : Time.time gen                    

4.3 Recursive types

As pointed out in the QuickCheck paper, one needs to be careful when generating tree-structured data, due to the strong possibility of non-termination. To avoid this problem, make the generator a function of a decreasing integer parameter. When that parameter reaches zero, the only choice is to return a leaf.

datatype tree = Node of tree * tree | Leaf of int
fun gentree 0 = Gen.map Leaf Gen.Int.int
  | gentree n = 
    Gen.choose' #[(1,Gen.map Leaf Gen.Int.int),
                  (4,Gen.map Node (Gen.zip(gentree(n div 2),
                                           gentree(n div 2))))]

This document was generated by Chris League on April, 14 2008 using texi2html 1.78.