
\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.


