[Haskell-cafe] Re: QuickCheck [Architecturally flawed]

[Paul Johnson]

Ryan Ingram wrote:
> I think you can use the duality of Writer/Reader to help you here; you
> have the law that, for suitable "dual" computations r and w,
>
> run_reader r (run_writer (w x)) == x
>
> Then you can build up a list of rules specifying which computations
> are dual; read64 is dual to write64, for example.  You can then have
> some laws like:
>
> if r1 is dual to w1, and r2 is dual to w2,
> then
>     r1 >>= \x -> r2 >>= \y -> (x,y)
> is dual to
>     \(x,y) -> w1 x >> w2 y
>
> if r1 is dual to w1, and r2 is dual to w2,
> then
>    read1 >>= \b -> case b of True -> liftM Left r1 ; False -> liftM Right r2
> is dual to
>    \x -> case x of Left l -> w1 l; Right r -> w2 r
>
> You can then use these to build up more complicated reader/writer
> duals and verify that the main "identity" law holds.
>
> It's a little bit tricky; QuickCheck is not good at dealing with
> polymorphic data, but you could generalize this to a simple term ADT:
>    data SimpleTerm = Leaf Word8 Word32 | Pair SimpleTerm SimpleTerm |
> Switch (Either SimpleTerm SimpleTerm) deriving Eq
>
> and make a suitable "arbitrary" instance for SimpleTerm to test your
> reader/writer.  Leaf would test readN/writeN, or you can make custom
> leaves to test the other operations.
>
>   -- ryan
>
> On Fri, Jul 11, 2008 at 11:10 AM, Andrew Coppin
> <andrewcoppin at btinternet.com> wrote:
>   
>> For starters, what would be a good set of properties to confirm that any
>> monad is actually working correctly? More particularly, how about a state
>> monad? It's easy to screw up the implementation and pass the wrong state
>> around. How would you catch that?
>>     
See http://www.cs.chalmers.se/~rjmh/Papers/QuickCheckST.ps on QuickCheck 
tests for monadic properties.  The basic idea is to write a Gen action 
to generate a list of actions in your target monad.
>> Secondly, the monads themselves. I started writing things like "if X has the
>> lowest bit set then the lowest bit of the final byte of the output should be
>> set"... but then all I'm really doing is reimplementing the algorithm as a
>> property rather than a monad! If a property fails, is the program wrong or
>> is the property wrong
This is a fundamental issue with the way that QuickCheck, or any other 
automatic test generator, works.  QuickCheck tests are a formal 
specification of the properties of your program, so they have the same 
fundamental complexity as your program.  See 
http://en.wikipedia.org/wiki/Kolmogorov_complexity for more on this.  
The only exception is when a complicated algorithm produces a simple 
result, such as sorting or square roots.  There are two ways of dealing 
with this:

1: Write abbreviated properties that only specify part of your program's 
behaviour, and trust to single-case tests and code inspection for the 
rest.  For instance a test for "reverse" done this way might test that 
reverse "abcd" = "dcba" and otherwise just check that the input and 
output strings were the same length.

2: Accept that your tests are going to be as long as the program 
itself.  When a test fails, just figure out which is at fault (you have 
to do this for any testing method anyway).  You still gain reliability 
because you have implemented the algorithm in two different ways, so 
hopefully a defect in one will not have a matching defect in the other.  
I say "hopefully" because the history of N-version programming suggests 
that such errors are not independent, even when the versions are 
developed by different teams.