▼Programming and Programming Languages
►4 Testing, Examples, and Program Checking
On this page:
4.1 From Examples to Tests
4.2 Oracles for Testing
4.3 Testing Erroneous Programs
    ← prev  up  next → 

4 Testing, Examples, and Program Checking

When we think through a problem, it is often useful to write down examples of what we are trying to do. For example (see what I did there?), if we’re asked to compute the [FILL]

There are, of course, many ways to write down examples. We could write them on a board, on paper, or even as comments in a computer document. These are all reasonable and indeed, often, the best way to begin working on a problem. However, if we can write our examples in a precise form that a computer can understand, we achieve two things:

  • When we’re done writing our purported solution, we can have the computer check whether we got it right.

  • In the process of writing down our expectation, we often find it hard to express with the precision that a computer expects. Sometimes this is because we’re still formulating the details and haven’t yet pinned them down, but at other times it’s because we don’t yet understand the problem. In such situations, the force of precision actually does us good, because it helps us understand the weakness of our understanding.

4.1 From Examples to Tests

failure of tests can be due to

- the program being wrong - the example itself being wrong

when we find a bug, we

- find an example that captures the bug - add it to the program’s test suite

so that if we make the same mistake again [REF: we do], we will catch it right away

4.2 Oracles for Testing

Consider the following problem: given a word (such as a name), we would like to spell it using the symbols of atoms (ignoring upper- and lower-case). This function, call it elemental, consumes a string and produces a list of strings such that

  • each string in the output is an atomic symbol, and

  • the concatenation of the strings in the output yields the input.

For instance, consider my name; it can be spelled as [list: "S", "H", "Ri", "Ra", "M"] (for [FILL], respectively). Thus we would write: 
check:
  elemental("Shriram") is [list: "S", "H", "Ri", "Ra", "M"]
end

Now consider another example: [FILL]. We can clearly see that this breaks down as 
check:
  elemental("...") is [list: ...]
end
We complete our program, get it correct, and turn it in. When we do, our examples are run against someone else’s programs, and vice versa. And then we both get reports that our programs are failing.

How could this happen?!? Well, consider the example: it also breks down as [FILL]. Since our program produces one output and other person’s program produces the other, each one fails.

Earlier [REF] we said that a test failure means one of two things: either the program is wrong or the test is wrong. But in this case, each person’s program produces a perfectly reasonable output, and each test is correct as well. In fact something more subtle is happening: there may be more than one way to solve a problem, and different implementations may pick different strategies, all correct. For such problems, the simple form of testing we’ve used until now no longer works. Instead, we need to do something more sophisticated.

4.3 Testing Erroneous Programs

- use RAISES to check erroneous code

    ← prev  up  next →