[Haskell-cafe] Quickcheck research

[Jason Dagit]

On Tue, Nov 22, 2011 at 9:42 AM, wren ng thornton <wren at freegeek.org> wrote:
> On 11/22/11 6:09 AM, Macías López wrote:
>>
>> Hello:
>>
>> I'm a Master's student in Computer Science. I have to make a project
>> involving some research, I'm very interested in Quickcheck and I wonder if
>> there are some areas which need work or if there is some potential
>> research
>> topic related to it.
>>
>> In particular I know that Erlang Quickcheck has been worked on a lot and
>> has some features like state machines or C bindings which may be useful to
>> the Haskell community.
>>
>> I would appreciate any directions.
>
> Something I think would be nice is to see full integration between
> SmallCheck and QuickCheck. In particular, I'd like to use SmallCheck to
> exhaustively search the small cases, and then use QuickCheck in a way that
> ensures that it only tests on things larger than the ones which have already
> been tested.
>
> One of the problems with mixing the two these days is that QuickCheck often
> wastes a lot of time checking things that SmallCheck will also test. While
> the goal may not seem very researchy, it actually gets at one of the main
> weaknesses of QuickCheck: namely, how to properly control generation of
> arbitrary values in order to ensure you're testing something helpful. It's
> too easy to design Arbitrary instances which only generate small values
> (e.g., half of all lists are the empty list) or which loop forever (because
> of trying to avoid the too-small problem), which makes me think that
> Arbitrary isn't the right set of abstractions for controlling coverage of
> the value space.

Especially in the case where you find a counter example it may help to
slightly mutate that input and see if cases "near" it fail or succeed.

On a similar line of reasoning, I've wondered if Perlin style noise
generation could be applied to get a sort of "fuzzing" effect.  This
would be more interesting for cases where writing instances of
arbitrary is hard to do but test cases do exist.  Apply some sort of
pseudo-random noise to your examples and see if your properties still
hold.  I could see this having applications in parsers.

As far as I can tell, no one has used Perlin noise on algebraic
structures.  It seems to have only been applied to real valued spaces.
 Imagine having a parse tree then applying noise to the structure of
the tree then "unparsing" the tree back to concrete syntax.  You're
making the structure noisy instead of just fussing the concrete syntax
directly (which should increase the frequency that you change the
shape/meaning instead of just changing the tokens in the parse tree).

Jason