On this page:
1 Theme Song
2 The Oracle
3 Assignment Starting Point
4 Input-Output Specification
5 Testing the Tester
6 Determinism
7 Testing
8 Builtins
9 Handing In

Sortacle

    1 Theme Song

    2 The Oracle

    3 Assignment Starting Point

    4 Input-Output Specification

    5 Testing the Tester

    6 Determinism

    7 Testing

    8 Builtins

    9 Handing In

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 Theme Song

Right and Wrong by Cameo Culture

2 The Oracle

This assignment is not sponsored by any particular large technology company.

Suppose we have a list of people giving their names and ages, where a Person is as follows:

data Person:

  | person(name, age)

end

where name is a String and age is a non-negative 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 (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.

3 Assignment Starting Point

Template

You have not been given any wheats and chaffs (as noted below), but you still get the setup of three buffers to organize your work, in case that helps.

4 Input-Output Specification

Your assignment has three tasks:

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—e.g., one that produces the wrong answer only when the input has 19 elements—and if we do for fun, we won’t penalize you for not catching those. In short, be thorough! That’s the name of the game when testing.

5 Testing the Tester

Observe that the test cases for your oracle are programs. That is, to test your oracle, you need good and bad implementations of sorting. If you’d like a correct sorter, here’s one:

import lists as L

 

fun correct-sorter(people :: List<Person>) -> List<Person>:

  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:

  tdelvecc = person("Thomas", 18)

  sli96    = person("Ell", 65)

  jmcclel1 = person("Julia", 32)

 

  correct-sorter(empty) is empty

  correct-sorter([list: sli96]) is [list: sli96]

  correct-sorter([list: sli96, tdelvecc]) is [list: tdelvecc, sli96]

  correct-sorter([list: tdelvecc, sli96]) is [list: tdelvecc, sli96]

  correct-sorter([list: tdelvecc, sli96, jmcclel1])

    is [list: tdelvecc, jmcclel1, sli96]

end

You can only use this function in test cases. Feel free to perturb it or its output to create incorrect implementations, though you should also think of other interesting ways of producing incorrect “sorting” algorithms.

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—namely, the ones you’re using to test your oracle.

6 Determinism

In previous assignments, we wrote programs that are deterministic. That is, on a given input, they always produce the same output.

The testing oracle you will be implementing is non-deterministic: that is, because of randomness, your oracle may not always return the same output on a fixed input. Thus, the results of your tests could change from run to run. For example, when running your oracle on a wrong implementation, your oracle could catch the bug one time it is run, and miss it the next time.

Almost always, we prefer deterministic testing. It provides replicable results that are easier to debug. However, there are cases where deterministic testing is undesirable or impossible, such as in this assignment.

When dealing with non-deterministic functions, you will always have some amount of unpredictability. This unpredictability cannot be eliminated, but there are ways you can try to minimize it. Think of how you could decrease the chance your oracle reports incorrect implementations as correct.

7 Testing

There is no Examplar for this assignment. (If you’re curious why, think about what a wheat must be able to do.) You will still be required to turn in a final test suite.

8 Builtins

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 Campuswire.) However, you are allowed to use other functions in your check blocks.

Please also remember to follow our coding guidelines.

9 Handing In

sortacle-code.arr and sortacle-tests.arr

Submission form