In What a Proof Covers the property tests were in C# and Go. lean-hedgehog is a port of Hedgehog to Lean 4, for the Lean code that has no proof, or not yet. Version 0.2.1 was released on November 19.
import Hedgehog
open Hedgehog
def reverseReverse : Property Id := property do
let xs ← forAll (Gen.list (.linear 0 100) Gen.alpha)
xs.reverse.reverse === xs
#eval check reverseReverse "reverse reverse"
✓ reverse reverse passed 100 tests.
The #eval runs when the file is compiled. When a property fails,
check throws the report, so the build fails with the counterexample
in the error.
Nobody would test this rule in Lean. The library has it as a theorem,
List.reverse_reverse, and Every List proves it by induction.
It is here only to show how the library works.
The third post of that series had a function that is wrong on purpose, and a theorem that holds for it anyway:
-- Wrong on purpose: returns its input.
def revId {α : Type} (xs : List α) : List α := xs
def roundTrip : Property Id := property do
let xs ← forAll (Gen.list (.linear 0 100) Gen.alpha)
revId (revId xs) === xs
def mirrored : Property Id := property do
let xs ← forAll (Gen.list (.linear 0 100) Gen.alpha)
revId xs === xs.reverse
The round trip passes, as the theorem did. The stronger statement,
checked against the library’s reverse, does not:
✓ round trip passed 100 tests.
✗ mirrored failed after 6 tests and 8 shrinks.
forAll ['a', 'b']
=== failed
lhs: ['a', 'b']
rhs: ['b', 'a']
This failure can be reproduced by running:
> recheck 5 ⟨8852088549225143798, 9597001414623567681⟩ <property>
So I check a statement before I try to prove it. A counterexample this small saves the attempt. A pass saves nothing: the proof is still owed.
A generator carries its own shrinks, the idea from Erlang QuickCheck. There is no shrinker to write, and a shrunk value is one the generator could have produced:
def genEven : Gen Nat := do
let n ← Gen.nat (.linear 0 1000)
pure (2 * n)
def smallEvens : Property Id := property do
let n ← forAll genEven
ensure (n < 99) "too large"
✗ small evens failed after 8 tests and 2 shrinks.
forAll 100
too large
The counterexample is 100, the smallest even number that fails. A
shrinker that knew only about Nat would have arrived at 99, a number
the generator never produces.
The library also tests a system against a model, in the two styles of the madhouse-rs series:
A scenario runs its commands once, in the order given; with MADHOUSE=1
it runs a hundred tests, each a random sequence of them. One of the
library’s examples is a toy shaped after a virtual machine such as
leanVM: a program of eight instructions and a counter that
says which one runs next. NEXT steps to the following instruction and
asserts that there is one, and JUMP goes to any of the eight:
structure Registers where
pc : Nat := 0
deriving Inhabited
structure Next where
instance : Command Next Registers Unit Id where
apply _ r := do
ensure (r.pc + 1 < 8) "pc left the program"
pure { pc := r.pc + 1 }
label _ := "NEXT"
build _ := pure {}
structure Jump where
target : Nat
instance : Command Jump Registers Unit Id where
apply c _ := pure { pc := c.target }
label c := s!"JUMP({c.target})"
build _ := Jump.mk <$> Gen.nat (.constant 0 7)
def program (mode : Mode) : Property Id :=
scenario mode () [Command.gen Next, Command.gen Jump]
One step and then one jump, the order given, stays in the program. A random order finds the jump to the last instruction with a step after it:
$ lake exe examples
✓ pc stays in the program (Hedgehog.Mode.deterministic) passed 1 test.
$ MADHOUSE=1 lake exe examples
✗ pc stays in the program (Hedgehog.Mode.madhouse) failed after 29 tests and 1 shrink.
forAll [JUMP(7), NEXT]
executed JUMP(7)
executed NEXT
pc left the program
The bug is put there on purpose, and nothing like it was found in leanVM. Adding a third command is a new type and a new instance; neither of these two changes.
Hedgehog’s own state machines, with symbolic variables, are not ported.
A theorem is about a Lean definition. It can’t say that the definition matches the RFC or the specification it was written from. So most of my tests ask a reference in another process: Lean generates the input, another program answers, and a disagreement shrinks.
The two issues were small. The check of an eth_getProof answer
refused the proof of no nodes that go-ethereum gives for a storage slot
of an account without storage (#3386), and the type of
Engine API errors lacked one code of the specification’s table
(#3387). The rest agreed.
That use changed the library. In EthLib the property of the slashing penalties passed a thousand cases, and the step changed the state in three. The report couldn’t say so. Since 0.2.0 a property can name the cases that matter and ask for a share of them:
def sorted : Property Id := (property do
let xs ← forAll (Gen.list (.linear 0 50) (Gen.nat (.linear 0 100)))
classify "empty" xs.isEmpty
cover 30 "long" (xs.length > 10)
xs.mergeSort.length === xs.length).withTests 500
✓ sort keeps the length passed 500 tests.
9.4% empty
43.8% long, at least 30%
With cover 30 "empty" xs.isEmpty in place of the classify, the same
500 tests on the same seed pass one by one, and the property fails:
✗ sort keeps the length passed 500 tests, with insufficient coverage.
9.4% empty, at least 30% ✗
43.8% long, at least 30%
The tests also missed a bug. EthLib’s Keccak block step was wrong at rates above 136 bytes; I had compared only Keccak-256 and Keccak-512, which passed, and the maintainers found and fixed it without me. I had generated the messages and not the rate.
map and bind are total, and LawfulMonad Tree is a
theorem. In Lean the port could prove a law of its own that the
original can only test.withConfidence, parallel state
machine testing, floating-point generators, diffs of the two sides of
===, and test discovery.It has no dependencies, needs Lean 4.35.0 or later, and keeps the BSD-3-Clause license of the original:
[[require]]
name = "hedgehog"
git = "https://github.com/hedgehogqa/lean-hedgehog"
rev = "v0.2.1"
The guide is the USAGE file in the repository.
lean-hedgehog was written with strong assistance from AI coding agents, with humans leading the ideas, as its README says. It would not exist without haskell-hedgehog, written by hand, or without what I learned in Write You Some QuickCheck.
lean-hedgehog is dedicated to Jacob Stanley, author and co-founder of Hedgehog, who passed away on 9 April 2023.
The examples were run with lean-hedgehog 0.2.1 on Lean 4.35.0.