Write you some QuickCheck - Generating random integers

Feb 13, 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 the previous post I’ve generated random booleans. In this post, I’ll be generating random 32-bit signed integers.

Recall that the Gen<'a> type is ported already in this previous post as:

/// <summary>
/// A generator for values of type 'a.
/// </summary>
type Gen<'a> =
    private
    | Gen of (int -> StdGen -> 'a)

This means we can write functions that handle state (—monadster!) combining:

  • a size measure for data structures, i.e. list length, numbers, i.e. absolute bounds
  • a pseudo-random generation seed — more about that later on

So, to generate numbers, we need:

  • a generator that picks numbers with absolute value bounded by the size
  • a generator that gives us the current size at runtime

Porting Gen’s sized

/// <summary>
/// Used to construct generators that depend on the size parameter.
/// </summary>
/// <param name="g">A generator for values of type 'a.</param>
let sized g =
    Gen(fun n r ->
        let (Gen m) = g n
        m n r)

Given the above, a 32-bit signed integer generator can be written as:

let int = Gen.sized (fun n -> Gen.choose (-n, n))

val int : Gen<int>

Here are some sample integers:

> Gen.int |> Gen.generate;;
val it : int = 0

> Gen.int |> Gen.generate;;
val it : int = -18

> Gen.int |> Gen.generate;;
val it : int = 0

> Gen.int |> Gen.generate;;
val it : int = 6

> Gen.int |> Gen.generate;;
val it : int = -6

> Gen.int |> Gen.generate;;
val it : int = 1

> Gen.int |> Gen.generate;;
val it : int = -2

> Gen.int |> Gen.generate;;
val it : int = 5

> Gen.int |> Gen.generate;;
val it : int = -4

> Gen.int |> Gen.generate;;
val it : int = -18

> Gen.int |> Gen.generate;;
val it : int = 5

> Gen.int |> Gen.generate;;
val it : int = -17

> Gen.int |> Gen.generate;;
val it : int = -7

> Gen.int |> Gen.generate;;
val it : int = -3

> Gen.int |> Gen.generate;;
val it : int = 1

> Gen.int |> Gen.generate;;
val it : int = 12

> Gen.int |> Gen.generate;;
val it : int = 5

> Gen.int |> Gen.generate;;
val it : int = 6

> Gen.int |> Gen.generate;;
val it : int = -8

> Gen.int |> Gen.generate;;
val it : int = -10

But there’s a pattern here (can you tell?); all the generated integers are in the range [-30, 30] — that’s because generate sets the size for the generators to be up to 301.

Generating numbers in range [-999, 999]

I can run the integer generator again, but this time I’ll override the runtime size.

This prompts me to port Gen’s resize

/// <summary>
/// Overrides the size parameter. Returns a generator which uses the given size
/// instead of the runtime-size parameter.
/// </summary>
/// <param name="n">The size that's going to override the runtime-size.</param>
let resize n (Gen m) = Gen(fun _ r -> m n r)

Finally, here are some sample integers in the range [-999, 999]:

> Gen.int |> Gen.resize 999 |> Gen.generate;;
val it : int = -808

> Gen.int |> Gen.resize 999 |> Gen.generate;;
val it : int = 797

> Gen.int |> Gen.resize 999 |> Gen.generate;;
val it : int = -676

> Gen.int |> Gen.resize 999 |> Gen.generate;;
val it : int = 3

> Gen.int |> Gen.resize 999 |> Gen.generate;;
val it : int = 304

> Gen.int |> Gen.resize 999 |> Gen.generate;;
val it : int = -476

> Gen.int |> Gen.resize 999 |> Gen.generate;;
val it : int = 276

  1. That’s how the generate function works in QuickCheck 2; It’s slightly different (and easier to use) compared to QuickCheck 1.

Write you some QuickCheck - Generating random booleans

Feb 12, 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 the previous post I’ve generated random characters. In this post, I’ll be doing the same for booleans.

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

  • a generator that lifts a value to the elevated world of generators; that’s the one ported as Gen.init
  • a generator that randomly uses one of the above generators, that’s Gen.oneof

Given the above, a boolean generator can be written as:

let bool =
    Gen.oneof [ Gen.init true
                Gen.init false ]

val bool : Gen<bool>

Finally, here are some sample booleans:

> Gen.bool |> Gen.generate;;
val it : bool = true

> Gen.bool |> Gen.generate;;
val it : bool = true

> Gen.bool |> Gen.generate;;
val it : bool = true

> Gen.bool |> Gen.generate;;
val it : bool = false

> Gen.bool |> Gen.generate;;
val it : bool = false

> Gen.bool |> Gen.generate;;
val it : bool = false

> Gen.bool |> Gen.generate;;
val it : bool = false

> Gen.bool |> Gen.generate;;
val it : bool = true

> Gen.bool |> Gen.generate;;
val it : bool = false

> Gen.bool |> Gen.generate;;
val it : bool = true

> Gen.bool |> Gen.generate;;
val it : bool = true

> Gen.bool |> Gen.generate;;
val it : bool = false

> Gen.bool |> Gen.generate;;
val it : bool = false

Write you some QuickCheck - Generating random characters

Feb 11, 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 the previous post I’ve generated random bytes. In this post, I’ll be generating random characters.

I’m going to need a couple of generators for this:

  • one that picks numbers from the range (in HEX)1
    • [20h..7Eh] for ASCII printable characters
    • [80h..FFh] for ASCII extended characters
  • a generator that randomly uses one of the above generators
  • a generator that applies a function (in this case Operators.char<^T> to the above)

Porting Gen’s oneof

/// <summary>
/// Randomly uses one of the given generators.
/// </summary>
/// <param name="gens">The input list of generators to use.</param>
/// <remarks>
/// The input list must be non-empty.
/// </remarks>
let oneof gens =
    let join x = Gen.bind x id
    join (Gen.elements gens)

Porting Gen’s elements since oneof depends on it

/// <summary>
/// Generates one of the given values.
/// </summary>
/// <param name="xs">The input list.</param>
/// <remarks>
/// The input list must be non-empty.
/// </remarks>
let elements xs =
    // http://stackoverflow.com/a/1817654/467754
    let flip f x y = f y x
    Gen.choose (0, (Seq.length xs) - 1) |> Gen.map (flip Seq.item xs)

All the pieces are now in place, and so a char generator can be written as:

let char =
    Gen.oneof [ Gen.choose ( 32, 126)
                Gen.choose (127, 255) ]
    |> Gen.map Operators.char

val char : Gen<char>

Finally, here are some sample characters:

> Gen.char |> Gen.generate;;
val it : char = 'æ'

> Gen.char |> Gen.generate;;
val it : char = 'W'

> Gen.char |> Gen.generate;;
val it : char = 'h'

> Gen.char |> Gen.generate;;
val it : char = 'à'

> Gen.char |> Gen.generate;;
val it : char = 'ì'

> Gen.char |> Gen.generate;;
val it : char = '&'

> Gen.char |> Gen.generate;;
val it : char = ' '

> Gen.char |> Gen.generate;;
val it : char = 'o'

> Gen.char |> Gen.generate;;
val it : char = 'X'

  1. I used the ASCII codes from this table.

Write you some QuickCheck - Generating random bytes

Feb 10, 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.

We already have a function that runs a generator Gen<'a> and returns random test data of type 'a.

val generate : Gen<'a> -> 'a

Now, in order to be able to generate random bytes, we need a couple of generators:

  • a generator that picks numbers from a given range (in this case [0..255])
  • a generator that applies a function (in this case Operators.byte<^T>) to an existing generator

Porting Gen’s choose

/// <summary>
/// Generates a random element in the given inclusive range, uniformly
/// distributed in the closed interval [lo,hi].
/// </summary>
/// <param name="lo">The lower bound.</param>
/// <param name="hi">The upper bound.</param>
let choose (lo, hi) = Gen(fun n r -> r) |> Gen.map (Random.range (lo, hi) >> fst)

Porting Gen’s map, bind, and return1 since choose depends on them

/// <summary>
/// Sequentially compose two actions, passing any value produced by the first
/// as an argument to the second.
/// </summary>
/// <param name="f">
/// The action that produces a value to be passed as argument to the generator.
/// </param>
let bind (Gen m) f =
    Gen(fun n r ->
        let (r1, r2) = r |> Random.split
        let (Gen m') = f (m n r1)
        m' n r2)

/// <summary>
/// Injects a value into a generator.
/// </summary>
/// <param name="a">The value to inject into a generator.</param>
let init a = Gen(fun n r -> a)

/// <summary>
/// Returns a new generator obtained by applying a function to an existing
/// generator.
/// </summary>
/// <param name="f">The function to apply to an existing generator.</param>
/// <param name="m">The existing generator.</param>
let map f m =
    bind m (fun m' ->
        init (f m'))

All the pieces are now in place, and so a byte generator can be written as:

let byte = Gen.choose (0, 255) |> Gen.map Operators.byte

val byte : Gen<byte>

Finally, here are some sample bytes:

> Gen.byte |> Gen.generate;;
val it : byte = 125uy

> Gen.byte |> Gen.generate;;
val it : byte = 201uy

> Gen.byte |> Gen.generate;;
val it : byte = 3uy

  1. In F#, return is already taken, so I used init instead.

Write you some QuickCheck - Prelude

Feb 9, 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.

I’ll be basing this minimal F# version of QuickCheck on QuickCheck 1.2.0.1, the last version of QuickCheck depending exclusively on base and Random 1.11.

Random is a basic random number generation library, including the ability to split random number generators. QuickCheck 1.2.0.1 uses

from the Random package, and so it’ll be easier to start by porting those in F#:

/// <summary>
/// This module deals with the common task of pseudo-random number generation.
/// It makes it possible to generate repeatable results, by starting with a
/// specified initial random number generator, or to get different results on
/// echch run by using the system-initialised generator or by supplying a seed
/// from some other source.
/// </summary>
/// <remarks>
/// This implementation uses the Portable Combined Generator of L'Ecuyer for
/// 32-bit computers, transliterated by Lennart Augustsson. It has a period of
/// roughly 2.30584e18.
/// </remarks>
[<AutoOpen>]
module internal LightCheck.Random

type StdGen =
    private
    | StdGen of int * int

/// <summary>
/// The next operation returns an Int that is uniformly distributed in the
/// rangge of at least 30 bits, and a new generator. The result of repeatedly
/// using next should be at least as statistically robust as the Minimal
/// Standard Random Number Generator. Until more is known about implementations
/// of split, all we require is that split deliver generators that are (a) not
/// identical and (b) independently robust in the sense just given.
/// </summary>
let private next (StdGen (s1, s2)) =
    let k    = s1 / 53668
    let k'   = s2 / 52774
    let s1'  = 40014 * (s1 - k * 53668)  - k * 12211
    let s2'  = 40692 * (s2 - k' * 52774) - k' * 3791
    let s1'' = if s1' < 0 then s1' + 2147483563 else s1'
    let s2'' = if s2' < 0 then s2' + 2147483399 else s2'
    let z    = s1'' - s2''
    let z'   = if z < 1 then z + 2147483562 else z

    (z', StdGen (s1'', s2''))

/// <summary>
/// The split operation allows one to obtain two distinct random number
/// generators. This is very useful in functional programs (for example, when
/// passing a random number generator down to recursive calls), but very little
/// work has been done on statistically robust implementations of split.
/// </summary>
let split (StdGen (s1, s2) as std) =
    let s1' = if s1 = 2147483562 then 1 else s1 + 1
    let s2' = if s2 = 1 then 2147483398 else s2 - 1
    let (StdGen (t1, t2)) = next std |> snd

    (StdGen (s1', t2), StdGen (t1, s2'))

/// <summary>
/// The range operation takes a range (lo,hi) and a random number generator g,
/// and returns a random value, uniformly distributed, in the closed interval
/// [lo,hi], together with a new generator.
/// </summary>
/// <remarks>
/// It is unspecified what happens if lo > hi. For continuous types there is no
/// requirement that the values lo and hi are ever produced, although they very
/// well may be, depending on the implementation and the interval.
/// </remarks>
let rec range (l, h) rng =
    if l > h then range (h, l) rng
    else
        let (l', h')    = (32767, 2147483647)
        let b           = h' - l' + 1
        let q           = 1000
        let k           = h - l + 1
        let magnitude   = k * q
        let rec f c v g =
            if c >= magnitude then (v, g)
            else
                let (x, g') = next g
                let v'      = (v * b + (x - l'))
                f (c * b) v' g'
        let (v, rng') = f 1 0 rng

        (l + v % k), rng'

let private r = int System.DateTime.UtcNow.Ticks |> System.Random

/// <summary>
/// Provides a way of producing an initial generator using a random seed.
/// </summary>
let createNew() =
    let s       = r.Next() &&& 2147483647
    let (q, s1) = (s / 2147483562, s % 2147483562)
    let s2      = q % 2147483398

    StdGen (s1 + 1, s2 + 1)

To port QuickCheck’s basic generators, and combinators for making custom ones, we need a type of Gen<'a>:

/// <summary>
/// LightCheck exports some basic generators, and some combinators for making
/// new ones. Gen of 'a is the type for generators of 'a's and essentially is
/// a State Monad combining a pseudo-random generation seed, and a size value
/// for data structures (i.e. list length).
/// Using the type Gen of 'a, we can specify at the same time a set of values
/// that can be generated and a probability distribution on that set.
///
/// Read more about how it works here:
/// http://www.dcc.fc.up.pt/~pbv/aulas/tapf/slides/quickcheck.html#the-gen-monad
/// http://quviq.com/documentation/eqc/index.html
/// </summary>
module LightCheck.Gen

/// <summary>
/// A generator for values of type 'a.
/// </summary>
type Gen<'a> =
    private
    | Gen of (int -> StdGen -> 'a)

Finally, we also need a function2 that runs a generator; taking a Gen<'a> and returning random test data of type 'a:

/// <summary>
/// Runs a generator. The size passed to the generator is up to 30; if you want
/// another size then you should explicitly use 'resize'.
/// </summary>
let generate (Gen m) =
    let (size, rand) = Random.createNew() |> Random.range (0, 30)
    m size rand

val generate : Gen<'a> -> 'a

We’re all set! Let’s generate some random test data in the next post(s).


  1. The other thing to notice about QuickCheck 1.2.0.1, is that it’s the last version before version 2 came out. In version 2 there’s added support for shrinking, which is a major advancement. The shrinking functions are going to be ported from QuickCheck 2.8.2.

  2. The implementation of the generate function is based on both QuickCheck 1.2.0.1 and QuickCheck 2.8.2.

subscribe via RSS