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]
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
each string in the output is an atomic symbol, and
the concatenation of the strings in the output yields the input.
check: elemental("Shriram") is [list: "S", "H", "Ri", "Ra", "M"] end
check: elemental("...") is [list: ...] end
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