Source lean/Determinize/Proof/RewardModel/Native.lean
import Determinize.Finite.Reward.Exploreimport Determinize.Proof.RewardModel.Sparseimport Determinize.Proof.RewardModel.Soundnessimport Lean.Data.Json.Parsernamespace Determinize.Proof.RewardModelopen Spec.FiniteModelopen Spec.Paper (Core)structure Vectors where  dead : Array Bool  rank : Array Nat  next : Array Nat  mass : Array Rat  first : Array Rat  second : Array Rat  rejection : Array Ratderiving Inhabitedprivate def rational (s : String) : Except String Rat := do  match s.splitOn "/" with  | [num] =>    let some n := num.toInt? | throw "invalid numerator"    return n  | [num, den] =>    let some n := num.toInt? | throw "invalid numerator"    let some d := den.toNat? | throw "invalid denominator"    if d == 0 then throw "zero denominator"    return (n : Rat) / d  | _ => throw "invalid rational"def Vectors.decode (text : String) : Vectors :=  let parsed : Except String Vectors := do    let json ← Lean.Json.parse text    let field (object : Lean.Json) (name : String) :=      object.getObjVal? name >>= Lean.Json.getArr?    let dead ← (← field json "dead").mapM Lean.Json.getBool?    let rank ← (← field json "rank").mapM Lean.Json.getNat?    let next ← (← field json "next").mapM Lean.Json.getNat?    let values ← json.getObjVal? "values"    let rats ← #["mass", "first", "second", "rejection"].mapM fun name ↦ do      (← field values name).mapM fun x ↦ x.getStr? >>= rational    return ⟨dead, rank, next, rats[0]!, rats[1]!, rats[2]!, rats[3]!⟩  parsed.toOption.getD defaultdef Vectors.certificate (v : Vectors) (n : Nat) (positive : 0 < n) : Certificate n where  dead i := v.dead[i.val]?.getD false  rank i := v.rank[i.val]?.getD 0  next i := ⟨v.next[i.val]?.getD 0 % n, Nat.mod_lt _ positive⟩  mass i := v.mass[i.val]?.getD 0  first i := v.first[i.val]?.getD 0  second i := v.second[i.val]?.getD 0  rejection i := v.rejection[i.val]?.getD 0def Vectors.statistics (v : Vectors) (i : Nat) : OutputStatistics :=  ⟨v.mass[i]?.getD 0, v.first[i]?.getD 0, v.second[i]?.getD 0⟩def Vectors.verify (v : Vectors) (source : Core) (subject : Subject)    (limits : Finite.Limits) (initial : Nat) (answer : OutputStatistics) : Bool :=  match Finite.Reward.explore source subject limits with  | .complete candidate replay =>    let model := candidate.toModel replay    if positive : 0 < model.size then      let c := v.certificate model.size positive      decide (candidate.initial = initial) &&      decide (v.dead.size = model.size ∧ v.rank.size = model.size ∧        v.next.size = model.size ∧ v.mass.size = model.size ∧ v.first.size = model.size ∧        v.second.size = model.size ∧ v.rejection.size = model.size) &&      v.next.all (fun i ↦ decide (i < model.size)) &&      decide (∀ i, c.StateValid model i) && decide (v.statistics initial = answer)    else false  | _ => falsetheorem Vectors.verify_sound (v : Vectors) (source : Core) (subject : Subject)    (limits : Finite.Limits) (initial : Nat)    (answer : OutputStatistics)    (checked : v.verify source subject limits initial answer = true) :    answer.Matches (Spec.Paper.bigStepMeasure (subject.program source)) := by  unfold Vectors.verify at checked  cases explored : Finite.Reward.explore source subject limits with  | incomplete limit discovered expanded edges => simp [explored] at checked  | failed state failure => simp [explored] at checked  | complete candidate replay =>    simp only [explored] at checked    split at checked    next positive =>      simp only [Bool.and_eq_true, decide_eq_true_eq] at checked      have valid := checked.1.2      have first := checked.1.1.1.1      have sound := solution_outputStatistics (candidate.toModel replay) _        (replay_matches candidate replay) ((v.certificate _ positive).solution _ valid)      have result : (v.statistics initial).Matches (Spec.Paper.bigStepMeasure (subject.program source)) := by        simpa [Finite.Reward.Solution.statistics, Certificate.solution,          Vectors.statistics, Vectors.certificate, Finite.Reward.Candidate.toModel, first] using sound      exact checked.2 ▸ result    next => contradictionend Determinize.Proof.RewardModel