\subsection{Testing and Quality Control} Testing computer programs is an important but difficult art. The goal is to build a test suite which is exhaustive but non-exhausting: {\em exhaustive} in the sense that programs which satisfy the test suite are likely to be correct, and {\em non-exhausting} in the sense that the procedures for constructing, evaluating, and maintaining the test suite are simple enough that they are not circumvented in the name of expediency. The LINK testing environment represents an attempt to strike a balance between these two forces. It provides tools and procedures to solve problems such as these: \begin{itemize} \item How do I know that I didn't break anything I make a change somewhere deep in the code? \item How do I know that the system is really portable across different machines? \item How do I know if making a change to a collection or container implementation significantly reduces the efficiency of some algorithm which uses it. \item How can we incorporate other people's code into the system and still feel confident about correctness? \item How can I test whether an algorithm works when the only interesting behavior is on large instances, where I may not know the correct answer. \end{itemize} The rest of this section describes the testing and quality control procedures for the LINK project. We describe two software tools which help in constructing and maintaining the test suite, and how they are used to ensure reliability. \subsubsection{The Regression Test Environment: ttool} STEAL JOHN'S TTOOL STUFF \subsubsection{Building Good Test Files} There are two aspects to any combat against an adversary: strategy and tactics. {\em Strategy} concerns the global plan of attack, while {\em tactics} are small scale actions with only an immediate end in view. Both are important, but they require thinking at different levels. In programming, algorithm development issues represent strategic thinking, while using mnemonic variable names and spacing to reflect program structure are important tactics. In testing, we are attempting to defeat the bugs being planted by our adversary, the gremlin. The strategic issues in building good test files include: \begin{itemize} \item Testing boundary conditions! It is important to test each function on (1) the empty structure, (2) the smallest non-empty structure, (3) a small but easily understood instance of the structure, and (4) a large or (if possible) the largest structure. Boundary conditions account for a large faction of all errors, but these can be easily smoked out with careful testing. \item Using random test structures and iteration. Running 10,000 random tests are a good way to see if the system will crash, and such a test is easily constructible using TCL control structures and random numbers. The difficulty is often how one should best interpret the result of a random test, since you usually do not know the correct result in advance. But if you are clever, you can work around this. For example, to test a graph isomorphism program, you can randomly permute the order of the edges and vertices of a copy of the graph, and verify that it is still isomorphic to the original. Another solution is to ... \item Use redundant implementations to test both simultaneously. If you have two ways to compute the same thing, say two different dictionary data structures like trees and priority queues, you can perform the same random sequence of insertions, deletions, and searches to both data structures, and see whether all the answers are consistent. If they are consistent, either both are right or both are wrong, but most likely both are right. If there is an inconsistency, somewhere there is definitely a bug. \item Test timing as well as correctness. A function taking too long on a small instance is a sign of a bad algorithm. To get an accurate timing on short functions, you should repeat the test in a loop enough so it runs for 4-5 seconds. \end{itemize} Tactics for ensuring good test files include: \begin{itemize} \item Build tests which minimize the amount of human intervention, and hence human error. Printing the contents of a 100 element list to make sure everything was inserted correctly is a bad test case, because it is hard to eyeball the list and be confident that you really know what it should be, and that it is what you know it should be. Much better would be to build two copies of the list in two different ways, and test if they are equal. It is easy to eyeball whether TRUE or FALSE is TRUE or FALSE. \item Making sure that each `\#test' block tests for exactly one potential problem in the program. It can be difficult to interpret what the correct output of a test should be when the test is complicated. It is also easier to see whether a set of simple test cases covers all possibilities -- ``there are four boundary cases, and look, there are four `\#test' blocks''. \item Use comments to explain what the test case is trying to establish. If you can't explain what a test case is doing, it probably isn't really doing something important, and if all your test cases are so simple that they need no explanation, you probably have too many test cases verifying too few properties. \item Break the test cases logically into fairly small files. Once you have verified that the program returns correct answers to each `\#test' in a given test script, you need never look at those test cases again, for the {\em tdiff} program will report whenever there is a violation. However, as you debug your testfile, you must verify each result by eyeballing it -- so you eyeball each `\#test' a smaller number of times if the file is small. \item Don't be afraid to write little TCL programs to make your testing easier. You have a full programming language at your disposal, including procedures with recursion, arbitrary control structures, etc. -- it is silly for your test scripts to consist of a long chain of single calls to the LINK library. \item Don't be afraid to hack up and reuse the same script to test different but related objects, such as containers. Devote the time to developing one good script, and then use it as a model. \end{itemize} GIVE AN EXAMPLE?? \subsubsection{The Regression Test Environment: tdiff} \subsubsection{The Test Suite} DISCUSS PROCEDURES FOR ADDING TO THE TEST SUITE, AND VALIDATING A NEW VERSION.