import Determinize.Proof.FiniteModel.Transitionnamespace Determinize.Proof.FiniteModelopen Spec.Paper Determinize.Finite Checking Binding MeasureTheorydef pushStack (state : State) (stack : List Frame) : State := match state with | .eval expression environment saved => .eval expression environment (saved ++ stack) | .deliver value saved => .deliver value (saved ++ stack) | .rejected => .rejectedtheorem stateExpr_pushStack (state : State) (stack : List Frame) (notRejected : state ≠ .rejected) : stateExpr (pushStack state stack) = stackExpr stack (stateExpr state) := by cases state <;> simp_all [pushStack, stateExpr, stackExpr, List.foldl_append]theorem paperStep_pushStack (before after : State) (root : RootStep before after) (notValue : (stateExpr before).isValue = false) (beforeLive : before ≠ .rejected) (afterLive : after ≠ .rejected) (stack : List Frame) (shape : ∀ frame ∈ stack, FrameShape frame) : PaperStep (pushStack before stack) [(1, pushStack after stack)] := by have context := reduce_stackExpr stack shape (stateExpr before) notValue apply paperStep_next · simpa [stateExpr_pushStack before stack beforeLive] using context.1 · rw [stateExpr_pushStack before stack beforeLive, context.2, root.2] simp [Action.wrap, stateExpr_pushStack after stack afterLive]theorem stepMeaning_deliver (value : Value) (stack : List Frame) (shape : ∀ frame ∈ stack, FrameShape frame) (result : Step) (action : step (.deliver value stack) = .ok result) : StepMeaning (.deliver value stack) result := by cases stack with | nil => cases value <;> simp only [step, reduceCtorEq, Except.ok.injEq] at action subst result exact stepMeaning_returned _ | cons frame stack => have tailShape : ∀ f ∈ stack, FrameShape f := fun f hf ↦ shape f (by simp [hf]) cases frame with | left operation right environment => obtain rfl := Except.ok.inj action exact Or.inl ⟨_, rfl, trivial, sameObservations_of_eq _ _ (administrativeStep_left_argument _ _ _ _ _).2⟩ | discrete kind => cases read : value.probabilities? with | none => simp only [step, read] at action change Except.error (Failure.invalid "expected a list of probabilities") = Except.ok result at action contradiction | some p => simp only [step, read] at action change draw (kind, .discrete p.length) p stack = .ok result at action unfold draw at action cases law : finiteLaw (.discrete p.length) kind p 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 := Except.ok.inj action apply Or.inr apply paperStep_sample _ (kind, .discrete p.length) p outcomes stack law · simpa [stateExpr, stackExpr, List.foldl_cons, frameExpr] using (reduce_stackExpr stack tailShape (.discrete kind (valueExpr value)) rfl).1 · exact reduce_stateExpr_discrete kind value p read stack outcomes law tailShape | draw site pending environment arguments => cases value <;> simp only [step, pure, bind, Except.bind, Except.pure, throw] at action all_goals try contradiction rename_i x cases pending with | cons next rest => obtain rfl := Except.ok.inj action exact Or.inl ⟨_, rfl, trivial, sameObservations_of_eq _ _ (administrativeStep_draw_argument _ _ _ _ _ _ _).2⟩ | nil => change draw site (arguments ++ [x]) stack = .ok result at action unfold draw at action cases law : finiteLaw site.2 site.1 (arguments ++ [x]) 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 := Except.ok.inj action apply Or.inr apply paperStep_sample _ site (arguments ++ [x]) outcomes stack law · have nv := (reduce_stackExpr stack tailShape (primitiveExpr site ((arguments ++ [x]).map fun (q : Rat) ↦ .real (q : ℝ))) (isValue_primitiveExpr _ _)).1 simpa only [stateExpr, stackExpr, List.foldl_cons, frameExpr, valueExpr, List.map_append, List.map_cons, List.map_nil] using nv · exact reduce_stateExpr_draw site arguments x environment stack outcomes law tailShape | unary operation => cases operation <;> cases value <;> simp only [step, unary, pure, bind, Except.bind, Except.pure, reduceCtorEq] at action all_goals obtain rfl := Except.ok.inj action all_goals try apply Or.inl refine ⟨_, rfl, trivial, sameObservations_of_eq _ _ ?_⟩ simp [stateExpr, stackExpr, frameExpr, unaryExpr, valueExpr] all_goals apply Or.inr all_goals first | apply paperStep_pushStack _ _ (rootStep_fst _ _) (by simp [stateExpr, stackExpr, frameExpr, unaryExpr, Expr.isValue]) (by simp) (by simp) stack tailShape | apply paperStep_pushStack _ _ (rootStep_snd _ _) (by simp [stateExpr, stackExpr, frameExpr, unaryExpr, Expr.isValue]) (by simp) (by simp) stack tailShape | apply paperStep_pushStack _ _ (rootStep_neg _) (by simp [stateExpr, stackExpr, frameExpr, unaryExpr, Expr.isValue]) (by simp) (by simp) stack tailShape | right operation left => cases operation <;> cases left <;> cases value <;> simp only [step, binary, pure, bind, Except.bind, Except.pure, reduceCtorEq] at action all_goals try split_ifs at action all_goals try simp only [beq_iff_eq] at * all_goals obtain rfl := Except.ok.inj action all_goals try apply Or.inl refine ⟨_, rfl, trivial, sameObservations_of_eq _ _ ?_⟩ simp [stateExpr, stackExpr, frameExpr, binaryExpr, valueExpr] all_goals apply Or.inr all_goals first | apply paperStep_pushStack _ _ (rootStep_closure _ _ _) (by simp [stateExpr, stackExpr, frameExpr, binaryExpr, Expr.isValue]) (by simp) (by simp) stack tailShape | apply paperStep_pushStack _ _ (rootStep_recursive _ _ _) (by simp [stateExpr, stackExpr, frameExpr, binaryExpr, Expr.isValue]) (by simp) (by simp) stack tailShape | apply paperStep_pushStack _ _ (rootStep_add _ _) (by simp [stateExpr, stackExpr, frameExpr, binaryExpr, Expr.isValue]) (by simp) (by simp) stack tailShape | apply paperStep_pushStack _ _ (rootStep_mul _ _) (by simp [stateExpr, stackExpr, frameExpr, binaryExpr, Expr.isValue]) (by simp) (by simp) stack tailShape | apply paperStep_pushStack _ _ (rootStep_div _ _ (by assumption)) (by simp [stateExpr, stackExpr, frameExpr, binaryExpr, Expr.isValue]) (by simp) (by simp) stack tailShape | apply paperStep_pushStack _ _ (rootStep_lt _ _) (by simp [stateExpr, stackExpr, frameExpr, binaryExpr, Expr.isValue]) (by simp) (by simp) stack tailShape | choose yes no environment => cases value <;> simp only [step, pure, bind, Except.bind, Except.pure, throw, reduceCtorEq] at action obtain rfl := Except.ok.inj action apply Or.inr apply paperStep_pushStack _ _ (rootStep_branch _ _ _ _) (by simp [stateExpr, stackExpr, frameExpr, Expr.isValue]) (by simp) (by simp) stack tailShape | letBody body environment => obtain rfl := Except.ok.inj action apply Or.inr apply paperStep_pushStack _ _ (rootStep_let _ _ _) (by simp [stateExpr, stackExpr, frameExpr, Expr.isValue]) (by simp) (by simp) stack tailShape | matchSum left right environment => cases value <;> simp only [step, pure, bind, Except.bind, Except.pure, throw, reduceCtorEq] at action all_goals obtain rfl := Except.ok.inj action all_goals apply Or.inr all_goals first | apply paperStep_pushStack _ _ (rootStep_sum_left _ _ _ _) (by simp [stateExpr, stackExpr, frameExpr, Expr.isValue]) (by simp) (by simp) stack tailShape | apply paperStep_pushStack _ _ (rootStep_sum_right _ _ _ _) (by simp [stateExpr, stackExpr, frameExpr, Expr.isValue]) (by simp) (by simp) stack tailShape | matchList nilCase consCase environment => cases value <;> simp only [step, pure, bind, Except.bind, Except.pure, throw, reduceCtorEq] at action all_goals obtain rfl := Except.ok.inj action all_goals apply Or.inr all_goals first | apply paperStep_pushStack _ _ (rootStep_list_nil _ _ _) (by simp [stateExpr, stackExpr, frameExpr, Expr.isValue]) (by simp) (by simp) stack tailShape | apply paperStep_pushStack _ _ (rootStep_list_cons _ _ _ _ _) (by simp [stateExpr, stackExpr, frameExpr, Expr.isValue]) (by simp) (by simp) stack tailShapetheorem stepMeaning (state : State) (shape : StateShape state) (result : Step) (action : step state = .ok result) : StepMeaning state result := by cases state with | eval expression environment stack => exact stepMeaning_eval expression environment stack result action | deliver value stack => exact stepMeaning_deliver value stack shape result action | rejected => obtain rfl := Except.ok.inj action exact stepMeaning_rejectedend Determinize.Proof.FiniteModel