Sortacle🔗

1 What is This Assignment’s Purpose?🔗

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. One likely cause is that the problem statement allows a given input to produce multiple different answers.

Both these motivations point in the same direction, which is to write programs that can check programs. Specifically, we will study a form of it called property-based testing. This technique is seeing increasing use in industry, especially to test systems that are complex or may have non-deterministic behavior (e.g., distributed systems, cryptographic systems, etc.). You should think hard about the range of values that are sensible for the data below.

2 Theme Song🔗

I Can Sort by HeidiSongs

3 A Simple Example🔗

Consider the square-root function. Given an input of 4, you might write that you expect it to produce 2. Mathematically, however, it’s equally reasonable for the implementation (if it produces only one value) to produce -2. Neither your expectation nor the implementation is wrong; you’re just mis-matched. So what is a better way to test the range of possible square-root functions? It would be to square the output and check that it does, in fact, produce the same value as what it was given. Keep this example in mind as you read on.

4 The Oracle🔗

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

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

5 Input-Output Specification🔗

Your assignment has three tasks:

1. Write a function named generate-input that generates a list of random Persons. It should take a non-negative integer length, and return a list of that many randomly constructed people. You will probably find it helpful to use num-random for ages. Names should also be randomly generated.Sometimes this can also become part of an allegedly criminal activity! See items 48–71 of this SEC Complaint. Choosing from a pool of names is not sufficiently random; instead, you might consider using string-from-code-points.

   generate-input :: Number -> List<Person>

   Keep in mind that you would not be able to directly test generate-input, as it returns random lists. However, you could still write tests to check whether the value it produces has reasonable properties.

2. Write a function that consumes two lists of Persons and determines whether the second input is a sorted version of the first.

   is-valid :: List<Person>, List<Person> -> Boolean

3. Using is-valid and generate-input, write a function that consumes a function and tests whether the given function is a valid sorter. Note that you must use generate-input (possibly many times), but should also explicitly include any edge cases that you think are important.

   oracle :: (List<Person> -> List<Person>) -> Boolean

   Note that the argument to oracle is a function that 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—e.g., one that produces the wrong answer only when the input has 19 elements. In short, be thorough! That’s the name of the game when testing.

6 Testing the Tester🔗

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.

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

8 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; make sure to write tests for all required functions.

9 Builtins🔗

For this assignment, you should not use any libraries that are not explicitly permitted. You are permitted to use the number and string libraries, and from the list library, only map, filter, the two folds, sort, and sort-by. Note that you should use sort and sort-by only for testing (the parts of) your oracle, not in its implementation! You should be able to implement everything else you need on your own. (If you think we’re mistaken, please ask on EdStem.) However, you are allowed to use other functions in your check blocks.

Please also remember to follow our coding guidelines.

10 Starter🔗

Template

There are no wheats and chaffs for this assignment.

11 Socially Responsible Computing🔗

Read/View

Read this article.

Write

Why do you think we assigned this reading? Can you think of any falsehoods that the author missed? How might you (or how did you) go about mitigating some of these falsehoods in your Sortacle implementation?

In some sense, all user profiles are reductionist in that they condense a human being into an object with several predefined traits. What human characteristics (beyond names) do you think software developers tend to reduce in ways that are harmful to people who carry specific traits?

Optional Readings

This article contains illustrative examples for the previous one, in case you need them. It’s always good to have examples!

This thread introduces you to naming conventions for Vietnamese and other Southeast Asian names. If you can’t read the thread on Twitter/X, here’s a ThreadReader Unroll of the whole thing.