gmane.comp.lang.haskell.libraries

David Benbennick | 3 Dec 05:54

QuickCheck properties for IntSet

Here's a patch to IntSet.hs that adds many QuickCheck properties.  It
adds properties testing almost all of the public interface of IntSet,
and also properties testing that the data type invariants are never
broken.  (The patch doesn't test the Data, Eq, Monoid, Read, or
Typeable instances.)

Also, this patch removes a helper function, foldlStrict, and replaces
it with calls to Data.List.foldl'.

I have two questions:

1) Is this the right way to submit patches?
2) Is there a good reason that IntSet doesn't use "deriving Eq", and
instead manually implements the Eq instance?


New patches:

[IntSet QuickCheck properties
David Benbennick <dbenbenn <at> gmail.com>**20071203040728

 1) Remove foldlStrict, and use Data.List.foldl' instead.
 2) Add many QuickCheck properties, checking almost
    every exported function of IntSet.
] {
hunk ./Data/IntSet.hs 114
-import List (nub,sort)
-import qualified List
hunk ./Data/IntSet.hs 115

(Continue reading)

Don Stewart | 3 Dec 06:13

Re: QuickCheck properties for IntSet

dbenbenn:
> Here's a patch to IntSet.hs that adds many QuickCheck properties.  It
> adds properties testing almost all of the public interface of IntSet,
> and also properties testing that the data type invariants are never
> broken.  (The patch doesn't test the Data, Eq, Monoid, Read, or
> Typeable instances.)
> 
> Also, this patch removes a helper function, foldlStrict, and replaces
> it with calls to Data.List.foldl'.
> 
> I have two questions:
> 
> 1) Is this the right way to submit patches?

Thanks so much David, for taking the time to do this! Getting the
testing up to date on the somewhat-forgotten base code is really
important.

Ian, can we get these into the base library testsuite?

Have you tried getting some code coverage for you testsuite, btw? 
(Compile with -fhpc, and then run "hpc report" on the resulting .tix
file, to get numbers on how thorough the coverage is)

-- Don

Henning Thielemann | 3 Dec 12:16

Re: QuickCheck properties for IntSet


On Sun, 2 Dec 2007, Don Stewart wrote:

> dbenbenn:
> > Here's a patch to IntSet.hs that adds many QuickCheck properties.  It
> > adds properties testing almost all of the public interface of IntSet,
> > and also properties testing that the data type invariants are never
> > broken.  (The patch doesn't test the Data, Eq, Monoid, Read, or
> > Typeable instances.)
> >
> > Also, this patch removes a helper function, foldlStrict, and replaces
> > it with calls to Data.List.foldl'.
> >
> > I have two questions:
> >
> > 1) Is this the right way to submit patches?
>
> Thanks so much David, for taking the time to do this! Getting the
> testing up to date on the somewhat-forgotten base code is really
> important.

Me too. Whenever I used IntSet, I discovered a bug ...

David Benbennick | 3 Dec 21:29

Re: QuickCheck properties for IntSet

On 12/2/07, Don Stewart <dons <at> galois.com> wrote:
> Have you tried getting some code coverage for you testsuite, btw?
> (Compile with -fhpc, and then run "hpc report" on the resulting .tix
> file, to get numbers on how thorough the coverage is)

Thanks for the suggestion!  Here's what I get:

 89% expressions used (1973/2214)
 62% boolean coverage (69/110)
      60% guards (62/103), 35 always True, 6 unevaluated
     100% 'if' conditions (7/7)
     100% qualifiers (0/0)
 87% alternatives used (183/209)
 96% local declarations used (26/27)
 84% top-level declarations used (144/171)

Next weekend I'll work on pushing these percentages up.

I wish I could use QuickCheck to write an actual unit test: that is,
an executable program that returns 0 on success, and non-zero on
failure.  Then we could put these properties in the tests/ directory,
and have them automatically executed.  Is anyone working on such a
feature for QuickCheck?

Don Stewart | 3 Dec 21:55

Re: QuickCheck properties for IntSet

dbenbenn:
> On 12/2/07, Don Stewart <dons <at> galois.com> wrote:
> > Have you tried getting some code coverage for you testsuite, btw?
> > (Compile with -fhpc, and then run "hpc report" on the resulting .tix
> > file, to get numbers on how thorough the coverage is)
> 
> Thanks for the suggestion!  Here's what I get:
> 
>  89% expressions used (1973/2214)
>  62% boolean coverage (69/110)
>       60% guards (62/103), 35 always True, 6 unevaluated
>      100% 'if' conditions (7/7)
>      100% qualifiers (0/0)
>  87% alternatives used (183/209)
>  96% local declarations used (26/27)
>  84% top-level declarations used (144/171)
> 
> Next weekend I'll work on pushing these percentages up.
> 
> I wish I could use QuickCheck to write an actual unit test: that is,
> an executable program that returns 0 on success, and non-zero on
> failure.  Then we could put these properties in the tests/ directory,
> and have them automatically executed.  Is anyone working on such a
> feature for QuickCheck?

The 'quickCheck' function does this, iirc. 

-- Don

David Benbennick | 3 Dec 22:12

Re: QuickCheck properties for IntSet

On 12/3/07, Don Stewart <dons <at> galois.com> wrote:
> > I wish I could use QuickCheck to write an actual unit test: that is,
> > an executable program that returns 0 on success, and non-zero on
> > failure.  Then we could put these properties in the tests/ directory,
> > and have them automatically executed.  Is anyone working on such a
> > feature for QuickCheck?
>
> The 'quickCheck' function does this, iirc.

I don't think so.  I do:

> cat foo.hs
import Test.QuickCheck
main = quickCheck False
> runhaskell foo.hs
Falsifiable, after 0 tests:
> echo $?
0

As far as I can see, quickCheck never causes an error exit to happen.
And it doesn't even return IO Bool, so I can't use quickCheck to write
my own function that calls System.Exit.exitFailure

Don Stewart | 3 Dec 22:18

Re: QuickCheck properties for IntSet

dbenbenn:
> On 12/3/07, Don Stewart <dons <at> galois.com> wrote:
> > > I wish I could use QuickCheck to write an actual unit test: that is,
> > > an executable program that returns 0 on success, and non-zero on
> > > failure.  Then we could put these properties in the tests/ directory,
> > > and have them automatically executed.  Is anyone working on such a
> > > feature for QuickCheck?
> >
> > The 'quickCheck' function does this, iirc.
> 
> I don't think so.  I do:
> 
> > cat foo.hs
> import Test.QuickCheck
> main = quickCheck False
> > runhaskell foo.hs
> Falsifiable, after 0 tests:
> > echo $?
> 0
> 
> As far as I can see, quickCheck never causes an error exit to happen.
> And it doesn't even return IO Bool, so I can't use quickCheck to write
> my own function that calls System.Exit.exitFailure

Oh, there's something like this that does actually work in xmonad's
tests directory (we use it to have darcs prevent bad patches).

Perhaps steal that?

-- Don

(Continue reading)

Henning Thielemann | 3 Dec 22:29

Re: QuickCheck properties for IntSet


On Mon, 3 Dec 2007, David Benbennick wrote:

> On 12/3/07, Don Stewart <dons <at> galois.com> wrote:
> > > I wish I could use QuickCheck to write an actual unit test: that is,
> > > an executable program that returns 0 on success, and non-zero on
> > > failure.  Then we could put these properties in the tests/ directory,
> > > and have them automatically executed.  Is anyone working on such a
> > > feature for QuickCheck?
> >
> > The 'quickCheck' function does this, iirc.
>
> I don't think so.  I do:
>
> > cat foo.hs
> import Test.QuickCheck
> main = quickCheck False
> > runhaskell foo.hs
> Falsifiable, after 0 tests:
> > echo $?
> 0
>
> As far as I can see, quickCheck never causes an error exit to happen.
> And it doesn't even return IO Bool, so I can't use quickCheck to write
> my own function that calls System.Exit.exitFailure

This problem was discussed recently:
 http://www.haskell.org/pipermail/haskell-cafe/2007-November/034811.html

David Benbennick | 3 Dec 22:58

Re: QuickCheck properties for IntSet

On 12/3/07, Henning Thielemann <lemming <at> henning-thielemann.de> wrote:
> > And it doesn't even return IO Bool, so I can't use quickCheck to write
> > my own function that calls System.Exit.exitFailure
>
> This problem was discussed recently:
>  http://www.haskell.org/pipermail/haskell-cafe/2007-November/034811.html

Yes, quickCheck' from QuickCheck 2
(http://darcs.haskell.org/QuickCheck/Test/QuickCheck/Test.hs) would do
the trick.  Are there any plans to upgrade Test.QuickCheck to version
2 in GHC?

David Benbennick | 8 Dec 11:18

Re: QuickCheck properties for IntSet

Here's an improved version of the patch.  It adds 11 more QuickCheck
properties.  Now everything is tested except:

* The Data instance for IntSet (does anyone know how to test that?)
* The debugging functions showTree and showTreeWith
* The various read functions (read, readList, reads, readsPrec) are
not that well tested, especially parse failures.

I found that IntSet.showTree and IntSet.showTreeWith are not identical
to Set.showTree and Set.showTreeWith.  Not a big deal since they're
just debugging functions, I guess.  But it means I can't include
QuickCheck properties for them.

I commented out some code that could never be executed:
* Some case-statement cases that could never occur.
* >>= for the Identity monad used internally.

union had an odd comment about "right bias".  I understand how right
bias and left bias can be different in a generic container like Set
(since the Eq instance for the contained type might not be structural
equality).  But for IntSet, there's no way to distinguish different
copies of the number 7.  In any case, the documentation at
http://www.haskell.org/ghc/docs/latest/html/libraries/containers-0.1.0.0/Data-IntSet.html#v%3Aunion
doesn't mention anything about bias.  So I took out insertR, the
function that implemented "right bias".

If this patch is accepted, I intend to work on QuickCheck properties
for Data.Set next.

(Continue reading)

David Benbennick | 9 Dec 10:25

Re: QuickCheck properties for IntSet

On 12/8/07, David Benbennick <dbenbenn <at> gmail.com> wrote:
> I commented out some code that could never be executed:
> * Some case-statement cases that could never occur.
> * >>= for the Identity monad used internally.

Sorry, I forgot to run the "validate" script on the previous patch.
Turns out validate requires >>= to be explicitly set, even though it
isn't used.  New patch bundle is attached.

This version also removes an unused function, and adds a QuickCheck
property for dataTypeOf.


New patches:

[IntSet QuickCheck properties
David Benbennick <dbenbenn <at> gmail.com>**20071203040728

 1) Remove foldlStrict, and use Data.List.foldl' instead.
 2) Add many QuickCheck properties, checking almost
    every exported function of IntSet.
] {
hunk ./Data/IntSet.hs 114
-import List (nub,sort)
-import qualified List
hunk ./Data/IntSet.hs 115
+import qualified Prelude
hunk ./Data/IntSet.hs 315
-  = foldlStrict union empty xs

(Continue reading)

Ian Lynagh | 30 Apr 19:34

Re: QuickCheck properties for IntSet

On Sun, Dec 09, 2007 at 01:25:48AM -0800, David Benbennick wrote:
> On 12/8/07, David Benbennick <dbenbenn <at> gmail.com> wrote:
> > I commented out some code that could never be executed:
> > * Some case-statement cases that could never occur.
> > * >>= for the Identity monad used internally.
> 
> Sorry, I forgot to run the "validate" script on the previous patch.
> Turns out validate requires >>= to be explicitly set, even though it
> isn't used.  New patch bundle is attached.

Sorry, I've had this sitting in my mailbox for some time, but only just
got around to looking at it properly. Thanks for writing it!

If I export test_all and make a program that runs it then it takes
almost exactly 1 minute to test this one module, as compared to 19
minutes to run the whole testsuite in fast mode, so I don't think that
running this as part of the fast testsuite is feasible.

I am not even convinced that it makes sense to run it as part of the
full testsuite - I don't think we can afford to spend an hour for every
60 modules that we want to test.

You might claim that it is taking so long because it is testing IntSet
thoroughly, but I claim that it is merely testing it a lot (and, I
suspect, testing some cases many times). I believe that a much smaller
number of carefully chosen unit tests could test the library just as
well, and two or three orders of magnitude more quickly. I hope that
soonish we will add hpc support to the testsuite, so we can signal a
failure if we don't get 100% coverage.

(Continue reading)

Don Stewart | 30 Apr 20:08

Re: QuickCheck properties for IntSet

igloo:
> On Sun, Dec 09, 2007 at 01:25:48AM -0800, David Benbennick wrote:
> > On 12/8/07, David Benbennick <dbenbenn <at> gmail.com> wrote:
> > > I commented out some code that could never be executed:
> > > * Some case-statement cases that could never occur.
> > > * >>= for the Identity monad used internally.
> > 
> > Sorry, I forgot to run the "validate" script on the previous patch.
> > Turns out validate requires >>= to be explicitly set, even though it
> > isn't used.  New patch bundle is attached.
> 
> Sorry, I've had this sitting in my mailbox for some time, but only just
> got around to looking at it properly. Thanks for writing it!
> 
> If I export test_all and make a program that runs it then it takes
> almost exactly 1 minute to test this one module, as compared to 19
> minutes to run the whole testsuite in fast mode, so I don't think that
> running this as part of the fast testsuite is feasible.
> 
> I am not even convinced that it makes sense to run it as part of the
> full testsuite - I don't think we can afford to spend an hour for every
> 60 modules that we want to test.
> 
> You might claim that it is taking so long because it is testing IntSet
> thoroughly, but I claim that it is merely testing it a lot (and, I
> suspect, testing some cases many times). I believe that a much smaller
> number of carefully chosen unit tests could test the library just as
> well, and two or three orders of magnitude more quickly. I hope that
> soonish we will add hpc support to the testsuite, so we can signal a
> failure if we don't get 100% coverage.

(Continue reading)

Ian Lynagh | 30 Apr 22:10

Re: QuickCheck properties for IntSet

On Wed, Apr 30, 2008 at 11:08:07AM -0700, Donald Bruce Stewart wrote:
> 
> What if we used QC tests with SmallCheck generators, so you 
> actually got decent search through the value space, rather than
> just a random walk?

This might be better than the normal QC way, but I don't think it's the
best way to write tests. e.g. for some tests on Integer the interesting
values might be [0..], while for other tests they might be
2^n +/- [-3..3].

Thanks
Ian

Don Stewart | 30 Apr 22:22

Re: QuickCheck properties for IntSet

igloo:
> On Wed, Apr 30, 2008 at 11:08:07AM -0700, Donald Bruce Stewart wrote:
> > 
> > What if we used QC tests with SmallCheck generators, so you 
> > actually got decent search through the value space, rather than
> > just a random walk?
> 
> This might be better than the normal QC way, but I don't think it's the
> best way to write tests. e.g. for some tests on Integer the interesting
> values might be [0..], while for other tests they might be
> 2^n +/- [-3..3].

So then it comes down the to property writer.

I don't think it makes sense to not include tests at all, when we have
them. *Any* testing (even QuickCheck -depth 4 ) is better than none.

-- Don

David Benbennick | 30 Apr 22:35

Re: QuickCheck properties for IntSet

On Wed, Apr 30, 2008 at 10:34 AM, Ian Lynagh <igloo <at> earth.li> wrote:
>  I believe that a much smaller number of carefully chosen unit tests could test the library just as
>  well

I think that if you remove any of the properties from my patch, I can
break the implementation of IntSet in such a way that it still passes
all the tests.  Anyway, the new QuickCheck properties are just
comments, so they don't have any affect on the test suite.

Ian Lynagh | 30 Apr 22:48

Re: QuickCheck properties for IntSet

On Wed, Apr 30, 2008 at 01:35:45PM -0700, David Benbennick wrote:
> On Wed, Apr 30, 2008 at 10:34 AM, Ian Lynagh <igloo <at> earth.li> wrote:
> >  I believe that a much smaller number of carefully chosen unit tests could test the library just as
> >  well
> 
> I think that if you remove any of the properties from my patch, I can
> break the implementation of IntSet in such a way that it still passes
> all the tests.

I don't mean that any of your QC tests were redundant, what I mean is
that QC runs your tests with redundant values.

> Anyway, the new QuickCheck properties are just
> comments, so they don't have any affect on the test suite.

I don't think there is much benefit in having the tests if we aren't
going to run them. People making changes to the library will probably
forget to check that they pass (or not know that they exist), and the
tests will probably bitrot due to changes in other libraries etc.

Thanks
Ian

Don Stewart | 30 Apr 23:08

Re: QuickCheck properties for IntSet

igloo:
> On Wed, Apr 30, 2008 at 01:35:45PM -0700, David Benbennick wrote:
> > On Wed, Apr 30, 2008 at 10:34 AM, Ian Lynagh <igloo <at> earth.li> wrote:
> > >  I believe that a much smaller number of carefully chosen unit tests could test the library just as
> > >  well
> > 
> > I think that if you remove any of the properties from my patch, I can
> > break the implementation of IntSet in such a way that it still passes
> > all the tests.
> 
> I don't mean that any of your QC tests were redundant, what I mean is
> that QC runs your tests with redundant values.
> 
> > Anyway, the new QuickCheck properties are just
> > comments, so they don't have any affect on the test suite.
> 
> I don't think there is much benefit in having the tests if we aren't
> going to run them. People making changes to the library will probably
> forget to check that they pass (or not know that they exist), and the
> tests will probably bitrot due to changes in other libraries etc.

So I don't know what is being decided here?

No QuickCheck properties for the containers library because Ian doesn't
believe in them? Or ..?

-- Don

Ian Lynagh | 1 May 17:41

Re: QuickCheck properties for IntSet

On Wed, Apr 30, 2008 at 02:08:36PM -0700, Donald Bruce Stewart wrote:
> 
> So I don't know what is being decided here?
> 
> No QuickCheck properties for the containers library because Ian doesn't
> believe in them? Or ..?

Well, I've decided that I'm not going to just apply the patch, but I am
not the library maintainer. We have
    http://www.haskell.org/haskellwiki/Library_submissions
for deciding whether or not changes should be made.

Thanks
Ian

Duncan Coutts | 1 May 21:36

Re: QuickCheck properties for IntSet

On Thu, 2008-05-01 at 16:41 +0100, Ian Lynagh wrote:
> On Wed, Apr 30, 2008 at 02:08:36PM -0700, Donald Bruce Stewart wrote:
> > 
> > So I don't know what is being decided here?
> > 
> > No QuickCheck properties for the containers library because Ian doesn't
> > believe in them? Or ..?
> 
> Well, I've decided that I'm not going to just apply the patch, but I am
> not the library maintainer. We have
>     http://www.haskell.org/haskellwiki/Library_submissions
> for deciding whether or not changes should be made.

Well, that's really for interface or behaviour changes.

I think it is clear that the library should come with those QC
properties. The issue at stake is if they should be run every time as
part of GHC's testing process.

So I'd suggest applying the patch and then disabling the automatic
running of the tests until that issue is decided. It'd be a bit sad to
let good test code languish just because we can't decide if it should be
run regularly or not.

Duncan

David Benbennick | 30 Apr 23:18

Re: QuickCheck properties for IntSet

As I recall, IntSet overrides the number of times to check each QC
property, to 500 or 5000?  Removing the override, or putting it down
at 10 or 50, makes the checks run much faster.

On Wed, Apr 30, 2008 at 1:48 PM, Ian Lynagh <igloo <at> earth.li> wrote:
>  I don't think there is much benefit in having the tests if we aren't
>  going to run them.

I agree that having them run automatically would be much better.

Don Stewart | 30 Apr 23:20

Re: QuickCheck properties for IntSet

dbenbenn:
> As I recall, IntSet overrides the number of times to check each QC
> property, to 500 or 5000?  Removing the override, or putting it down
> at 10 or 50, makes the checks run much faster.

Yeah, I think we can do quite well by having even only 10 tests, as
long as we use a new random seed each time. Given enough nightly
builds we'll end up testing more than with the fixed seed/1000 run.

-- Don

Return

Return to gmane.comp.lang.haskell.libraries.

Advertisement

Search Archive

Language

Change language

Options

Current view: Threads only / Showing only 20 lines / Not hiding cited text.
Change to All messages, whole messages, or hide cited text.

Post a message
NNTP Newsgroup
Classic Gmane web interface
XML

XML

RSS Feed
List Information

About Gmane