moodmosaic

Hedgehog for Lean

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.

A property

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.

A false statement, found before the proof

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.

Shrinking keeps the invariant

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.

Systems with state

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 reference in another process

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.

A pass that tested little

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.

What differs from the Haskell

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.

How it was written

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.