Source lean/Determinize/Proof/FiniteModel/IndexedGraph.lean
import Determinize.Proof.FiniteModel.Soundnessimport Determinize.Proof.FiniteModel.IndexedReplaynamespace Determinize.Proof.FiniteModelopen Spec.Paper Spec.FiniteModel Determinize.Finite MeasureTheory/-- Push probability mass through supplied indices. Equal state labels are allowed. -/theorem weightedOutput_indexed {n : Nat} (states : Fin n → State) (fallback : Fin n)    (outcomes : List (Rat × State)) (indices : Nat → Nat)    (nonnegative : ∀ outcome ∈ outcomes, 0 ≤ outcome.1)    (covered : ∀ k : Fin outcomes.length, 0 < outcomes[k].1 →      ∃ bound : indices k.val < n, states ⟨indices k.val, bound⟩ = outcomes[k].2)    (output : State → Measure ℝ) :    weightedOutput outcomes output =      ∑ j, ENNReal.ofReal (indexedMass outcomes indices j.val : ℝ) • output (states j) := by  let destination (k : Nat) : Fin n := if h : indices k < n then ⟨indices k, h⟩ else fallback  let indexed := outcomes.zipIdx.map fun (outcome, k) ↦ (outcome.1, destination k)  have destination_eq (outcome : Rat × State) (k : Nat)      (member : (outcome, k) ∈ outcomes.zipIdx) (positive : 0 < outcome.1) :      (destination k).val = indices k ∧ states (destination k) = outcome.2 := by    have position := List.mem_zipIdx' member    obtain ⟨bound, located⟩ := covered ⟨k, position.1⟩ (by simpa [position.2] using positive)    constructor    · simp [destination, bound]    · simpa [destination, bound, position.2] using located  have law : weightedOutput outcomes output =      weightedOutput indexed (fun j ↦ output (states j)) := by    unfold weightedOutput indexed    conv_lhs => rw [← List.zipIdx_map_fst 0 outcomes]    simp only [List.map_map]    congr 1    apply List.map_congr_left    intro pair member    obtain ⟨outcome, k⟩ := pair    by_cases positive : 0 < outcome.1    · simp only [Function.comp_apply, (destination_eq outcome k member positive).2]    · have zero : ENNReal.ofReal (outcome.1 : ℝ) = 0 :=        ENNReal.ofReal_eq_zero.mpr (by exact_mod_cast le_of_not_gt positive)      simp [zero]  have weights (j : Fin n) : successorWeight indexed j = indexedMass outcomes indices j.val := by    unfold successorWeight indexed indexedMass    simp only [List.map_map]    congr 1    apply List.map_congr_left    intro pair member    obtain ⟨outcome, k⟩ := pair    by_cases positive : 0 < outcome.1    · simp only [Function.comp_apply, Fin.ext_iff, (destination_eq outcome k member positive).1]    · have zero : outcome.1 = 0 := le_antisymm (le_of_not_gt positive)        (nonnegative outcome (List.fst_mem_of_mem_zipIdx member))      simp [zero]  rw [law, weightedOutput_group id (fun _ _ h ↦ h) indexed]  · simp only [id_eq, weights]  · intro entry member    change entry ∈ outcomes.zipIdx.map (fun (outcome, k) ↦ (outcome.1, destination k)) at member    obtain ⟨pair, member, equal⟩ := List.mem_map.mp member    rw [← equal]    exact nonnegative pair.1 (List.fst_mem_of_mem_zipIdx member)  · intro entry _ _    exact ⟨entry.2, rfl⟩theorem indexedReplay_machineOutput (candidate : Candidate) {source : Spec.Paper.Core}    {subject : Subject}    (indices : Fin candidate.states.size → Nat → Nat)    (valid : candidate.IndexedReplayValid source subject indices) (fuel : Nat)    (i : Fin candidate.states.size) :    (candidate.graphModel        (indexedReplay_valid candidate source subject indices valid)).outputWithin fuel i =      machineOutput fuel (candidate.state i) := by  let graph := indexedReplay_valid candidate source subject indices valid  have replays := valid.2.2.2.2.2.2  induction fuel generalizing i with  | zero =>    have row := replays i    cases action : step (candidate.state i) with    | error failure => simp [Candidate.IndexedRowReplays, action] at row    | ok result =>      cases result <;> simp only [Candidate.IndexedRowReplays, action] at row      all_goals simp_all [Model.outputWithin, machineOutput]  | succ fuel ih =>    have row := replays i    cases action : step (candidate.state i) with    | error failure => simp [Candidate.IndexedRowReplays, action] at row    | ok result =>      cases result with      | returned reward =>        simp only [Candidate.IndexedRowReplays, action] at row        simp [Model.outputWithin, row, machineOutput, action]      | rejected =>        simp only [Candidate.IndexedRowReplays, action] at row        simp [Model.outputWithin, row, machineOutput, action]      | next evidence successors =>        simp only [Candidate.IndexedRowReplays, action] at row        rw [Model.outputWithin.eq_2 (candidate.graphModel graph) i fuel]        have kind : (candidate.graphModel graph).kind i = .transient := row.1        rw [kind]        change (∑ j, ENNReal.ofReal (candidate.weight i j : ℝ) •          (candidate.graphModel graph).outputWithin fuel j) = _        simp only [machineOutput, action]        simp_rw [ih,          indexedRow_weights candidate (indices i) i _ evidence successors action (replays i)]        symm        apply weightedOutput_indexed candidate.state i successors (indices i) row.2.1        intro k positive        obtain ⟨bound, located⟩ := Array.getElem?_eq_some_iff.mp (row.2.2.1 k positive).1        exact ⟨bound, located⟩theorem indexedReplay_matches (candidate : Candidate) {source : Spec.Paper.Core} {subject : Subject}    (indices : Fin candidate.states.size → Nat → Nat)    (valid : candidate.IndexedReplayValid source subject indices) :    (candidate.graphModel (indexedReplay_valid candidate source subject indices valid)).Matches      (subject.program source) := by  let graph := indexedReplay_valid candidate source subject indices valid  have initial : candidate.state (candidate.graphModel graph).initial =      initialState source subject := by    simpa [Candidate.state, Candidate.graphModel, graph.initial_lt] using valid.2.2.1  have replays := valid.2.2.2.2.2.2  have covered : ∀ state, MachineReachable (initialState source subject) state →      ∃ i, candidate.state i = state := by    intro state reachable    induction reachable with    | initial => exact ⟨_, initial⟩    | next previous action member positive ih =>      obtain ⟨i, hi⟩ := ih      have row := replays i      rw [← hi] at action      simp only [Candidate.IndexedRowReplays, action] at row      obtain ⟨k, boundK, hk⟩ := List.getElem_of_mem member      obtain ⟨bound, located⟩ := Array.getElem?_eq_some_iff.mp        (row.2.2.1 ⟨k, boundK⟩ (by simpa [hk] using positive)).1      exact ⟨⟨indices i k, bound⟩, by simpa [Candidate.state, hk] using located⟩  have noFailure : ∀ state, MachineReachable (initialState source subject) state →      ∀ failure, step state ≠ .error failure := by    intro state reachable failure action    obtain ⟨i, hi⟩ := covered state reachable    have row := replays i    simp [Candidate.IndexedRowReplays, hi, action] at row  have meaning : ∀ state, MachineReachable (initialState source subject) state → ∀ result,      step state = .ok result → StepMeaning state result :=    fun state reachable result action ↦ stepMeaning state      (stateShape_of_reachable_initialState source subject state reachable) result action  have initialEqual : stateExpr (initialState source subject) = subject.program source :=    initial_reification source subject      ((Binding.scoped_map source (fun q : Rat ↦ (q : ℝ)) 0).mpr valid.2.2.2.1)  have outputEqual : (candidate.graphModel graph).outputMeasure =      machineOutputMeasure (initialState source subject) := by    unfold Model.outputMeasure machineOutputMeasure    apply iSup_congr    intro fuel    simpa only [initial] using indexedReplay_machineOutput candidate indices valid fuel      (candidate.graphModel graph).initial  constructor  · intro fuel    rw [← initialEqual]    exact execution_safe _ meaning noFailure fuel _ .initial  · rw [outputEqual, execution_output_eq _ meaning noFailure _ .initial, initialEqual]end Determinize.Proof.FiniteModel