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 30 ^{1} .
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
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
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'
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 return
^{1} 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 = 125 uy
> Gen . byte |> Gen . generate ;;
val it : byte = 201 uy
> Gen . byte |> Gen . generate ;;
val it : byte = 3 uy
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.1 ^{1} .
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 function^{2} 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) .