Automated testing is a powerful tool for finding bugs and specifying correctness properties of code. Haskell’s Quickcheck library is the most well-known automated testing library, based on over 15 years of research into how to write property-base tests, generate useful sources of inputs, and report manageable counterexamples. Jane Street’s Core library has not had anything comparable up until now; version 113.00 of Core finally has a version of Quickcheck, integrating automated testing with our other facilities like s-expression reporting for counterexample values, and support for asynchronous tests using Async.
There are at least two other Quickcheck implementations on OPAM. Why write implementation N+1?
Before working at Jane Street, I did some research relating to randomized testing (Eastlund 2009, Klein et al. 2012). In both cases, users of the software packages involved found it easy to write tests that use random data, but hard to write random distributions that actually produce values that are useful to test.
This Quickcheck clone started as an attempt to address those concerns by building tools for tuning random distributions of values. One way I’ve done that is building in tools for “remembering” sets of chosen values; for example, random tests won’t repeat values, and it is easy to build distributions that generate sets or sorted lists and maintain uniqueness. This design is still in early stages, I don’t know if these are the sort of tools that will be needed most, and I’m eager to get feedback from more users. The library has also evolved to integrate Quickcheck-style testing with the Jane Street Core and Async libraries. Over time I hope this will also produce useful random distributions for more of the Core types, so they will be easily testable.
For those unfamiliar with Haskell’s Quickcheck, the library allows users to write tests of some property of a function, then test that property on many automatically-generated input values. For example, we might want to test that the optimized implementation of list-append in Core is associative:
TEST_UNIT "associativity of list append" = Quickcheck.test Quickcheck.Generator.(tuple3 (list int) (list int) (list int)) ~sexp_of:<:sexp_of> ~f:(fun (xs, ys, zs) -> <:test_eq> (List.append xs (List.append ys zs)) (List.append (List.append xs ys) zs))
The test above randomly generates three lists of integers, appends them together two different ways, and tests that the results are equal. This process is repeated with different randomly chosen lists each time, until an error is reported or the default trial count is reached. Let’s break down the parts of the code here.
TEST_UNITis a camlp4 syntax for unit tests.
Quickcheck.testis the main entry point for running a test using Quickcheck. It takes two required, unnamed arguments. The first is a generator, specifying the probability distribution of values to choose from when generating inputs for the test. The second is a function that consumes the generated input values and runs a test. The function returns
()if successful and raises an exception otherwise.
Quickcheck.Generator.(tuple3 (list int) (list int) (list int))constructs the generator that we want to use here. Most of the functions in the
Quickcheck.Generatormodule are named after the types they generate; here, default probability distributions for
ints, combined using
- We provide the optional named argument
Quickcheck.test. This argument is used to render the first generated value that triggers an error. The
<:sexp_of< ... >>expression is camlp4 syntax for the default sexp conversion for a type.
- The final argument to
Quickcheck.testis a function that takes the tuples of lists produced by our generator, appends them two different ways, and compares the output.
<:test_eq< ... >>is camlp4 syntax for an equality test.
The example above uses the s-expression conversions and camlp4 syntax extensions
that are common in Jane Street’s libraries, but these things are not necessary
for using Quickcheck.
Quickcheck.test just needs a generator built from the
Quickcheck.Generator and a function that raises an exception on
failure, and it will return
() if successful or raise an exception describing
the nature of the failure if not.
The primary data structure used by Quickcheck is the generator, or
'a Quickcheck.Generator.t. This corresponds to an implementation of the
Arbitrary type class in Haskell’s Quickcheck. Primarily, a generator
represents a random distribution of values of type
'a, although in our
implementation there is a little more metadata besides that under the hood. The
Quickcheck.Generator module provides default distributions of several types,
and tools for creating more distributions or customizing the existing ones.
In our example above, we generated three lists of integers using the following expression.
Quickcheck.Generator.(tuple3 (list int) (list int) (list int))
Looking at the implementation of
Core.Std.List.append, we can see that the
implementation works in chunks of 5 elements, and changes behavior after 1000
chunks. So we might want to change our generator to make sure we get lists of
the lengths we want to test.
let open Quickcheck.Generator in let list_int = list int ~length:(`Between_inclusive (4900,5100)) in tuple3 list_int list_int list_int
Some experimentation might show us that this still doesn’t hit the list lengths we want, as often as we want. The [Quickcheck.Generator.int_between] function, however, is documented as stressing boundary conditions, so we should be able to use it to get values at the upper and lower ends of the range we want. Here, it helps us that generators form a monad. If we combine generators using monadic bind, we get a weighted composition of their probability distributions. We can use that to first generate lengths for our lists, then use those randomly-generated lengths to build generators for the lists themselves.
let open Quickcheck.Generator in let list_int = int_between ~lower_bound:(Incl 4900) ~upper_bound:(Incl 5100) >>= fun len -> list int ~length:(`Exactly len) in tuple3 list_int list_int list_int
Now we have a generator for three lists of integers, each list with a length
between 4900 and 5100 inclusive, weighted toward the ends of that range. This is
probably sufficient for our purposes. But if we want to go further down, if we
decide that we need a very specific probability distribution, we can build one
from scratch ourselves. Here is a rather idiosyncratic example that demonstrates
the tools available in
let open Quickcheck.Generator in let rec ranges_of_five_between lower upper = if upper - lower < 10 then of_list (List.range lower upper ~start:`inclusive ~stop:`inclusive) else weighted_union [ 5., singleton (lower + 0) ; 4., singleton (lower + 1) ; 3., singleton (lower + 2) ; 2., singleton (lower + 3) ; 1., singleton (lower + 4) ; 1., of_fun (fun () -> ranges_of_five_between (lower + 5) (upper - 5)) ; 1., singleton (upper - 4) ; 2., singleton (upper - 3) ; 3., singleton (upper - 2) ; 4., singleton (upper - 1) ; 5., singleton (upper - 0) ] in let list_int = ranges_of_five_between 4900 5100 >>= fun len -> list int ~length:(`Exactly len) in tuple3 list_int list_int list_int
This example uses a few more functions from
of_list function takes a list of values and produces a generator that makes a
uniform choice among them.
weighted_union creates a probability distribution
representing a weighted choice among the probability distributions of the
singleton produces constant-valued generators, and
of_fun produces a lazily-evaluated (but not memoized) generator. (Memoizing
during random testing causes some unfortunate space leaks, it is important to be
able to release resources after a batch of tests.) While this peculiar generator
is probably not of practical use, it shows that when we need to, we can dig down
into the interface and build whatever probability distribution we want.
Of course, it is also useful to construct generators for new types.
type bst = Leaf | Node of bst * int * bst let gen : bst Quickcheck.Generator.t = let open Quickcheck.Generator in recursive (fun self -> let node = self >>= fun l -> int >>= fun k -> self >>| fun r -> Node (l, k, r) in union [ singleton Leaf; node ])
Quickcheck.Generator.recursive is a fixed-point generator that
helps build simply-recursive generators that need to invoke themselves and don’t
have additional arguments. The function
union is like
for uniform choice.
In Haskell’s Quickcheck, there is a duality between the type class
for generating random values and
Coarbitrary for observing inputs to random
functions. Our version of Quickcheck mirrors
tests using Quickcheck do not need an observer, but if you want to generate a
random input for a higher-order function, you will need an observer for the
function’s input type.
TEST_UNIT "function composition" = let open Quickcheck.Generator in Quickcheck.test (tuple3 (fn Quickcheck.Observer.int char) (fn Quickcheck.Observer.string int) string) ~f:(fun (f, g, x) -> <:test_eq< char >> ((Fn.compose f g) x) (f (g x)))
Quickcheck.Generator.fn creates a generator for functions. It takes two
arguments: an observer for the function’s input type and a generator for the
function’s output type.
Think of an observer as a “generator of decision trees”. For instance,
Quickcheck.Observer.int might randomly generate any of the following decision
? x>5 / \ ? ? x>4 / \ x>2 ? / \ ? ?
These decision trees control how a randomly-generated function will use its
input. The generator for the function’s output is used to fill each of the
in with a concrete value. The result is a family of functions operating on the
appropriate types, making randomly-chosen observations on the input and
producing randomly-chosen outputs based on those observations.
If you need to build an observer for a custom type, there are tools for that as well.
type bst = Leaf | Node of bst * int * bst let obs : bst Quickcheck.Observer.t = let open Quickcheck.Observer in recursive (fun self -> unmap (variant2 unit (tuple3 self int self)) ~f:(function | Leaf -> `A () | Node (l, k, r) -> `B (l, k, r)) ~f_sexp:(fun () -> Atom "variant2_of_bst"))
As with generators, there is a fixed point function
Quickcheck.Observer.recursive that helps for simply-recursive types. The
unmap transforms an input of some new type into an input for which we
already have an observer. Variant types can be transformed to polymorphic
variants, which have default observers
and constructor arguments can be transformed to tuples, which have default
Work in Progress
Our OCaml adaptation of Quickcheck is new and still evolving. We already have
some changes to the library internally which will be released over time, such as
moving default generators and observers out of the
Quickcheck module and into
the modules for each type. For example,
There are still some pragmatic lessons to learn about how best to use our formulation of the library, how to calibrate our default distributions, and what other distributions we might want to provide. As always, we hope to get feedback from anyone who tries out this library so that we can improve it.