op75_parse_nat
def
Decode one canonical self-delimiting binary natural, returning its value, the unconsumed suffix, and whether the value is nonzero; reject malformed or noncanonical encodings.
Statement
def op75_parse_nat : List Bool → Option (ℕ × List Bool × Bool)- Source
- OP-75: canonical binary natural parser for the subset-sum-to-network compiler.
- Verified
- 15 Nov 2026
- Axioms
- none listed
- Used by 6
- op75_parse_subset_auxA total fuel-bounded decoder for canonical subset-sum instances.
- op75_parse_nat_soundEvery successful natural parse exactly consumes the canonical encoding of its returned value and returns the correct nonzero flag.
- op75_parse_subset_aux_soundEvery successful fuel-bounded parse reconstructs exactly the original canonical subset-sum word.
- op75_parse_subset_aux_completeSufficient fuel makes the parser accept every canonical instance and return its weights and target.
- op75_parse_nat_specA successful natural parse is equivalent to the input being its canonical value encoding followed by the returned suffix, with the correct…
- op75_parse_nat_completeThe parser accepts every canonical natural encoding with an arbitrary suffix and returns the value, suffix and correct nonzero flag.
Lean source view module on GitHub
def op75_parse_nat : List Bool → Option (ℕ × List Bool × Bool) | [] => none | false :: tail => some (0, tail, false) | true :: [] => none | true :: bit :: tail => match op75_parse_nat tail with | none => none | some (n, rest, nz) => if nz || bit then some (bit.toNat + 2*n, rest, true) else none