Files: use62.m
Back to main

# QuickCheck Tutorial 6

## Generators: Discriminated Union & Specific Frequency

Default generator is able to generate discriminated unions provided that all types in the body of the definition have default/custom generators. In default frequency mode, all branches at each level have the same chance of being selected.

    :- func rand_union(type_desc, list(frequency), list({type_desc,
                       list(frequency)}), list(user_gen_type), rnd, rnd) = univ.
    :- mode rand_union(in,in,in,list_skel_in(user_gen_inst),in,out) = out is det.

use61.m shows the randomly generated value for the type bullet, with default frequency :

    :- module use61.

    :- interface.

    :- use_module io.

    :- pred main(io__state, io__state).
    :- mode main(di, uo) is det.

    %---------------------------------------------------------------------------%

    :- implementation.

    :- import_module list.
    :- import_module qcheck.

    %---------------------------------------------------------------------------%
    %       arbitrary user-defined types for testing purposes
    %---------------------------------------------------------------------------%

    :- type bullet
            --->    good(color)
            ;       inaccurate(color)
            ;       defective(color).

    :- type color
            --->    black
            ;       white.

    %---------------------------------------------------------------------------%
    main -->
            qcheck(qcheck__f(prop1), "even distribution", 1000, [], []).

    :- func prop1(bullet) = property.
    prop1(X) = X `>>>` [yes].

Sample output shows the expected distribution :

            Test Description : even distribution
            Number of test cases that succeeded : 1000
            Number of trivial tests : 0
            Number of tests cases which failed the pre-condition : 0
            Distributions of selected argument(s) :
            150     inaccurate(white)
            153     defective(black)
            165     inaccurate(black)
            176     good(white)
            178     defective(white)
            178     good(black)

## Specific Frequency

Specific Frequency changes a term's default frequency (which is evenly spread) to one the user has provided. General Frequency changes a type's default frequency to one the user has provided. An example :

            :- func Invariant_Function_X(bullet, bullet) = property.

Different SF can be passed to the first and second bullet. For example, the first bullet can have 80% chance of being black, while the second argument has 20% chance of being black. However there can only be one GF for each type. The key advantage of Specific Frequency over General Frequency is that it allows different frequencies for the same type, where GF doesn't allow. The draw back is that SF only goes as deep (down the branches) as the user defines it, and the amount of work blows up as the depth of branches increases.

Suppose there are two bullet manufacturers. Company_W's bullets are painted black; 50% are good, 10% inaccurate, 40% defective. Company_B's bullets are painted white; 40% are good, 30% inaccurate, 30% defective. A good bullet always hits its target, inaccurate one misses 50% of time, defective bullet always misses. And color does affect performance.

    :- type frequency
            --->    {int, list(list(frequency))}.

frequency defines the relative chance of a branch being selected, and gives information of that branch's sub-branches. list(frequency) contains distribution information about 1 discrimated union, ie: the list must contain a frequency for each possible branch. list(list(frequency)) contains distribution information about a list of discrimated unions.

Let's try to describe Company_W's bullet, Bullet is discrimated union, so the list is 3 length long :

            list(frequency)

There are 3 top level branches for Type Bullet, so the list is 3 length long :

            [frequency_good, frequency_inaccurate, frequency_defective]

            :- type frequency       = {int, list(list(frequency))}.
            frequency_good          = {50,  ...something_good...}
            frequency_inaccurate    = {10,  ...something_inaccurate...}
            frequency_defective     = {40,  ...something_defective...}

Any int is a valid 1st argument of frequency. (Negative numbers are treated by qcheck as zeros.)

    chance of good-bullet     is 50 / (50 + 10 + 40)
    the chance of inaccurate  is 10 / (50 + 10 + 40)
    the chance of defective   is 40 / (50 + 10 + 40)

Another example (for type bullet):

    :- type frequency       = {int, list(list(frequency))}.
    frequency_good          = {5,  ...something_good...}
    frequency_inaccurate    = {1,  ...something_inaccurate...}
    frequency_defective     = {4,  ...something_defective...}

    the chance of good-bullet is 5 / (5 + 1 + 4)
    the chance of inaccurate  is 1 / (5 + 1 + 4)
    the chance of defective   is 4 / (5 + 1 + 4)

In both examples, the result distribution is the same (i.e. 50% good, 10% inaccurate, 40% defective).

...something_good... has format list(list(frequency)), and should describe the argument(s) of good/1. good/1 only has 1 arguments, thus the list of 1 element,

            [ info_color ]

info_color has format list(frequency), color has 2 branches, thus this list is of 2 elements.

            [ frequency_black, frequency_white ]

            :- type frequency       = {int, list(list(frequency))}.
            frequency_black         = {100, ...something_black...}
            frequency_white         = {0,   ...something_white...}

something_black has format list(list(frequency)), and should describe the argument(s) of black/0. black/0 has no argument, thus the list is [], likewise for white/0. If instead of black/0, it's black/3, eg:

            :- type color
                    --->    black(paint_manufacturer, warranty_type, warranty_provider)
                    ;       white(paint_manufacturer, warranty_type, warranty_provider)

Then you can either use [] to use default frequeny for generating paint_manufacturer, warranty_type, and warranty_provider. Or you can specify a list of 3 element ; each element describing the frequency of paint_manufacturer, warranty_type or warranty_provider.

    So far:      info_color = [ frequency_black, frequency_white ]
                            = [ {100, []},  {0, []} ]
    Then:    frequency_good = {50,  ...something_good...}
                            = {50,  [ info_color ] }
                            = {50,  [ [ {100, []},  {0, []} ] ] }

in this case ...something_good..., ...something_inaccurate... and ...something_defective are the same, since they all describe a list which contains Color that has the same distribution.

    So:     frequency_good          = {50, [ [ {100, []}, {0, []} ] ] }
            frequency_inaccurate    = {10, [ [ {100, []}, {0, []} ] ] }
            frequency_defective     = {40, [ [ {100, []}, {0, []} ] ] }

    Then:           [frequency_good, frequency_inaccurate, frequency_defective]
            =       [ {50, [ [ {100, []}, {0, []} ] ] },
                      {10, [ [ {100, []}, {0, []} ] ] },
                      {40, [ [ {100, []}, {0, []} ] ] }
                    ]

For Company_W's bullet, its list(frequency) would be :

                    [frequency_good, frequency_inaccurate, frequency_defective]
            =       [ {40, [ [ {0, []}, {100, []} ] ] },
                      {30, [ [ {0, []}, {100, []} ] ] },
                      {30, [ [ {0, []}, {100, []} ] ] }
                    ]

The complete code (use62.m):

    :- module use62.

    :- interface.

    :- use_module io.

    :- pred main(io__state, io__state).
    :- mode main(di, uo) is det.

    %---------------------------------------------------------------------------%

    :- implementation.

    :- import_module int, list, string.
    :- import_module qcheck, rnd.

    %---------------------------------------------------------------------------%
    %       arbitrary user-defined types for testing purposes
    %---------------------------------------------------------------------------%

    :- type bullet
            --->    good(color)
            ;       inaccurate(color)
            ;       defective(color).

    :- type color
            --->    black
            ;       white.

    %---------------------------------------------------------------------------%

    main -->
            { freq_B(B) },
            { freq_W(W) },
            qcheck(qcheck__f(prop2), "bullet fight", 10000, [[],B,W], []).

    :- pred freq_B(list(frequency)).
    :- mode freq_B(out) is det.
    freq_B(Out) :-
            Out = [ {50, [ [ {100, []}, {0, []} ] ] },
                    {10, [ [ {100, []}, {0, []} ] ] },
                    {40, [ [ {100, []}, {0, []} ] ] }
                  ].

    :- pred freq_W(list(frequency)).
    :- mode freq_W(out) is det.
    freq_W(Out) :-
            Out = [ {40, [ [ {0, []}, {100, []} ] ] },
                    {30, [ [ {0, []}, {100, []} ] ] },
                    {30, [ [ {0, []}, {100, []} ] ] }
                  ].

    :- func prop2(int, bullet, bullet) = property.
    prop2(Seed, B, W) = fight(Seed, B, W) `>>>`
                            ({"ComB",B} `>>>`
                                    ({"ComW", W} `>>>` [yes])
                            ).

    :- func fight(int, bullet, bullet) = string.
    :- mode fight(in, in, in) = out is det.
    fight(Seed, B, W) = String :-
            rnd__init(Seed, RS0),
            B_hit = is_hit(B, RS0, RS1),
            W_hit = is_hit(W, RS1, _),
            (if             B_hit = W_hit
             then
                            String = "draw"
             else if        B_hit > W_hit
                  then
                            String = "B win"
             else
                            String = "W win"
            ).

    :- func is_hit(bullet, rnd, rnd) = int.
    :- mode is_hit(in, in, out) = out is det.
    is_hit(Bullet, RS0, RS) = Int :-
            Temp = rand_allint(RS0, RS) rem 2,
            (
                    Bullet = good(_),
                    Int = 1
            ;
                    Bullet = inaccurate(_),
                    (if     Temp = 0
                     then
                            Int = 1
                     else
                            Int = 0
                    )
            ;
                    Bullet = defective(_),
                    Int = 0
            ).

In use62.m

    main -->
             { freq_B(B) },
             { freq_W(W) },
             qcheck(qcheck__f(prop2), "bullet fight", 10000, [[],B,W], []).

The 4th argument of qcheck/7 is for passing Specific Frequency. Because the invariant function has three input arguments, qcheck/7 's 4th argument must be list of 3. [[],B,W]

The first argument of prop2/3 is of type int, and I've passed [] as it's SF. When qcheck is trying to generate that int, it will completely ignore the [] since an int is not a discriminated union. In that sense, one can replace that [] with anything, as long as it's the correct format ; ie, a list(frequency). However the presence of [] will allow qcheck to recognize that [] is for the first argument, B is for the second argument and W is for the third argument.

A sample output:

            Test Description : bullet fight
            Number of test cases that succeeded : 10000
            Number of trivial tests : 0
            Number of tests cases which failed the pre-condition : 0
            Distributions of selected argument(s) :
            909     {"ComB", inaccurate(black)}
            2403     "B win"
            2533     "W win"
            2949     {"ComW", defective(white)}
            3012     {"ComW", inaccurate(white)}
            4017     {"ComB", defective(black)}
            4039     {"ComW", good(white)}
            5064     "draw"
            5074     {"ComB", good(black)}

Regroup the output to make comparison :

    5074     {"ComB", good(black)
    909      {"ComB", inaccurate(black)}
    4017     {"ComB", defective(black)}

    4039     {"ComW", good(white)}
    3012     {"ComW", inaccurate(white)}
    2949     {"ComW", defective(white)}

Note that ComB only makes black bullet; ComW only white. And their bullet quality is what was expected of them.

    2403     "B win"
    2533     "W win"
    5064     "draw"

Walk through in generating a Company_B 's bullet :

1. The program first enters the generator with

               SF = [  {50, [ [ {100, []}, {0, []} ] ] },
                       {10, [ [ {100, []}, {0, []} ] ] },
                       {40, [ [ {100, []}, {0, []} ] ] }
                    ].

2. Suppose the 3rd branch is selected, then qcheck will extract `[ {100, []}, {0, []} ]` from `{40, [ [ {100, []}, {0, []} ] ] }`.
3. It then calls the generator with SF = [ {100, []}, {0, []} ]
4. So qcheck enters generator for the sub-branch (for color) with SF = [ {100, []}, {0, []} ]
5. Suppose the 1st branch is selected, then qcheck will extract [] from {100, []}
6. Since constructor black/0 has no argument, the program will stop the recursive call.