Source lean/Determinize/Proof/FiniteModel/Progress.lean
import Determinize.Proof.FiniteModel.Invariantsnamespace Determinize.Proof.FiniteModelopen Spec.Paper Determinize.Finite Checkingdef expressionWork : Core → Nat  | .app a b | .pair a b | .cons a b | .add a b | .mul a b | .div a b | .lt a b =>    expressionWork a + expressionWork b + 3  | .fst a | .snd a | .inl a | .inr a | .neg a => expressionWork a + 2  | .letE a _ | .ite a _ _ | .matchSum a _ _ | .matchList a _ _ => expressionWork a + 2  | .uniform _ a b | .gaussian _ a b | .beta _ a b | .gamma _ a b =>    expressionWork a + expressionWork b + 3  | .poisson _ a | .bernoulli _ a | .exponential _ a | .discrete _ a => expressionWork a + 2  | _ => 1def frameWork : Frame → Nat  | .left _ right _ => expressionWork right + 2  | .draw _ pending _ _ => (pending.map fun e ↦ expressionWork e + 1).sum + 1  | _ => 1def bookkeepingRank : State → Nat  | .eval expression _ stack => expressionWork expression + (stack.map frameWork).sum  | .deliver _ stack => (stack.map frameWork).sum  | .rejected => 0/-- States whose next transition only evaluates operands, delivers values, or rejects. -/def Bookkeeping : State → Prop  | .eval _ _ _ => True  | .deliver _ (.left .. :: _) => True  | .deliver _ (.unary .inl :: _) | .deliver _ (.unary .inr :: _) => True  | .deliver _ (.right .pair _ :: _) | .deliver _ (.right .cons _ :: _) => True  | .deliver _ (.draw _ (_ :: _) _ _ :: _) => True  | _ => Falseprivate theorem bookkeepingRank_lt_of_singleton (before state : State)    (decrease : bookkeepingRank state < bookkeepingRank before)    (tag evidence : Evidence) (successors : List (Rat × State))    (action : (Except.ok (.next tag [(1, state)]) : Except Failure Step) =      .ok (.next evidence successors))    (probability : Rat) (after : State) (member : (probability, after) ∈ successors) :    bookkeepingRank after < bookkeepingRank before := by  obtain ⟨rfl, rfl⟩ := Step.next.inj (Except.ok.inj action)  obtain ⟨rfl, rfl⟩ := Prod.mk.inj (List.mem_singleton.mp member)  exact decreasetheorem bookkeepingRank_lt (before : State) (bookkeeping : Bookkeeping before)    (evidence : Evidence) (successors : List (Rat × State))    (action : step before = .ok (.next evidence successors))    (probability : Rat) (after : State) (member : (probability, after) ∈ successors) :    bookkeepingRank after < bookkeepingRank before := by  cases before with  | rejected => contradiction  | eval expression environment stack =>    cases expression <;> simp only [Bookkeeping] at bookkeeping    all_goals simp only [step, pure, bind, Except.bind, Except.pure, throw] at action    all_goals repeat' (split at action)    all_goals first      | contradiction      | apply bookkeepingRank_lt_of_singleton _ _ ?_ _ _ _ action _ _ member        simp [bookkeepingRank, expressionWork, frameWork] <;> omega  | deliver value stack =>    cases stack with    | nil => contradiction    | cons frame stack =>      cases frame <;> simp only [Bookkeeping] at bookkeeping      case left =>        apply bookkeepingRank_lt_of_singleton _ _ ?_ _ _ _ action _ _ member        simp [bookkeepingRank, frameWork]        omega      case unary operation =>        cases operation <;> simp only at bookkeeping        all_goals apply bookkeepingRank_lt_of_singleton _ _ ?_ _ _ _ action _ _ member        all_goals simp [bookkeepingRank, frameWork]      case right operation left =>        cases operation <;> simp only at bookkeeping        all_goals apply bookkeepingRank_lt_of_singleton _ _ ?_ _ _ _ action _ _ member        all_goals simp [bookkeepingRank, frameWork]      case draw site pending environment arguments =>        cases pending with        | nil => contradiction        | cons next rest =>          cases value <;> simp only [step, pure, bind, Except.bind, Except.pure, throw] at action          all_goals first            | contradiction            | apply bookkeepingRank_lt_of_singleton _ _ ?_ _ _ _ action _ _ member              simp [bookkeepingRank, frameWork]              omegadef BookkeepingTransition (before after : State) : Prop :=  Bookkeeping before ∧ ∃ evidence successors probability,    step before = .ok (.next evidence successors) ∧ (probability, after) ∈ successorstheorem bookkeepingRank_lt_of_transition (before after : State)    (transition : BookkeepingTransition before after) :    bookkeepingRank after < bookkeepingRank before := by  obtain ⟨bookkeeping, evidence, successors, probability, action, member⟩ := transition  exact bookkeepingRank_lt before bookkeeping evidence successors action probability after membertheorem bookkeepingRank_path_add_le (path : Nat → State) (length : Nat)    (steps : ∀ i < length, BookkeepingTransition (path i) (path (i + 1))) :    bookkeepingRank (path length) + length ≤ bookkeepingRank (path 0) := by  induction length with  | zero => simp  | succ n ih =>    have previous := ih (fun i hi ↦ steps i (by omega))    have decrease := bookkeepingRank_lt_of_transition _ _ (steps n (by omega))    omegatheorem not_forall_bookkeepingTransition (path : Nat → State) :    ¬∀ i, BookkeepingTransition (path i) (path (i + 1)) := by  intro steps  have bound := bookkeepingRank_path_add_le path (bookkeepingRank (path 0) + 1) (fun i _ ↦ steps i)  omegaend Determinize.Proof.FiniteModel