Write you some QuickCheck - Shrinking numbers

Mar 17, 2016

This post is part of a series of posts on implementing a minimal version of QuickCheck from scratch. The source code is available on GitHub.

In this post I’ll be porting the function from QuickCheck that shrinks numbers.

Prelude

When reporting back the actual input that caused a function to fail, QuickCheck first cleans the noise by reporting back the counterexample. — This is called shrinking. See how it works here.

All the shrinking functions have the same signature:

shrink :: a -> [a]

So in F# it can look like this:

'a -> 'a seq

Shrinking numbers

QuickCheck shrinks towards smaller numeric values with the following generic function:

-- | Shrink an integral number.
shrinkIntegral :: Integral a => a -> [a]
shrinkIntegral x =
  nub
  $
  [ -x | x < 0, -x > x ]
  ++
  [ x' | x' <- takeWhile (<< x) (0:[ x - i | i <- tail (iterate (`quot` 2) x) ]) ]
 where
   -- a << b is "morally" abs a < abs b, but taking care of overflow.
   a << b = case (a >= 0, b >= 0) of
            (True , True ) -> a < b
            (False, False) -> a > b
            (True , False) -> a + b < 0
            (False, True ) -> a + b > 0

(View on Hackage)

Let’s try this one out first:

λ> :t shrinkIntegral
shrinkIntegral :: Integral a => a -> [a]

λ> shrinkIntegral 1
[0]

λ> shrinkIntegral (-1)
[1,0]

λ> shrinkIntegral (-2)
[2,0,-1]

λ> shrinkIntegral (-3)
[3,0,-2]

λ> shrinkIntegral (-4)
[4,0,-2,-3]

λ> shrinkIntegral (-2)
[2,0,-1]

λ> shrinkIntegral 2
[0,1]

λ> shrinkIntegral 3
[0,2]

λ> shrinkIntegral 4
[0,2,3]

λ> shrinkIntegral (-700)
[700,0,-350,-525,-613,-657,-679,-690,-695,-698,-699]

λ> shrinkIntegral 700
[0,350,525,613,657,679,690,695,698,699]

λ> shrinkIntegral 7
[0,4,6]

λ> shrinkIntegral (-7)
[7,0,-4,-6]

Here’s the equivalent one in F#:

(* This has the type n:int -> seq<int> but we'll
   come and fix this later on. *)

let shrinkNumber n =
    n
    |> Seq.unfold (fun s -> Some(n - s, s / 2))
    |> Seq.tail
    |> Seq.append [ 0 ]
    |> Seq.takeWhile (fun el -> abs n > abs el)
    |> Seq.append (if n < 0 then Seq.singleton -n
                   else Seq.empty)
    |> Seq.distinct

I’m going to try this one with the same values as the ones used in Haskell:

> val shrinkNumber : n:int -> seq<int>

> shrinkNumber 1;;
val it : seq<int> = seq [0]

> shrinkNumber (-1);;
val it : seq<int> = seq [1; 0]

> shrinkNumber (-2);;
val it : seq<int> = seq [2; 0; -1]

> shrinkNumber (-3);;
val it : seq<int> = seq [3; 0; -2]

> shrinkNumber (-4);;
val it : seq<int> = seq [4; 0; -2; -3]

> shrinkNumber (-2);;
val it : seq<int> = seq [2; 0; -1]

> shrinkNumber 2;;
val it : seq<int> = seq [0; 1]

> shrinkNumber 3;;
val it : seq<int> = seq [0; 2]

> shrinkNumber 4;;
val it : seq<int> = seq [0; 2; 3]

> shrinkNumber (-700);;
val it : seq<int> = seq [700; 0; -350; -525; ...]

> shrinkNumber 700;;
val it : seq<int> = seq [0; 350; 525; 613; ...]

> shrinkNumber 7;;
val it : seq<int> = seq [0; 4; 6]

> shrinkNumber (-7);;
val it : seq<int> = seq [7; 0; -4; -6]

Shrinking not only integers, but floats, decimals, and so on

Here is again the shrinkNumber number function that was ported from Haskell:

(* This has the type n:int -> seq<int> but we'll
   come and fix this later on. *)

let shrinkNumber n =
    n
    |> Seq.unfold (fun s -> Some(n - s, s / 2))
    |> Seq.tail
    |> Seq.append [ 0 ]
    |> Seq.takeWhile (fun el -> abs n > abs el)
    |> Seq.append (if n < 0 then Seq.singleton -n
                   else Seq.empty)
    |> Seq.distinct

Because of 2, and 0, the F# compiler infers that this function works with integers.

Fortunately, there’s a way to make this polymorphic with compile-time generics:

Here’s the end result:

open FSharp.Core.LanguagePrimitives

let inline shrinkNumber n =
    let genericTwo = GenericOne + GenericOne
    n
    |> Seq.unfold (fun s -> Some(n - s, s / genericTwo))
    |> Seq.tail
    |> Seq.append [ GenericZero ]
    |> Seq.takeWhile (fun el -> abs n > abs el)
    |> Seq.append (if n < GenericZero then Seq.singleton -n
                   else Seq.empty)
    |> Seq.distinct

And now the type has become generic:

// Formatted, in order to be easier to read:
val inline shrinkNumber :
  n: ^a -> seq< ^a>
    when  ^a         : (static member get_Zero :           ->  ^a) and
          ^a         : (static member ( - )    :  ^a *  ^a ->  ^a) and
        ( ^a or  ^b) : (static member ( / )    :  ^a *  ^b ->  ^a) and
          ^a         : (static member Abs      :  ^a       ->  ^a) and
          ^a         : (static member ( ~- )   :  ^a       ->  ^a) and 
          ^a         : comparison                                  and
          ^c         : (static member get_One  :           ->  ^c) and
        ( ^c or  ^d) : (static member ( + )    :  ^c *  ^d ->  ^b) and
          ^d         : (static member get_One  :           ->  ^d)

Let’s try this one out:

> shrinkNumber 3.14;;
val it : seq<float> = seq [0.0; 1.57; 2.355; 2.7475; ...]

> shrinkNumber 4.0f;;
val it : seq<float32> = seq [0.0f; 2.0f; 3.0f; 3.5f; ...]

>shrinkNumber (-700.15M);;
val it : seq<decimal> = seq [700.15M; 0M; -350.075M; -525.1125M; ...]

>shrinkNumber 900s;;
val it : seq<int16> = seq [0s; 450s; 675s; 788s; ...]

Write you some QuickCheck - Generating random floats

Feb 25, 2016

This post is part of a series of posts on implementing a minimal version of QuickCheck from scratch. The source code is available on GitHub.

In this post I’ll be generating random 32-bit floating-point numbers.

In Haskell’s QuickCheck 1.2.0.1 (but also in version 2.8), random 32-bit floating-point numbers are generated as shown below:

instance Arbitrary Float where
  arbitrary     = liftM3 fraction arbitrary arbitrary arbitrary
  coarbitrary x = ...

Two things are important in the above code:

Here’s the original fraction function in Haskell:

fraction :: Fractional a => Integer -> Integer -> Integer -> a
fraction a b c = fromInteger a + (fromInteger b / (abs (fromInteger c) + 1))

It takes 3 integers and returns an a which is a fractional (a numeric type that supports the ordinary division operator /).

Here are some sample values generated by fraction:

λ> fraction 1 2 3
1.5

λ> fraction 2 2 2
2.6666666666666665

λ> fraction 7 8 9
7.8

Now, what I want to do is to call the fraction function passing random integers, something like this (pseudo-code):

-- Pseudo-code
fraction Gen<int> Gen<int> Gen<int>

Here’s where liftM3 comes into play:

liftM3 :: Monad m => (a1 -> a2 -> a3 -> r) -> m a1 -> m a2 -> m a3 -> m r
  • a1, a2, and a3, correspond to the arguments of fraction
  • r corresponds to the return value of fraction
  • m a1, m a2, m a3 will be 3 generators for integers
  • m r the return value (the random float).

So, in F#, a generator for floats can be written as:

(* Generates a random real number. *)
let float =
    let fraction a b c = float a + float b / (abs (float c) + 1.0)
    Gen.lift3 fraction Gen.int Gen.int Gen.int

And the lift3 function in F# can be written in terms of apply and return:

(* Unpacks a function wrapped inside a generator, applying it into a new
   generator. *)
let apply f m =
    Gen.bind f (fun f' ->
        Gen.bind m (fun m' ->
            Gen.init (f' m')))

(* Returns a new generator obtained by applying a function to three existing
   generators. *)
let lift3 f m1 m2 m3 = Gen.apply (Gen.apply (Gen.apply (Gen.init f) m1) m2) m3

Finally, here are some sample floats:

> Gen.float |> Gen.generate;;
val it : float = 3.466666667

> Gen.float |> Gen.generate;;
val it : float = 9.352941176

> Gen.float |> Gen.generate;;
val it : float = 18.14285714

> Gen.float |> Gen.generate;;
val it : float = 9.4

> Gen.float |> Gen.generate;;
val it : float = -16.8

> Gen.float |> Gen.generate;;
val it : float = -1.5

> Gen.float |> Gen.generate;;
val it : float = -1.25

> Gen.float |> Gen.generate;;
val it : float = -16.94117647

Write you some QuickCheck - Generating random strings

Feb 22, 2016

This post is part of a series of posts on implementing a minimal version of QuickCheck from scratch. The source code is available on GitHub.

In this post I’ll be generating random strings from randomly selected characters. I will also describe a way of customizing the whole creation process.

The following generators are required for this:

Given the above, a generator for strings can be written as:

/// <summary>
/// Generates a random string.
/// </summary>
let string =
    Gen.char
    |> Gen.list
    |> Gen.map (List.toArray >> System.String)

Here are some sample strings:

> Gen.string |> Gen.generate;;
val it : String = "lof5ºÛ"

> Gen.string |> Gen.generate;;
val it : String = "'fv*™ì UÇ"

> Gen.string |> Gen.generate;;
val it : String = "Ðê

Customizations

Generarting upper-case strings

let upperCase = Gen.choose (65,  90) |> Gen.map Operators.char

val upperCase : Gen<char>


let customString g =
    g
    |> Gen.list
    |> Gen.map (List.toArray >> System.String)

val customString : g:Gen<char> -> Gen<String>

Sample output:

> upperCase |> customString |> Gen.generate;;
val it : String = "DGVHAYFAWIHQBOD"

> upperCase |> customString |> Gen.generate;;
val it : String = "HEDDZYBATTYL"

> upperCase |> customString |> Gen.generate;;
val it : String = "XLYJSMEYYZXN"

Generating lower-case strings

let lowerCase = Gen.choose (97, 122) |> Gen.map Operators.char

val lowerCase : Gen<char>


let customString g =
    g
    |> Gen.list
    |> Gen.map (List.toArray >> System.String)

val customString : g:Gen<char> -> Gen<String>

Sample output:

> lowerCase |> customString |> Gen.generate;;
val it : String = "qsnj"

> lowerCase |> customString |> Gen.generate;;
val it : String = "cltfvqckqxeirmuqvjn"

> lowerCase |> customString |> Gen.generate;;
val it : String = "wzwfojfjlrjglu"

Write you some QuickCheck - Generating random lists

Feb 19, 2016

This post is part of a series of posts on implementing a minimal version of QuickCheck from scratch. The source code is available on GitHub.

In this post I’ll be generating lists of random length.

The maximum length of the list will depend on the runtime size parameter. See this previous post that explains how size works.

Two generators are required for this:

  • a generator that picks numbers with absolute value bounded by the size (that’s Gen’s choose)
  • a generator that creates lists of a given length (that’s Gen’s vector). The length will be the number obtained by the above generator

Gen’s choose is already available. Porting Gen’s vector, which essentially means porting replicateM

/// <summary>
/// Takes a list of generators of type 'a, evaluates each one of them, and
/// collect the result, into a new generator of type 'a list.
/// </summary>
/// <param name="l">The list of generators of type 'a.</param>
/// <remarks>
/// This is written so that the F# compiler will use a tail call, as shown in
/// the resulting excerpt of generated IL:
///   IL_0000: nop
///   IL_0001: call class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<cl...
///   IL_0006: ldarg.0
///   IL_0007: call class [FSharp.Core]Microsoft.FSharp.Collections.FSharpLi...
///   IL_000c: call class LightCheck.Gen/Gen`1<!!0> LightCheck.Gen::'init'<c...
///   IL_0011: tail.
///   IL_0013: call !!1 [FSharp.Core]Microsoft.FSharp.Collections.ListModule...
///   IL_0018: ret
/// See also:
///   http://stackoverflow.com/a/6615060/467754,
///   http://stackoverflow.com/a/35132220/467754
/// </remarks>
let sequence l =
    let k m m' =
        Gen.bind m (fun x ->
            Gen.bind m' (fun xs ->
                Gen.init (x :: xs)))
    Gen.init [] |> List.foldBack k l

/// <summary>
/// Generates a list of the given length.
/// </summary>
/// <param name="n">The number of elements to replicate.</param>
/// <param name="g">The generator to replicate.</param>
let vector n g =
    Gen.sequence [ for _ in [ 1..n ] -> g ]

Creating a custom gen computation expression

Most, if not all, monadic computations on the Gen<'a> type can be written in terms of Gen.bind and Gen.init (return).

A computation expression just makes this a whole lot easier:

[<AutoOpen>]
module Builder =
    type GenBuilder() =
        member this.Bind       (g1, g2) = Gen.bind g1 g2
        member this.ReturnFrom (f)      = f

    let gen = GenBuilder()

Given the above, a generator for lists of random length can be written as:

/// <summary>
/// Generates a list of random length. The maximum length of the list depends
/// on the size parameter.
/// </summary>
/// <param name="g">The generator from which to create a list from.</param>
let list g = Gen.sized (fun s -> gen { let! n = Gen.choose (0, s)
                                       return! Gen.vector n g })

Finally, here are some sample lists of type int and char, but it can be any generator of type 'a really

> Gen.int |> Gen.list |> Gen.generate;;
val it : int list = [-10; 1; 0; -14; 11; -2; -7]

> Gen.int |> Gen.resize 1337 |> Gen.list |> Gen.generate;;
val it : int list =
  [-1027; 739; -571; 475; 979; 144; -1239; -1282; -1012; -932; -952]

> Gen.char |> Gen.list |> Gen.generate
val it : char list = [':'; 'e'; '«']

> Gen.char |> Gen.list |> Gen.generate
val it : char list =
  ['H'; 'µ'; 'Ø'; '°'; 'ò'; 'k'; '<'; 't'; 't'; 'È'; '\\'; '\151'; 'Æ'; '¥';
   '/'; '\137'; 'é'; '\145'; '/'; 'Ì'; 'ï'; '\153'; '·'; '7']

Write you some QuickCheck - Generating random long integers

Feb 17, 2016

This post is part of a series of posts on implementing a minimal version of QuickCheck from scratch. The source code is available on GitHub.

Two generators are required for this, which have been ported already on previous posts:

The long integers are going to be generated by the integer returned by the first generator and then multiplied by a 16-bit1 integer’s largest possible value.

Given the above, a long integer generator can be written as:

/// <summary>
/// Generates a 64-bit integer (with absolute value bounded by the generation
/// size multiplied by 16-bit integer's largest possible value).
/// </summary>
let int64 = Gen.int |> Gen.map (fun n -> Operators.int64 (n * 32767))

val int64 : Gen<int64>

Finally, here are some sample long integers:

> Gen.int64 |> Gen.generate;;
val it : int64 = -294903L

> Gen.int64 |> Gen.generate;;
val it : int64 = -32767L

> Gen.int64 |> Gen.generate;;
val it : int64 = 163835L

> Gen.int64 |> Gen.generate;;
val it : int64 = 131068L

> Gen.int64 |> Gen.generate;;
val it : int64 = -65534L

> Gen.int64 |> Gen.generate;;
val it : int64 = 229369L

> Gen.int64 |> Gen.generate;;
val it : int64 = 393204L

  1. To be more precise, I should use a 32-bit integer’s largest possible value, but then the generated numbers become very big and less interesting.

subscribe via RSS