Arbitrary

Generate arbitrary sequences for testing.

Overview

The Arbitrary package allows testing properties that must hold for data types. For example, the BigInt implementation needs to ensure that addition and multiplication are commutative and associative, that 0 and 1 are the additive and multiplicative identity, etc. In an ideal world, we would want the compiler to prove that these properties hold (or at least to verify a human-written proof). In the real world, we can test these properties hold for "arbitrary" BigInt numbers.

The basic API consists of the function arbitrary(::Type{T}), which returns an iterator that produces values of type T. The iterator will first produce "simple" or "special" values (such as 0 or 1), and will then go on to produce more "difficult" values via a random number generator. I expect that testing properties with e.g. 100 such arbitrary values make for good property tests.

Example 1:

using Base.Iterators
using Test
using Arbitrary
# Generate arbitrary values
xs = collect(take(arbitrary(BigInt), 100))
ys = collect(take(arbitrary(BigInt), 100))
zs = collect(take(arbitrary(BigInt), 100))
# Test commutativity
@test all(xs .+ ys .== ys .+ xs)
# Test associativity
@test all((xs .+ ys) .+ zs .== xs .+ (ys .+ zs))

Why not just use random values?

This package takes its motivation from Haskell's Test.QuickCheck.Arbitrary type class.

Arbitrary values are quite similar to random values. The main difference is that one has (better) control over the the probability with which certain values are produced. This ensures that corner cases receive proper testing. For example, the default random number generator for Int values creates numbers with a uniform distribution, and it is thus very unlikely to obtain small integers (e.g. from 1 to 10).

Defining arbitrary for your own type

The Arbitrary package contains methods for various built-in types. To extend this for your own type, you need to provide a respective method for the arbitrary function.

Example 2:

using Base.Iterators
using Arbitrary
# Define your own type
struct Point{T}
    x::T
    y::T
end
# Define a method for Arbitrary.arbitrary
function Arbitrary.arbitrary(::Type{Point{T}}, ast::ArbState) where {T}
    xs = Iterators.Stateful(arbitrary(T, ast))
    flatten([Point{T}[Point(T(0), T(0)),
                      Point(T(0), T(1)),
                      Point(T(1), T(0)),
                      Point(T(-1), T(-1))],
            Generate{Point{T}}(
                () -> Point(popfirst!(xs), popfirst!(xs)))])
end

This arbitrary method first generates 4 points with particular values, which are presumably simple but interesting. Next it uses existing arbitrary methods for the type T to generate new points. Generate is a wrapper type that creates an iterator from a function. The function Base.Iterators.flatten concatenates iterators, while the type Base.Iterators.Stateful captures iterators into mutable objects.

julia> collect(take(arbitrary(Point{Int}, UInt(42)), 20))

20-element Array{Point{Int64},1}:
  Point{Int64}(0, 0)                                      
  Point{Int64}(0, 1)                                      
  Point{Int64}(1, 0)                                      
  Point{Int64}(-1, -1)                                    
  Point{Int64}(0, 1)                                      
  Point{Int64}(2, 3)                                      
  Point{Int64}(-1, -2)                                    
  Point{Int64}(10, 100)                                   
  Point{Int64}(-10, 9223372036854775807)                  
  Point{Int64}(9223372036854775806, -9223372036854775808)
  Point{Int64}(-9223372036854775807, 9067366622006296321)
  Point{Int64}(-2256197071093261190, -5795687145721743680)
  Point{Int64}(2798402323870333227, 8156153274284847668)  
  Point{Int64}(8296248152788523164, 2972613083423981281)  
  Point{Int64}(6437123995368952903, -7346326483082348639)
  Point{Int64}(5681684189447142543, 499062510383072047)   
  Point{Int64}(-4069693335803290299, -5159697560496114268)
  Point{Int64}(5657203908704019168, -551782769629649706)  
  Point{Int64}(5497552197468976212, -2695328260518845352)
  Point{Int64}(-1464621002877751017, -7952756775211842320)

The generated arbitrary points start out with the four special values that are specified explicitly, and then continue with arbitrary Int values. If you run this example, then your output will differ since you will be using a different random number generator seed. You can explicitly pass in a seed by calling e.g. arbitrary(Point{Int}, UInt(42)) to ensure reproducible arbitrary sequences.