Hacker News new | past | comments | ask | show | jobs | submit login
QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs (2000) [pdf] (tufts.edu)
123 points by tosh on Dec 24, 2016 | hide | past | web | favorite | 38 comments

A fun riff on QuickCheck is QuickSpec[1], a tool that automatically generates laws (invariants) for an API and tests them with QuickCheck. The example in the documentation is pretty good:

Given reverse, ++ (list concatenation) and [], it finds six laws:

    xs ++ [] == xs
    [] ++ xs == xs
    (xs ++ ys) ++ zs == xs ++ (ys ++ zs)
    reverse [] == []
    reverse (reverse xs) == xs
    reverse xs ++ reverse ys == reverse (ys ++ xs)
It's not perfect—it's limited to reasonably small equational laws on a small set of provided functions—but I think it's a really cool example of what's possible and even practical starting from a simple and elegant tool like QuickCheck.

[1]: https://hackage.haskell.org/package/quickspec

I've been looking for a tool like QuickSpec, thank you for mentioning it.

If only my bugs were as simple as the methods reverse, concat, and index...

Granted, to an extent, my bugs probably were as simple as that. But it was as likely an emergent simplicity. Not to mention that one of my laws will be performance.

This is like showing how awesome a language is with a to-do app. Neat. Possibly educational. Mostly an exercise in how well the author knew how to write a to-do app.

> If only my bugs were as simple as the methods reverse, concat, and index...

When I first read about QuickCheck, I had similar reaction.

But then I learned that QuickCheck can test stateful systems also. For example, this bug reported against LevelDB, a database system developed at Google, was discovered using QuickCheck: https://github.com/google/leveldb/issues/50. You can read more about it at http://htmlpreview.github.io/?https://raw.github.com/strange...

These links are awesome. More examples of real world successes go a long way to not just impressing with technical ability, but convincing of practical use.

That is quick check impresses me. I just haven't seen many real world examples of it providing significant value. And I no longer buy in to appealing arguments. :(

If only your core logic had some straightforward invariants...

QuickCheck can work effectively with complex data structures.

For an example of a simple invariant that can still uncover subtle and important bugs:

encode(decode(X)) = X

Where encode and decode are some domain specific blobs of protocol logic. It's pretty useful to have the computer verify that isomorphism with a huge number of generated inputs.

(There's also SmallCheck which is like QuickCheck but checking all possible values within some depth limit, instead of random values.)

And there's no reason you couldn't use QuickCheck to verify a performance law, by the way.

My complaint was less against quick check, and more against the examples. Pedagogically themed ideas make sense. Practical and visible results are better. By orders of magnitude.

> And there's no reason you couldn't use QuickCheck to verify a performance law, by the way.

In fact, I've done something similar to this.

I'd be interested in seeing how you did this.

More precisely what I did was minimization on an unusually slow example input, but I don't think I can share the code. The approach generalizes, though:

To verify performance, you would set it up to benchmark the code in question (in Haskell, this would probably mean using Criterion) and then assert that it was "fast enough" (probably relative to the size of the input).

This library does more than "random" testing: when it finds a failure, it will try to reduce the input (called "shrinking") to report a minimal example. Here are some similar tools for other languages: http://hypothesis.works/articles/quickcheck-in-every-languag...

Indeed. Beware of tools claiming to be "quickcheck for language X." Without shrinking, you've lost an invaluable part of what makes quickcheck so useful.

Go also has a version of this in the stdlib https://golang.org/pkg/testing/quick/

Yes, but the Go tool doesn't do shrinking, which is troublesome once you start building big models.

(disclosure: I have some pretty large Erlang QuickCheck models on Github)

Gopter for Go can shrink examples: https://github.com/leanovate/gopter.

This looks amazingly useful. I've been looking for a clojure-esque spec package for Go!

Any examples of those you can share? I've been curious about quickcheck for a while now, but have not known how it would work beyond the simple examples that are most often shown.

Since several people have posted links to quickcheck implementations in other languages, here is a comparison of implementations in many different languages: http://hypothesis.works/articles/quickcheck-in-every-languag....

In case anyone is interested, TestCheck.js [0] is a JavaScript implementation of QuickCheck. When I had last checked it out I vaguely remember thinking it was still too young to pick up. But looking over the APIs right now, it looks like its been steadily improving.

I think my first introduction to property based testing was this video [1] from F# for fun and profit. The speaker does a great job at presenting the topic in a way that's clear and approachable. Ff you prefer text over video, on the same post there's links to other blog posts which cover the same material.

[0] https://github.com/leebyron/testcheck-js

[1] https://fsharpforfunandprofit.com/pbt/

I'd recommend watching this https://www.youtube.com/watch?v=zi0rHwfiX1Q to see how powerful this can be.

I've just discovered generative testing due to clojure.spec. Describing specs for your data works not only to help validate data structures but can be plugged in as properties for generative testing.

After the "aha" moment it was followed by a feeling that I've wasted so much time writing specs just to validate data structures and writing specs just to see if my functions are working as they should.

This is one of the things I wish was obvious in my learning track right after vim/emacs will help you code faster.

QuickCheck is awesome and indispensable in the Haskell world. Instead of writing a single unit test with a hard coded example case, QuickCheck allows you to describe that unit test generically and it can randomly generate unit tests of the type described, focusing on extrema etc. Very powerful.

I really like Crockford's JS version, JSCheck [0].

[0] https://github.com/douglascrockford/JSCheck

At a skim, it doesn't look like it does minimization on failure? That's a big part of the value of QuickCheck.

(As I said, it was a skim - I'd love to be wrong!)

Not sure what you mean by minimization on failure, but there's a 'classifier' and 'on_fail' method that be might interwoven into the capability you're speaking of.

QuickCheck et al do a random walk to find a value that fails the tests. Typically the value is large, complicated and unwieldy - particularly if the test involves nested structures. It might by 10s of KBytes in size, and most of the value is irrelevant.

Minimization is the process of starting from that known value and simplifying it as much as possible while still failing the test. For example QuickCheck discovers a 1235 element list, that fails. The problem happens to be a 0 in the last element. Minimisation might simplify that list to [1, 0]. So finding the cause is quite a bit easier.

The idea of Smallcheck is to start with minimal values. If we're going to shrink big values to small ones, why not just start with small values in the first place. Smallcheck tests the small values exhaustively rather than randomly.

To be fair though, QuickCheck is not completely random. It has a "size" parameter that starts small and grows, thus allowing small values to be tested first.

> If we're going to shrink big values to small ones, why not just start with small values in the first place.

Because you want to test things in the order that will most quickly find you a small error. This winds up being a trade-off, and as you say QuickCheck doesn't start with arbitrarily large inputs. But just testing all small inputs in order is often not the best choice.

For example, if your function takes an unsigned 32 bit integer, and you've tested inputs 0 through 15161, do you expect you're more likely to find an error next testing 15162, or 4294967295?

Because you're not going to check every small value, it's still random.

Minimisation would go something like this:

I have a function takes a list and fails if it has more than two negative numbers in.

Quickcheck first finds a failing test with a list of 200 numbers in. It then tries removing parts of the list to see if it can find a smaller failing example. The final output ends up (hopefully) as [-1,-1,-1]

Much easier to debug than a 200 element input.

I found this very useful when creating a tester for guis because I'd get minimal ui examples where things failed.

"Don't write tests. Generate them."

I love the Erlang portage of QC. Really saved my life multiple times.

Which Erlang library are you referring to? Isn't there more than one property-based testing library for Erlang?

The QuviQ implementation =)

proper is the good one

Does a coverage-guided QuickCheck exists, à la AFL? AFL is really good at finding deeper code path that the randomness only approach might not find.

I looked into this while making RamFuzz[1], but parameter generation (QuickCheck) is quite different from input-blob evolution (AFL). It wasn't clear to me how best to leverage a parameter mutation that happens to increase coverage. Ultimately, I decided that random generation (without guidance by coverage) coupled with AI classification of test outcomes is the most interesting approach.

[1] https://github.com/dekimir/RamFuzz

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact