Exercises

Note: if the links to code do not seem to work in your browser, try opening them in a new tab or downloading them, instead of only clicking on them.

Exercise: black box test [✭✭]

Download sets.ml It implements sets with a list. Read the Set signature at the top of it; do not read down to the end of the file where that signature is implemented as ListSet.

Based on the specification comments of Set, write an OUnit test suite for ListSet that does black-box testing of size and choose. Write enough tests to detect at least one bug in both size and choose without ever reading their implementations.

□

Exercise: black box test rest [✭✭✭]

Finish writing a black-box OUnit test suite for the rest of the functions in ListSet. Find at least one bug in every function except empty and to_list.

□

Exercise: fix ListSet [✭✭✭]

After you have found at least one bug in each function, go read the implementation of ListSet. Fix all the bugs in it and make your test suite pass.

□

Exercise: set glass box [✭✭✭, optional]

Achieve as close to 100% code coverage with Bisect as you can for ListSet.

□

Exercise: Enigma glass box [✭✭✭✭]

Go back to your A1 solution. Find out what your code coverage was from your test suite. If it wasn't 100%, add more unit tests!

□

QCheck

The exercises in this section are all optional.

Exercise: generate list [✭✭, optional]

Use QCheck.Gen.generate1 to generate a list whose length is between 5 and 10, and whose elements are integers between 0 and 100. Then use QCheck.Gen.generate to generate a 3-element list, each element of which is a list of the kind you just created with generate1.

□

Exercise: arbitrary list [✭✭, optional]

Use QCheck.make and part of your solution to generate list from above to create an arbitrary that represents a list whose length is between 5 and 10, and whose elements are integers between 0 and 100. The type of your arbitrary should be int list QCheck.arbitrary.

□

Exercise: even arbitrary list [✭✭, optional]

Use your solution to arbitrary list from above to create and run a QCheck test that checks whether at least one element of an arbitrary list (of 5 to 10 elements, each between 0 and 100) is even. You'll need to "upgrade" the is_even property to work on a list of integers rather than a single integer.

Each time you run the test, recall that it will generate 100 lists and check the property of them. If you run the test many times, you'll likely see some successes and some failures.

□

Exercise: even arbitrary list QCheck test driver [✭✭, optional]

Transform your solution to even arbitrary list to a file test_list.ml that, when compiled an executed from the command line, runs that test and prints the result.

□

Exercise: even arbitrary list OUnit test driver [✭✭, optional]

Convert your test driver test_list.ml from using the QCheck runner to using the OUnit test runner (that is, the final line of the file should invoke OUnit2.run_test_tt_main).

□

Exercise: arbitrary list [✭✭, optional]

Use QCheck.make and part of your solution to generate list from above to create an arbitrary that represents a list whose length is between 5 and 10, and whose elements are integers between 0 and 100. The type of your arbitrary should be int list QCheck.arbitrary.

□

Exercise: even arbitrary list improved [✭✭, optional]

Upgrade your solution to even arbitrary list to use QCheck.list_of_size and its friends instead of QCheck.Gen.list_size. When finished, you'll be able to see lists that violate the property.

You'll likely notice after finishing that exercise that there's only one list that is ever reported as violating the property, which is the empty list. That's because when QCheck finds a value that violates the property, QCheck attempts to shrink that value down to the smallest input it can find that also violates the property. The shrink field of arbitrary is part of that functionality. Shrinking an int involves making it closer to 0; shrinking a list involves shrinking its elements individually as well as omitting elements from the list; and so forth.

□

Exercise: odd_divisor [✭✭, optional]

Download qchecks.ml In it there is a function odd_divisor. Write a QCheck test to determine whether the output of that function (on a positive integer, per its precondition; hint: there is an arbitrary that generates positive integers) is both odd and is a divisor of the input. You will discover that there is a bug in the function. What is the smallest integer that triggers that bug?

□

Exercise: qcheck max [✭✭✭, optional]

The file qchecks.ml contains a function max that is buggy. Write a QCheck test that detects the bug. You will have to figure out how to make an arbitrary that can generate two integers as inputs. Hint: QCheck.pair has type 'a arbitrary -> 'b arbitrary -> ('a * 'b) arbitrary. You will also have to devise an appropriate property to check. Hint: the maximum of two numbers must be at least as big as each of them, and must be equal to one of them.

□

Exercise: qcheck avg [✭✭✭✭, optional]

The file qchecks.ml contains a function avg that is buggy. Write a QCheck test that detects the bug. For the property that you check, construct your own reference implementation of average, such as the following:

let ref_avg lst =
  (float_of_int (List.fold_left (+) 0 lst)) 
    /. (float_of_int (List.length lst))

Compare the output of avg to the output of ref_avg to determine correctness.

Hint: this bug is harder to find and might require coming up with good inputs to check based on glass-box inspection of the source code.

□