Oracle
1 What is This Assignment’s Purpose?
Sometimes, as we already saw with Sortacle, a where block just isn’t enough. When you are testing complex functions, or perhaps even relations (as in the case of this assignment), you will need to put time and effort into building testing oracles. This assignment gives you a harder problem to test than Sortacle.
This assignment is also, however, subtly different from Sortacle. In Sortacle, you had already seen an implementation of a solution to the problem before the assignment went out. (And even if you hadn’t, you could quite easily have implemented it yourself.) Here, you’re seeing a problem you are most probably unfamiliar with and may very well not know how to solve. This often happens with testing: you have to test a program whose implementation details you don’t know (and perhaps cannot know, because of size, complexity, reliance on niche concepts, or legal concerns).
2 Group Work
When working with partners, the collaboration policy applies to a pair as a whole, rather than to individuals. Indeed, you are required to collaborate.
We strongly recommend a pair-programming strategy called driver/navigator. The driver is the person with the keyboard; the navigator is the person discussing, reading each line as it’s written, and providing feedback. Every fifteen minutes, swap roles. It’s a really good habit to get used to.
Please turn in only one submission, agreeing with your partner who will do the submitting.
You may not use a late pass for this assignment!
3 Theme Song
The Less I Know by Tame Impala
4 The Stable Hiring Problem
In this assignment, you will develop oracles to test purported solutions to the Stable Hiring Problem. You can learn more about the problem from Wikipedia, but a summary of the problem is as follows:
Assume you have two sets, A and B, each with n members. Every member in A wants to be matched with exactly one member of B and vice versa. Every member of each set ranks its preference for being matched with each member of the other set by assigning each one a unique number between 0 and n-1 (i.e., providing a total ordering of members of the other set). No member from set A can assign the same ranks to two distinct members of set B, and vice versa.
As an application of this problem, imagine matching companies with candidates. Each company will keep an internal ranking of all the candidates, based on who they would prefer to hire (we assume that only one candidate will be hired per company). Each candidate also has an opinion about where they want to work and therefore ranks each company as well. A programmer is asked to design and implement a program that generates n pairings of n companies with n candidates. The program’s generated “hires” are stable if there are no two members, one from each set, that would prefer each other to their current match.
There are many problems of this nature. Consider assigning TAs to classes; matching residents with hospitals; pairing students for homeworks; and much more. Of course, some of these problems represent a slight variation on the theme (maybe the companies don’t rank every candidate, or are allowed to give some of them the same rank; maybe you have only partial information for making the assignment; etc.). Ultimately, however, this problem in its many guises has wide application.
5 The Assignment
Being confident that your software is correct involves more than just writing code you think is right. However, it’s difficult to test complex software entirely by hand. Naturally, a computer scientist’s solution to this problem is to automate testing. Your job in this assignment is to use property-based testing to evaluate hypothetical solutions to the stable hiring problem.
Your oracle’s job is to generate and feed test inputs to this solution, and test the correctness of the output. In the past, excluding Sortacle, you did this by comparing the output to a precomputed correct answer. This assumes two things: that there is only one right answer, and that it is easy for you to find it. In the real world either or both of these can and will be false. (How do you know what the right answer to an arbitrary instance of the problem is if the original problem was to write a program to find it?)
Before you start writing code, we once again want you to write a Testing Plan. Recall that the testing plan should be written before you begin your implementation. Hopefully you are getting more practice with these now! Once again, upload it early!
To seed your implementation work, we are giving you an input generator and a correct solution to the stable hiring problem to help you write and test your oracle. You submit your oracle, and we unleash all forms of incorrect solutions on it, each with its own subtle flaw.It’s worth thinking about when we can conclude that we’re “done”. We ought to have multiple correct matchmakers because there are multiple correct outputs for each input. How many suffice?
You are not expected to create another solution to the stable hiring problem, but you should consider how many possible outputs there are for a given input.
You should create incorrect matchmakers, which you can do by thinking about how you can manipulate the output from the provided matchmaker implementation to create incorrect matchmakers.
You have access to the data structures and functions Hire, hire, is-hire, matchmaker, and generate-input from the support code, which is automatically imported in the template given below. Be cautious about using the provided matchmaker function in your oracle implementation, as this assumes that there is only one right answer to a given instance of the stable hiring problem, but that is not the case for this problem statement.
data Hire:
| hire(company :: Number, candidate :: Number)
end
fun matchmaker(companies :: List<List<Number>>,
candidates :: List<List<Number>>)
-> Set<Hire>:
See the next section for a more in-depth description of generate-input.
6 Input-Output Specification
Each purported solution will be a function like matchmaker that
consumes two arguments, both of which are List<List<Number>> in
which every list (both inner and outer, for both lists) is of the same
size (call it n but n is naturally not fixed). The first list
provides the companies’ preferences, the second one those for the
candidates (though you should convince yourself it doesn’t matter
which one is which). Each inner list corresponds to a specific
candidate or company—
generate-input :: Number -> List<List<Number>>
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. This will be helpful when testing your oracle. Be thorough! That’s the name of the game when testing.
fun is-valid(companies :: List<List<Number>>,
candidates :: List<List<Number>>,
matches :: Set<Hire>)
-> Boolean:
Using generate-input and is-valid, write a function named oracle that tests whether an algorithm is a valid solution to the stable hiring problem.
Remember, an algorithm may sometimes produce a correct solution even if it is an incorrect algorithm. At the same time, there are numerous ways for an algorithm to return an incorrect solution. Therefore, your oracle should try to only return true if an algorithm seems to always produce a stable set of hires (where “always” is quantified by some number of tests).
fun oracle(
a-matchmaker :: (List<List<Number>>, List<List<Number>>
-> Set<Hire>)
)
-> Boolean:
7 Built-Ins
For this assignment, we are allowing you to use Pyret’s built-in List, Number, and Set libraries (in addition to anything in the course programming language instructions). Feel free to use any set functions or methods, including list-to-list-set and .to-list. These have all been provided for you.
8 Starter
We do not expose wheats and chaffs for this assignment.