Erlang Central

# Recursive Genereators

## Recursive Generators

Assume you write a function that takes a recursively defined data type as input and you like to test it with QuickCheck. How would you do that?

### Example - Cartesian product of sets

We add the function 'product/2' to Erlang's sets module (in standard library) computing the Cartesian product of two sets. A new set can be constructed by associating every element of one set with every element of another set. The Cartesian product of two sets A and B, denoted by A × B is the set of all ordered pairs (a, b) such that a is a member of A and b is a member of B.

For example,

```> S1 = sets:from_list([1,2]),
S2 = sets:from_list([red,white,blue]),
sets:to_list(sets:product(S1,S2)).
[{1,red},{1,white},{1,blue},{2,red},{2,white},{2,blue}]
```

In the fashion of test driven development, we start by writing down a property that should hold.

```prop_relative_complement() ->
?FORALL({S1,S2},{set(int()),set(colour())},
begin
equal(sets:to_list(sets:product(S1,S2)),
[ {I,C} || I<-sets:to_list(S1), C<-sets:to_list(S2)])
end).

%% Since lists originating from sets may have the elements in different
%% orders, we need to compare that they contain the same elements.
equal(L1,L2) ->
(L1 -- L2) == [] andalso (L2 -- L1) == [].
```

Surely, we could implement the product function with the list comprehension above, but we want a more efficient implementation. The test, however, need not at all be efficient.

### Generators for data type

After formulating the property, we need to implement the generators for the data types, sets and colours in our case, since there is a standard generator for integers. Picking a colour from a predefined set of colours is simple. Creating a set needs a thought... we have to use the library functions in the set module to do so, since we do not want to rely upon the implementation details. One possibility is to simply create a list and turn it into a set:

```colour() ->
elements([red,white,blue,yellow,green,black]).

set(Gen) ->
?LET(L,list(Gen),sets:from_list(L)).
```

The generator for 'set' is, however, not very satisfactory. For a long discussion see the research paper: ["http://portal.acm.org/citation.cfm?id=1411275" Testing Erlang Data Types with Quviq QuickCheck], by Thomas Arts, Laura M. Castro and John Hughes. In short,

• In case of a test failure or a sample you are exposed to the internal representation of the set, without knowing how the set is created,
• You may test the sets module insufficiently by only considering sets created in this way,
• You miss the opportunity to test operations on sets that are result of the newly added product operation.
• Instead we propose to define a generator for sets recursively, by applying the operators available in the sets module. We need an extra argument to bind the size of the recursion. We create symbolic calls in order to be sure we can track the history of the set creation and in addition to simplify the presentation.

```set(Gen,0) ->
{call,sets,new,[]};
set(Gen,Size) ->
Set = set(Gen,Size div 2),
oneof([set(Gen,0),
{call,sets,from_list,[list(Gen)]},
{call,sets,del_element,[Gen,Set]},
{call,sets,union,[Set,Set]},
{call,sets,product,[Set,Set]}
]).
```

We divide the size of a smaller set by two instead of subtracting one, since we want to obtain terms of a certain size. If we have two subterms in the recursion, we devide by two, if we have three, we devide by three, etc. If only one subterm, it would suffice to subtract by one. Note that we also have to provide a starting size for the recursion. Here we want QuickCheck to use the same strategy as for other generators, viz. starting with small values and slowly choosing large values. This is done by a standard primitive ?SIZED:

```set(Gen) ->
?SIZED(Size,set(Gen,Size)).
```

Now we have defined a recursive generator which executes a lot of code in the sets module when creating a test case, therefore, already testing the module even before the property is actually checked. But, we need to adapt the property to our symbolic representation of sets.

```prop_product() ->
?FORALL({SymS1,SymS2},{set(int()),set(colour())},
begin
S1 = eval(SymS1),
S2 = eval(SymS2),
equal(sets:to_list(sets:product(S1,S2)),
[ {I,C} || I<-sets:to_list(S1), C<-sets:to_list(S2)])
end).
```