Old Confluence Notes

These notes were hastily exported from dev.clojure.org on 2019-04-24.

Formatting was mostly preserved, except that bulleted lists ended up as preformatted text.

Main Page

Some old and largely outdated design ideas for test.check.

API Overhaul Ideas

Responding to TCHECK-99 got me thinking about trying to pull off a complete redesign of the (mostly generators) API, while maintaining as much backwards compatibility as possible, at least for a few versions.

I'm going to try to list here the sorts of problems that could be fixed with such an overhaul that would be hard to fix otherwise.

Generators
    Convert all generators to be functions; if a default generator is available, it would be obtained by calling the function with 0 args
        Removes confusion such as with the current pair of large-integer and large-integer*
    Get rid of nat, pos-int, s-pos-int, and similar. Replace with a generator called small-integer that takes various options
    rename large-integer to integer, consider whether to allow bigints
    change gen/vector and gen/list APIs to match gen/set
    Maybe allow passing options when calling a generator, so that generators like strings and doubles can be customizable in a different way
        e.g., this way a generator like gen/any could support being customized to never generate NaNs anywhere without having to explicitly code for that
clojure-test
    change defspec to use clojure.test/is
        can maybe do this w/o breaking changes by putting an alternative to prop/for-all in the clojure-test namespace???
Properties

Numerics

The situation here used to be much worse, when all of the integer generators would only generate numbers up to ~200 by default, and no double generator existed at all. Now we have gen/large-integer which does well for large ranges of integers, and gen/double which is also pretty good. The remaining holes are relatively minor:

numbers from infinite sets
    a generator for bigints; unclear if this would require bounds or not
    a good generator for ratios; again unclear about bounds, both on abs value and on denominator size
    bigdecimals
some lower-level utility generators
    a generator for doubles between 0 and 1
    a raw generator of evenly-distributed longs

What is a solid approach to generating infinite-domain types?

In particular bigints, ratios, bigdecimals, and maybe even collections.

One idea I had was a generator that always has a non-zero probability of generating any given value, and the size parameter determines the average size of the thing generated (e.g., in bits). I think this means that the size of the output, at least to start, would have a geometric distribution.

How should NaNs be handled?

Background

gen/double and gen/double* generate NaN, at least by default. This is intentional, since NaN is a useful edge case to test for any code that deals with doubles. However NaN != NaN, which means that any data structure containing a NaN is not equal to itself, which screws up all sorts of things.

This isn't such a problem for gen/double, since users can opt-out of NaNs with gen/double* when appropriate. However, gen/simple-type, gen/simple-type-printable, gen/any, and gen/any-printable are all affected by this in 0.9.0.

Possible Approaches

Modify generators in-place
    Just the four composite generators (gen/simple-type{-printable} and gen/any{-printable})
    gen/double doesn't generate NaN, and gen/double* allows it as opt-in
Add new generators
    Analogues of the four composite, or some subset (gen/simple-type-no-NaN, gen/any-no-NaN, etc.)
Something else?
    arguably users can manage this on their own, although excluding NaN from gen/any is not so simple, since a naïve wrapping in gen/such-that won't work

Test Runner Topics

Test Failure Feedback

Currently a test error (i.e., exception caught) gives ample feedback because the user gets the exception object to inspect, but a mere failure (falsy return value) doesn't communicate anything other than whether the result was false or nil. clojure.test goes farther for this, with a probably-overly-macrocentric approach.

Probably the best approach is to evaluate the result of a property expression with a protocol, so the current behavior can be maintained but new implementations can provide more information.

I think reid has already started in this direction on the "feature/result-map" branch

Related: https://github.com/yeller/matcha and this alternate clojure.test integration.

Parallel Tests

Requires the immutable RNG for full determinism.

Do we actually need complex coordination of threads or can we do a naive thing?

Rerunning a single test easily

Running tests for a specific amount of time

Related: test.chuck/times, and a branch that Tom Crayford worked on

Some ideas from Hypothesis

From this (http://www.drmaciver.com/2015/01/using-multi-armed-bandits-to-satisfy-property-based-tests/) blog post primarily. The library itself is here.

It essentially uses a rather more sophisticated approach to getting more interesting distributions.

Idea for trying this out: have each generator keep track of how many size parameters it can accept. E.g., gen/int takes one size parameter. (gen/list gen/int) takes two (one for the size of the list, one for the size given to gen/int). (gen/tuple g1 g2 g3) takes the sum of the size-parameter-counts for its args. This breaks down when using bind and recursive generators, so we might have to fall back on just passing an infinite number of size parameters, or using the RNG to determine them, or something like that.

On the other hand, I spoke to David directly about this feature and he says he regrets including it in hypothesis due to the high complexity and low value. I didn't ask why he thought it was low value.

Orchestrating Concurrent (and distributed?) Programs

The point being to test them deterministically, and to test different possible linearizations to look for concurrency bugs.

Testing Generators, Regression Tests

Several related topics:

How do we validate that a generator is likely to generate certain kinds of things?
How could we collect stats about the sorts of things generated?
When we find a rare failing test, is there an easy way to ensure that such cases are generated more often?

Need to research other QC impls.

Generator Syntax Sugar

We ended up adding gen/let for this, but test.chuck/for is still fancier and especially useful for tuples.

Shrinking Topics

Check other QC impls for all of this.

Can we use more specialized generators to minimize the need for bind?

There was an example somewhere of trying to generate a 2d vector, where doing it without bind seemed impossible but bind caused it to shrink poorly.

Also see "Stateful Generators" elsewhere on this page.

Should shrink-resumption be part of the API?

Custom shrinking algorithms?

Advanced Generators

"Stateful" Generators

There are common use cases for being able to generate sequences of events, where each event can affect what future events are possible. Perhaps the most natural is modeling a collection of records with create/update/delete events, where you can only have an update or delete for a record that already exists (and no updates on a deleted record).

This can be done pretty easily with a recursive generator that uses gen/bind at each step, but this comes at the huge expense of almost entirely thwarting the shrinking process. It would be great to devise some general way of constructing these sorts of generators that also shrinks well. This seems easier for special cases like the record-set case described above, but difficult in the general case.

Single Set of Independent Records

A specialized generator that takes as input args similar to gen/hash-map (i.e., a description of what keys a record has and generators for each of the keys) and shrinks reasonably well should be possible to write, especially if there are no constraints beyond the ordering of the create/update/delete for individual records.

There would be custom low-level generator code that avoids using gen/bind, paired with custom shrinking code. The shrinking part might only have to ensure that if a shrink removes a "create" event that it deletes all subsequent events for that record. There might also have to be a reified "id" that doesn't shrink or else shrinks all references to an id in unison.

Full Relational Dataset

This would be like the previous example, but would involve multiple datasets ("tables") and relationships between them ("foreign keys"). The tricky part would be intelligent handling of foreign keys. If a record's relative disappears, the shrinking code would manually do cascading deletes when necessary (or perhaps divert foreign keys to other records when that makes sense).

General Problem

The only natural framing of the general problem that I can think of is a generator such as:

(defn gen-events
  "Given an init-state and a reduce function for determining the
  current state from a sequence of events, together with a function
  that takes a state and returns a generator of a new event, returns
  a generator of sequences of events."
  [reduce-func init-state state->event-gen]
  ...)

It seems difficult to find a general way to layer smart shrinking on top of this sort of API, since any change to earlier events could potentially require arbitrary changes to future events, and I'm not sure how to build in a way of allowing the user to specify those changes.

One idea is to take an additional argument, a function that receives an event that was previously generated and a new state that is the precursor to that event. The function can choose to leave the event as-is (if it's still valid in the new state), apply return a function suitable for use with fmap (if the event can be easily adjusted to the new state), or signal that the event should be removed altogether. I think this should be sufficient for implementing the two dataset examples above, but I'm not sure whether it works for more complex uses.

Breaking Changes Fantasy

If we decided to make a large breaking-changes release, what would we include?

Rename the pos-int/s-pos-int style functions
Change the arg order for bind? It's awkward that it's opposite fmap
Change the multi-clause behavior of prop/for-all?
    Currently can't integrate test.chuck/for w/ prop/for-all support without breaking this

Old/Obsolete Notes

Things that are done or decided against.

Immutable RNG

I think we need to do some more performance checks. Ideas for things to look into:

How does linear generation with java.util.SplittableRandom compare to JUR and IJUSR? Knowing this should give us an idea if the slowdown with IJUSR is more about the algorithm or immutability
    Seems to be entirely about immutability. E.g., JUSR is actually slightly faster with JUR, even after removing concurrency from JUR.
Can we squeeze any extra performance by using a more specialized API anywhere?
    Like split-n
        This is looking like the most promising
Can we generate batches of numbers faster than the more general splitting method? If so, can we take advantage of that cleanly in the generators?
    E.g., you could linearly generate 256 longs, put them in an immutable array, and have the RNG reference a range of that array. rand-long returns the first number in the range, splitting returns two objects with the range cut in half. Splitting a singleton range triggers another array creation. I think there are still some subtleties to work out though.
    It's also worth noting that the splittable API involves twice as many allocation as a linear-immutable API (see split-n idea above)
Is the macro usage subverting inlining?
Is the long->double->int process taking a while?
Try using an unrolled pair (ztellman style) for the return value from split

Some code for messing with this stuff is on this branch.

Generators Reboot

This is a list of problems that can be addressed to some extent by creating a new generators-2 namespace.

For each problem, there is a proposed solution with and without adding a new namespace.

Under every "WITHOUT Reboot" section, there is an implicit alternative to do nothing.

Many generators have confusing names
    E.g., monadic names (return, fmap, bind), and others (elements, hash-map, one-of)
    WITH Reboot
        Pick better names
    WITHOUT Reboot
        Add aliases and mark the old names as deprecated
Difference between a var referring to a generator vs a function that returns a generator can be error-prone for users, and leads to a duplication of names like gen/double and gen/double* to allow for options to be passed
    WITH Reboot
        Make every var a function that returns a generator
    WITHOUT Reboot
        Add an IGenerator protocol so that vars like gen/double can be backwards-compatibly changed to functions that can act as generators in a deprecated manner (with optional warnings?)
Options API is inconsistent
    Some functions take an options map, others have similar options as positional args
    WITH Reboot
        every generator should take an options map, as an optional argument after all of the required args
    WITHOUT Reboot
        Modify signatures with backwards compatible support for the deprecated signatures
Built-in composite generators like gen/any do not allow customizing the underlying base generators – most notably, you cannot ask gen/any to avoid generating NaNs (but with more options on other base generators this would be a more general problem)
    WITH Reboot
        These generators would be functions and could therefore pass options down to their constituent generators
    WITHOUT Reboot
        Do the "WITHOUT Reboot" steps in the previous two points, and then do the same thing we would do in a reboot
Integer generators need overhauling
    There are a lot and some are misleadingly named. They could all be collapsed into a single generator with rich options for specifying the distribution
    WITH Reboot
        Make a single gen2/integer
    WITHOUT Reboot
        Make gen2/integer and deprecate all the others
gen/bind has confusing argument order
    Every other combinator takes the generator as its last argument
    WITHOUT Reboot
        Accept args in either order? This could be ambiguous if we also convert everything to functions but allow the functions to be used as generators
    WITH Reboot
        Change the arg order in the new function
String generators are pretty basic
    the non-ascii generators use a fixed small range of non-ASCII unicode characters
    WITHOUT Reboot
        Add a new string generator that takes options for distribution, deprecate all the old ones
    WITH Reboot
        Add a new string generator that takes options
Collection sizing is bad
    Collection generations naïvely result in the expected size of the generated value being N times larger than the expected size from the element generator
    A better situation would perhaps involve
        Collection generators that reduce the `size` used for their elements according to some rule, perhaps based on the expected size of the collection
        Some sort of in-place accounting for how much stuff is being generated as it goes, so that the size can be suppressed further if the value is getting too big, mitigating the risk of the largest 0.001% of values being OOMly large
        Standard options for users to have more control of the above behavior
    WITHOUT Reboot
        Change built-in generators in place to effect the above solution (should this be considered a breaking change, if old calls still work but perhaps generate different distributions?)
        Create new collection generators according to the above solution and deprecate the old ones
    WITH Reboot
        New collection generators according to the above solution

quickcheck refactoring

This is a hopefully temporary page, tracking evaluation of Nico's proposed refactoring and any alternatives and related issues.

Organized as (nested) list of questions.

What problem are we trying to solve?
    A general change to allow an implementation of a variety of useful features (in test.check directly or by users/libraries):
        async tests
        statistics
        time-bounded runs, time-bounded shrinks
        more speculatively, pausing and resuming shrinks
    Note that we shouldn't assume we have to solve all these problems with the same changes, but if a change simultaneously enables all of them, that could be considered evidence in its favor
How do other quickchecks do any of those things?
    At least
        Hedgehog
        Proper
    Optionally
        Quickcheck
        Hypothesis
Nico's solution
    My general concern is that it changes the public API, so we have to get it right, and it seems to allow a lot of undefined/strange things, since the user's supplied function could return whatever it wants; e.g., it could return a structure that's inconsistent or sends the algorithm to an unexpected state
    I'm also wondering how it composes; e.g., if the stats library provides one implementation of the state transition function, and the user provides another for limiting shrink time, how do you combine those functions together? does `comp` work? is it commutative?