op75_parse_nat_spec
theoremverified
A successful natural parse is equivalent to the input being its canonical value encoding followed by the returned suffix, with the correct nonzero flag.
Statement
theorem op75_parse_nat_spec (w : List Bool) (n : ℕ) (rest : List Bool) (nz : Bool) : op75_parse_nat w = some (n, rest, nz) ↔ w = relu_encode_nat n ++ rest ∧ nz = decide (n ≠ 0)
- Source
- OP-75: canonical binary natural parser for the subset-sum-to-network compiler.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- op75_parse_nat_soundEvery successful natural parse exactly consumes the canonical encoding of its returned value and returns the correct nonzero flag.
- op75_parse_nat_completeThe parser accepts every canonical natural encoding with an arbitrary suffix and returns the value, suffix and correct nonzero flag.
- op75_parse_natDecode one canonical self-delimiting binary natural, returning its value, the unconsumed suffix, and whether the value is nonzero; reject…
- relu_encode_natBinary encoding of a natural number as a self-delimiting Bool word: each base-2 digit, least significant first, is preceded by a true…
Lean source view module on GitHub
theorem op75_parse_nat_spec (w : List Bool) (n : ℕ) (rest : List Bool) (nz : Bool) : op75_parse_nat w = some (n, rest, nz) ↔ w = relu_encode_nat n ++ rest ∧ nz = decide (n ≠ 0) := by constructor · exact op75_parse_nat_sound w n rest nz · rintro ⟨rfl,rfl⟩ exact op75_parse_nat_complete n rest