Source lean/Determinize/Proof/FiniteModel/Contexts.lean
import Determinize.Proof.FiniteModel.Reificationnamespace Determinize.Proof.FiniteModelopen Spec.Paper Determinize.Finite Checking Binding MeasureTheorydef primitiveArity : Op → Nat  | .discrete _ => 0  | .poisson | .bernoulli | .exponential => 1  | .uniform | .gaussian | .beta | .gamma => 2def FrameShape : Frame → Prop  | .draw site pending _ arguments =>    arguments.length + 1 + pending.length = primitiveArity site.2  | _ => Truetheorem reduce_frameExpr (frame : Frame) (shape : FrameShape frame) (hole : Expr)    (notValue : hole.isValue = false) :    (frameExpr frame hole).isValue = false ∧      reduce (frameExpr frame hole) = (reduce hole).wrap (frameExpr frame) := by  cases frame with  | unary op =>    cases op <;> simp [frameExpr, unaryExpr, Expr.isValue, reduce, notValue] <;> rfl  | left op right environment =>    cases op <;> simp [frameExpr, binaryExpr, Expr.isValue, reduce, notValue] <;> rfl  | right op left =>    cases op <;> simp [frameExpr, binaryExpr, Expr.isValue, reduce, notValue, isValue_valueExpr] <;>      rfl  | discrete action | choose yes no environment | letBody body environment  | matchSum left right environment | matchList nilCase consCase environment =>    simp [frameExpr, Expr.isValue, reduce, notValue]    rfl  | draw site pending environment arguments =>    rcases site with ⟨kind, op⟩    rcases arguments with _ | ⟨a, _ | ⟨b, arguments⟩⟩ <;>      rcases pending with _ | ⟨p, _ | ⟨q, pending⟩⟩ <;>      cases op <;> simp_all only [FrameShape, List.length_nil, zero_add, add_zero, primitiveArity,        OfNat.one_ne_ofNat, frameExpr, primitiveExpr, List.map_nil, List.nil_append, Expr.isValue,        reduce, Bool.false_eq_true, ↓reduceIte, true_and, one_ne_zero, List.length_cons,        Nat.reduceAdd, List.map_cons, OfNat.ofNat_ne_one, OfNat.ofNat_ne_zero, Nat.add_eq_left,        Nat.add_eq_zero_iff, List.length_eq_zero_iff, and_false, and_self, List.cons_append,        Nat.succ_ne_self, Nat.reduceEqDiff, Nat.add_eq_right, List.cons.injEq,        List.append_eq_nil_iff, List.map_eq_nil_iff, reduceCtorEq, implies_true] <;>        first | rfl | omegatheorem wrap_wrap (action : Action) (first second : Expr → Expr) :    (action.wrap first).wrap second = action.wrap (second ∘ first) := by  cases action <;> rfltheorem reduce_stackExpr (stack : List Frame) (shape : ∀ frame ∈ stack, FrameShape frame)    (hole : Expr) (notValue : hole.isValue = false) :    (stackExpr stack hole).isValue = false ∧      reduce (stackExpr stack hole) = (reduce hole).wrap (stackExpr stack) := by  induction stack generalizing hole with  | nil =>    refine ⟨notValue, ?_⟩    cases h : reduce hole <;> simp [stackExpr, Action.wrap, h]    rfl  | cons frame stack ih =>    have outerShape : ∀ f ∈ stack, FrameShape f := fun f hf ↦ shape f (by simp [hf])    have inner := reduce_frameExpr frame (shape frame (by simp)) hole notValue    have outer := ih outerShape (frameExpr frame hole) inner.1    refine ⟨outer.1, ?_⟩    change reduce (stackExpr stack (frameExpr frame hole)) = _    rw [outer.2, inner.2, wrap_wrap]    rflprivate theorem reduce_list_prefix_of_absorbing (supplied : List Rat) (tail : Expr)    (notValue : tail.isValue = false) (absorbing : reduce tail = .next tail) :    (supplied.foldr (fun (p : Rat) (rest : Expr) ↦ .cons (.real (p : ℝ)) rest) tail).isValue =      false ∧      reduce (supplied.foldr (fun (p : Rat) (rest : Expr) ↦ .cons (.real (p : ℝ)) rest) tail) =        .next (supplied.foldr (fun (p : Rat) (rest : Expr) ↦ .cons (.real (p : ℝ)) rest) tail) := by  induction supplied with  | nil => exact ⟨notValue, absorbing⟩  | cons p ps ih =>    simp only [List.foldr_cons, Expr.isValue, Bool.true_and, ih.1, reduce, Bool.false_eq_true,      ↓reduceIte, ih.2, Action.wrap, and_self]/-- Evaluation frames preserve an absorbing nonvalue, including a rejection. -/theorem reduce_frameExpr_of_absorbing (frame : Frame) (hole : Expr)    (notValue : hole.isValue = false) (absorbing : reduce hole = .next hole) :    (frameExpr frame hole).isValue = false ∧      reduce (frameExpr frame hole) = .next (frameExpr frame hole) := by  cases frame with  | unary op =>    cases op <;> simp [frameExpr, unaryExpr, Expr.isValue, reduce, notValue, absorbing, Action.wrap]  | left op right environment =>    cases op <;> simp [frameExpr, binaryExpr, Expr.isValue, reduce, notValue, absorbing,      Action.wrap]  | right op left =>    cases op <;> simp [frameExpr, binaryExpr, Expr.isValue, reduce, notValue, absorbing,      isValue_valueExpr, Action.wrap]  | discrete action | choose yes no environment | letBody body environment  | matchSum left right environment | matchList nilCase consCase environment =>    simp [frameExpr, Expr.isValue, reduce, notValue, absorbing, Action.wrap]  | draw site pending environment arguments =>    rcases site with ⟨kind, op⟩    cases op with    | discrete n =>      have inner := reduce_list_prefix_of_absorbing arguments        (.cons hole (pending.foldr          (fun e rest ↦ .cons (close (environmentExpr environment) 0 (interpret e)) rest) .nil))        (by simp [Expr.isValue, notValue])        (by simp [reduce, notValue, absorbing, Action.wrap])      simp only [frameExpr, primitiveExpr, List.foldr_append, List.foldr_cons, List.foldr_map,        Expr.isValue, reduce, inner.1, Bool.false_eq_true, ↓reduceIte, inner.2, Action.wrap,        and_self]    | _ =>      rcases arguments with _ | ⟨a, _ | ⟨b, arguments⟩⟩ <;>        rcases pending with _ | ⟨p, _ | ⟨q, pending⟩⟩ <;>        simp [frameExpr, primitiveExpr, Expr.isValue, reduce,          notValue, absorbing, Action.wrap]theorem reduce_stackExpr_of_absorbing (stack : List Frame) (hole : Expr)    (notValue : hole.isValue = false) (absorbing : reduce hole = .next hole) :    (stackExpr stack hole).isValue = false ∧      reduce (stackExpr stack hole) = .next (stackExpr stack hole) := by  induction stack generalizing hole with  | nil => exact ⟨notValue, absorbing⟩  | cons frame stack ih =>    have frameResult := reduce_frameExpr_of_absorbing frame hole notValue absorbing    exact ih (frameExpr frame hole) frameResult.1 frameResult.2theorem outputMeasureAt_eq_zero_of_absorbing (expression : Expr)    (notValue : expression.isValue = false) (absorbing : reduce expression = .next expression)    (fuel : Nat) : outputMeasureAt fuel expression = 0 := by  induction fuel with  | zero => cases expression <;> simp_all [Expr.isValue, outputMeasureAt]  | succ fuel ih => simpa [outputMeasureAt, notValue, absorbing] using ihtheorem domainSafe_of_absorbing (expression : Expr)    (notValue : expression.isValue = false) (absorbing : reduce expression = .next expression) :    DomainSafe expression := by  intro fuel  induction fuel with  | zero => trivial  | succ fuel ih => simpa [DomainSafeAt, notValue, absorbing] using ihtheorem bigStepMeasure_stackExpr_reject (stack : List Frame) :    bigStepMeasure (stackExpr stack .reject) = 0 := by  have absorbing := reduce_stackExpr_of_absorbing stack .reject rfl rfl  simp [bigStepMeasure, outputMeasureAt_eq_zero_of_absorbing _ absorbing.1 absorbing.2]theorem domainSafe_stackExpr_reject (stack : List Frame) :    DomainSafe (stackExpr stack .reject) := by  have absorbing := reduce_stackExpr_of_absorbing stack .reject rfl rfl  exact domainSafe_of_absorbing _ absorbing.1 absorbing.2/-- Dropping a machine stack on rejection agrees with the paper output law.The paper expression need not reduce to a bare rejection. -/theorem step_eval_reject (environment : List Value) (stack : List Frame) :    step (.eval .reject environment stack) = .ok (.next .evaluate [(1, .rejected)]) ∧    bigStepMeasure (stateExpr (.eval .reject environment stack)) =      bigStepMeasure (stateExpr .rejected) ∧    DomainSafe (stateExpr (.eval .reject environment stack)) := by  refine ⟨rfl, ?_, ?_⟩  · simp [stateExpr, interpret, close, Expr.map, Expr.mapVars, bigStepMeasure_stackExpr_reject,      show bigStepMeasure (.reject : Expr) = 0 from bigStepMeasure_stackExpr_reject []]  · simpa [stateExpr, interpret, close, Expr.map, Expr.mapVars]      using domainSafe_stackExpr_reject stackend Determinize.Proof.FiniteModel