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.

For instance, suppose we have a list of people giving their names and ages, as follows:

(define-struct person (name age))

where name is a string and age is a number.

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

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 aged people of that length. Feel free to use the function random.
  

  generate-input : number -> (listof person)

• Write a function that determines whether the second input is a sorted version of the first.
  

  valid? : (listof person) (listof person) -> boolean

• Using valid? and generate-input (along with any other edge cases you think to include), write a function that tests whether an algorithm is a valid sorter.
  

  oracle : ((listof person) -> (listof person)) -> boolean

To do well on this assignment, you will want to spend time considering all the different ways that output could be either invalid or inconsistent with the original problem statement. Be thorough! That's the name of the game when testing.

Testing the Tester

To exercise your oracles, you would benefit from having a correct implementation of a sorting function. You can either implement one yourself, or use the built-in sort function to create one. You can then perturb its output to create incorrect implementations as well, to test your oracle.

What to turn in:

Create a single Racket file, sortacle.rkt, containing your implementation. Turn it in using

cs019_supp_handin sortacle

Note that you are using a different command than used for CSCI 0170, because the homeworks are being graded by different people.