Homework 4: Creating a Test Harness
[Starting with this assignment, please create a separate file for each class/interface that you define.]
Writing test cases can be tedious. In some cases, such as tests over very large data or tests of programs that could return one of many possible answers (such as AVL-tree rotation), writing explicit expected answers isn’t even feasible. We need to be able to run such tests in practice though, so what do we do?
Clearly, we need to rethink how we describe expected answers. Rather than write a specific expected answer, we can instead write programs that check various aspects of a correct answer. If a computed answer passes all of these test programs, we consider the test to be successful.
For example, imagine that you want to test a program that sorts a list into increasing order. You could write one program that checks whether the returned list is in sorted order, a second that checks whether the returned list has all of the elements of the original list, and a third that checks whether the two lists have the same size. The test case would then look something like
boolean SortTest (Tester t) { |
// your input test |
List<Integer> L1 = new ConsList (5, ...) |
// your computed output |
List<Integer> SL = L1.sort; |
boolean allTests = (SL.isSorted() && |
SL.sameSize(L1) && |
SL.containsEltsOf(L1)); |
return t.checkExpect(allTests, true); |
} |
This design isn’t ideal for several reasons:
We have to manually construct the allTests answer every time. An better testing framework would have us call some function with a computed answer and a list of tests (ie, functions) to run on that computed answer.
If allTests is false, we have no idea which tests failed. A better framework would report which tests failed, which suggests returning a list of failed tests rather than a boolean.
This design assumes that all of the testing methods are built into the data classes (ie, sorted lists have isSorted, sameSize, etc). This conflates testing with the programs we want to run. A better framework would define these testing functions externally so as not to clutter up the classes. This suggests that we should define the testing functions as methods that consume Lists.
In this assignment, we will start to build a testing harness with these better features. We’ll create tests for sorted lists this week. You will use your testing harness again on another assignment later in the term.
1 A Version in Racket
For those trying to picture what a testing harness looks like, this section sketches out a simple design in Racket. If you want to jump directly to the problems in the next section, feel free to do so. This section does not describe problems or assignment requirements.
1.1 The Racket Code
Here is a straightforward version of the code. The checker is in the last function (sortedListChecker1). The remaining functions define the tests that determine whether a sort function works properly. The andmap function used in hasEltsOf takes a predicate and a list and returns true if the predicate is true of every item in the list. The filter function takes a predicate and a list and returns the list of items from the original list that satisfy the predicate.
(define (sameSize L1 L2) |
(= (length L1) (length L2))) |
|
(define (hasEltsOf L1 L2) |
(andmap (lambda (elt) (member elt L2)) L1)) |
|
(define (allGtEq e L) |
(empty? (filter (lambda (Lelt) (> e Lelt)) L))) |
|
(define (isSorted L) |
(cond [(empty? L) true] |
[(cons? L) (and (allGtEq (first L) (rest L)) |
(isSorted (rest L)))])) |
|
(define (resultSorted L1 L2) (isSorted L2)) |
|
(define (sortedListChecker1 Lin Lans) |
(and (sameSize Lin Lans) |
(hasEltsOf Lin Lans) |
(isSorted Lans))) |
The sortedListChecker1 function isn’t very general, as it hardcodes the test (remember, our goal is to write a general-purpose testing framework). We first generalize the code by representing the tests as a list (sortedListChecker2), then take the list of tests as a parameter (make-Checker and sortedListChecker3).
(define (sortedListChecker2 Lin Lans) |
(andmap (lambda (test) (test Lin Lans)) |
(list sameSize hasEltsOf resultSorted))) |
|
(define (make-Checker tests) |
(lambda (Lin Lans) |
(andmap (lambda (test) (test Lin Lans)) |
tests))) |
|
(define sortedListChecker3 |
(make-Checker (list sameSize hasEltsOf resultSorted))) |
If you don’t understand how this code is set up, please ask questions before you start working on the Java version. The Java version won’t make sense if you don’t understand what this one is doing.
1.2 Converting the Racket Design to Java
What will we need to do to implement this Racket design in Java?
We will need to add andmap and filter to our list classes.
The test functions are passed as arguments (in sortedListChecker, so we will need to turn them into objects (ie, we need a class for tests). The class for a test needs fields for the arguments to the test (in this case, two lists).
We can’t have top-level functions in Java, so the sortedListChecker has to be an object with a method that can be used to execute the test.
The make-Checker function returns another function, so we will need to turn it into an object that provides the returned function as a method.
The following sections break these steps down into stages that will help you test your work incrementally. If you are confident in the course material, you might want to think about how you would break this problem into steps before reading further (it’s a good exercise). You can get partial credit for this assignment by completing the earlier stages, so work from the stages if necessary.
2 Stage 1: Adding Iteration Methods to Lists
Extend your GList (lists via generics) implementation from Homework 3 to satisfy the following interface (a different interface name for your lists is fine, as long as it uses generics):
interface IGList<T> { |
// returns the size (length) of the list |
int size(); |
// determines whether the list contains the given element |
boolean hasElt(T e); |
// returns list of elements for which predicate returns true |
IGList<T> filter(IPred<T> pred); |
// determines whether predicate returns true on all |
// elements in the list |
boolean andmap(IPred<T> f); |
} |
3 Stage 2: Creating a SameSize List Checker
In this stage, we will create enough of a testing harness to check whether two lists have the same size. We need to define a checker that takes a list of tests as input, and set up the methods to execute that list of tests.
Create an interface IListTest that requires a run method that consumes two lists of integers as arguments and returns a boolean.
Create a class sameSize that implements IListTest and whose run method returns true if the two input lists have the same size.
Create a class Checker with one field that holds a list of ListTests.
Add a Checker to your Examples class that has a list containing just the SameSize test. Make sure your code compiles at this point.
Now add a run method to Checker that consumes two lists (representing the input to and output from the list function you are testing) and returns a boolean indicating whether all of the tests pass when given those two lists.
Add some test cases on your Same-Size checker.
4 Stage 3: Adding the ContainsElt tests to the Checker
Create a class ContainsAllElts that implements IListTest and whose run method returns true if the second list contains all of the elements of the first list. Use the andmap function that you added to the list classes in Stage 1. Extend your Examples class (including tests) accordingly.
5 Stage 4: Improving the Feedback
Now, we want to extend the testing framework to report the status of each individual test in the list. Edit your framework to print out the result of each test. Do this by adding a toString method to each test, and printing the corresponding string prefixed with either "PASSED" or "FAILED" as appropriate. Figuring out where to put this code is part of the point of the question. Please add a comment to the point where you did this extension to help us find your solution.
6 Extra Credit: Add the IsSorted Check
We have not yet added the check that the returned list is sorted. For extra credit, extend your framework with this ListTest as well.
7 Perspective
We’ve made a lot of headway towards a testing harness in this assignment. Ideally, we would abstract this harness to work over any kind of data (not just lists of integers). We would also want to generate random test data (to help us test at scale). We will return to these and other issues in the coming weeks.
8 What to Turn In
Submit .java files containing the final versions of all classes, interfaces, and examples developed for this assignment. Do not submit the .class files. Submit a separate file for each class/interface (standard for Java) or a single file containing all classes and interfaces.
9 Grading
You will get more points for complete solutions to some stages than partial solutions to all stages.