[klntsky]

It seems to only implement a half of QuickCheck idea, because there is no counterexample shrinking. Good effort though! I wonder how hard would it be to derive generators for any custom types in python - probably not too hard, because types are just values

[sunshowers]

Shrinking is by far the most important and impressive part of Hypothesis. Compared to how good it is in Hypothesis, it might as well not exist in QuickCheck.

Proptest in Rust is mostly there but has many more issues with monadic bind than Hypothesis does (I wrote about this in https://sunshowers.io/posts/monads-through-pbt/).

[eru]

Python's Hypothesis has some very clever features to deal with shrinking past a monadic bind.

If I remember right, it basically uses a binary 'tape' of random decisions. Shrinking is expressed as manipulations of that tape. Your generators (implicitly) define a projection from that tape to your desired types. Shrinking an early part of the tape, leave the later sub-generators to try and re-use the later parts of the tape.

That's not guaranteed to work. But it doesn't have to work reliably for every shrink operation the library tries! It's sufficient, if you merely have a good-enough-chance to recover enough of the previous structure to trigger the bug again.

[ctenb]

> Shrinking is expressed as manipulations of that tape.

How do you do that in general? I can't find any documentation on that.

[sunshowers]

This paper by the Hypothesis authors has some information: https://www.doc.ic.ac.uk/~afd/papers/2020/ECOOP_Hypothesis.p...

[sunshowers]

I've always wondered if there could be a small machine learning model trained on shrinking.

[eru]

I'm not sure whether it would be useful, but it would definitely get you a grant (if done academically) or VC money (if done as a company) these days.

[Jtsummers]

> because there is no counterexample shrinking

Hypothesis does shrink the examples, though.

[eru]

And Hypothesis is miles ahead of QuickCheck in how it handles shrinking! Not only does it shrink automatically, it has no problem preserving invariants from generation in your shrinking; like only prime numbers or only strings that begin with a vowel etc.

[lgas]

QuickCheck also shrinks automatically and preserves invariants though?

[eru]

Others have pointed out that QuickCheck doesn't shrink automatically. But in addition: QuickCheck's shrinking also doesn't preserve invariants (in general).

QuickCheck's shrinking is type based. There's lots of different ways to generate eg integers. Perhaps you want them in a specific range, or only prime numbers or only even numbers etc. To make QuickCheck's shrinker preserve these invariants, you'd have make a typed wrapper for each of them, and explicitly write a new shrinking strategy. It's annoying and complicated.

Hypothesis does this automatically.

[chriswarbo]

QuickCheck won't preserve invariants, since its shrinkers are separate from its generators. For example:

    data Rat = Rat Int Nat deriving (Eq, Show)

    genRat = do
      (num, den) <- arbitrary
      pure (Rat num (1 + den))

`genRat` is a QuickCheck generator. It cannot do shrinking, because that's a completely separate thing in QuickCheck.

We can write a shrinker for `Rat`, but it will have nothing to do with our generator, e.g.

    shrinkRat (Rat num den) = do
      (num', den') <- shrink (num, den)
      pure (Rat num' den')

Sure, we can stick these in an `Arbitrary` instance, but they're still independent values. The generation process is essentially state-passing with a random number generator; it has nothing to do with the shrinking process, which is a form of search without backtracking.

    instance Arbitrary Rat where
      arbitrary = genRat
      shrink = shrinkRat

In particular, `genRat` satisfies the invariant that values will have non-zero denominator; whereas `shrinkRat` does not satisfy that invariant (since it shrinks the denominator as an ordinary `Nat`, which could give 0). In fact, we can't even think about QuickCheck's generators and shrinkers as different interpretations of the same syntax. For example, here's a shrinker that follows the syntax of `genRat` more closely:

    shrinkRat2 (Rat n d) = do
      (num, den) <- shrink (n, d)
      pure (Rat num (1 + den))

This does have the invariant that its output have non-zero denominators; however, it will get stuck in an infinite loop! That's because the incoming `d` will be non-zero, so when `shrink` tries to shrink `(n, d)`, one of the outputs it tries will be `(n, 0)`; that will lead to `Rat n 1`, which will also shrink to `Rat n 1`, and so on.

In contrast, in Hypothesis, Hedgehog, falsify, etc. a "generator" is just a parser from numbers to values; and shrinking is applied to those numbers, not to the output of a generator. Not only does this not require separate shrinkers, but it also guarantees that the generator's invariants hold for all of the shrunken values; since those shrunken values have also been outputted by the generator (when it was given smaller inputs).

[sunshowers]

No, QuickCheck very importantly does not shrink automatically. You have to write the shrinker yourself. Hypothesis, Hedgehog, proptest and a few others shrink automatically.

[valcron1000]

Yes, but instances require the user to provide shrinking while Hypothesis does not: shrinking is derived automatically.

[pfdietz]

The way it does counterexample shrinking is the most clever part of Hypothesis.

[ctenb]

Do you have a reference where it is explained? It's not part of the docs as far as I can tell

[pfdietz]

You might try this blog entry (or other blog entries that talk about shrinking):

https://hypothesis.works/articles/how-hypothesis-works/