Quantcast

Testing data with subsets using QuickCheck

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Testing data with subsets using QuickCheck

Krzysztof Jurewicz
Let’s say that we want to test lists:member/2 using QuickCheck/triq/PropEr. We want to ensure that:

For every element and a list such that the element is member of the list, lists:member/2 returns true.

Written as a QuickCheck property, this may look like:

prop_member() ->
    ?FORALL(
       {List, Member},
       list_with_member(),
       lists:member(Member, List)).

The problem is that there is no list_with_member/0 generator. A few solutions are possible:

⒈ Test all list members instead of one.

prop_member() ->
    ?FORALL(
       List,
       list(int()),
       lists:all(
         fun (Member) -> lists:member(Member, List) end,
         List)).

This may look like checking a bit too much in one test iteration.

We can also write list_with_member/0 generator in one of the following ways:

⒉ Choose one member randomly.

list_with_member() ->
    ?LET(
       {List, Seed},
       {non_empty(list(int())), {int(), int(), int()}},
       begin
           _ = rand:seed(exs64, Seed),
           Index = rand:uniform(length(List)),
           {List, lists:nth(Index, List)}
       end).

This doesn’t look very elegantly and raises questions about whether it will shrink gracefully.

⒊ Insert an element into generated list.

list_with_member() ->
    ?LET(
       {List, Element},
       {list(int()), int()},
       {[Element|List], Element}).

The problem with this approach in this particular case is that an element is always inserted at the beginning of the list, so we won’t get any errors for implementations like this one:

member(Element, [Element|_]) ->
    true;
member(_, _) ->
    false.

⒋ Write a custom generator.

This seems to be generally discouraged.

Any thoughts about which of the approaches above (or maybe yet another one) should be recommended in similar cases?

Krzysztof
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Testing data with subsets using QuickCheck

Alex S.
Remember that you can generate a random element of the list using built-in generators. I think this would be the most natural approach.

> 10 мая 2017 г., в 19:18, Krzysztof Jurewicz <[hidden email]> написал(а):
>
> Let’s say that we want to test lists:member/2 using QuickCheck/triq/PropEr. We want to ensure that:
>
> For every element and a list such that the element is member of the list, lists:member/2 returns true.
>
> Written as a QuickCheck property, this may look like:
>
> prop_member() ->
>    ?FORALL(
>       {List, Member},
>       list_with_member(),
>       lists:member(Member, List)).
>
> The problem is that there is no list_with_member/0 generator. A few solutions are possible:
>
> ⒈ Test all list members instead of one.
>
> prop_member() ->
>    ?FORALL(
>       List,
>       list(int()),
>       lists:all(
>         fun (Member) -> lists:member(Member, List) end,
>         List)).
>
> This may look like checking a bit too much in one test iteration.
>
> We can also write list_with_member/0 generator in one of the following ways:
>
> ⒉ Choose one member randomly.
>
> list_with_member() ->
>    ?LET(
>       {List, Seed},
>       {non_empty(list(int())), {int(), int(), int()}},
>       begin
>           _ = rand:seed(exs64, Seed),
>           Index = rand:uniform(length(List)),
>           {List, lists:nth(Index, List)}
>       end).
>
> This doesn’t look very elegantly and raises questions about whether it will shrink gracefully.
>
> ⒊ Insert an element into generated list.
>
> list_with_member() ->
>    ?LET(
>       {List, Element},
>       {list(int()), int()},
>       {[Element|List], Element}).
>
> The problem with this approach in this particular case is that an element is always inserted at the beginning of the list, so we won’t get any errors for implementations like this one:
>
> member(Element, [Element|_]) ->
>    true;
> member(_, _) ->
>    false.
>
> ⒋ Write a custom generator.
>
> This seems to be generally discouraged.
>
> Any thoughts about which of the approaches above (or maybe yet another one) should be recommended in similar cases?
>
> Krzysztof
> _______________________________________________
> erlang-questions mailing list
> [hidden email]
> http://erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Testing data with subsets using QuickCheck

Jesper Louis Andersen-2
In reply to this post by Krzysztof Jurewicz
On Wed, May 10, 2017 at 6:18 PM Krzysztof Jurewicz <[hidden email]> wrote:
Let’s say that we want to test lists:member/2 using QuickCheck/triq/PropEr. We want to ensure that:

For every element and a list such that the element is member of the list, lists:member/2 returns true.

Written as a QuickCheck property, this may look like:

prop_member() ->
    ?FORALL(
       {List, Member},
       list_with_member(),
       lists:member(Member, List)).


You have a couple of options:

gen_naive() ->
    ?SUCHTHAT({L,M}, {list(nat()), nat()},
      lists:member(M, L)).

is a simple generator which uses ?SUCHTHAT. It just generates a list and a member and then verifies if the member is indeed a member of the list. Of course in this case, when we want to test exactly lists:member/2 this is silly, but in general that is a way to get at the game.

The rule for a ?SUCHTHAT generator is to use it when you know it is fairly easy to generate something for which the suchthat is true. If the chance of generating an valid value is small, then you are just slowing down generation which means you can do fewer test cases.

Another way is to be a bit smarter:

gen_smarter() ->
    ?LET({L, M, R}, {list(nat()), nat(), list(nat())},
         {L ++ [M] ++ R, M}).

Generate a Left and a Right side and an element. Then append them together to form a list. This should generate any form of list, not just those where the element is at the beginning. And this should in principle make the test cover the domain space well.

 In this case I run a little above 80.000 tests in 10 seconds on this machine for both approaches, so it is fairly unlikely to slow you down much. But in general, it is more efficient to construct a specimen in a generator than search for it through ?SUCHTHAT.

Writing your own custom generators is necessary for any real QuickCheck work. Automated generators can get you a long way, but if you know something about your problem domain, it is often possible to improve testing quite a lot by constructing test cases you know are troublesome far more often than what a typical autogenerated or derived generator can give you.

For instance: when I wrote tests for the Erlang maps code, I found a lot of sibling pairs which hash to the same value in the HAMT. This meant I could test collisions on hashes all the time and this found some sign extension bugs in the runtime as a result which got fixed before the release of Erlang version 18.0.

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Testing data with subsets using QuickCheck

Jesper Louis Andersen-2
In reply to this post by Alex S.
On Wed, May 10, 2017 at 8:27 PM Alex S. <[hidden email]> wrote:
Remember that you can generate a random element of the list using built-in generators. I think this would be the most natural approach.


gen_alex() ->
    ?LET(L, non_empty(list(nat())),
      {L, elements(L)}).

Indeed, this is also a way to do it. Generate a non-empty list of elements, then pick a random element in the list. This is quite a deal faster since you don't have to run appending all the time. 270.000 test cases in 10 seconds.
 

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Testing data with subsets using QuickCheck

Krzysztof Jurewicz
Jesper Louis Andersen writes:

> On Wed, May 10, 2017 at 8:27 PM Alex S. <[hidden email]> wrote:
>
>> Remember that you can generate a random element of the list using built-in
>> generators. I think this would be the most natural approach.
>>
>>
> gen_alex() ->
>     ?LET(L, non_empty(list(nat())),
>       {L, elements(L)}).

Thank you. Somehow I haven’t noticed the existence of elements/1 generator. (Why is it named in plural)?
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Testing data with subsets using QuickCheck

Alex S.
I think it’s supposed to describe the data set or something. “Can generate from elements of L."

> 11 мая 2017 г., в 16:15, Krzysztof Jurewicz <[hidden email]> написал(а):
>
> Jesper Louis Andersen writes:
>
>> On Wed, May 10, 2017 at 8:27 PM Alex S. <[hidden email]> wrote:
>>
>>> Remember that you can generate a random element of the list using built-in
>>> generators. I think this would be the most natural approach.
>>>
>>>
>> gen_alex() ->
>>    ?LET(L, non_empty(list(nat())),
>>      {L, elements(L)}).
>
> Thank you. Somehow I haven’t noticed the existence of elements/1 generator. (Why is it named in plural)?

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Testing data with subsets using QuickCheck

Krzysztof Jurewicz
Alex S. writes:

> I think it’s supposed to describe the data set or something. “Can generate from elements of L."

Then there should be also generators named “binaries”, “integers”, “lists” etc. Looks like an inconsistency to me.
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Testing data with subsets using QuickCheck

Jesper Louis Andersen-2
In reply to this post by Krzysztof Jurewicz
On Thu, May 11, 2017 at 3:15 PM Krzysztof Jurewicz <[hidden email]> wrote:

Thank you. Somehow I haven’t noticed the existence of elements/1 generator. (Why is it named in plural)?

The name goes back a long way: the original Haskell implementation used elements as well. And Hughes/Claessen's original paper does so too. I think the notion is "the elements of" but I am not sure, but the plurality might just be a historical thing that caught on.
 

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Loading...