Essentials of Vintage QuickCheck - Property-Based Testing (Part 2)

This second post in the series goes through the design and implementation of the original property-based testing library, QuickCheck. The first and introductory post is Even if you already know what property-based testing is, it's worth familiarizing yourself with the example. Property-based testing #1: What is it anyway? The complete code can be found on - in particular and . GitHub example.py vintage.py Last time we looked at why you'd want to write property-based tests, and introduced the basic functionality that a property-based testing library should provide. Now, we'll dive into how a property-based testing library with random generation is implemented - and more in particular the approach set out by the OG, QuickCheck. We'll create a mini reference implementation in just a couple pages of code (including comments and examples)! At its core, any modern PBT library provides three related modules. The first allows defining and combining generators - a few functions to create generators for primitive types, ways to skew or restrict generated values, and combine them to generate custom types. For example, to generate the field of objects, you'd want to restrict to positive values up to say 100. To write a generator for objects, you'd want to combine the generator for and the generator for names. I'll call this the module. age Person Person age generator The second allows defining properties, which means specifying some parametrized test, and specifying which generator you'd like to use for it. It also includes ways to observe and log the distribution of generated values so you can convince yourself the generated values are sensible. I'll call this the module. property The third and last allows running a series of tests based on some configuration, e.g. the number of test cases to generate, how long the test should be running, and so on. I'll call this the module. runner As a sneak peek ahead, at the end of this post we'll be able to define generators, and run tests for the property we discussed in the last post. Recall that is defined as: sort_by_age Person @dataclass(frozen=True) class Person: name: str age: int We'll be able to create a generator for random objects as follows: Person ages = int_between(0,100) letters = map(chr, int_between(ord('a'), ord('z'))) simple_names = map("".join, list_of_length(6, letters)) persons = mapN(Person, (simple_names, ages)) lists_of_person = list_of(persons) These are five random generators for random ages, lowercase letters, simple names consisting of 6 random lowercase letters, person objects and lists of person objects respectively. We'll implement and discuss the , , and functions below - they're part of the generator module of our library. int_between map mapN list_of We'll also be able to define properties though the function: for_all def is_valid(persons_in: list[Person], persons_out: list[Person]) -> bool: same_length = len(persons_in) == len(persons_out) sorted = all(persons_out[i].age <= persons_out[i + 1].age for i in range(len(persons_out)-1)) unchanged = { p.name for p in persons_in } == { p.name for p in persons_out } return same_length and sorted and unchanged prop_sort_by_age = for_all( lists_of_person, lambda persons_in: is_valid(persons_in, sort_by_age(persons_in)) ) Finally, through the function, we'll check that the property holds for 100 randomly generated lists: test > test(prop_sort_by_age) Success: 100 tests passed. All things random Let's first focus on how to create a generator API - as we'll see the two other modules are entirely based on it. The first question is - why bother at all and not just use the built-in random API? Most languages have one, here's Python's . random module The main reason is abstraction - at this point it may look like premature abstraction, but in the following posts we'll change the implementation of generators quite a few times, to add features and change their behaviour, and we won't have to change the users of the API. This is powerful, both from the user and the maintainer's perspective - the maintainer has considerable freedom to improve, without bothering users too much. One straightforward example is changing to a different pseudo-random number generator that is faster or has better properties. Another reason is that typical built-in random APIs are quite poor - Python's has more features than some other languages, but still, writing the above generator would require quite a bit of plumbing. Person Without further ado, let's first take a stab at what the representation of a generator should be. Since a generator is something that when asked, can produce a new random value, the simplest representation is a function without arguments that returns a value. To make the code more readable and safe, we wrap it in a small class: class Random(Generic[Value]): def __init__(self, generate: Callable[[], Value]): self._generate = generate def generate(self) -> Value: return self._generate() Pretty straightforward - is a class that just wraps a function that generates a value of some generic type. To make what follows visible, let's first implement a simple function to sample the actual values from a generator - even though we don't have any to sample yet! Random def sample(gen: Random[T]) -> list[T]: return [gen.generate() for _ in range(5)] takes a instance and calls on it 5 times, collecting the results in a list. sample Random generate() With that in place, we'll now build up increasingly powerful functions that allow us to create and combine generators, so we can ultimately generate a list of values - which is what we need to be able to check the properties of . Random Person sort_by_age Let's write the simplest generator possible - one that always generates the same value. For each new function, I'll first give the implementation with a usage example. Then I'll show the output of sampling the generator. def constant(value:T) -> Random[T]: return Random(lambda: value) pie = constant(math.pi) takes some value as argument, and creates a instance which always generates that value: constant Random > sample(pie) [3.141592653589793, 3.141592653589793, 3.141592653589793, 3.141592653589793, 3.141592653589793] Amazing. Now slightly more exciting. def int_between(low: int, high: int) -> Random[int]: return Random(lambda: random.randint(low, high)) ages = int_between(0,100) creates generators for integers within a range. It's a straightforward wrapper around Python's . Let's use it to generate reasonable ages for people: int_between random.randint > sample(ages) [37, 15, 1, 62, 21] That's one field done, now how about generating names for ? Generating random letters seems like a good start. Since we already know how to generate integers, and it's straightforward to turn an integer into a letter, we should be able to build on . It'll be generally useful to be able to convert, or map, generated values to another type. This idea is analogous to using the built-in function for iterables. So let's add to our arsenal, and use it to write a lowercase letter generator. Person int_between map map def map(f: Callable[[T], U], gen: Random[T]) -> Random[U]: return Random(lambda: f(gen.generate())) letters = map(chr, int_between(ord('a'), ord('z'))) takes a function and a instance, and then applies the function to each value of the underlying generator. map Random > sample(letters) ['t', 'm', 's', 'u', 'c'] That's great, but a single letter doesn't make for a believable name. We could map again and repeat the same letter a number of times, but I think you'll agree that is not exactly an interesting name either. What we'd like to have is a method that runs a given generator N times, and combines the result. zzzzz The answer: applies a function to generators, like applies a function to a single generator (so it's actually more general than what we need for this particular example). A related function you may be more familiar with is , which combines the inputs into a tuple. mapN. mapN N map zip def mapN(f: Callable[...,T], gens: Iterable[Random[Any]]) -> Random[T]: return Random(lambda: f(*[gen.generate() for gen in gens])) Given we can write a function, which generates a list of a given length, where each element is generated from a given generator: mapN list_of_length Random def list_of_length(l: int, gen: Random[T]) -> Random[list[T]]: gen_of_list = mapN(lambda *args: list(args), [gen] * l) return gen_of_list With all that we're finally able to write a somewhat reasonable generator - thanks to again, now used in its generality: Person mapN simple_names = map("".join, list_of_length(6, letters)) persons = mapN(Person, (simple_names, ages)) > sample(persons) [Person(name='vuaufc', age=38), Person(name='kmvmpy', age=34), Person(name='wiuoph', age=34), Person(name='cvuxbu', age=72), Person(name='fykqmn', age=33)] Pleased to meet you, Mr vuaufc! Okay, perhaps these are not the most believable names - but they will do for our purposes, which is to eventually test . sort_by_age As the final piece of the puzzle, we'd like to generate lists of . For the moment, we can only generate lists of a given length, using . Without breaking abstraction (e.g. by using directly) we can't yet generate a list of random length with random elements. That's because we have no way to write a generator that's dependent on the random value generated by another generator - we simply have no way to put them together. Try to write it with only the functions so far to convince yourself, if you like. Person list_of_length random This is where the following function helps: def bind(f: Callable[[T], Random[U]], gen: Random[T]) -> Random[U]: return Random(lambda: f(gen.generate()).generate()) Before going into the details of its implementation, here's how you use it: def list_of(gen: Random[T]) -> Random[list[T]]: length = int_between(0, 10) return bind(lambda l: list_of_length(l, gen), length) lists_of_person = list_of(persons) > sample(lists_of_person) [[Person(name='rsgiud', age=81), Person(name='ywcelx', age=55)], [Person(name='bskmxa', age=99), Person(name='jaonqc', age=55), Person(name='igelts', age=67)], [Person(name='yuhtkg', age=78)], [Person(name='coessh', age=43), Person(name='fpjnqi', age=18), Person(name='fjojvw', age=86), Person(name='tbneue', age=97), Person(name='ejirnj', age=76)], [Person(name='wopfbo', age=22), Person(name='yjgfkf', age=39), Person(name='xsslyn', age=34), Person(name='kjpqus', age=12), Person(name='cjlldt', age=24), Person(name='bqthxy', age=29), Person(name='ttqlhx', age=20), Person(name='wyumfv', age=99), Person(name='ucdeqz', age=14), Person(name='eqrxir', age=41)]] Note there are 5 lists that each have a different, randomly chosen length. How does work? It first runs the given generator, and feeds the resulting value into . takes the value as an argument and returns a new generator, which is then run in turn. The fact that the user can write the function and is given a value from , allows expressing the dependence we need - we can now generate a random list length, and then use to plumb that into a generator of a random list with fixed length. bind f f f gen bind Before taking a step back to look at what we've got in our generator module - there's one implementation subtlety in that is worth mentioning. It's tempting to think that the implementation can be simplified to: bind def bad_bind(f: Callable[[T], Random[U]], gen: Random[T]) -> Random[U]: # let's get rid of the lambda return Random(f(gen.generate()).generate) Unfortunately that doesn't work - it only generates from and applies once, which means in the example it would create a generator that chooses a random length , and then forever returns random lists of that length. gen f once It's maps all the way down With a small but beautiful arsenal of functions - , , , and , we can generate the list of person objects we need. With small additions like (which you can find in the , implemented in terms of ) and this handful of functions is the sufficient and necessary core of any generator module. int_between constant map mapN bind choice source code bind filter As we touched on in the last post, these functions are sometimes called "combinators" because they are designed to be combined without limit. All of the functions return a object, and so can be used again as an argument of a further combinator - another way of saying that is that they are infinitely composable. That makes it a beautiful and powerful approach to API design. Random This may have all felt quite familiar if you've used collections APIs before - most of the generator functions have corresponding built-in python functions that work on collections (iterables, more precisely). is like int_between range is like map map is like + mapN zip map is like a nested loop in a list comprehension bind for This is perhaps not a surprise - generators are infinite streams of random values, and so any API that can work with a container of values of some sort can support similar operations. If Python would allow changing how are processed, we'd be able to write random generators like: generator expressions # not actually Python lists_of_person = gen ( pl for length in int_between(0, 10) for pl in list_of_length(length, persons) ) Which can be automatically translated into the version with (which actually works!) above - illustrating that is equivalent to . bind for x in generator ... bind(lambda x: ..., generator) An interesting aspect is that the sequence of functions , and gives the user an increasing amount of expressive power. One way to understand this is that and can be implemented in terms of , but can not be implemented in terms of and . The same is true for vs - if you have you have , but not vice versa. map mapN bind map mapN bind bind map mapN map mapN mapN map Why not just implement then? Indeed we could do that without any loss of functionality or expressivity. The flip side is that exposes strictly less information to the implementation and so can make fewer assumptions about what's intended compared to and . This is reflected in the relative complexity of their implementations. As a result typically is less performant than which is less performant than - if you can write it with , don't use to give the implementation more to work with. bind bind bind map mapN bind mapN map map bind This pattern of functions - , , and - returns time and time again in various guises in collection libraries, streams, reactive libraries and the like. In languages with expressive type systems like Haskell explicit abstractions or interfaces exist to encapsulate them - , and respectively. The concepts also have a deep connection to category theory, which is a branch of mathematics that Eric Meijer describes as " ". constant map mapN bind Functor Applicative Monad the Mathematicians' interpretation of interface-based design We can only scratch the surface of that here - hopefully you now have an intuitive idea of what these "API design patterns" entail with some leads to learn more if you're interested. Many libraries besides PBT use these patterns and recognizing them makes it easier to get started. As a library designer, it's definitely useful to know and learn when these patterns can be used - they're a valuable tool in your toolbox. If you've made it this far, now would be a good time to reward yourself with a slice of pecan pie! Let me write some tests already Now that we can write random generators, let's go the final distance and write a few functions to define properties and run some tests. First, we need a way for the user to write a property. A property is just a combination of a generator and an assertion. We'll run the assertion 100 times with randomly generated values. The function to connect a generator to an assertion is typically called "for all", because this is reminiscent of the logical for all quantifier. In prose, we want to write "For all lists of person, the result of sort by age is valid." In some sense "for all" is a misnomer, as of course we won't really be testing or proving anything for values, but let's stick with it anyway. all For simplicity we'll write assertions as functions that return if the assertion holds, if not. More traditionally you'd use and fail the test on exception, but doing it this way allows us to build up the implementation in an easier to understand way. True False assert Our first attempt at defining a property, is that it's a boolean generator indicating whether the test has failed or not. That means we don't even need a new class - we can just use : Random[bool] Property1 = Random[bool] def for_all_1(gen: Random[T], property: Callable[[T], bool]) -> Property1: return map(property, gen) sort_by_age_1 = for_all_1(lists_of_person, lambda persons_in: is_valid(persons_in, sort_by_age(persons_in))) # wrong_sort_by_age is sort_by_age with a bug, # to show what a failing test looks like. wrong_sort_by_age_1 = for_all_1(lists_of_person, lambda persons_in: is_valid(persons_in, wrong_sort_by_age(persons_in))) Our first attempt at implementing is just a , applying the assertion to each generated element. Since a property created by is just a instance, we can it: for_all map for_all Random sample > sample(sort_by_age_1) [True, True, True, True, True] > sample(wrong_sort_by_age_1) [False, True, False, False, False] That's not user-friendly output though. In the actual function, we 100 values - if they're all , our test has succeeded: test generate True def test_1(property: Property1): for test_number in range(100): if not property.generate(): print(f"Fail: at test {test_number}.") return print("Success: 100 tests passed.") In action: > test_1(sort_by_age_1) Success: 100 tests passed. > test_1(wrong_sort_by_age_1) Fail: at test 0. Okay that seems to work, but it doesn't allow writing properties that draw from two or more generators - it would be nice if we could nest . Here's which allows that: for_all for_all_2 def for_all_2(gen: Random[T], property: Callable[[T], Union[Property1,bool]]) -> Property1: def property_wrapper(value: T) -> Property1: outcome = property(value) if isinstance(outcome, bool): return constant(outcome) else: return outcome return bind(property_wrapper, gen) sum_of_list_2 = for_all_2( list_of(int_between(-10,10)), lambda l: for_all_2(int_between(-10,10), lambda i: sum(e+i for e in l) == sum(l) + len(l) * i)) We allow the property function to return either a bool value (in which case it's the innermost ) as before, or a (in which case it's one of the outer functions). Because we may now get a back, which is a , it's not enough to use : we have to upgrade to in the implementation of . for_all Property1 for all Property1 Random[bool] map bind for_all_2 As a final improvement let's print the generated arguments if the test fails. We'll use the same trick as before by piggy-backing on , but instead of use a richer type : Random bool TestResult @dataclass(frozen=True) class TestResult: is_success: bool arguments: Tuple[Any,...] Property = Random[TestResult] def for_all(gen: Random[T], property: Callable[[T], Union[Property,bool]]) -> Property: def property_wrapper(value: T) -> Property: outcome = property(value) if isinstance(outcome, bool): return constant(TestResult(is_success=outcome, arguments=(value,))) else: return map(lambda inner_out: replace(inner_out, arguments=(value,) + inner_out.arguments), outcome) return bind(property_wrapper, gen) def test(property: Property): for test_number in range(100): result = property.generate() if not result.is_success: print(f"Fail: at test {test_number} with arguments {result.arguments}.") return print("Success: 100 tests passed.") This is more user-friendly when the test fails: > test(prop_wrong_sort_by_age) Fail: at test 0 with arguments ([Person(name='qqdkng', age=31), Person(name='lcqyva', age=73)],). At least it now tells us which arguments are a failing input! With that it's straightforward to reproduce and debug the error. Note that for mutable values, capturing the arguments in this way can be problematic: captures a reference to the generated value, but if the assertion or the function under test changes it, we'll print the value after the change. For a pure functional language like Haskell that can't happen, but for Python and others it's definitely a problem. One neat way to deal with this is to store the pseudo-random number generator's seed instead of the generated values, and then re-generate the value from scratch with that seed. We'll come back to issues around mutability in the next posts. TestResult.arguments That's as far as I want to take this initial implementation. Let's take stock of what we have, what's missing, and what we'll cover in the next post. Finally The 80/20 rule applies here - this code, which altogether is just a couple pages, represents 80% of the functionality of a property-based testing library. A lot of the work goes into writing and maintaining a wide range of useful generators for commonly used types. I've definitely simplified and omitted a number of aspects though, only some of which we'll come back to. The property and test "modules" here only have one function each ( and respectively). Real PBT libraries have more functions to gather statistics and info on generated values, and this is implemented by adding more fields on to collect them. For example, we might print information like "20% of the generated lists were empty, generating values took 12% of the test time" and so on. Also there will be a bunch more options to configure the test run in various ways. for_all test TestResult QuickCheck was written in Haskell which is a pure language and so QuickCheck's needs to include the pseudo-random number generator's seed value as input. In the implementation above, that seed is hidden away in the module, and updated as values are generated. Random.generate random QuickCheck's also includes an integer argument. This size is used to restrict the "size" of the generated values - which is not unambiguously defined, but it's typically used to make sure that generators for recursive types (like trees) don't end up generating huge values, by e.g. interpreting the given size as the maximum depth of the tree. We will come back to the notion of size when we discuss shrinking in the next few posts. generate size That's it for this post, a lot of ground covered! The next post will discuss shrinking - which is an area where most experimentation has happened since QuickCheck was introduced. If you feel like it, please share this post, comment below or discuss on Twitter . @kurt2001 Until next time! Also Published Here