AFTD Auto-Formalizing Theoretical Domains

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
See it in the graphDiscuss this resultChallenge it