Sortacle
Being confident that your software is correct involves more than just writing code you think is right. That’s why we write tests. As computer scientists, we should therefore think about taking this a step further: to automate testing. How can we do that? We’ll see in this assignment.
There’s another motivation for what we’re going to do, which illustrates a weakness in the nature of testing as you’ve done it until now. When a test fails, the error is either in the implementation of the function (most likely) or in the test itself (usually less likely, but certainly possible). However, there is a third, more subtle reason: both the implementation and test are correct, but the implementation returned a different result than the test expected. The most likely cause is that the problem statement allows a given input to produce multiple different answers.
1 The Oracle
This assignment is not sponsored by any particular large technology company. In fact, if some other company would like to occupy this space, we could always consider changing the assignment’s name....
data Person:
| person(name, age)
end
Given a list of these people, suppose we want to sort them by increasing age. This ordering expressly does not say what should happen to people whose ages are the same; therefore, every permutation of their names is valid. As a result, concrete tests (i.e., ones where you write a specific output corresponding to an input) may fail for no good reason.
The problem lies in the fact that we wrote concrete tests at all. Instead, we should have written a function that checks whether the output has the right relationship with the input; then, all the valid outputs for a given input would pass, but no others. This checking function is sometimes called an oracle.
That is what we will do in this assignment: write a testing oracle for a function that sorts lists of persons. Your oracle will be given purported implementations of such a sort function, and it must (try to) determine whether the given function is indeed a valid sorter or not. In addition, you will write a generator of inputs. Combining the two, you arrive at a system that automates the testing of solutions to this problem.
2 Input-Output Specification
Your assignment has three tasks:
- Write a function named generate-input that generates input. It should take an integer length, and return a list of randomly constructed people of that length. You will probably find it helpful to use num-random.
generate-input :: Number -> List<Person>
Keep in mind that you would not be able to directly test generate-input, as it is returns random lists. However, you could still write tests to check whether the value it produces has reasonable properties. - Write a function that determines whether the second input is a sorted version of the first.
is-valid :: List<Person>, List<Person> -> Boolean
- Using is-valid and generate-input, write a function that tests whether an algorithm is a valid sorter. Note that you must use generate-input, but should also explicitly include any edge cases that you think are important.
oracle :: (List<Person> -> List<Person>) -> Boolean
Note that the first argument to oracle is a function, which consumes a list of Person and produces a list of Person (that’s what the notation (List<Person> -> List<Person>) means).
To do well on this assignment, you will want to spend time considering
different types of incorrect output an algorithm might produce, and
make sure your oracle covers all those cases. Of course, we may have
thought up cases you didn’t, so your oracle needs to be general, not
specific to those cases.However, we will not use
especially perverse non-sorters—
3 Testing the Tester
import lists as L
fun correct-sorter(people :: List) -> List:
doc: ```Consumes a list of people and produces a list of people
that are sorted by age in ascending order.```
L.sort-by(people,
lam(p1, p2): p1.age < p2.age end,
lam(p1, p2): p1.age == p2.age end)
where:
vince = person("Vince", 20)
joe = person("Joe", 18)
alex = person("Alex", 23)
correct-sorter(empty) is empty
correct-sorter([list: vince]) is [list: vince]
correct-sorter([list: vince, joe]) is [list: joe, vince]
correct-sorter([list: joe, vince]) is [list: joe, vince]
correct-sorter([list: alex, joe, vince]) is [list: joe, vince, alex]
end
One natural question you might have is how many tests you have to write of your oracle. It’s fine to have only one “positive” test, namely using sort or sort-by. You should have several “negative” tests (namely, functions that do not sort correctly).
You do not need to follow the recipe (write tests, etc.) of
these functions—
4 Coding Style
For this assignment, you should not use any libraries that are not explicitly permitted. We are permitting you the number and string libraries, and from the list library, only map, filter, the two folds, sort, and sort-by. You should be able to implement everything else you need on your own. (If you think we’re mistaken, please ask on Piazza.)
Please also remember to follow our coding guidelines.
5 Handing In
Use the filenames sortacle-code.arr and sortacle-tests.arr.