{'fraction_non_alphanumeric': 0.03164188124581813, 'fraction_numerical': 0.003928255379767326, 'mean_word_length': 4.6974913920314805, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Parsing Randomness: Unifying and Differentiating Parsers and Random Generators

"A generator is a parser of randomness."This perspective on generators for random data structures is well established as folklore in the programming languages community, but it has apparently never been formalized, nor have its consequences been deeply explored. We present free generators, which unify parsing and generation using a common structure that makes the relationship between the two concepts precise. Free generators lead naturally to a proof that a large class of generators can be factored into a parser plus a distribution over choice sequences. Further, free generators support a notion of derivative, analogous to familiar Brzozowski derivatives of formal languages, that allows analysis tools to"preview"the effect of a particular generator choice. This, in turn, gives rise to a novel algorithm for generating data structures satisfying user-specified preconditions.


Introduction
"A generator is a parser of randomness. . . " It's one of those observations that's totally puzzling right up to the moment it becomes totally obvious: a random generator-such as might be found in a property-based testing tool like QuickCheck [4]is a transformer from a series of random choices into a data structure, just as a parser transforms a series of characters into a data structure.
Although this connection may be obvious once it is pointed out, few actually think of generators this way. Indeed, to our knowledge the framing of random generators as parsers has never been explored formally. But this is a shame! The relationship between these fundamental concepts deserves a deeper look.
A generator is a program that builds a data structure by making a sequence of random choices-those choices are the key. A "traditional" generator makes decisions using a stored source of randomness (e.g., a seed) that it consults and updates whenever it must make a choice. Equivalently, if we like, we can pre-compute a list of choices and pass it in to the generator, which gradually walks down the list whenever it needs to make random decisions. In this mode of operation, the generator is effectively parsing the sequence of choices into a data structure! To connect generators and parsers, we introduce a data structure called a free generator that can be interpreted as either a generator or as a parser. Free generators have a rich theory; in particular, we can use them to prove that a subset of generator programs can be factored into a parser and a distribution over sequences of choices.
Besides clarifying folklore, free generators admit transformations that cannot be implemented for standard generators and parsers. A particularly exciting one is a notion of derivative which modifies a generator by asking the question: "what would this generator look like after it makes choice ?" The derivative gives a way of previewing a particular choice to determine how likely it is to lead us to useful values.
We use derivatives of free generators to tackle a wellknown problem-we call it the valid generation problem. The challenge is to generate a large number of random values that satisfy some validity condition. This problem comes up often in property-based testing, where the validity condition is the precondition of some functional specification. Since generator derivatives give a way of previewing the effects of a particular choice, we can use gradients (derivatives with respect to a vector of choices) to preview all possible choices and pick a promising one. This leads us to an elegant algorithm for turning a naïve free generator into one that only generates valid values.
In §2 below, we introduce the ideas behind free generators and the operations that can be defined on them. We then present our main contributions: • We formalize the folklore analogy between parsers and generators using free generators, a novel class of structures that make choices explicit and support syntactic transformations ( §3). We use free generators to prove that every "applicative" generator can factored into a parser and a probability distribution. • We exploit free generators to to transport an idea from formal languages-the Brzozowski derivative-to the context of generators ( §4). • To illustrate the potential applications of these formal results, we present an algorithm that uses derivatives to turn a naïve generator into one that produces only 1 arXiv:2203.00652v1 [cs.PL] 1 Mar 2022 values satisfying a Boolean precondition ( §5). Our algorithm performs well on simple benchmarks, in most cases producing more than twice as many valid values as a naïve "rejection sampling" generator in the same amount of time ( §6). We conclude with related and future work ( §7 and §8).

The High-Level Story
Let's take a walk in the forest before we dissect the trees.
Generators and Parsers. Consider the generator genTree in Figure 1, which produces random binary trees of Booleans like Node True Leaf Leaf and Node True Leaf (Node False Leaf Leaf), up to a given height ℎ, guided by a series of random coin flips. 1 Now, consider parseTree (also in Figure 1), which parses a string over the characters n, l, t, and f into a tree. The parser turns ntll into Node True Leaf Leaf and ntlnfll into Node True Leaf (Node False Leaf Leaf). It consumes the input string character by character with consume and uses the characters to decide what to do next.
Obviously, there is considerable structural similarity between genTree and parseTree. One apparent difference lies in the way they make choices and the "labels" for those choices: in genTree, choices are made randomly during the execution of the program and are marked by sides of a coin, while in parseTree the choices are made ahead of time and manifest as the characters in the input string. But this difference is rather superficial.
Free Generators. We can unify random generation with parsing by abstracting both into a single data structure. For this, we introduce free generators. 2 Free generators are syntactic structures (a bit like abstract syntax trees) that can be interpreted as programs that either generate or parse. Observe the structural similarities between fgenTree and the programs in Figure 1.
While the free generator fgenTree ℎ is just a data structure, its shape is much the same as genTree and parseTree. A Pure node in the free generator corresponds roughly to return; it represents a pure value that makes no choices. MapR takes two arguments, a free generator and a function that will eventually be applied to the result of generation / 1 Program synthesis experts might wonder why we represent generators as programs of this form, rather than, for example, PCFGs. Our work may very well translate to grammar-based generators, but we chose to target "applicative" generator programs because they are more expressive and more familiar for QuickCheck-style testing. 2 This document uses the knowledge package in L A T E X to make definitions interactive. Readers viewing the PDF electronically can click on technical terms and symbols to see where they are defined in the document. (fgenTree (ℎ − 1)))) ( (x , ( l , r )) → Node x l r )) ] parsing. The Pair constructor maps to sequencing the original programs: it generates / parses using its first argument, then does the same with its second argument, and finally pairs the results together. Finally-the real magic-lies in how we interpret the Select structure. When we want a generator, we treat it as making a uniform random choice, and when we want a parser we treat it as consuming a character and checking it against the first elements of the pairs. In §3 we give formal definitions of free generators, along with several interpretation functions. We write G⟦·⟧ for the generator interpretation of a free generator and P⟦·⟧ for the parser interpretation. In other words, G⟦fgenTree 5⟧ ≈ genTree 5 and P⟦fgenTree 5⟧ ≈ parseTree 5. Now let's consider how the generator and parser interpretations relate. The key lies in one final interpretation function, C⟦·⟧, which yields the choice distribution. Intuitively, the choice distribution interpretation produces the set of sequences of choices that the generator interpretation can make, or equivalently the set of sequences that the parser interpretation can parse.
The choice distribution interpretation is used below in Theorem 3.4 to connect parsing and generation. The theorem says that for any free generator , where ⟨$⟩ is a "mapping" operation that applies a function to samples from a distribution. Since many normal QuickCheck generators can also be written as free generators, another way to read this theorem is that such generators can be factored into two pieces: a distribution over choice sequences (given by C⟦·⟧), and a parser of those sequences (given by P⟦·⟧). This precisely formalizes the intuition that "A generator is a parser of randomness. " Derivatives of Free Generators. But wait, there's more! Since a free generator defines a parser, it also defines a formal language: we write L⟦·⟧ for this language interpretation of a free generator. The language of a free generator is the set of choice sequences that it can parse (or make).
Viewing free generators this way suggests some interesting ways that free generators might be manipulated. In particular, formal languages come with a notion of derivative, due to Brzozowski [1]. Given a language , the Brzozowski derivative of is That is, the derivative of with respect to is all the strings in that start with , with the first removed.
Conceptually, the derivative of a parser with respect to a character is whatever parser remains after has just been parsed. For example, the derivative of parseTree 5 with respect to n is: After parsing the character n, the next step in the original parser is to parse either t or f and then construct a Node; the derivative does just that.
Next let's take a derivative of the new parser n (parseTree 5)this time with respect to t: t n (parseTree 5) ≈ ← parseTree 4 ← parseTree 4 return Node True Now we have fixed the value True for , and we can continue by making the recursive calls to parseTree 4 and constructing the final tree.
Free generators have a closely related notion of derivative. The derivatives of the free generator produced by fgenTree look almost identical to the ones that we saw above for parse-Tree: Pure True ), (f, Pure False ) ]) ( Pair (fgenTree 4) (fgenTree 4))) ( (x , ( l , r )) → Node x l r ) t n (fgenTree 5) ≈ MapR ( Pair (fgenTree 4) (fgenTree 4)) ( ( l , r ) → Node True l r ) Moreover, like derivatives of regular expressions and contextfree grammars, derivatives of free generators can be computed by a simple syntactic transformation. In §4 we define a procedure for computing the derivative of a free generator and prove it correct, in the sense that, for all free generators , In other words, the derivative of the language of is equal to the language of the derivative of . (See Theorem 4.2.) Putting Free Generators to Work. The derivative of a free generator is intuitively the generator that remains after a particular choice. This gives us a way of "previewing" the effect of making a choice by looking at the generator after fixing that choice.
In §5 and §6 we present and evaluate an algorithm called Choice Gradient Sampling that uses free generators to address the valid generation problem. Given a validity predicate on a data structure, the goal is to generate as many unique, valid structures as possible in a given amount of time. Given a simple free generator, our algorithm uses derivatives to evaluate choices and search for valid values.
We evaluate our algorithm on four small benchmarks, all standard in the property-based testing literature. We compare our algorithm to rejection sampling-sampling from a naïve generator and discarding invalid results-as a simple but useful baseline for understanding how well or algorithm performs. Our algorithm does remarkably well on all but one benchmark, generating more than twice as many valid values as rejection sampling in the same period of time.

Free Generators
We now turn to developing the theory of free generators, beginning with some background on applicative abstractions for parsing and random generation.
Background: Applicative Parsers and Generators. In §2 we represented generators and parsers with pseudo-code.
Here we flesh out the details. We present all definitions as Haskell programs, both for the sake of concreteness and also because Haskell's abstraction features (e.g., typeclasses) allow us to focus on the key concepts. Haskell is a lazy functional language, but our results are also applicable to eager functional languages and imperative languages. We represent both generators and parsers using applicative functors [17] 3 At a high level, an applicative functor is a type constructor f with operations: When it might not be clear which applicative functor we mean, we prefix the operator with the name of the functor (e.g., Gen.⟨$⟩). These operations are mainly useful as a way to apply functions to values inside of some data structure or computation. For example, the idiom "g ⟨$⟩ x ⟨ * ⟩ y ⟨ * ⟩ z" applies a pure function g to the values in three structures x, y, and z.
We can use these operations to define genTree like we would in QuickCheck [4], since the QuickCheck type constructor Gen, which represents generators, is an applicative functor: genTree :: Int → Gen Tree genTree 0 = pure Leaf Here, pure is the trivial generator that always generates the same value, and Node ⟨$⟩ g1 ⟨ * ⟩ g2 ⟨ * ⟩ g3 means apply the constructor Node to three sub-generators to produce a new generator. Operationally, this means sampling x1 from g1, x2 from g2, and x3 from g3, and then constructing Node x1 x2 x3. Notice that we need one extra function beyond the applicative interface: oneof makes a uniform choice between generators, just as we saw in the pseudo-code. We can do the same thing for parseTree, using combinators inspired by libraries like Parsec [13]: parseTree :: In this context, pure is a parser that consumes no characters and never fails. It just produces the value passed to it. We can interpret Node ⟨$⟩ p1 ⟨ * ⟩ p2 ⟨ * ⟩ p3 as running each sub-parser in sequence (failing if any of them fail) and then wrapping the results in the Node constructor. Finally, we have replaced oneof with choice, but the idea is the same: choose between sub-parsers. Parsers like this have type String → Maybe (a, String ). They can be applied to a string to obtain either Nothing or Just (a, s ), where a is the parse result and s contains any extra characters.
Representing Free Generators. With the applicative interface in mind, we can now give the formal definition of a free generator. 4 Type Definition. We represent free generators as an inductive data type, FGen, defined as: These constructors form an abstract syntax tree with nodes that roughly correspond to the functions in the applicative interface. Clearly Pure represents pure. Pair is a slightly different form of ⟨ * ⟩; one is definable from the other, but this version makes more sense as a data constructor. Map corresponds to ⟨$⟩ (but note that the arguments to Map are flipped relative to MapR from §2). Finally, Select subsumes both oneof and choice: it might mean either, depending on the interpretation. Finally Void represents an always-failing parser or a generator of nothing. Free generators draw inspiration from free applicative functors [2]. As with free applicative functors, we can write transformations FGen a → f a for any f with similar structure. This fact motivates the rest of this section.
Language of a Free Generator. The language of a free generator is the set of choice sequences that it can make or parse. It is defined recursively, by cases: Smart Constructors and Simplified Forms. Free generators admit a useful simplified form. To ensure that generators are simplified, we can require that free generators be built using smart constructors.
In particular, instead of using Pair directly, we can pair free generators with the smart constructor ⊗ which makes sure that Void and Pure are collapsed with respect to Pair. For example, Pure a ⊗ Pure b collapses to Pure (a, b).
The smart constructor ⟨$⟩ is a version of Map that does similar collapsing: We define pure and ⟨ * ⟩ so as to make FGen an applicative functor: pure :: a → FGen a pure = Pure ( ⟨ * ⟩ ) :: The smart constructor Select looks like this: This smart constructor filters out any sub-generators that are Void (since those are functionally useless), and it fails (returning ⊥) if the final list of sub-generators is empty or if it has duplicated choice tags. This ensures that the operations on generators defined later in this section will be well formed.
Finally, we define a smart constructor void = Void for consistency.
When a generator is built using a finite tree of smart constructors, we say it is in simplified form. 5 Examples. We saw a version of fgenTree in §2 that was written out explicitly as an AST. Here's how it would actually be done in our framework, with smart constructors: fgenTree :: Int → FGen Tree fgenTree 0 = pure Leaf Recall that fgenTree is meant to subsume both genTree and parseTree. The height parameter ℎ is used to cut off the depth of trees and prevent the resulting free generators from being infinitely deep.
Here is another example of a free generator that produces random terms of the simply-typed lambda-calculus: 5 In strict languages, the finiteness requirement for simplified forms is needed because it guarantees that the program producing the free generator will terminate. In lazy languages, one can write infinite co-inductive data structures; nevertheless, we focus on finite free generators, because, in practice, one rarely wants to generate values of arbitrary size. 5 fgenExpr :: Int → FGen Expr Structurally this is quite similar to the previous generator; it just has more cases and more choices. This lambda calculus uses de Bruijn indices for variables and has integers and functions as values. This is a useful example because while syntactically valid terms in this language are easy to generate (as we just did), it is more difficult to generate only well-typed terms. We use this example as one of our case studies in §6.
Interpreting Free Generators. A free generator does not do anything on its own-it is simply a data structure. We next define the interpretation functions that we mentioned in §2 and prove a theorem linking those interpretations together.
Free Generators as Generators of Values. The first and most natural way to interpret a free generator is as a QuickCheck generator-that is, as a distribution over data structures. We define the generator interpretation of a free generator to be: Note that the operations on the right-hand side of this definition are not free generator constructors; they are QuickCheck generator operations. This definition maps "AST nodes" to the equivalent interpretation implemented by Gen. In the case for Pair, notice the pattern that we described earlier in this section. The code ( x y → (x , y )) Gen.⟨$⟩ G⟦x⟧ Gen.⟨ * ⟩ G⟦y⟧ pairs the results of G⟦x⟧ and G⟦y⟧ in a tuple via applicative idiom "g ⟨$⟩ x ⟨ * ⟩ y". One detail worth noting is that the interpretation behaves poorly (it diverges) on Void; fortunately, the following lemma shows that this does not cause problems in practice: Proof. By induction on the structure of and inspection of the smart constructors. □ Thus we can conclude that, as long as is in simplified form and not Void, G⟦ ⟧ is defined.
Free Generators as Parsers of Choice Sequences. Now we come to the main technical point of the paper. We can make use of the character labels in the Select nodes using a free generator's parser interpretation-in other words, we can view a free generator as a parser of choices. The translation looks like this: This definition uses the representation of parsers as functions of type String → Maybe (a, String ) that we saw earlier.
Free Generators as Generators of Choice Sequences. Our final interpretation of free generators captures the part of the generator "missed" by the parser-it represents the distribution with which the generator makes choices. We define the choice distribution of a free generator to be: We can think of the result of this interpretation as a distribution over L⟦ ⟧. The language of a free generator is exactly those choice sequences that the generator interpretation can make and the parser interpretation can parse.
Factoring Generators. These different interpretations of free generators are closely related to one another; in particular, we can reconstruct G⟦·⟧ from P⟦·⟧ and C⟦·⟧. In essence, this means that a free generator's generator interpretation can be factored into a distribution over choice sequences plus a parser of those sequences.
To make this more precise, we need a notion of equality for generators like the ones produced via G⟦·⟧. We say two QuickCheck generators are equivalent, written 1 ≡ 2 , if and only if the generators represent the same distribution over values. This is coarser notion than program equality, since two generators might produce the same distribution of values in different ways.
With this in mind, we can state and prove the relationship between different interpretations of free generators: This corollary gives a concrete way to view the connection between applicative generators and parsers.
Replacing a Generator's Distribution. Since a generator can be factored using C⟦·⟧ and P⟦·⟧, we can explore what it would look like to modify a generator's distribution (i.e., change or replace C⟦·⟧) without having to modify the entire generator.
Suppose we have some other distribution that we want our choices to follow. We can represent an external distribution as a function from a history of choices to a generator of next choices, together with a "current" history. We write this type as: type Dist = ( String , String → Gen (Maybe Char)) (If the choice function returns Nothing, then generation stops.) A Dist may be arbitrarily complex: it might contain information obtained from example-based tuning, a machine learning model, or some other automated tuning process. How would we use such a distribution in place of the standard distribution given by C⟦·⟧?
The solution is to replace C⟦·⟧ with our new distribution to yield a modified definition of the generator interpretation: This definition exploits our new connection between parsers and generators to obtain a new generator interpretation via the parser interpretation.
Since replacing a free generator's distribution does not actually change the structure of the generator, we can have a different distribution for each use-case of the free generator. In a property-based testing scenario, one could imagine the tester fine-tuning a distribution for each property, carefully optimized to find bugs as quickly as possible.

Derivatives of Free Generators
Next, we review the notion of Brzozowski derivative in formal language theory and show that a similar operation exists for free generators. The way these derivatives fall out from the structure of free generators highlights the advantages of taking the correspondence between generators and parsers seriously.
Background: Derivatives of Languages. The Brzozowski derivative [1] of a formal language with respect to some choice is defined as In other words, the derivative is the set of strings in with removed from the front. For example, a {abc, aaa, bba} = {bc, aa}. Many formalisms for defining languages support syntactic transformations that correspond to Brzozowski derivatives.
For example, we can take the derivative of a regular expression like this: The operator, used in the "·" rule and defined on the right, determines the nullability of an expression (whether or not it accepts ). As one would hope, if has language , it is always the case that has language .
The Free Generator Derivative. Since free generators define a language (given by L⟦·⟧), can we take their derivatives? Yes, we can! The derivative of a free generator with respect to a character , written ( ), is defined as follows: : Most of this definition should be intuitive. The derivative of a generator that does not make a choice (i.e., Void and Pure) is void, since the corresponding language would be empty. The derivative commutes with Map since the transformation affects choices, not the final result. Select 's derivative is just the argument generator corresponding to the appropriate choice.
The one potentially confusing case is the one for Pair. We have defined the derivative of a pair of generators by taking the derivative of the first generator in the pair and leaving the second unchanged, which seems inconsistent with the case for "·" in the regular expression derivative (what happens when the first generator's language is nullable?). Luckily, our simplified form clears up the confusion: if Pair x y is in simplified form, x is not nullable. This is a simple corollary of Lemma 4.1.

Proof sketch. See Appendix A. □
Note that the derivative of a simplified generator is simplified. This follows simply from the definition, since we only use smart constructors and parts of the original generator to build the derivative generators. By induction, this also means that repeated derivatives preserve simplification.
Besides clearing up the issue with Pair, Lemma 4.1 also says that we can define nullability for free generators simply as: :: FGen a → Set a (Pure v) = {v} g = ∅ (g ≠ Pure v) Note that we get a bit more information here than we do from regular expression nullability. For a regular expression , is either ∅ or . Here, we allow the null check to return either ∅ or the singleton set containing the value in the Pure node. This means that for free generators extracts a value that can be obtained by making no further choices.
Our definition of derivative acts the way we expect:

Proof sketch. By induction (see Appendix C). □
This theorem says that the derivative of a free generator's language is the same as the language of its derivative.
Besides consistency with respect to the language interpretation, the derivative operation should preserve the generator output for a given sequence of choices. If a free generator chooses ntll to yield Node True Leaf Leaf, we would like for the derivative of that free generator with respect to n to produce the same value after choosing tll. We can formalize this expectation via the parser interpretation: The upshot of this theorem is that derivatives do not fundamentally change the results of a free generator, they only fix a particular choice.
These two consistency theorems together mean that we can simulate a free generator's choices by taking repeated derivatives. Each derivative fixes a particular choice, so a sequence of derivatives fixes a choice sequence.

Generating Valid Results with Gradients
We now put the theory of free generators and their derivatives into practice. We introduce Choice Gradient Sampling (CGS), an algorithm for generating data that satisfies a validity condition.
The Algorithm. Given a simple free generator, Choice Gradient Sampling "previews" its choices using derivatives.
In fact, it previews all possible choices, essentially taking the gradient of the free generator. (This is akin to the gradient in calculus, which is a vector of partial derivatives with respect to each variable.) We write for the gradient of with respect to alphabet {a, b, c}. Each derivative in the gradient can then be sampled, using G⟦·⟧, to get a sense of how good or bad the respective choice was. This provides a metric that guides the algorithm toward valid inputs.
With this intuition in mind, we present the CGS algorithm, shown in Figure 4, which searches for valid results using repeated free generator gradients. if max ∈ = 0 then 16: for ∈ do ← 1 17: weightedChoice {( , ) | ∈ } Figure 4. Choice Gradient Sampling: Given a free generator in simplified form, a sample rate constant , and a validity predicate , this algorithm produces a set of outputs that all satisfy ( ).
The intuition from earlier plays out in lines 7-14, and is shown pictorially in Figure 5. We take the gradient of by taking the derivative with respect to each possible choice, in this case a, b, and c. Then we evaluate each of the derivatives by interpreting the free generator with G⟦·⟧, sampling values from the resulting generator, and counting how many of those results are valid with respect to . The precise number of samples is controlled by , the sample rate constant; this is up to the user, but in general higher values for will give better information about each derivative at the expense of time spent sampling. At the end of sampling, we have values a , b , and c , which we can think of as the "fitness" of each choice. We then pick a choice randomly, weighted based on fitness, and continue until our choices produce a valid output. Critically, we avoid wasting effort by saving the samples (V) that we use to evaluate the gradients. Many of those samples will be valid results that we can use, so there is no reason to throw them away.
Modified Distributions. Interestingly, this algorithm works equally well for free generators whose distributions have been replaced (as discussed in §3). Recall that we modify the distribution of a free generator by pairing it with a pair of a history ℎ and a distribution function . We can define the derivative of such a structure to be: We take the derivative of and internalize into the distribution's history. Furthermore, we can say that a modified generator's nullable set is the same as the nullable set of the underlying generator.
These definitions, along with the ones in §3, are enough to replicate Choice Gradient Sampling for a free generator with an external distribution.

Exploratory Evaluation
This paper is primarily about the theory of free generators and their derivatives, but readers may be curious (as we were) to see how well Choice Gradient Sampling performs on a few property-based testing benchmarks. In this section, we describe some preliminary experiments in this direction; the results suggest that, with a few interesting caveats, CGS is a promising approach to the valid generation problem.
Experimental Setup. Our experiments explore how well CGS improves on the base, naïve generator by comparing it to rejection sampling, which takes a naïve generator, samples from it, and discards any results that are not valid. Rejection sampling is the default method that QuickCheck uses for properties with preconditions when no bespoke generator is available, and makes for a clean baseline that we can compare CGS to.
We use four simple free generators to test four different benchmarks: BST, SORTED, AVL, and STLC. Details about each of these benchmarks are given in Table 1.
Each of our benchmarks requires a simple free generator to act as a baseline and as a starting point for CGS. For consistency, and to avoid potential biases, our generators follow the respective inductive data types as closely as possible. For example, fgenTree, shown in §3 and used in the BST benchmark, follows the structure of Tree exactly. We chose values for via trial and error in order to balance fitness accuracy with sampling time.
Results. We ran CGS and Rejection on each benchmark for one minute (on a MacBook Pro with an M1 processor and 16GB RAM) and recorded the unique valid values produced. We counted unique values because duplicate tests are generally less useful than fresh ones (in property-based testing of pure programs, in particular, duplicate tests add no value). The totals, averaged over 10 trials, are presented in Table 2.
These measurements show that CGS is always able to generate more unique values than Rejection in the same amount of time, and it often generates significantly more. (The exception is the AVL benchmark; we discuss this below.) Besides unique values, we measured some other metrics; the charts in Figure 6 give some deeper insights for the STLC benchmark. The first plot ("Unique Terms over Time") shows that, after one minute, CGS has not yet begun to "run out" of unique terms to generate. Additionally "Normalized Size Distribution" chart shows that CGS also generates larger terms on average. This is good from the perspective of property-based testing, where test size is often positively correlated with bug-finding power, since larger test inputs tend to exercise more of the implementation code. Charts for the remaining benchmarks are in Appendix E.
Measuring Diversity. When testing, we care about more than just the number of valid test inputs generated in a period of time-we care about the diversity of those inputs, since a more diverse test suite will find more bugs more quickly.
Our diversity metric relies on the fact that each value is roughly isomorphic to the choice sequence that generated it. For example, in the case of BST, the sequence n5l6ll can be parsed to produce Node 5 Leaf (Node 6 Leaf Leaf) and a simple in-order traversal can recover n5l6ll again. Thus, choice sequence diversity is a reasonable proxy for value diversity.
We estimated the average Levenshtein distance [14] (the number of edits needed to turn one string into another) between pairs of choice sequences in the values generated by each of our algorithms. Computing an exact mean distance between all pairs in such a large set would be very expensive, Figure 6. Unique values and term sizes for the STLC benchmark (first trial). so we settled for the mean of a random sample of 3000 pairs from each set of valid values. The results are summarized in Table 3.
While SORTED does see significantly improved diversity, the effect is less dramatic STLC and BST, and diversity for AVL actually gets slightly worse.
One explanation for these lackluster results rests on the way CGS retains intermediate samples. While the first few samples will be mostly uncorrelated, the samples drawn later on in the generation process (once a number of choices have been fixed) will tend to be similar to one another. This likely results in some clusters of inputs that are all valid but that only explore one particular shape of input.
Of course, is already common practice to test clusters of similar inputs in certain fuzzing contexts [11], so the fact that CGS does this is not unusual. In fact, this method has been shown to be effective at finding bugs in some cases. Additionally, for most of our benchmarks (again, we return to AVL in a moment) CGS does increase diversity of tests; combined with the sheer number of valid inputs available, this means that CGS covers a slightly larger space of tests much more thoroughly. This effect should lead to better bugfinding in testing scenarios.
The Problem with AVL. The AVL benchmark is an outlier in most of these measurements: CGS only manages to find a modest number of extra valid AVL trees, and their pairwise  Table 3. Average Levenshtein distance between pairs of choice sequences (first trial). diversity is actually slightly worse than that of rejection sampling. Why might this be? We suspect that this effect arises because AVL trees are quite difficult to find randomly. Balanced binary search trees are hard to generate on their own, and AVL trees are even more difficult because the generator must guess the correct height to cache at each node. This is why rejection sampling only finds 156 AVL trees in the time it takes to find 9,762 binary search trees.
This all means that CGS is unlikely find any valid trees while sampling. In particular, the check in line 15 of Figure 5 will often be true, meaning that choices will be made uniformly at random rather than guided by the fitness of the appropriate derivatives. We could reduce this effect by significantly increasing the sample rate constant , but then sampling time would likely dominate generation time, resulting in worse performance overall.
The lesson here seems to be that the CGS algorithm does not work well with especially hard-to-satisfy predicates. In §8, we present an idea that would do some of the hard work ahead of time and help with this issue, but clearly many predicates (including complex ones like well-typedness of STLC terms) are within reach of the current algorithm. Indeed, as long as every samples from the naïve generator has at least a few valid values on average, the AVL issue will not come up. We expect that many real-world structural and semantic constraints will require a small enough for CGS to be effective.

Related Work
We discuss a number of approaches that are similar to ours, via either connections to free generators or connections to our Choice Gradient Sampling algorithm.
Parsing and Generation. The connection between parsers and generators is not just "intellectual folklore"-it is used in some implementations too. At least two popular propertybased testing libraries, Hypothesis [16] and Crowbar [6], implement generators by parsing a stream of random bits (and there may very well be others that we do not know of.) This further illustrates the value in formalizing the connection between parsers and generators, as a way to explain existing implementations uncover potential opportunities.
The Clotho [5] library introduces "parametric randomness, " providing a way to carefully control generator choices from outside of the generator. While Darragh et al. do not use parsing in their formalism, it is still exciting to see others considering the implications of controlling generator choices externally.
Free Applicative Generators. Claessen et al. [3] present a generator representation that is structurally similar to our free generators, but which is used in a very different way. They primarily use the syntactic structure of their generators (they call them "spaces") to control the size distribution of generated outputs; in particular, spaces do not make choice information explicit in the way free generators do. Claessen et al.'s generation approach uses Haskell's laziness, rather than derivatives and sampling, to prune unhelpful paths in the generation process. This pruning procedure performs well when validity conditions are written to take advantage of laziness, but it is highly dependent on evaluation order and it does not differentiate between generator choices that are not obviously bad. In contrast, CGS respects observational equivalence between predicates and uses sampling to weight next choices.
The Valid Generation Problem. Many other approaches to the valid generation problem have been explored.
The domain-specific language for generators provided by the QuickCheck library [9] makes it easier to write manual generators that produce valid inputs by construction. This approach is extremely general, but it can be labor intensive. In the present work, we avoid manual techniques like this in the hopes of making property-based testing more accessible to programmers that do not have the time or expertise to write their own custom generators.
The Luck [10] language provides a sort of middle-ground solution; users are still required to put in some effort, but they are able to define generators and validity predicates at the same time. Luck provides a satisfying solution if users are starting from scratch and willing to learn a domain-specific language, but if validity predicates have already been written or users do not want to learn a new language, a more automated solution is preferable.
When validity predicates are expressed as inductive relations, approaches like the one in Generating Good Generators for Inductive Relations [12] are extremely powerful. Unfortunately, most programming languages cannot express inductive relations that capture the kinds of preconditions that we care about.
Target [15] uses search strategies like hill-climbing and simulated annealing to supplement random generation and significantly streamline property-based testing. Löscher and Sagonas's approach works extremely well when inputs have a sensible notion of "utility, " but in the case of valid generation the utility is often degenerate-0 if the input is invalid, and 1 if it is valid-with no good way to say if an input is "better" or "worse. " In these cases, derivative-based searches may make more sense.
Some approaches use machine learning to automatically generate valid inputs. Learn&Fuzz [7] generates valid data using a recurrent neural network. While the results are promising, this solution seems to work best when a large corpus of inputs is already available and the validity condition is more structural than semantic. In the same vein, RLCheck [18] uses reinforcement learning to guide a generator to valid inputs. This approach served as early inspiration for our work, and we think that the theoretical advance of generator derivatives may lead improved learning algorithms in the future (see §8).

Future Directions
There are a number of exciting paths forward from this work; some continue our theoretical exploration and others look towards algorithmic improvements.
Bidirectional Free Generators. We believe that we have only scratched the surface of what is possible with free generators. One concrete next step is to merge the theory of free generators with the emerging theory of ungenerators [8]. Goldstein expresses generators that can be run both forward (to generate values as usual) and backward. In the backward direction, the program takes a value that the generator might have generated and "un-generates" it to give a sequence of choices that the generator might have made when generating that value.
Free generators are quite compatible with these ideas, and turning a free generator into a bidirectional generator that can both generate and ungenerate should be fairly straightforward. From there, we can build on the ideas in the ungenerators work and use the backward direction of the generator to learn a distribution of choices that approximates some user-provided samples of "desirable" values. Used in conjunction with the extended algorithm from §5, this would give a better starting point for generation with little extra work from the user.
Algorithmic Optimizations. In §6, we saw some problems with the Choice Gradient Sampling algorithm: because CGS evaluates derivatives via sampling, it does poorly when validity conditions are particularly difficult to satisfy. This begs the question: might it be possible to evaluate the fitness of a derivative without naïvely sampling?
One potential angle involves staging the sampling process. Given a free generator with a depth parameter, we can first evaluate choices on generators of size 1, then evaluate choices with size 2, etc. These intermediate stages would make gradient sampling more successful at larger sizes, and might significantly improve the results on benchmarks like AVL. Unfortunately, this kind of approach might perform poorly on benchmarks like STLC where the validity condition is not uniform: size-1 generators would avoid generating variables, leading larger generators to avoid variables as well. In any case, we think this design space is worth exploring.
Making Choices with Neural Networks. Another algorithmic optimization is a bit farther afield: we think it may be possible to use recurrent neural networks (RNNs) to improve our generation procedure.
As Choice Gradient Sampling makes choices, it generates useful data about the frequencies with which choices should be made. Specifically, every iteration of the algorithm produces a pair of a history and a distribution over next choices that looks something like abcca ↦ → {a : 0.3, b : 0.7, c : 0.0}.
In the course of CGS, this information is used once (to make the next choice) and then forgotten-what if there was a way to learn from it? Pairs like this could be used to train an RNN to make choices that are similar to the ones made by CGS.
There are still details to work out, including network architecture, hyper-parameters, etc., but in theory we could run CGS for a while, then train the model, and after that point only use the RNN to generate valid data. Setting things up this way would recover some of the time that is currently wasted by the constant sampling of derivative generators.
One could imagine a user writing a definition of a type and a predicate for that type, and then setting the model to train while they work on their algorithm. By the time the algorithm is finished and ready to test, the RNN model would be trained and ready to produce valid test inputs. A workflow like this could significantly increase adoption of property-based testing in industry.
Free generators and their derivatives are powerful structures that give a unique and flexible perspective on random generation. Our formalism yields a useful algorithm and clarifies the folklore that a generator is a parser of randomness.

B Proof of Theorem 3.4
Lemma B.1. Pairing two parser interpretations and mapping over the concatenation of the associated choice distributions is equal to a function of the two parsers mapped over the distributions individually. Specifically, for all simplified free generators x and y, Proof. First, note that for any simplified generator, , if C⟦ ⟧ generates a string , for any other string P⟦ ⟧ ( · ) = Just ( , ) for some value . This can be shown by induction on the structure of . Now, assume C⟦x⟧ generates a string , and C⟦y⟧ generates . This means that (·) ⟨$⟩ C⟦x⟧ ⟨ * ⟩ C⟦y⟧ generates · . By the above fact, it is simple to show that both sides of the above equation simplify to Just (( , ), ) for some values and that depend on the particular interpretations of x and y.
Since this is true for any and that the choice distributions generate, the desired fact holds. □ Thus we have shown that the symbolic derivative of free generators is compatible with the derivative of the generator's language. □ There is another proof of this theorem, suggested by Alexandra Silva, which uses the fact that 2 Σ * is the final coalgebra, along with the observation that FGen has a 2 × (−) Σ coalgebraic structure. This approach is certainly more elegant, but it abstracts away some helpful operational intuition.