Hacker News Reader

Comment by dllthomas | Hacker News Reader

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.

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.

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.

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

> 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?

Reply on news.ycombinator.com