Generating a random rule for property based test

Question

I am using Triq (erlang quickcheck) and I am having trouble generating a set of nice rules for my program.

What I want to generate are things that looks like this:

A -> B

where I would like to provide A and the size of B, with latter not having any dupicates.

For example, if I say generate me rules with L.H.S. of [a] and R.H.S. of size 4 (ie. A = [a] and size(B) = 4) I would like to get something like this:

{rule, [a], [1,2,4,5]}
{rule, [a], [a,d,c,e]}
{rule, [a], [q,d,3,4]}

Note, I don't want any dupicates in B (this is the part I'm having trouble with). Also, it doesn't really matter what B is made up of - it can be anything as long as it is distinct and without dupicates.

My spec is far too messy to show here, so I'd rather not.

aronisstav · Accepted Answer · 2016-04-07T11:59:22.447

2

I am not familiar with Triq, but in PropEr and Quviq's Qickcheck you can use ?SUCHTHAT conditions that filter 'bad' instances.

If a generated instance does not satisfy a ?SUCHTHAT constraint it is discarded and not counted as a valid test. You could use this mechanism to generate lists of the specified size (i.e. what PropEr calls 'vectors') and then discard those that have duplicates, but I think that too many instances would then be discarded (see also the link).

It is usually more efficient to tinker with the generator so that all instances are valid, in your case by e.g. generating ~~(3)~~ X-times as many elements, removing duplicates and keeping as many as you need. This can still fail, and it will fail, so you need to guard against it.

Here is a generator for your case, in PropEr, together with a dummy property:

-module(dummy).

-export([rule_prop/0]).

-include_lib("proper/include/proper.hrl").

-define(X, 5).

rule_prop() ->
  ?FORALL(_, rule_gen(integer(), 4, integer()), true).

rule_gen(A, SizeB, TypeB) ->
  ?LET(
     EnoughB,
     ?SUCHTHAT(
        NoDupB,
        ?LET(
           ManyB,
           vector(?X * SizeB, TypeB),
           no_dups(ManyB)
          ),
        length(NoDupB) >= SizeB
       ),
     begin
       B = lists:sublist(EnoughB, SizeB),
       {rule, A, B}
     end).

no_dups([]) ->
  [];
no_dups([A|B]) ->
  [A | no_dups([X || X <- B, X =/= A])].

edited Apr 07 '16 at 11:59

answered Apr 06 '16 at 08:50

aronisstav

7,755
5
23
48

Thanks, just one question: why do we generate 3 times as many? Is the number three special, or you mean that we just need to generate more than needed? – Andriy Drozdyuk Apr 06 '16 at 13:46
No it isn't, it just "ensures" that enough distinct elements will remain after removing duplicates. – aronisstav Apr 06 '16 at 14:03
Will this _always_ generate something? – Andriy Drozdyuk Apr 06 '16 at 14:06
Oh, ok I finally got it. You generate only bigger lists than necessary, and then making them smaller. Thank you very much. – Andriy Drozdyuk Apr 06 '16 at 23:27
One more question, what is the `begin` and `end` block construction you are using here? Where is it in the docs? – Andriy Drozdyuk Apr 07 '16 at 05:00
Hm... it seems like I'm getting "Error: Couldn't produce an instance that satisfies all strict constraints after 50 tries." I am using PropEr. – Andriy Drozdyuk Apr 07 '16 at 05:46
For `begin` `end` see [this](http://stackoverflow.com/questions/20125277/what-is-begin-end-in-erlang-used-for). – aronisstav Apr 07 '16 at 10:23
1

This means that `?SUCHTHAT` failed with just 3 times as many elements. For lists of 10 unique `integer()` elements, 50 elements seems to be ok, but this is probably also a bug of PropEr. – aronisstav Apr 07 '16 at 12:01
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/108535/discussion-between-drozzy-and-aronisstav). – Andriy Drozdyuk Apr 07 '16 at 14:39

Generating a random rule for property based test

1 Answers1