Property based testing in ReasonML

May 19, 2019

Michael Boulton

A rough overview of a partially complete implementation of hedgehog, done in ReasonML.

Notes before reading

There is already two quickcheck implementations for OCaml, both of which behave slightly differently. the Jane street one has some nice stuff like having generators and shrinkers built into their other libraries, so that's probably the one I would advise using.

This library however is an implementations of something more akin to another implementation of Hedgehog, which is similar to quickcheck but does not require you to explicitly define a shrinker for a value, only a generator (see this article for some more information and why defining shrinkers separately doesn't always work as expected)

A lot of it was hacked together from the haskell and F# versions and has been modified to work without typeclasses, which did require changing the way you use it quite a lot.

Not to put too fine a point on it but this library can charitably be defined as "unfinished". The basic functionality is there and it works but there is some more stuff to do around usability and documentation.

One thing that would make it more usable is to add some sort of a PPX which will let you define generators more easily but getting any meaningful documentation and/or examples on how to do that is difficult.

I also want to see if there's some way to define a Shrinkable module which will let you just define something that can be sized and fed directly into a generator.

Range

The concept of being able to create a value within a given range. This could be some like a range of numbers from 100-200, an array with a length of 20-30, a binary tree of depth 1-50, a string of length 1-20, etc etc.

A lot of the time these will be defined in such a way that it depends on an input parameter to determine the size of whatever value it will produce.

// Integers between 0 and `size` 
let from_zero = (size) => (0, Random.bits mod size);

// Floating point numbers from +size to -size
let around_zero = (size) => ((float_of_int(-size)), float_of_int(size)));

This range is created by using the Range type constructor. The first element is the 'origin' - the 'start' of the range, where the 'start' can be whatever you define it to be (within the range). This is an important value - it is what the range will be shrunk towards when trying to find counterexamples (see later on). This origin should be the 'minimal' value for your range - what this means depends on what you are trying to test.

// Shrink towards zero - for example, we could use this when generating
// lists of length n, where 0 is an empty list
let from_zero_range = Range.Range(0, from_zero);

// Same as above
let around_zero_range = Range.Range(0.0);

A lot of the time you will want a range that doesn't depend on the input size though. For example, if you want to sample from letters of the alphabet then you only ever want your range to be between 0 and 26. You might also want your 'minimal' value (the origin) to not be the middle/end of the range. This can be done with a 'constant' range.

// This will generate a function like (size)=>(0,26), ie the 'size' is
// ignored
let choose_alphabet_idx = Range.constant(0, 26);

// Always returns pi
let always_pi = Range.singleton(3.142);

This library also provides a utility which will just generate a range to fit the maximum range of a data type, with predefined values available for the common datatypes like int and float.

// Range which will generate a value from min_int to max_int
let full_int_range = Range.constant_bounded(Numeric.NumberInt);

If you create a module that implements the Number module interface from Numeric then it can be used in this function as well.

Remember that the type of range you are using depends on what you want to generate. You can't generate lists that have a fractional length with a float for example. Because list lengths are measured in ints, you can't use a 64 bit integer to generate lists of random lengths either.

Generating numbers in a range

There is some utility code in Range to sample random numbers from the full range of the basic 'number' data types, with either linear or exponential sampling in the range specified. These are also defined for common data types such as int or float.

These are used to automatically create ranges that will be scaled to within the 'size' parameter given - instead of out choose_alphabet_idx, we could just create a new range using the IntRanges module:

// A range of integers from 0-26
let choose_alphabet_idx = Range.IntRanges.linear(0, 26);

// A range of floats from -100.0 to 100.0, exponentially more likely to
// sample nearer the origin
let float_sample = Range.FloatRanges.exponential_from(0.0, -100.0, 100.0);

// Any 64 bit integer - very large range
let bigint_sample = Range.Int64Ranges.linear_bounded();

Generating random values

Once you have a range, now you can actually generate a random variable within that range. The Random variant contains a function that maps random state (Note that the random state is an opaque value, it is passed around as a seed for a pure functional random number generator) and a 'size' parameter to use to sample from the range. The simplest introduction is the NextNumber module which takes a Numeric.Number and returns a module which has a function which will generate a random value from a given range. This is used like so:

// Use as above
let choose_alphabet_idx = ...

let generate_random_alphabet_idx = RandomValues.NextNumber(Numeric.NumberInt).next_number(choose_alphabet_idx);

NOTE: This is pointlessly verbose at the moment, still trying to solve an issue with NextNumber module types.

This will create a Random type which can be used with a generator to sample random values form that range. Note that it is not just a way to sample random values,

Much like the Range, there is a constant function which will return a random value generator that will only ever return one value.

let always_5 = RandomValues.constant(5);

// Still always returns 5
let resized = RandomValues.resize(always_5);

Trees

Before talking about generating or shrinking functions, we need to get an idea of the data structure it operates on. This is a rose tree, which is a tree which has a value at the node and a number of branches per node (each of which is a rose tree). There is no limit on the number of branches per node, though we will realistically keep it bounded to a sensible number. These are lazily evaluated so that we don't have to store an exponentially growing number of possible shrunk values.

In terms of how we use it, the value at the node is a value (called an 'outcome') that we are going to use to test our function and each of the branches will be possible 'shrunk' values based on this value (called 'shrinks'). These can be created by 'unfolding' a tree based on an initial outcome, using some kind of way to generate shrinks based on it.

In our context, we will use the random value generation to unfold a tree based on an outcome. Each branch off a node will contain some randomised way of shrinking the value, for example it might shrink the value by a different amount to another branch.

Generators

At its core, a 'generator' is created using a function that maps some randomly generated value to a lazily evaluated list of whatever you want to test. For example, if we want to generate a load of random integers, we just need to use a Range and use one of the Gen utility functions

let gen_alphabet_id_ints = Gen.GenPrimitives.int(choose_alphabet_idx);

This wraps the range into a Random for us and then turns it into a generator. If we want to create a random list of integers which have random lengths, we first need to construct the generator for the random integers and then use a Range for the length of the sequence we want to generate (Note that there are predefined modules in the library for arrays and lists, here we are using GenList).

// always between 10 and 20
let list_lengths = Range.constant(10, 20);
// A generator for lists of length 10-20, where each element is an
// integer from 0 to 26
let gen_random_int_lists = Gen.GenLists.seq(list_lengths, gen_alphabet_id_ints);

There are also lots of predefined things to generate random booleans, options, ascii characters etc. These generators can be sampled using the functions in Gen.GenSamples to see what you're getting out.

These generators can also be zipped together, for example we could have one generator which generates floats and one which generates integers, and zip them together to make a generator which generates pairs of floats and integers.

let gen_alphabet_id_ints = ...;
// Maybe weights for how often they should occur in a sentence or something
let gen_weights = Gen.GenPrimitives.float(Range.constant(0.0, 1.0));

let gen_pairs = Gen.zip(gen_alphabet_id_ints, gen_weights);

Shrinking

One of the good things about this library and Hedgehog is that you do not need to specify a separate 'shrinking' function, as long as you have defined a range with an 'origin' it knows what to shrink towards. There are predefined shrinkers for the basic data types such as int and float which will shrink towards the origin you have defined. There are also shrinkers for sequences like list, which will shrink towards an empty sequence, removing elements from the list as it goes.

If we try to shrink ["a", "b", "c", "d"], we might get something like:

  • [] (The empty list is always generated first, because it is 'optimal')
  • ["a", "b"]
  • ["c", "d"]
  • ["a", "b", "c"]
  • etc

Bear in mind however that the range for this list can be defined - if we have defined the minimum length for a list as 1, the empty list will be generated then discarded and we will only see the subsequent shrinks. This is obviously not ideal, but its the tradeoff between the hedgehog/hypothesis way of doing things and having to specify a separate shrinking function (which has its own various issues)

If the list we were checking was a list of integers, the elements inside the list will also be shrunk to try and find a counterexample - for example, the function we are trying to test might only raise an error if the input list is very long but all elements in it are very small.

Properties

This is the 'core' of the library. A 'property' is just referring to how the function behaved when given the input from a generator. An example:

// The function to test
let check_reverse = xs => xs == List.rev(List.rev(xs));

// Some random integers
let size_range = Range.constant(0, 100);
let sizes = Gen.GenIntegers.integral(size_range);

// Some random lists of integers
let length_range = Range.constant(0, 100);
let gen_lists = Gen.GenLists.seq(length_range, sizes);

// Map our function over the randomly generated lists of integers
let matches = Gen.(map(check_reverse, gen_lists));

// How the function behaved - we want it to be always true
let prop = Property.for_all(matches, Property.of_bool);

of_bool converts the boolean return value of check_reverse into a Success or Failure - Any Failure will cause your test to fail, which will then cause the Property to search through the tree to find the smallest possible counterexample that will still cause it to fail.

Depending on how you have specified your generation function and/or ranges, it might be impossible to find a value which actually satisfies the input restrictions you have specified. At this point the property will 'give up' and fail.

NOTE: At some point I need to implement the property which checks if an exception was raised, which would result in a Failure. Would be used like Property.for_all(might_raise, Property.try).

Addendum: utilities

Because one of the aims was to try and get it working with bucklescript as well as native code and js_of_ocaml, there are no external dependencies except for console.lib from the reason-native project which does some object hackery to be able to print generic values.

To be able to properly express some of the things used in the library (like the concept of a generic 'sequence'), I also had to write some module types that could be used in various places in the code.

Lazy list

A lazily evaluated list and the associated functions. It is implemented using the lazy construct which is built into reason - this is a way of 'suspending' an operation until a later point (when it has been 'forced') which is used to describe a way of generating a list without actually evaluating it. This is used a lot in the Tree module, because each tree is actually infinitely large (so we can't fully evaluate it).

Each lazy list is defined as a 'suspension' (lazily evaluated value) of a value and then a lazily evaluated 'rest of the list'.

type t(+'a) = Lazy.t(node('a))
and node('a) =
  | Nil
  | Cons('a, t('a));

Forcing the lazy list only evaluates the head value and leaves the rest suspended.

There are the usual utilities like mapping over a lazy list, appending two lazy lists, and taking the first n elements (also lazily evaluated). It also defines the common monadic bind operation (concat_map) so the lazy lists can be used as a monad. There are also some utility functions to use with the tree generation like unfold which creates a lazy list based on repeated applications of a function.

Int64 operations

A simple module which overrides operators like - and * so that 64 bit values can be manipulated more easily

let x = 4L;
let y = 2L;

let z = Int64Util.Int64Operations.(x + y);

There is also a format_bits function which will format a 64 bit variable into a string where each character is a bit in the original number (mainly for debugging).

Splittable random

Adapted from https://github.com/janestreet/splittable_random as well as the other hedgehog implementations, this is a basic implementation of a pure functional random number generator which takes some state as an input and outputs a random value (int, float, int64, bool, ...) and returns this value as well as the new state of the random number generator.

There is also a unit_float function which will take a 64 bit integer and return a floating point number scaled between 0 and 1 - note that this function may not behave as you expect, as it directly operates on the bit patterns of the underlying representation of the 64 bit integer. unit_float(0) will not return 0.0!

'Numeric' values

Describes some way to operate on a 'number' and how to convert it to and from a 64 bit integer (which is used throughout the code to do things like scaling sizes). This is also used to create the 'predefined' values such as GenInt, ShrinkInt, IntRanges, etc. Implementing the Numeric.Number interface is enough to be able to just pass it to various functions throughout the code to create generators/ranges/etc to match whatever data type you are using.

NOTE: This is really muddled in at the moment, the module types will be separated out a bit more in future.

Object printer

This is the core of the reason-native console library which is used in just one place - formatting counterexamples from generators into human readable values. This does some weird object magic to do it.

Basic monad module

A lot of the core parts of the library uses bind and map a lot behind the scenes, the CoolMonad (silly name) module just exposes a way of creating a monad from each of the modules which define these operations (Gen.GenMonad, RandomValues.RandomMonad, etc). This defines the common monadic operators so they can be used inline, like this part from the library itself:

          RandomValues.RandomMonad.(
            k
            >>= replicate(_, random_g)
            <$> S.of_list
            <$> SeqShrink.sequence_seq
            <$> Tree.filter(filter_at_least, _)
          )

Cross-toolchain compilation

This is a bit of a hassle since it's not officially supported by any tool, but it is kind of possible to get the same library code compiled with Bucklescript and esy (including js_of_ocaml). The main issue is that some of the core OCaml libraries seem to be missing from Bucklescript.

Next steps

A lot of this is 'on hold' because of the state of actually trying to edit ReasonML. The 'newer' VSCode plugin doesn't work very well and the 'older' one can also be a bit flaky. Neither of them highlight some valid syntax correctly.

I've been working on a Jetbrains based plugin to make this easier over the past few months.

Recent Posts