## 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 file. **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% coverage. 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 example:  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 bstDict.mli. 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 program. 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 TESTs will not normally be executed; to actually run the tests, you can run cs3110 test <program>. This will cause all of the TESTs defined in your program to be run; any that evaluate to false will be printed out on the console. **Warning**: before running cs3110 test <program> you must first cs3110 compile <program>. 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 run them. 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 TESTs 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 end  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 worked. - 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 regression tests! ### 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 comfortable with. 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 rejected immediately. ### 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 module. **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 open D TEST = remove 0 empty = empty TEST = remove 1 (insert 1 empty) = empty end  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 simply write  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!