Richard Ipsum Property Testing in C

One nice thing about Haskell is Quickcheck, if you're not familiar with Haskell or Quickcheck it works like this:

Prelude> let evens xs = [ x | x <- xs, x `mod` 2 == 0 ]
Prelude> evens [1..10]
[2,4,6,8,10]

Here we define a function that takes a list of numbers and returns only the even numbers. We can use Quickcheck to test this function:

Prelude> import Test.QuickCheck
Prelude Test.QuickCheck> let test_evens xs = [ x | x <- evens xs, x `mod` 2 /= 0 ] == []
Prelude Test.QuickCheck> quickCheck test_evens
+++ OK, passed 100 tests.

Here we define a test function that asserts that a list of even numbers shouldn't contain any odd ones. Passing this function to Quickcheck shows that the function passed 100 tests. Quickcheck sees that our test_evens function takes a list of numbers and returns a boolean, and it tests our code by generating a set of random inputs and executing it with those inputs.

Clearly this type of testing can be very useful, and not just for Haskell programs. Theft is a C library that brings Quickcheck style testing to C. This sort of testing is known as Property Testing.

Let's reimplement our Haskell code in C,

#include <stdio.h>
#include <stdlib.h>
#include <theft.h>

struct IntArray {
    int len;
    int arr[];
};

struct IntArray *evens(struct IntArray *input)
{
    int nevens = 0;
    struct IntArray *output;

    if (input == NULL) {
        return NULL;
    }

    output = malloc(sizeof (struct IntArray) + input->len * sizeof(int));

    if (output == NULL) {
        return NULL;
    }

    for (int i = 0; i < input->len; i++) {
        if (input->arr[i] % 2 == 0) {
            output->arr[nevens++] = input->arr[i];
        }
    }

    output->len = nevens;
    return output;
}

Here we define a function that takes an array of integers and outputs an array of even integers.

Now let's do some testing!

Since C is not strongly typed like Haskell we need to define a function that describes what a test input should look like. Providing this information to Theft will allow it to generate real test input data. The function should have the following prototype,

enum theft_alloc_res allocate_int_array(struct theft *, void *, void **)

Let's write it!

enum theft_alloc_res allocate_int_array(struct theft *t, void *data, void **result)
{
    int SIZE_LIMIT = 100;

    int size = theft_random_choice(t, SIZE_LIMIT);

    struct IntArray *numbers = malloc(sizeof (struct IntArray) + size * sizeof(int));

    if (numbers == NULL) {
        return THEFT_ALLOC_ERROR;
    }

    for (int i = 0; i < size; i++) {
        numbers->arr[i] = theft_random_choice(t, INT_MAX);
    }

    numbers->len = size;

    *result = numbers;

    return THEFT_ALLOC_OK;
}

theft_random_choice is a function that will pick a random number between 0 and some defined limit. The result is not truly random, but instead based on the complexity of the input Theft requires. The documentation for Theft points out that the main thing with this is to ensure that wherever theft_random_choice returns 0 our alloc_int_array function should return the simplest input possible, in our case that would be an empty array.

Theft passes a reference pointer to the alloc_int_array function, this must be updated to point to the array we have allocated before the function returns with THEFT_ALLOC_OK. In the event of some kind of error the function should return THEFT_ALLOC_ERROR

Next we write the property function, this function takes an input array of integers generated by Theft, runs our evens function over that input and asserts that the resultant output doesn't contain any odd numbers.

enum theft_trial_res property_array_of_evens_has_no_odd_numbers(struct theft *t, void *test_input)
{
    struct IntArray *test_array = test_input;

    struct IntArray *result = evens(test_array);

    // Array of even numbers should not contain any odd numbers
    for (int i = 0; i < result->len; i++) {
        if (result->arr[i] % 2 != 0) {
            return THEFT_TRIAL_FAIL;
        }
    }

    return THEFT_TRIAL_PASS;
}

Putting this together, we define some boiler plate to cover the various functions we just defined for generating test inputs,

struct theft_type_info random_array_info = {
    .alloc = allocate_int_array,
    .free = theft_generic_free_cb,
    .autoshrink_config = {
        .enable = true,
    }
};

The alloc member is updated to point to the function we just defined. Since the test inputs are dynamically allocated with malloc they will need to be freed later on. Theft provides a generic function for freeing which is sufficient for our purposes: theft_generic_free_cb.

The last member of this structure needs more explanation. If Theft encounters an input which causes the test to fail, it will try to pare down the input to the smallest input that causes failure; this is called shrinking.

Theft lets you define a function that can provide some control over the shrinking process, or it can use its own shrinking functions: autoshrinking. If autoshrinking is used however, the function that allocates test inputs must base the complexity of the input it generates upon the result of one of the theft_random functions, such as theft_random_bits, or theft_random_choice. This is why our alloc_int_array function uses theft_random_choice rather than standard pseudo random number generating functions.

Finally we write a function to execute the tests,

int main(void)
{
    theft_seed seed = theft_seed_of_time();
    struct theft_run_config config = {
        .name = __func__,
        .prop1 = property_array_of_evens_has_no_odd_numbers,
        .type_info = { &random_array_info },
        .seed = seed
    };

    return (theft_run(&config) == THEFT_RUN_PASS) ? EXIT_SUCCESS : EXIT_FAILURE;
}

Compiling and running:

$ gcc -o test test.c -ltheft
$ ./test 

== PROP 'main': 100 trials, seed 0x62a401b7fa52ac8b
.......................................................................
.............................
== PASS 'main': pass 100, fail 0, skip 0, dup 0

I hope this helps anyone looking to try out Property Testing in C. Another guide that might be useful can be found here, it has an example that uses a manually defined shrinking function, which may be useful for more complex situations.

Posted Wed Dec 6 12:00:07 2017

We've previously spoken about how your workstation area matters, mentioning topics such as consistency in input surfaces, arrangement of screens, good chairs, etc. Today I'd like to extend that to talk about the general environment in which you're working/hacking/playing.

As with all these little articles, I have a story to tell, and this one is about how my heating boiler died at home and I had to spend two weeks with a computer room which was consistently below 10 degrees celsius unless I spent a lot of electricity heating it up. Sitting in the cold at my keyboard was difficult. You can put jumpers on, and generally keep yourself warm, but for at least some of us, our hands still get cold, and that can be quite unpleasant when you're a keyboard worker.

The temperature of your working/hacking/playing environment will affect your effectiveness dramatically. If it's too cold, or too warm, you will not be able to think properly and your reaction times will grow. Keeping the area around your workstation clear of clutter will also improve your ability to think, though some do benefit from having one or two fiddling things for when you need to do something with your hands while your brain wanders off to solve the problem.

I recommend ensuring that there's not too much in the way of noise distraction at your workstation too. Music is something that some of us find helps, as can a white noise generator or rain generator. I sometimes use an internet cat to help me relax, but it's important to try and block out sounds which you cannot predict or control such as building site noise, other people talking, etc.

For me, it's also important to try and eliminate unexpected or unpleasant scents from your workstation too. I find that I cannot concentrate if I can smell food (sometimes a big issue because my neighbours love to fry onions at times of day when I'm hungry).

Keep hydrated. While that's not entirely an environmental thing, ensuring that you have an adequate supply of water, squash, tea, or whatever you prefer, is very important. Bad hydration causes your brain to behave similarly to being drunk or super-tired. Obviously if you're going to keep hydrated, don't try and sit and work through a full bladder, that can be just as distracting/unhelpful.

Your homework for this week is to look critically at your work/hack/play environment and make at least one small change for the better. Perhaps you could comment below about a change you made and how you feel it has affected you, either positively or negatively. If you have other tips for improving your work/hack/play space then also include them below.

Posted Wed Dec 13 12:00:10 2017

When I was young and has just started to learn programming, I read some descriptions of what programming was like as a job. These fell roughly into one of two categories:

  • long meetings, and writing a lot of documentation
  • long days of furious hacking fuelled by chemicals

That was decades ago. I have since learn from experience that a programmer's productivity is best boosted by:

  • knowing clearly what to do
    • a well-defined goal is easier to reach than one that is unclear or changes all the time
  • knowing one's tools and being comfortable with them
    • the exploration phase of using a new tool is rarely very productive
  • not being interrupted while doing it
    • being in the flow is commonly preferred, but may or may not be necessary; however, frequent interruptions are anti-productive in any case
  • getting enough sleep
    • continuous yawning is distracting, concentration is difficult if your brain is hallucinating from lack of sleep
  • avoidance of bad stress
    • stress that makes you worry about the future is bad
  • having a reliable source of lapsang tea
    • but I need to stop drinking it at least six hours before bedtime, or I sleep badly
  • a comfortable work environment

It further helps to use various tools that allow the programmer concentrate on cranking out the code:

  • automated language checkers
    • statically types languages require you to get types right, and will catch you if you mistype a variable name
    • static checkers for dynamically typed languages can often do the same job
    • either way, they help you catch errors earlier, which means you spend less time waiting for an error to happen
  • automated tests
    • unit tests, integration tests, etc, allow you to avoid spending time and effort on doing the same tests manually over and over
  • reuse of high-quality code
    • this means libraries, code generators, tools you can run, etc
    • these save you time by not having to write the code yourself
    • they further save time by not having to debug the code you wrote
    • however, beware of low-quality code; it won't save you time, since you'll almost certainly have to debug and fix it yourself
  • automated systems to run your automated tests
    • continuous integration runs without you having to remember to run your tests
    • it also runs them in the background, meaning you don't need to wait for them to finish, which is especially useful when you have slow tests
    • the tests also get run in a well-defined environment, rather than the developer's randomly configured ever-changing laptop
  • automated system for installing software on target machines
    • continuous delivery takes care of installing your software somewhere you can use it, which may or may not be the production server
    • this is especially useful for server, web, and command line software, but is generally useful
    • often the process of installing manually is tedious - just like doing manual testing - so the more it's automated the less time you waste on repetitive work
Posted Thu Dec 28 12:00:08 2017 Tags: