Source lean/Determinize/Proof/RewardModel/Safety.lean
import Determinize.Proof.RewardModel.Correspondencenamespace Determinize.Proof.RewardModelopen Determinize.Finite Determinize.Proof.FiniteModeldef FailureWithin : Nat → State → Prop  | 0, s => ∃ e, step s = .error e  | n + 1, s => match step s with      | .error _ => True      | .ok (.next _ xs) => ∃ x ∈ xs, 0 < x.1 ∧ FailureWithin n x.2      | _ => Falseprivate theorem not_failureWithin_number (offsets : List Rat) (b : Rat) (n : Nat) :    ¬ FailureWithin n (.deliver (.number b) (additionStack offsets)) := by  induction n generalizing b offsets with  | zero =>    cases offsets <;> simp [FailureWithin, additionStack, step, binary, pure, bind, Except.bind,      Except.pure]  | succ n ih =>    cases offsets with    | nil => simp [FailureWithin, additionStack, step]    | cons c cs =>      simpa [FailureWithin, additionStack, step, binary, pure, bind, Except.bind, Except.pure]        using ih cs (c + b)theorem failureWithin_pushStack_additionStack_iff (offsets : List Rat) (n : Nat) (state : State) :    FailureWithin n (pushStack state (additionStack offsets)) ↔ FailureWithin n state := by  induction n generalizing state with  | zero =>    cases action : step state with    | error e =>      obtain ⟨err, herr⟩ := addition_failure state offsets e action      simp [FailureWithin, action, herr]    | ok result =>      rcases step_terminal state result action with ⟨tag, xs, rfl⟩ | ⟨b, rfl, rfl⟩ | ⟨rfl, rfl⟩      · simp [FailureWithin, action, step_pushStack state (additionStack offsets) tag xs action]      · simpa [pushStack, FailureWithin, step] using not_failureWithin_number offsets b 0      · simp [pushStack, FailureWithin, step]  | succ n ih =>    cases action : step state with    | error e =>      obtain ⟨err, herr⟩ := addition_failure state offsets e action      simp [FailureWithin, action, herr]    | ok result =>      rcases step_terminal state result action with ⟨tag, xs, rfl⟩ | ⟨b, rfl, rfl⟩ | ⟨rfl, rfl⟩      · simp [FailureWithin, action, step_pushStack state (additionStack offsets) tag xs action,          extend,          ih]      · simpa [pushStack, FailureWithin, step] using not_failureWithin_number offsets b (n + 1)      · simp [pushStack, FailureWithin, step]theorem failureWithin_normalize_iff (state : State) (n : Nat) :    FailureWithin n (Reward.normalize state).2 ↔ FailureWithin n state := by  cases state with  | rejected => rfl  | eval e env stack =>    let base := State.eval e env (Reward.splitStack stack).1    have original := failureWithin_pushStack_additionStack_iff (Reward.splitStack stack).2 n base    have canonical := failureWithin_pushStack_additionStack_iff [0] n base    have reconstructed := RewardModel.splitStack_reconstruct stack    simp only [pushStack, base, additionStack, reconstructed] at original    by_cases empty : (Reward.splitStack stack).2 = []    · simpa [Reward.normalize, Reward.normalizeStack, empty, base, pushStack, additionStack]        using original.symm    · simpa [Reward.normalize, Reward.normalizeStack, empty, base, pushStack, additionStack,        Reward.guard] using        canonical.trans original.symm  | deliver v stack =>    let base := State.deliver v (Reward.splitStack stack).1    have original := failureWithin_pushStack_additionStack_iff (Reward.splitStack stack).2 n base    have canonical := failureWithin_pushStack_additionStack_iff [0] n base    have reconstructed := RewardModel.splitStack_reconstruct stack    simp only [pushStack, base, additionStack, reconstructed] at original    by_cases empty : (Reward.splitStack stack).2 = []    · simpa [Reward.normalize, Reward.normalizeStack, empty, base, pushStack, additionStack]        using original.symm    · simpa [Reward.normalize, Reward.normalizeStack, empty, base, pushStack, additionStack,        Reward.guard] using        canonical.trans original.symmdef RewardFailureWithin : Nat → State → Prop  | 0, s => ∃ e, step s = .error e  | n + 1, s => match step s with      | .error _ => True      | .ok (.next _ xs) => ∃ x ∈ xs, 0 < x.1 ∧ RewardFailureWithin n (Reward.normalize x.2).2      | _ => Falsetheorem rewardFailureWithin_of_failureWithin (n : Nat) (state : State) :    FailureWithin n state → RewardFailureWithin n state := by  induction n generalizing state with  | zero => exact id  | succ n ih =>    cases action : step state with    | error e => simp [FailureWithin, RewardFailureWithin, action]    | ok result =>      cases result with      | returned b => simp [FailureWithin, action]      | rejected => simp [FailureWithin, action]      | next tag xs =>        simp only [FailureWithin, RewardFailureWithin, action]        rintro ⟨x, member, positive, failed⟩        exact ⟨x, member, positive, ih _ ((failureWithin_normalize_iff x.2 n).mpr failed)⟩end Determinize.Proof.RewardModel