Property-based testing: Visual walkthrough — Coding deep dive

Step 1 — What a property actually is (a rule that judges every input)

WHAT the figure shows: a single input xs (a list of numbers) enters a box labelled $P$ . The box asks one yes/no question and lights green (PASS) or red (FAIL).

WHY we start here: shrinking only makes sense once you see the property as a machine that labels inputs. It doesn't know your code's intent — it just answers "did the rule hold, yes or no?" for whatever list you feed it.

Our concrete property, term by term:

$smallest value in the list min (x s) \leq the mean we computed average (x s) \leq largest value in the list max (x s)$

$min (x s)$ — the smallest number present. If xs = [4, 9, 2], this is $2$ .
$max (x s)$ — the largest number present, here $9$ .
$average (x s)$ — the sum divided by how many numbers there are.
$\leq$ ("less than or equal to") — the average must sit between the two extremes.

The whole line is one boolean: for [4, 9, 2] it reads $2 \leq 5 \leq 9$ → PASS (green).

Step 2 — The input space: a whole universe of lists

WHAT the figure shows: a big region ("all lists of integers"). Green dots = inputs where $P$ passes. Red dots = inputs where $P$ fails. A few hand-picked example tests sit in a tiny cluster; the random generator sprinkles dots everywhere — including a red one your examples never reached.

WHY this picture: it makes the parent's slogan literal — "bugs live in the inputs you forgot." The forgotten inputs are the red dots outside your hand-picked cluster. The generator's job is to land on a red dot. (See Fuzzing — same random-scatter idea; PBT adds the rule and the shrinking below.)

Here the deadly red region is any empty list [], because $average ([]) = \frac{0}{0}$ — a division by zero. We will hunt that dot.

Step 3 — Generating a random input and hitting a red dot

WHAT the figure shows: the generator rolls dice and produces a first messy input $x_{0} = [847, - 3, 901, 0, - 12, 47]$ It walks through the gate $P$ from Step 1... and the light turns red. We caught a failure.

WHY random and not exhaustive: there are infinitely many lists — you cannot test them all. Random sampling is the cheapest way to stumble onto a red dot you'd never think of. (This is why the parent stresses PBT is sampling, not proof.)

$x_{0}$ — the first failing input, our starting point. The subscript $0$ just means "step zero of shrinking", the raw catch before any simplification.

The problem: $x_{0}$ is huge and ugly. Six numbers, big magnitudes. Which one causes the bug? You can't tell. This is the pain shrinking solves.

Step 4 — The shrink move: propose something simpler

But what does "simpler" mean for a list? The figure names the two legal moves:

WHAT the figure shows two arrows leaving $x_{0}$ :

Move A — drop an element (fewer items is simpler): [847,-3,901,0,-12,47] → [847,901,0,-12,47].
Move B — pull a number toward $0$ (smaller magnitude is simpler): 847 → 0, or halve it 847 → 423.

We write a candidate as $x^{'}$ (read "x-prime"), meaning "a proposed simpler version of the current input."

$x^{'}$ — a candidate produced by one shrink move. It is a guess; we don't yet know if it still fails.

WHY these two moves: they define an ordering " $x^{'}$ is simpler than $x$ " — fewer elements, or values closer to zero. Simplicity is measured, not vibes. A shorter list with smaller numbers is objectively easier to read when debugging.

Step 5 — The keep-or-discard test (the heart of the loop)

WHAT the figure shows a fork: $x^{'}$ enters $P$ .

Red branch (still fails) → $x^{'}$ becomes the new "current worst", and we recurse from Step 4 on it.
Green branch (now passes) → throw $x^{'}$ away, try a different move on the old input.

WHY this rule is exactly right: we only ever move to inputs that preserve the bug. We never "shrink away" the failure — a candidate is allowed in only if it keeps failing. So every accepted step is simpler AND still broken.

Formally, we accept $x^{'}$ only when: $P (x^{'}) = FAIL AND x^{'} is simpler than the current input$

$P (x^{'})$ — the gate's verdict on the candidate.
" $= FAIL$ " — we require the bug to survive; a passing candidate is useless for debugging.

Step 6 — Greedy descent: watch the input melt down

WHAT the figure shows a staircase going down: $[847, - 3, 901, 0, - 12, 47] \to [847, - 3, 0] \to [- 3, 0] \to [0] \to []$ Each rung is simpler than the last, and every rung is still red (still crashes average). The final rung [] is where no drop-an-element move exists anymore.

WHY it terminates: the "size" of a list is a whole number $\geq 0$ . Each accepted shrink strictly lowers it. A strictly-decreasing sequence of non-negative whole numbers cannot go on forever — it bottoms out. That bottom is the minimal counterexample.

The arrow direction is always toward simpler; "greedy" means we take any improving step immediately, never planning ahead.

Step 7 — Edge & degenerate cases (what the descent bottoms out to)

Shrinking's answer depends on why the code broke. The figure shows three separate victims and where each descent lands:

WHY cover all three: the same loop yields different minimums because the property lights red on different regions. Shrinking never gives you a random small input — it gives you the smallest input that still exhibits your specific bug, which is precisely the debugging clue you want.

The one-picture summary

The final figure stacks all seven steps: the property-gate (Step 1) sits above the field of dots (Step 2); a random arrow lands on a red dot $x_{0}$ (Step 3); the shrink moves (Step 4) feed the keep/discard fork (Step 5); the fork drives the descent staircase (Step 6) down to the bug-specific floor (Step 7).

Recall Feynman retelling of the whole walkthrough

Your rule is a gate: feed it a bag of numbers, it flashes green (rule held) or red (rule broke). A dice-rolling robot tosses hundreds of random bags at the gate until one flashes red — but it's a huge messy bag, useless. So the robot plays a shrinking game: it makes the bag simpler — takes a number out, or nudges a big number toward zero — and re-checks the gate. Green? Undo, that fix wasn't the culprit. Still red? Keep it, the bug survived, go smaller again. Because a bag can't hold fewer than zero numbers, the shrinking can't go on forever; it bottoms out at the tiniest bag that still flashes red. And that tiniest bag is bug-shaped: if the crash needs an empty bag you get [], if it needs a negative you get [-1], if it needs two items you get [0, 1]. That final little bag is the robot pointing straight at your bug.

Recall

A property is a gate that answers what about an input? ::: Just PASS or FAIL — whether the rule held for that one input. Why can't shrinking accept a candidate that PASSES? ::: A passing candidate healed the bug; we only keep still-failing (still-red) simpler inputs so the failure is preserved. Why is shrinking guaranteed to terminate? ::: "Simpler" strictly decreases a non-negative whole-number size (fewer elements / smaller magnitude), and such a sequence must bottom out. The minimal counterexample for average([])'s crash is what, and why? ::: [] — the crash is the empty-list division by zero, and you cannot drop below zero elements. If a bug only fires with a negative present, what does the minimum look like? ::: Something like [-1] — the negative can't shrink to 0 without healing the bug, so it stays.

Connections

Property-based testing — this page is the visual derivation of its "shrinking" section.
Fuzzing — Step 2/3 (random scatter to hit a red dot) is the fuzzing half; PBT adds Steps 4–7.
Invariants and contracts — the property in Step 1 is a runtime-checkable invariant.
Hypothesis (Python) — the framework that runs exactly this generate-then-shrink loop.
QuickCheck (Haskell) — the original tool that introduced generator + shrinking.