For today's OCaml part we briefly covered modules as described in
Hickey, chap.11+12 (and parts of chap.13). You shouldn't spend time on
the gory details of, e.g., "sharing constraints" in chap.13, though.
The Patricia tree part is described in more detail in the attached
research paper.
As exercises I ask you to consider the following:
1. a. Formulate in words a more aggressive shrinking strategy for
arithmetic expressions. (If you were to simplify such test-input
by hand how would you proceed?)
b. Implement the strategy and test how well it works
(how much it simplifies, how many steps it uses)
compared to the one I proposed for different false properties
such as
(fun e -> interpret (Plus(e,e)) = interpret e)
and
(fun e -> interpret (Times(e,e)) = interpret e)
To make sure you are comparing the shrinkers over identical runs,
use, e.g., QCheck_runner.set_seed : int -> unit
2. a. Formulate in words a shrinking strategy for lists.
(How would you combine it with the element shrinker?)
b. Implement the strategy and test how well it works
(how much it simplifies, how many steps it uses)
compared to the builtin list shrinker, for some false properties
over lists, e.g., (fun es -> List.reverse es = es)
3. a. Clone or download the quickcheck code from here
https://github.com/jmid/qc-ptrees
b. Compile (run "make old") and run the code (run "./qctest.native")
to ensure that you can recreate the issue.
c. Extend the testsuite with tests for the following API operations:
val is_empty : t -> bool
val diff : t -> t -> t
val equal : t -> t -> bool
val subset : t -> t -> bool
(For which ones is it necessary to extend the generator?)