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