## Dictionaries revisited
This recitation relies on the attached [code](broken_code.zip), which implements a
dictionary interface using a binary search tree, a list, and a sorted list.
This code has some bugs. In this recitation, we will use testing and debugging
tools to find the bugs. You aren't required to fix them, but if you want extra
debugging practice, fixing them would be good exercise!
**Exercise**: unpack the code into your working directory for the recitation,
and create your usual recitation working file (the one that you'll `#use` as
you go). Read the `.mli` files to get a high-level overview of what's in each
**Exercise**: use `cs3110 compile` to compile the three dictionary
implementations. Add the appropriate `#directory` and `#load` commands to your
working file for the recitation. To make sure that you've set everything up,
add the following lines to your working file and `#use` it:
let x = BstDict.(insert empty 0 'x')
let y = ListDict.(insert empty 1 'y')
let z = SortedListDict.(insert empty 2 'z')
If this does not work, you may wish to revisit [lab 3](../03-var/rec.html) or
ask for help.
### Unit testing
Unit tests are tests of the smallest parts of the codebase. They will
typically test a single function on a variety of inputs to ensure that the
function gives the expected output.
When developing unit tests, it is important to test examples that exercise
different parts of the code, and also to try to design tests that stress unusual
corner cases. The **coverage** of a set of tests is the set of lines of code
that are executed while running the tests; ideally, your tests would have 100%
In fact, for many languages, there are tools called "coverage checkers" that
will run your tests and tell you how much of your code was actually tested. We
will not ask you to use coverage checkers, but if you are curious, you can look
into [the bisect tool](http://bisect.x9c.fr/).
**Exercise**: On a piece of paper, draw a collection of binary search trees and
elements to insert and remove that would give you good test coverage of
`BstDict.insert` and `BstDict.remove`. For each, draw the expected output tree.
**Exercise**: In your working file for the recitation, write down expressions
that test the inputs and outputs you drew in the previous exercise. For
insert (Node (Leaf, 0, 'x', Leaf)) 1 'y'
= Node (Leaf, 0, 'x', Node (Leaf, 1, 'y', Leaf));;
If you `#use` the file, you will find that it doesn't compile, because the
`Node` and `Leaf` constructors are not public; they are not exposed by
This leads to a problem: you can't put your unit tests anywhere but `bstDict.ml`
because the necessary details are hidden. But if you put them in `bstDict.ml`,
then they will be run anytime anyone uses your `bstDict` module in their
To resolve this dilemma, the `cs3110` tool provides a small syntax extension to
OCaml to let you write and run unit tests. You can write a test as follows:
TEST = ...
where "..." is an expression that evaluates to either true or false. You can
also give your test a name, for example:
TEST "my_test" = insert (Node (Leaf, 0, 'x', Leaf)) 1 'y'
= Node (Leaf, 0, 'x', Node (Leaf, 1, 'y', Leaf))
The code in the `TEST`s will not normally be executed; to actually run the
tests, you can run `cs3110 test `. This will cause all of the `TEST`s
defined in your program to be run; any that evaluate to false will be printed
out on the console.
**Warning**: before running `cs3110 test ` you must first `cs3110
compile `. If you change the code or the tests, you will need to
recompile before running `cs3110 test` again!
**Exercise**: to see how failing tests look, add
TEST "designed_to_fail" = 1 < 0
to `bstDict.ml`, and run `cs3110 test` on it.
**Exercise**: move your bst unit tests to the `bstDict.ml` file, using the
`TEST` keyword. Use `cs3110 test` to run them and see if any fail.
### Testing for exceptions
Sometimes you just want to test that a function doesn't raise an exception. You
can use `TEST_UNIT` to do that. `TEST_UNIT` is like `TEST` except that the
expression should evaluate to `unit` (instead of `true` or `false`); the test
fails if it raises an exception.
**Exercise**: `SortedListDict.first` uses `List.hd` and so it might throw an
exception. Write some tests using `TEST_UNIT` to check that it doesn't.
### Tests that share set-up code
Sometimes you want to write multiple tests that use some shared data structure
or code, or require some complicated procedure to set the tests up before you
The `TEST_MODULE` keyword allows you to write a large block of code that gets
executed during testing. In particular, it lets you define a module that is
only created during testing, and it runs any `TEST`s inside that module. The
syntax is as follows:
TEST_MODULE = ...
where ... is a module. As with `TEST` and `TEST_UNIT`, you can add a name if
you like. For example:
TEST_MODULE "tree_tests" = struct
let example = Node (Leaf, 0, 'x', Leaf)
TEST "insert_in_tree" =
insert example 1 'y' = Node (Leaf, 0, 'x', Node(Leaf, 1, 'y', Leaf))
TEST "remove_1_from_tree" =
remove example 1 = example
TEST "remove_0_from_tree" =
remove example 0 = empty
In general, creating example might be complicated; but the code in the
module defined by the `struct ... end` will only be executed during testing.
**Exercise**: group some of the tests you defined in `bstDict.ml` into a module
and use `TEST_MODULE` to run them.
### Regression testing
When developing your code, you will often come across bugs. A very good habit
to develop is to create a unit test as soon as you discover a bug. This helps
for three reasons:
- Narrowing down the bug to a "minimal test case" can help you figure out where
the bug actually is.
- By developing the test case first, you can easily check a fix to see whether
- It turns out that bugs often reappear in the future as people continue to
hack on the code. Documenting the bug in your test suite will notify someone
immediately if they accidentally reintroduce the bug, which will likely make
it easier for them to re-repair it.
Tests that are based on pre-existing bugs are called **regression tests**.
**Exercise** (\*): You probably remember at least one bug you had in A1. Write
a regression test to detect that bug.
**Exercise** (\*): As you implement future assignments, be sure to create
### Test-driven development
There is a popular approach to programming called "test-driven development"
(TDD). The idea behind TDD is that you start by writing your interface (your
`.mli` file), but leave your implementation completely stubbed out (for example
by defining every function as just `failwith "not implemented"`. Then you
write your tests (which won't pass, of course). Only *after* you have a test
suite that you're happy with do you start writing the actual code.
Whether to write your tests before, during, or after development of your code
is a matter of taste to some extent. I encourage you to experiment with TDD
during the course of the semester so that you can find the style that you are
However, regardless of *when* you write your tests, you should spend time
writing and thinking about tests. Don't put testing off until the last minute.
In many software development teams, code without adequate tests will be
### Interface testing
As you consider writing tests for the other `Dictionary` implementations
(`ListDict` and `SortedListDict`), you will find that there are many tests that
work just as well for all three implementations. For example, the `Dictionary`
specification says that for any `x`, `remove empty x = empty`; this test could
be written for any of the three dictionary modules, or for any other dictionary
**Exercise:** By examining the comments in `dictionary.mli`, describe at least
one general test for each function in the `Dictionary.S` module signature.
Tests that rely only on an interface are called **interface tests** or
**black-box tests** (because they don't depend on the implementation details
of the module being tested). Tests that do depend on the implementation are
sometimes called **glass-box tests**.
A good way to implement interface tests is by putting them in a functor in the
same file in which a module type is defined. The functor takes in an
implementation module, and contains a collection of interface tests. For
example, you might include the following in `dictionary.ml`:
module Tests (D : Dictionary) = struct
TEST = remove 0 empty = empty
TEST = remove 1 (insert 1 empty) = empty
If you define your tests this way, then new implementations of the interface
get all of those tests "for free". After implementing a module `D`, you can
TEST_MODULE "specification tests for D" = Dictionary.Tests(D)
to run all of the specification tests.
**Exercise**: write a `Dictionary.Tests` functor as described above. Include
all of the general tests you listed in the previous exercise. Create a file
called `tests.ml` containing the following lines:
TEST_MODULE "spec tests for BstDict" = Dictionary.Tests(BstDict)
TEST_MODULE "spec tests for ListDict" = Dictionary.Tests(ListDict)
TEST_MODULE "spec tests for SortedDict" = Dictionary.Tests(SortedDict)
Run the tests, and see if you discover any new bugs!