Hypothesis Blog

Python may be terrible, but this poster doesn't know Python at all. Here's how to fix the first snippet:

leaf = object()

Huh, that's funny, it's shorter than the Haskell? Why is that? Let's keep going.

def merge(lhs, rhs):
if lhs is leaf: return rhs
if rhs is leaf: return lhs
if lhs[0] <= rhs[0]: return lhs[0], merge(rhs, lhs[2]), lhs[1]
return rhs[0], merge(lhs, rhs[2]), rhs[1]

Ugh. My mouth tastes funny. Livecoding on this site is always disorienting. I need to sit down for a bit. Exercise for the reader: Continue on in this style and figure out whether the Haskell really deserves its reputation for terseness and directness.

Edit: I kept reading and was immediately sick. __dict__ abuse is a real problem in our society, folks. It's not okay.

def insert(tree, elt): return merge(tree, (elt, leaf, leaf))

The Haskell memes are growing stronger as I delve deeper into this jungle. The pop-minimum function here is a true abomination, breaking all SOLID principles at once. I can only imagine what it might look like in a less eldritch setting:

def popMin(tree):
if tree is leaf: raise IndexError("popMin from leaf")
return tree[0], merge(tree[1], tree[2])

We continue to clean up the monstrous camp.

def listToHeap(elts):
rv = leaf
for elt in elts:
rv = insert(rv, elt)
return rv

The monster...they knew! They could have done something better and chose not to. They left notes…

I have to admit the last time I seriously worked with QuickCheck was quite a while ago.

> My understanding is that Haskell’s QuickCheck can shrink functions [...]

Are you talking about shrinking a value of type (a -> b) (for some concrete a and b)? In Hypothesis, if you write a generator that spits out functions, you get a shrinker for free. So that shrinker will shrink functions.

As far as I can tell, QuickCheck's shrinking is based on values. I just checked, the type is still `shrink :: a -> [a]`, so that can't have changed.

In Hypothesis shrinking is based on the generation process. In Hypothesis generators act a bit like 'Functors' in Haskell, ie you can map over them. (You can also filter and `<>` and do monadic binds etc.)

So in Hypothesis you can take a generator that produces integers, and create one that produces only even numbers by (in Haskell terms) mapping (2) over it. Now, the shrinker you get for free will also only produce even numbers.

That's not possible (or at least not easily possible) in Haskell. You would have to define at least a newtype wrapper.

Have a look at https://hypothesis.works/articles/compositional-shrinking/ and https://hypothesis.works/articles/integrated-shrinking/ for some more write-up, especially about how Hypothesis can preserve information even when shrinking past a monadic bind.

If you follow some links in the two articles above, you land at https://github.com/icicle-lang/disorder.hs-ambiata/tree/master/disorder-jack…

I brought in the QuickTheories[0] library for property testing at work after being exposed to the articles here[1] (the final rule test is particularly interesting). My first use case was to test a generated parser for a restricted subset of the grammar for content security policy URLs, but I think this might be a bad use case since I'm not exactly testing "properties" so much as using the system for test data generation and quick code coverage. e.g. I have a test called something like testUrlPaths() that's mostly exercising the parser to make sure it doesn't forbid a valid but strange URL path that someone could enter. However while writing that test I discovered the parser was really doing the right thing, I found some violations with paths containing a '%' but not two hex digits immediately following. Unless I was writing unit tests for every bit of the grammar and paid attention to that part, I doubt I would have thought to test for them myself... Maybe the happy path of '%20' but not the fact that '%2' should be invalid. In the end I extracted those cases into three specific tests that will be there in case someone gets the funny idea to replace the validator with something not generated from a grammar (or generated from the wrong grammar), which isn't that unlikely since the spec allows for a lot more than what one might naturally consider allowing on your own (e.g. ftp resources).

Like with certain kinds of unit testing, I have the sense that the process of using a…

> In Hypothesis shrinking is based on the generation process. In Hypothesis generators act a bit like 'Functors' in Haskell, ie you can map over them. (You can also filter and `<>` and do monadic binds etc.)

You are right that the generators in Hypothesis correspond to `Functor`s, so you can map over it. Indeed, in QuickCheck, its `Gen` [1] (type of `arbitrary` [2], the generator in QuickCheck) is a `Functor`, and moreover a `Monad`, so you can do monadic binds on `Gen`.

> So in Hypothesis you can take a generator that produces integers, and create one that produces only even numbers by (in Haskell terms) mapping (2) over it. Now, the shrinker you get for free will also only produce even numbers.

> That's not possible (or at least not easily possible) in Haskell. You would have to define at least a newtype wrapper.

Since `Gen` in QuickCheck is a `Functor`, to multiply its output by 2 to generate only even numbers, you can do this in Haskell as:

fmap (\x -> x*2) (arbitrary @Int) Or, for those preferring OOP-style chaining:

arbitrary @Int <&> (*2) where `<&>` is `fmap` with arguments flipped, and `(*2) = \x -> x*2`, and `@Int` is type application to specialize `arbitrary` to generate `Int`.

> Have a look at https://hypothesis.works/articles/compositional-shrinking/ and https://hypothesis.works/articles/integrated-shrinking/ for some more write-up, especially about how Hypothesis can preserve information even when shrinking past a monadic bind.

I think what…

Well, normally Hypothesis just calls a function with some random arguments and checks that it "works", operationalized as "doesn't crash". But that's inadequate for testing stateful APIs, in which calling a single function isn't useful — for stateful APIs, you need to go through a series of calls, not just a single call. So the rule-based state machine thing gives you a way to describe the valid series of calls, and Hypothesis then generates 100 random sequences according to your spec and verifies that they all work. David wrote the article about it in 2017 that felixyz already linked: https://hypothesis.works/articles/rule-based-stateful-testing/

In many cases, though, it's better if you can refactor your code to support a stateless interface, and then you can write simple single-step function tests.

How do you know what to test? There's a whole spectrum. Just testing that valid inputs don't crash is often pretty useful. (If you're not sure what valid inputs would be, maybe try writing the README before the tests.) In the case of Dumpulse, I went to the other extreme; its actual semantics are extremely dumb (thus the name), so the test suite includes a reimplementation in Python of the intended semantics, and the test verifies that the implementation in C has the same behavior. (But in constant space and strictly limited runtime, which the Hypothesis test doesn't check.)

I picked a few functions and classes at random to see what kind of testable properties I…

Fuzzing can refer to randomly generated test inputs without bothering to minimize them when bugs are found. Property-based testing tools like Hypothesis and QuickCheck (which pioneered this approach), in addition to randomly generating test cases, when they find a test case that violates an assertion, they then start reducing the test case to try to find the minimal test case that violates the assertion.

Also, while they're very similar in a mechanical sense since they're both about randomly generated test inputs, in a broader sense my impression is that fuzzers have a very different focus from property-based testing. I think fuzz testing typically refers to testing very complex software, like compilers, interpreters, and virtual machines, and searching for crazy edge cases, especially ones that may expose security vulnerabilities. So a lot of effort goes into generating test inputs that are unlikely to happen with a naive testing strategy (automated or manual), yet still interesting and relatively likely to trigger a bug (rather than spending too much time in the very large space of uninteresting test inputs that a naive testing strategy wouldn't come up with but also is unlikely to trigger a bug).

By contrast, I think property-based testing is typically used for testing programs that are of ordinary complexity, and quickly finding bugs due to simple but common programmer errors, which can then be quickly fixed. So a lot of effort goes into reducing any bugs that are…