Source lean/Determinize/Proof/FiniteModel/Invariants.lean
import Determinize.Proof.FiniteModel.Samplingimport Determinize.Proof.FiniteModel.Replaynamespace Determinize.Proof.FiniteModelopen Spec.Paper Spec.FiniteModel Determinize.Finite Checkingdef StateShape : State → Prop  | .eval _ _ stack | .deliver _ stack => ∀ frame ∈ stack, FrameShape frame  | .rejected => Trueprivate theorem stateShape_singleton (state : State) (shape : StateShape state)    (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) :    StateShape after := by  obtain ⟨rfl, rfl⟩ := Step.next.inj (Except.ok.inj action)  obtain ⟨rfl, rfl⟩ := Prod.mk.inj (List.mem_singleton.mp member)  exact shapeprivate theorem stateShape_draw (site : DistributionAction × Op) (arguments : List Rat)    (stack : List Frame) (shape : ∀ frame ∈ stack, FrameShape frame)    (evidence : Evidence) (successors : List (Rat × State))    (action : draw site arguments stack = .ok (.next evidence successors))    (probability : Rat) (after : State) (member : (probability, after) ∈ successors) :    StateShape after := by  unfold draw at action  cases law : finiteLaw site.2 site.1 arguments with  | error failure => simp [law, bind, Except.bind] at action  | ok outcomes =>    simp only [law, bind, Except.bind, pure, Except.pure] at action    obtain ⟨rfl, rfl⟩ := Step.next.inj (Except.ok.inj action)    obtain ⟨⟨p, x⟩, _, equal⟩ := List.mem_map.mp member    obtain ⟨rfl, rfl⟩ := Prod.mk.inj equal    exact shapeprivate theorem stateShape_binary (op : Binary) (left right : Value) (stack : List Frame)    (shape : ∀ frame ∈ stack, FrameShape frame) (result : State)    (success : binary op left right stack = .ok result) : StateShape result := by  cases op <;> cases left <;> cases right <;>    simp only [binary, reduceCtorEq, Except.ok.injEq] at success  all_goals repeat' split at success  all_goals try simp only [reduceCtorEq, Except.ok.injEq] at success  all_goals subst result  all_goals exact shapeset_option maxHeartbeats 1000000 in-- One case per machine state and frame, each splitting every branch of `step`.theorem stateShape_step (before : State) (shape : StateShape before)    (evidence : Evidence) (successors : List (Rat × State))    (action : step before = .ok (.next evidence successors))    (probability : Rat) (after : State) (member : (probability, after) ∈ successors) :    StateShape after := by  cases before with  | rejected => simp [step] at action  | eval expression environment stack =>    cases expression <;>      simp only [step, pure, bind, Except.bind, Except.pure, throw] at action    all_goals repeat' (split at action)    all_goals try first      | contradiction      | apply stateShape_singleton _ ?_ _ _ _ action _ _ member        clear action member        simp_all [StateShape, FrameShape, primitiveArity]  | deliver value stack =>    cases stack with    | nil => cases value <;> simp [step] at action    | cons frame stack =>      have tailShape : ∀ frame ∈ stack, FrameShape frame :=        fun f hf ↦ shape f (by simp [hf])      cases frame <;> cases value <;>        simp only [step, unary, pure, bind, Except.bind, Except.pure, throw] at action      all_goals repeat' (split at action)      all_goals try first        | contradiction        | apply stateShape_singleton _ ?_ _ _ _ action _ _ member          clear action member          simp_all [StateShape, FrameShape, primitiveArity]          all_goals omega      all_goals try exact stateShape_draw _ _ _ tailShape _ _ action _ _ member      all_goals try        apply stateShape_singleton _ ?_ _ _ _ action _ _ member        exact stateShape_binary _ _ _ _ tailShape _ (by assumption)theorem stateShape_of_reachable (initial : State) (shape : StateShape initial) (state : State)    (reachable : MachineReachable initial state) : StateShape state := by  induction reachable with  | initial => exact shape  | next previous action member positive ih => exact stateShape_step _ ih _ _ action _ _ membertheorem stateShape_initialState (source : Core) (subject : Subject) :    StateShape (initialState source subject) := by  simp [initialState, StateShape]theorem stateShape_of_reachable_initialState (source : Core) (subject : Subject) (state : State)    (reachable : MachineReachable (initialState source subject) state) : StateShape state :=  stateShape_of_reachable _ (stateShape_initialState source subject) state reachabletheorem reduce_stateExpr_draw_of_reachable (source : Core) (subject : Subject)    (site : DistributionAction × Op) (arguments : List Rat) (x : Rat)    (environment : List Value) (stack : List Frame) (outcomes : List (Rat × Rat))    (reachable : MachineReachable (initialState source subject)      (.deliver (.number x) (.draw site [] environment arguments :: stack)))    (success : finiteLaw site.2 site.1 (arguments ++ [x]) = .ok outcomes) :    reduce (stateExpr (.deliver (.number x) (.draw site [] environment arguments :: stack))) =      .sample site (outcomeMeasure outcomes) (fun y ↦ stackExpr stack (.real y)) := by  apply reduce_stateExpr_draw site arguments x environment stack outcomes success  have shape := stateShape_of_reachable_initialState source subject _ reachable  exact fun frame member ↦ shape frame (by simp [member])end Determinize.Proof.FiniteModel