AFTD Auto-Formalizing Theoretical Domains

op75_parse_nat_sound

theoremverified

Every successful natural parse exactly consumes the canonical encoding of its returned value and returns the correct nonzero flag.

Statement

theorem op75_parse_nat_sound (w : List Bool) (n : ℕ) (rest : List Bool) (nz : Bool)
    (h : 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 2
  • 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…
Used by 2
  • op75_parse_subset_aux_soundEvery successful fuel-bounded parse reconstructs exactly the original canonical subset-sum word.
  • 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…

Lean source view module on GitHub

theorem op75_parse_nat_sound (w : List Bool) (n : ℕ) (rest : List Bool) (nz : Bool)
    (h : op75_parse_nat w = some (n, rest, nz)) :
    w = relu_encode_nat n ++ rest ∧ nz = decide (n ≠ 0) := by
  induction w using List.twoStepInduction generalizing n rest nz with
  | nil => simp [op75_parse_nat] at h
  | singleton head =>
      cases head with
      | false =>
          simp [op75_parse_nat] at h
          obtain ⟨rfl, rfl, rfl⟩ := h
          simp [relu_encode_nat]
      | true => simp [op75_parse_nat] at h
  | cons_cons head bit tail ih ih2 =>
      cases head with
      | false =>
          simp [op75_parse_nat] at h
          obtain ⟨rfl, rfl, rfl⟩ := h
          simp [relu_encode_nat]
      | true =>
          cases hp : op75_parse_nat tail with
          | none => simp [op75_parse_nat, hp] at h
          | some value =>
              rcases value with ⟨m, r, nonzero⟩
              have htail := ih m r nonzero hp
              rcases htail with ⟨hword, hnz⟩
              cases hc : nonzero || bit with
              | false => simp [op75_parse_nat, hp, hc] at h
              | true =>
                  simp [op75_parse_nat, hp, hc] at h
                  obtain ⟨rfl, rfl, rfl⟩ := h
                  have hne : bit.toNat ≠ 0 ∨ m ≠ 0 := by
                    cases bit <;> cases nonzero <;> simp_all
                  have hdig : Nat.digits 2 (bit.toNat + 2*m) = bit.toNat :: Nat.digits 2 m := by
                    apply Nat.digits_add 2 (by omega) bit.toNat m
                    · cases bit <;> decide
                    · exact hne
                  have hbit : decide (bit.toNat = 1) = bit := by cases bit <;> decide
                  constructor
                  · simpa only [relu_encode_nat, hdig, List.flatMap_cons, List.cons_append,
                      List.nil_append, List.append_assoc, hbit] using congrArg (fun z => true :: bit :: z) hword
                  · have hn : bit.toNat + 2*m ≠ 0 := by omega
                    exact (decide_eq_true hn).symm
See it in the graphDiscuss this resultChallenge it