Debugging, tests, and falsifiable hypotheses

Prerequisites: Functions, control flow, collections, and exceptions.

Learning objectives

• Reduce a failure to a small reproducible case.
• Choose tests from boundaries and invariants.
• Separate a test oracle from the implementation being tested.

Debugging is an experiment

A failing output is evidence that some assumption is false. Start by writing the expected behavior and the smallest input that demonstrates disagreement. Record the actual output, relevant environment, and a repeatable command. Changing several unrelated parts of a program at once makes it harder to learn which hypothesis was correct.

Suppose a maximum function starts its accumulator at zero. It appears correct on positive lists but returns zero for [-8,-3], although zero is not an input. The hidden assumption is that a valid maximum cannot be negative. A smaller failing case, [-3], exposes it clearly. Initialize from the first element and explicitly decide how empty input behaves.

def maximum(values):
    if not values:
        raise ValueError("empty input")
    best = values[0]
    for value in values[1:]:
        if value > best:
            best = value
    return best

assert maximum([-8, -3]) == -3
assert maximum([4]) == 4
assert maximum([2, 9, 9, 1]) == 9

Tests need independent expectations

A test oracle determines the correct result or property. Reimplementing the same algorithm inside a test can repeat the same defect. For tiny inputs, use hand-checked examples or a simpler exhaustive reference. For a sort, verify both nondecreasing order and preservation of the input multiset. Checking only order would incorrectly accept an implementation that always returns an empty list.

Properties cover families of cases. For nonempty numeric lists, maximum must be an element of the list and must be at least every element. Permuting the list should not change the result. These are useful checks, but generated examples still do not constitute a proof for all possible inputs. Contracts, proofs, tests, static checks, and runtime observation provide different kinds of evidence.

Observe the state that can explain the failure

Trace the values influencing the wrong decision, use a debugger to stop near the first divergence, and verify the suspected cause with a targeted change. After fixing it, keep a regression test that would fail on the old implementation. Avoid assertions that merely restate implementation details, such as the number of helper calls, unless those calls are themselves part of the contract.

Test layers serve different purposes. Unit tests isolate local behavior; integration tests check boundaries between real components; end-to-end tests exercise user-visible flows. Prefer the smallest level that can expose a defect, but do not assume isolated success proves the assembled system works. A passing test suite is evidence under the tested conditions, not a certificate that all defects are absent.

Practice problem

A deduplication function must retain the first occurrence of each value and preserve the original order. An implementation sorts the input and removes adjacent repeats. Construct a minimal example that exposes the contract violation. Specify three independent properties and at least five boundary-focused test cases. Describe a simple reference implementation suitable for small inputs, then explain why checking only that the output contains no duplicates would miss severe defects.

Worked solution

Input [2,1] should remain [2,1], but sorting returns [1,2], exposing order loss with no duplicates required. Properties include no repeated output values, equality between the input and output sets, and output order matching the indices of first appearances. Test empty input, one item, all items equal, already unique out-of-order input, and interleaved repeats such as [2,1,2,3,1], whose expected result is [2,1,3]. A simple reference scans left to right and appends an item only when it is absent from the output so far; its slower cost is acceptable for small tests and its logic directly reflects the specification. An implementation returning an empty list always has no duplicates, so uniqueness alone proves neither preservation nor ordering.

Check your understanding

A sorting test checks only that adjacent output items are ordered. Which faulty implementation could pass?

• One that always returns an empty list.
• One that reverses every nonempty list.
• One that returns a random permutation of every list.

Explanation

Ordering is vacuously true for an empty output. A second property must verify preservation of all input elements.

What is the main value of shrinking a failing input?

• It proves the bug cannot occur elsewhere.
• It makes the relevant assumptions and first divergence easier to inspect.
• It replaces the need for a specification.

Explanation

A minimal reproduction reduces irrelevant interactions while retaining the behavior that contradicts the contract.

Primary reading

• Structure and Interpretation of Computer Programs: University of California, Berkeley
• The Python Tutorial: Python Software Foundation

Open the study and save your work →