Source lean/Determinize/Proof/RewardModel/Table.lean
import Determinize.Proof.RewardModel.Sparseimport Determinize.Proof.RewardModel.Soundnessset_option backward.isDefEq.respectTransparency falsenamespace Determinize.Finite.Rewardopen Spec.FiniteModel Spec.Paperstructure Table where  size : Nat  initial : Fin size  state : Nat → State  row : Nat → Rowdef Table.RowClaim (t : Table) (i : Fin t.size) (action : Except Failure Step) : Prop :=  (∀ e ∈ (t.row i).edges, e.target < t.size ∧ 0 < e.probability) ∧  ((t.row i).edges.map Edge.probability).sum = 1 ∧  match action with  | .error _ => False  | .ok (.returned b) => (t.row i).kind = .returned b  | .ok .rejected => (t.row i).kind = .rejected  | .ok (.next _ outcomes) =>    (t.row i).kind = .transient ∧ (∀ o ∈ outcomes, 0 ≤ o.probability) ∧    ((t.row i).edges.map fun e ↦ (e.probability, t.state e.target, e.reward)) =      ((outcomes.filter fun o ↦ 0 < o.probability).map fun o ↦        (o.probability, o.state, o.reward))instance (t : Table) (i : Fin t.size) (action : Except Failure Step) :    Decidable (t.RowClaim i action) := by  unfold Table.RowClaim  split <;> infer_instancedef Table.StateValid (t : Table) (i : Fin t.size) : Prop :=  normalize (t.state i) = (0, t.state i) ∧ t.RowClaim i (step (t.state i))instance (t : Table) (i : Fin t.size) : Decidable (t.StateValid i) :=  inferInstanceAs (Decidable (_ ∧ _))theorem Table.stateValid_of_step (t : Table) (i : Fin t.size)    (action : Except Failure Step) (eq : step (t.state i) = action)    (normalized : normalize (t.state i) = (0, t.state i))    (row : t.RowClaim i action) : t.StateValid i := by  refine ⟨normalized, ?_⟩  rw [eq]  exact rowdef Table.candidate (t : Table) : Candidate :=  ⟨t.initial, Array.ofFn (fun i : Fin t.size ↦ t.state i),    Array.ofFn (fun i : Fin t.size ↦ t.row i)⟩@[simp] theorem Table.state_at (t : Table) (i : Fin t.candidate.states.size) :    t.candidate.states[i] = t.state i.val := by  change (Array.ofFn (fun i : Fin t.size ↦ t.state i.val))[i.val] = _  rw [Array.getElem_ofFn]@[simp] theorem Table.row_at (t : Table) (i : Fin t.candidate.states.size) :    t.candidate.row i = t.row i.val := by  have bound : i.val < t.size := by simpa [Table.candidate] using i.isLt  change (Array.ofFn (fun i : Fin t.size ↦ t.row i.val))[i.val]?.getD _ = _  rw [Array.getElem?_ofFn]  simp [bound]theorem Table.replay (t : Table) (source : Core) (subject : Subject)    (initial : t.state t.initial = initialState source subject)    (sourceScoped : Proof.FiniteModel.Binding.Scoped 0 source)    (valid : ∀ i, t.StateValid i) : t.candidate.ReplayValid source subject := by  refine ⟨by simp [Table.candidate], by simp [Table.candidate],    ?_, sourceScoped, ?_, ?_⟩  · simpa [Table.candidate, t.initial.isLt] using congrArg some initial  · intro i    simpa only [Table.state_at] using (valid ⟨i.val, by simpa [Table.candidate] using i.isLt⟩).1  · intro i    have bound : i.val < t.size := by simpa [Table.candidate] using i.isLt    have h := (valid ⟨i.val, bound⟩).2    simp only [Table.RowClaim] at h    unfold Candidate.RowValid Candidate.RowClaim    rw [t.state_at i, t.row_at i]    simp only [Table.candidate, Array.size_ofFn, Array.getElem?_ofFn]    refine ⟨h.1, h.2.1, ?_⟩    cases action : step (t.state i.val) with    | error e => simpa [action] using h.2.2    | ok result => cases result with      | returned b => simpa [action] using h.2.2      | rejected => simpa [action] using h.2.2      | next tag outcomes =>        simp only [action] at h ⊢        refine ⟨h.2.2.1, h.2.2.2.1, ?_⟩        rw [← h.2.2.2.2]        apply List.map_congr_left        intro e member        simp [(h.1 e member).1]abbrev Table.modelEdges (t : Table) (valid : ∀ i, t.StateValid i) (i : Fin t.size) :    List (Spec.RewardModel.Edge t.size) :=  (t.row i).edges.attach.map fun ⟨e, he⟩ ↦    ⟨⟨e.target, ((valid i).2.1 e he).1⟩, e.probability, e.reward⟩def Table.model (t : Table) (valid : ∀ i, t.StateValid i) : Spec.RewardModel.Model where  size := t.size  initial := t.initial  kind := fun i ↦ (t.row i).kind  edges := t.modelEdges valid  nonnegative := by    intro i e he    obtain ⟨⟨original, member⟩, _, rfl⟩ := List.mem_map.mp he    exact le_of_lt ((valid i).2.1 original member).2  normalized := by    intro i    simpa [Table.modelEdges, List.map_map] using (valid i).2.2.1private theorem lookupFunction_heq {n m : Nat} {β : Nat → Type}    (size : n = m) (f : Fin n → β n) (g : Fin m → β m)    (same : ∀ i, f i ≍ g ⟨i.val, size ▸ i.isLt⟩) : f ≍ g := by  subst m  apply heq_of_eq  funext i  exact eq_of_heq (same i)private theorem edgeLists_heq {n m : Nat} (size : n = m) (xs ys : List Edge) (same : xs = ys)    (left : ∀ e ∈ xs, e.target < n) (right : ∀ e ∈ ys, e.target < m) :    (xs.attach.map fun e ↦ (⟨⟨e.val.target, left e.val e.property⟩,      e.val.probability, e.val.reward⟩ : Spec.RewardModel.Edge n)) ≍    (ys.attach.map fun e ↦ (⟨⟨e.val.target, right e.val e.property⟩,      e.val.probability, e.val.reward⟩ : Spec.RewardModel.Edge m)) := by  subst m  subst ys  rfltheorem Table.model_eq (t : Table) (source : Core) (subject : Subject)    (initial : t.state t.initial = initialState source subject)    (sourceScoped : Proof.FiniteModel.Binding.Scoped 0 source)    (valid : ∀ i, t.StateValid i) :    t.model valid = t.candidate.toModel (t.replay source subject initial sourceScoped valid) := by  have size : t.size = t.candidate.states.size := by simp [Table.candidate]  have first : t.initial ≍ (t.candidate.toModel      (t.replay source subject initial sourceScoped valid)).initial := by    apply (Fin.heq_ext_iff size).mpr    rfl  have kinds : (t.model valid).kind ≍      (t.candidate.toModel (t.replay source subject initial sourceScoped valid)).kind := by    apply (Fin.heq_fun_iff size).mpr    intro i    change (t.row i.val).kind = (t.candidate.row _).kind    rw [t.row_at]  have edges : (t.model valid).edges ≍      (t.candidate.toModel (t.replay source subject initial sourceScoped valid)).edges := by    apply lookupFunction_heq (β := fun n ↦ List (Spec.RewardModel.Edge n)) size    intro i    simp only [Table.model, Table.modelEdges, Candidate.modelEdges]    apply edgeLists_heq size    rw [t.row_at]  simp only [Table.model, Candidate.toModel, Spec.RewardModel.Model.mk.injEq]  exact ⟨size, first, kinds, edges⟩theorem Table.matches (t : Table) (source : Core) (subject : Subject)    (initial : t.state t.initial = initialState source subject)    (sourceScoped : Proof.FiniteModel.Binding.Scoped 0 source)    (valid : ∀ i, t.StateValid i) : (t.model valid).Matches (subject.program source) := by  rw [t.model_eq source subject initial sourceScoped valid]  exact Proof.RewardModel.replay_matches _ _end Determinize.Finite.Reward