| name | hughes-property-based-testing |
| description | Test software in the style of John Hughes, inventor of QuickCheck and property-based testing. Emphasizes specifying properties that should hold for all inputs, generating random test cases, and shrinking failures to minimal examples. Use when testing algorithms, data structures, parsers, serializers, or any code with clear invariants. |
| tags | property-based-testing, quickcheck, generators, shrinking, invariants, fuzzing, random-testing, formal, specification |
John Hughes Property-Based Testing Style Guide
Overview
John Hughes, along with Koen Claessen, invented QuickCheck in 1999—a revolutionary approach to testing that generates random inputs and checks that specified properties hold. Instead of writing individual test cases, you describe properties that should be true for all valid inputs. When a property fails, QuickCheck shrinks the failing input to the smallest example that still fails, making debugging dramatically easier.
Core Philosophy
"Don't write tests. Write specifications. Let the computer generate the tests."
"One property can replace a hundred example-based tests."
"Shrinking is not optional—the minimal failing case is often the key to understanding the bug."
Property-based testing inverts the traditional approach: instead of "here's an input and expected output," you say "for all valid inputs, this property should hold." The framework then tries to prove you wrong by finding counterexamples.
Design Principles
-
Properties Over Examples: Describe what should always be true, not specific cases.
-
Random Generation: Let the computer explore the input space.
-
Shrinking: Automatically minimize failing cases for debugging.
-
Reproducibility: Seeds make random tests deterministic.
-
Coverage Through Volume: Run thousands of cases, not dozens.
The Property-Based Testing Cycle
┌─────────────────────────────────────────────────────────────┐
│ PROPERTY-BASED TESTING CYCLE │
├─────────────────────────────────────────────────────────────┤
│ │
│ 1. DEFINE PROPERTY │
│ "For all lists xs: reverse(reverse(xs)) == xs" │
│ │
│ │ │
│ ▼ │
│ │
│ 2. GENERATE RANDOM INPUTS │
│ xs = [], [1], [1,2], [42,-7,0,99], ... │
│ (hundreds or thousands of cases) │
│ │
│ │ │
│ ▼ │
│ │
│ 3. CHECK PROPERTY │
│ For each xs: assert reverse(reverse(xs)) == xs │
│ │
│ │ │
│ ┌───────┴───────┐ │
│ ▼ ▼ │
│ │
│ ALL PASS FOUND FAILURE │
│ ──────── ───────────── │
│ Property xs = [1, 2, 3, 4, 5] │
│ likely holds │ │
│ ▼ │
│ │
│ 4. SHRINK TO MINIMAL CASE │
│ Try smaller inputs: │
│ [1,2,3,4] → [1,2,3] → [1,2] → [1,2] │
│ Minimal failing: [1, 2] │
│ │
│ │ │
│ ▼ │
│ │
│ 5. REPORT MINIMAL COUNTEREXAMPLE │
│ "Property failed for input: [1, 2]" │
│ │
└─────────────────────────────────────────────────────────────┘
Types of Properties
Roundtrip / Inverse Properties
-- If you do something and undo it, you get back the original
prop_reverse_reverse :: [Int] -> Bool
prop_reverse_reverse xs = reverse (reverse xs) == xs
prop_encode_decode :: String -> Bool
prop_encode_decode s = decode (encode s) == s
prop_serialize_deserialize :: Data -> Bool
prop_serialize_deserialize d = deserialize (serialize d) == d
prop_compress_decompress :: ByteString -> Bool
prop_compress_decompress bs = decompress (compress bs) == bs
Invariant Properties
-- A property that should always hold
prop_sort_length :: [Int] -> Bool
prop_sort_length xs = length (sort xs) == length xs
prop_sort_ordered :: [Int] -> Bool
prop_sort_ordered xs = isOrdered (sort xs)
where isOrdered [] = True
isOrdered [_] = True
isOrdered (a:b:rest) = a <= b && isOrdered (b:rest)
prop_sort_permutation :: [Int] -> Bool
prop_sort_permutation xs = sort xs `isPermutationOf` xs
Idempotence Properties
-- Doing it twice is the same as doing it once
prop_sort_idempotent :: [Int] -> Bool
prop_sort_idempotent xs = sort (sort xs) == sort xs
prop_normalize_idempotent :: String -> Bool
prop_normalize_idempotent s = normalize (normalize s) == normalize s
prop_dedupe_idempotent :: [Int] -> Bool
prop_dedupe_idempotent xs = dedupe (dedupe xs) == dedupe xs
Equivalence / Oracle Properties
-- Two implementations should produce the same result
prop_optimized_equals_naive :: [Int] -> Bool
prop_optimized_equals_naive xs =
optimizedSort xs == naiveSort xs
prop_new_equals_old :: Input -> Bool
prop_new_equals_old input =
newImplementation input == oldImplementation input
Algebraic Properties
-- Mathematical laws
prop_monoid_associativity :: String -> String -> String -> Bool
prop_monoid_associativity a b c =
(a <> b) <> c == a <> (b <> c)
prop_monoid_identity :: String -> Bool
prop_monoid_identity a =
a <> mempty == a && mempty <> a == a
prop_functor_identity :: Maybe Int -> Bool
prop_functor_identity mx = fmap id mx == mx
prop_functor_composition :: Maybe Int -> Bool
prop_functor_composition mx =
fmap (f . g) mx == (fmap f . fmap g) mx
where f = (+1)
g = (*2)
When Using Property-Based Testing
Always
- Define properties for pure functions with clear invariants
- Test roundtrip properties (encode/decode, serialize/deserialize)
- Use shrinking to find minimal failing cases
- Set seeds for reproducibility in CI
- Run many iterations (100+ minimum, 1000+ preferred)
- Test algebraic laws for abstract data types
Never
- Skip shrinking (the minimal case is crucial)
- Use properties for side-effectful code without isolation
- Ignore flaky properties (fix the generator or property)
- Write properties that are just examples in disguise
- Forget to test edge cases explicitly too
- Assume passing 100 tests means correctness
Prefer
- Properties over example-based tests
- Custom generators over default ones
- Shrinking-aware generators
- Multiple complementary properties
- Testing invariants over specific outputs
- Algebraic properties for data structures
Code Patterns
Property-Based Testing Framework (Python-style)
import random
from typing import TypeVar, Callable, List, Any, Optional
from dataclasses import dataclass
T = TypeVar('T')
@dataclass
class TestResult:
success: bool
num_tests: int
counterexample: Optional[Any] = None
shrunk_counterexample: Optional[Any] = None
seed: int = None
class Generator:
"""Base class for random value generators."""
def generate(self, rng: random.Random, size: int) -> Any:
raise NotImplementedError
def shrink(self, value: Any) -> List[Any]:
"""Return smaller versions of value for shrinking."""
return []
class IntGenerator(Generator):
"""Generate random integers."""
def __init__(self, min_val: int = -1000, max_val: int = 1000):
.min_val = min_val
.max_val = max_val
() -> :
bound = (size, .max_val - .min_val)
rng.randint(.min_val, .min_val + bound)
() -> []:
value == :
[]
shrinks = []
(value) > :
shrinks.append(value // )
value > :
shrinks.append(value - )
:
shrinks.append(value + )
shrinks
():
():
.element_gen = element_gen
() -> :
length = rng.randint(, size)
[.element_gen.generate(rng, size) _ (length)]
() -> []:
shrinks = []
value:
shrinks.append([])
i ((value)):
shrinks.append(value[:i] + value[i+:])
i, elem (value):
shrunk_elem .element_gen.shrink(elem):
shrinks.append(value[:i] + [shrunk_elem] + value[i+:])
shrinks
():
():
.alphabet = alphabet
() -> :
length = rng.randint(, size)
.join(rng.choice(.alphabet) _ (length))
() -> []:
shrinks = []
value:
shrinks.append()
shrinks.append(value[:-])
shrinks.append(value[:])
i, c (value):
c != :
shrinks.append(value[:i] + + value[i+:])
shrinks
:
():
.num_tests = num_tests
.max_shrinks = max_shrinks
.seed = seed random.randint(, **)
() -> TestResult:
rng = random.Random(.seed)
i (.num_tests):
size = i * // .num_tests +
value = generator.generate(rng, size)
:
property_fn(value):
shrunk = ._shrink(generator, property_fn, value)
TestResult(
success=,
num_tests=i + ,
counterexample=value,
shrunk_counterexample=shrunk,
seed=.seed,
)
Exception e:
shrunk = ._shrink(generator, property_fn, value)
TestResult(
success=,
num_tests=i + ,
counterexample=value,
shrunk_counterexample=shrunk,
seed=.seed,
)
TestResult(
success=,
num_tests=.num_tests,
seed=.seed,
)
() -> :
smallest = value
shrink_count =
shrink_count < .max_shrinks:
candidates = generator.shrink(smallest)
found_smaller =
candidate candidates:
:
property_fn(candidate):
smallest = candidate
found_smaller =
Exception:
smallest = candidate
found_smaller =
found_smaller:
shrink_count +=
smallest
():
():
():
qc = QuickCheck(num_tests=num_tests)
result = qc.for_all(generator, prop_fn)
result.success:
AssertionError(
)
result
wrapper.__name__ = prop_fn.__name__
wrapper
decorator
Example Properties
@property_test(ListGenerator(IntGenerator()))
def prop_reverse_reverse(xs: List[int]) -> bool:
return list(reversed(list(reversed(xs)))) == xs
@property_test(ListGenerator(IntGenerator()))
def prop_sort_preserves_length(xs: List[int]) -> bool:
return len(sorted(xs)) == len(xs)
@property_test(ListGenerator(IntGenerator()))
def prop_sort_is_ordered(xs: List[int]) -> bool:
result = sorted(xs)
return all(result[i] <= result[i+1] for i in range(len(result)-1))
@property_test(ListGenerator(IntGenerator()))
() -> :
((xs)) == (xs)
() -> :
my_sort = quick_sort(xs.copy())
builtin = (xs)
my_sort == builtin
() -> :
a, b, c = s[:(s)//], s[(s)//:*(s)//], s[*(s)//:]
(a + b) + c == a + (b + c)
Custom Generators
class UserGenerator(Generator):
"""Generate random User objects."""
def __init__(self):
self.name_gen = StringGenerator("abcdefghijklmnopqrstuvwxyz")
self.age_gen = IntGenerator(0, 150)
self.email_gen = StringGenerator("abcdefghijklmnopqrstuvwxyz0123456789")
def generate(self, rng: random.Random, size: int) -> 'User':
return User(
name=self.name_gen.generate(rng, size),
age=self.age_gen.generate(rng, size),
email=f"{self.email_gen.generate(rng, size)}@example.com"
)
def shrink(self, user: 'User') -> List['User']:
shrinks = []
for name in self.name_gen.shrink(user.name):
shrinks.append(User(name=name, age=user.age, email=user.email))
for age in self.age_gen.shrink(user.age):
shrinks.append(User(name=user.name, age=age, email=user.email))
return shrinks
class JsonGenerator(Generator):
() -> :
size <= :
._generate_leaf(rng)
choice = rng.choice([, , ])
choice == :
._generate_leaf(rng)
choice == :
length = rng.randint(, (size, ))
[.generate(rng, size - ) _ (length)]
:
length = rng.randint(, (size, ))
{
: .generate(rng, size - )
i (length)
}
() -> :
choice = rng.choice([, , , , ])
choice == :
choice == :
rng.choice([, ])
choice == :
rng.randint(-, )
choice == :
rng.uniform(-, )
:
.join(rng.choices(, k=rng.randint(, )))
() -> []:
value (value, ):
[]
(value, ):
IntGenerator().shrink(value)
(value, ):
StringGenerator().shrink(value)
(value, ):
ListGenerator().shrink(value)
(value, ):
shrinks = [{}]
key value:
shrinks.append({k: v k, v value.items() k != key})
shrinks
[]
Stateful Testing
class StatefulTest:
"""
Test stateful systems by generating sequences of operations.
Hughes' approach to testing state machines.
"""
def __init__(self, model_class, system_class):
self.model_class = model_class
self.system_class = system_class
def run(self, num_tests: int = 100, max_steps: int = 50):
"""
Generate sequences of commands and check model matches system.
"""
rng = random.Random()
for test_num in range(num_tests):
model = self.model_class()
system = self.system_class()
commands = []
for step in range(max_steps):
cmd = self.generate_command(rng, model)
commands.append(cmd)
model_result = cmd.run_model(model)
system_result = cmd.run_system(system)
if model_result != system_result:
shrunk = self.shrink_commands(commands, model_result, system_result)
raise AssertionError(
f"Model/system mismatch!\n"
f"Commands: {shrunk}\n"
f"Model result: {model_result}\n"
)
:
():
.items = []
():
.items.append(item)
():
.items:
.items.pop()
():
(.items)
:
():
.item = item
():
model.push(.item)
():
system.push(.item)
:
():
model.pop()
():
system.pop()
Mental Model
Hughes approaches testing by asking:
- What properties should always hold? Think invariants, not examples
- Can I roundtrip it? encode/decode, serialize/deserialize
- What are the algebraic laws? Monoid, functor, monad laws
- What's the simplest failing case? Shrinking is essential
- Am I testing enough cases? Hundreds or thousands, not dozens
The Property-Based Testing Checklist
□ Identify properties that should hold for all inputs
□ Build or use appropriate generators
□ Ensure generators produce edge cases (empty, large, etc.)
□ Implement shrinking for custom generators
□ Run sufficient iterations (100+)
□ Set seeds for reproducibility
□ Analyze shrunk counterexamples carefully
□ Complement with example-based tests for specific cases
Signature Hughes Moves
- Properties over examples
- Random generation with size control
- Shrinking to minimal counterexamples
- Roundtrip testing (encode/decode)
- Algebraic properties (associativity, identity)
- Model-based stateful testing
- Custom generators with shrinking
- Seed-based reproducibility
