import Determinize.Proof.Semantics.Subtypingimport Determinize.Proof.Semantics.Measurability/-!# Type safety for the paper semanticsSubstitution and successful reduction preserve typing. `ActionTyped` also allowsstuck actions; the public `DomainSafe` assumption excludes them almost surely.-/namespace Determinize.Proof.Paperopen MeasureTheory ProbabilityTheoryopen Determinize.Spec.Papernamespace Typingtheorem hasVar_prepend (h : HasVar suffix index ty) : HasVar (inserted ++ suffix) (index + inserted.length) ty := by induction inserted with | nil => simpa | cons head inserted ih => simpa [Nat.add_assoc, Nat.add_comm, Nat.add_left_comm] using HasVar.tail (head := head) ihtheorem hasVar_shift (h : HasVar (before ++ suffix) index ty) : HasVar (before ++ inserted ++ suffix) (if before.length ≤ index then index + inserted.length else index) ty := by induction before generalizing index with | nil => simp only [List.nil_append, List.length_nil, Nat.zero_le, ↓reduceIte] exact hasVar_prepend h | cons head before ih => cases h with | head => simp only [List.cons_append, List.length_cons] exact .head | tail h => rename_i index simp only [List.cons_append, List.length_cons, Nat.succ_le_succ_iff] by_cases condition : before.length ≤ index · simp only [condition, ↓reduceIte] have shifted := ih h simp only [condition, ↓reduceIte] at shifted convert HasVar.tail (head := head) shifted using 1; omega · simp only [condition, ↓reduceIte] have shifted := ih h simp only [condition, ↓reduceIte] at shifted exact HasVar.tail (head := head) shiftedtheorem typed_shift (h : Typed (before ++ suffix) expression ty) : Typed (before ++ inserted ++ suffix) (expression.shift inserted.length before.length) ty := by generalize hcontext : before ++ suffix = context at h induction h generalizing before suffix with | bvar hvar => rw [← hcontext] at hvar rw [Expr.shift, Expr.mapVars] exact .bvar (hasVar_shift hvar) | reject => rw [Expr.shift, Expr.mapVars]; exact .reject | discrete hv ih => rw [Expr.shift, Expr.mapVars] exact .discrete (ih (before := before) (suffix := suffix) hcontext) | discreteMean hv ih => rw [Expr.shift, Expr.mapVars] exact .discreteMean (ih (before := before) (suffix := suffix) hcontext) | unit => rw [Expr.shift, Expr.mapVars]; exact .unit | bool => rw [Expr.shift, Expr.mapVars]; exact .bool | real => rw [Expr.shift, Expr.mapVars]; exact .real | lam h ih => rw [Expr.shift, Expr.mapVars] exact .lam (ih (before := _ :: before) (suffix := suffix) (by simpa using hcontext)) | fix h ih => rw [Expr.shift, Expr.mapVars] exact .fix (ih (before := _ :: _ :: before) (suffix := suffix) (by simpa using hcontext)) | app hf hx ihf ihx => rw [Expr.shift, Expr.mapVars] exact .app (ihf (before := before) (suffix := suffix) hcontext) (ihx (before := before) (suffix := suffix) hcontext) | pair hl hr ihl ihr => rw [Expr.shift, Expr.mapVars] exact .pair (ihl (before := before) (suffix := suffix) hcontext) (ihr (before := before) (suffix := suffix) hcontext) | fst hp ih => rw [Expr.shift, Expr.mapVars] exact .fst (ih (before := before) (suffix := suffix) hcontext) | snd hp ih => rw [Expr.shift, Expr.mapVars] exact .snd (ih (before := before) (suffix := suffix) hcontext) | inl hv ih => rw [Expr.shift, Expr.mapVars] exact .inl (ih (before := before) (suffix := suffix) hcontext) | inr hv ih => rw [Expr.shift, Expr.mapVars] exact .inr (ih (before := before) (suffix := suffix) hcontext) | matchSum hs hl hr ihs ihl ihr => rw [Expr.shift, Expr.mapVars] exact .matchSum (ihs (before := before) (suffix := suffix) hcontext) (ihl (before := _ :: before) (suffix := suffix) (by simpa using hcontext)) (ihr (before := _ :: before) (suffix := suffix) (by simpa using hcontext)) | nil => rw [Expr.shift, Expr.mapVars]; exact .nil | cons hh ht ihh iht => rw [Expr.shift, Expr.mapVars] exact .cons (ihh (before := before) (suffix := suffix) hcontext) (iht (before := before) (suffix := suffix) hcontext) | matchList hs hn hc ihs ihn ihc => rw [Expr.shift, Expr.mapVars] exact .matchList (ihs (before := before) (suffix := suffix) hcontext) (ihn (before := before) (suffix := suffix) hcontext) (ihc (before := _ :: _ :: before) (suffix := suffix) (by simpa using hcontext)) | ite hc ht he ihc iht ihe => rw [Expr.shift, Expr.mapVars] exact .ite (ihc (before := before) (suffix := suffix) hcontext) (iht (before := before) (suffix := suffix) hcontext) (ihe (before := before) (suffix := suffix) hcontext) | letE hv hb ihv ihb => rw [Expr.shift, Expr.mapVars] exact .letE (ihv (before := before) (suffix := suffix) hcontext) (ihb (before := _ :: before) (suffix := suffix) (by simpa using hcontext)) | sub hv h ih => exact .sub (ih (before := before) (suffix := suffix) hcontext) h | neg hv ih => rw [Expr.shift, Expr.mapVars] exact .neg (ih (before := before) (suffix := suffix) hcontext) | add hl hr ihl ihr => rw [Expr.shift, Expr.mapVars] exact .add (ihl (before := before) (suffix := suffix) hcontext) (ihr (before := before) (suffix := suffix) hcontext) | mul hl hr ihl ihr => rw [Expr.shift, Expr.mapVars] exact .mul (ihl (before := before) (suffix := suffix) hcontext) (ihr (before := before) (suffix := suffix) hcontext) | div hl hr ihl ihr => rw [Expr.shift, Expr.mapVars] exact .div (ihl (before := before) (suffix := suffix) hcontext) (ihr (before := before) (suffix := suffix) hcontext) | lt hl hr ihl ihr => rw [Expr.shift, Expr.mapVars] exact .lt (ihl (before := before) (suffix := suffix) hcontext) (ihr (before := before) (suffix := suffix) hcontext) | uniform hl hr ihl ihr | gaussian hl hr ihl ihr | beta hl hr ihl ihr | gamma hl hr ihl ihr => rw [Expr.shift, Expr.mapVars] first | exact .uniform (ihl (before := before) (suffix := suffix) hcontext) (ihr (before := before) (suffix := suffix) hcontext) | exact .gaussian (ihl (before := before) (suffix := suffix) hcontext) (ihr (before := before) (suffix := suffix) hcontext) | exact .beta (ihl (before := before) (suffix := suffix) hcontext) (ihr (before := before) (suffix := suffix) hcontext) | exact .gamma (ihl (before := before) (suffix := suffix) hcontext) (ihr (before := before) (suffix := suffix) hcontext) | uniformMean hl hr ihl ihr | gaussianMean hl hr ihl ihr | betaMean hl hr ihl ihr | gammaMean hl hr ihl ihr => rw [Expr.shift, Expr.mapVars] first | exact .uniformMean (ihl (before := before) (suffix := suffix) hcontext) (ihr (before := before) (suffix := suffix) hcontext) | exact .gaussianMean (ihl (before := before) (suffix := suffix) hcontext) (ihr (before := before) (suffix := suffix) hcontext) | exact .betaMean (ihl (before := before) (suffix := suffix) hcontext) (ihr (before := before) (suffix := suffix) hcontext) | exact .gammaMean (ihl (before := before) (suffix := suffix) hcontext) (ihr (before := before) (suffix := suffix) hcontext) | poisson hv ih | bernoulli hv ih | exponential hv ih => rw [Expr.shift, Expr.mapVars] first | exact .poisson (ih (before := before) (suffix := suffix) hcontext) | exact .bernoulli (ih (before := before) (suffix := suffix) hcontext) | exact .exponential (ih (before := before) (suffix := suffix) hcontext) | poissonMean hv ih | bernoulliMean hv ih | exponentialMean hv ih => rw [Expr.shift, Expr.mapVars] first | exact .poissonMean (ih (before := before) (suffix := suffix) hcontext) | exact .bernoulliMean (ih (before := before) (suffix := suffix) hcontext) | exact .exponentialMean (ih (before := before) (suffix := suffix) hcontext)theorem hasVar_subst (h : HasVar (before ++ binder :: suffix) index ty) : (index = before.length ∧ ty = binder) ∨ (index ≠ before.length ∧ HasVar (before ++ suffix) (if before.length < index then index - 1 else index) ty) := by induction before generalizing index with | nil => cases h with | head => exact .inl ⟨rfl, rfl⟩ | tail h => right exact ⟨by simp only [List.length_nil]; omega, by simpa using h⟩ | cons head before ih => cases h with | head => right simp only [List.cons_append, List.length_cons] exact ⟨by omega, .head⟩ | tail h => rcases ih h with equal | shifted · left exact ⟨congrArg Nat.succ equal.1, equal.2⟩ · right rcases shifted with ⟨notEqual, shifted⟩ rename_i index constructor · simp only [List.length_cons] omega simp only [List.cons_append, List.length_cons, Nat.succ_lt_succ_iff] by_cases condition : before.length < index · simp only [condition, ↓reduceIte] have shifted := shifted simp only [condition, ↓reduceIte] at shifted have shifted' := HasVar.tail (head := head) shifted convert shifted' using 1; omega · simp only [condition, ↓reduceIte] have shifted := shifted simp only [condition, ↓reduceIte] at shifted exact HasVar.tail (head := head) shiftedtheorem typed_substAt (h : Typed (before ++ binder :: suffix) expression ty) (replacementTyped : Typed suffix replacement binder) : Typed (before ++ suffix) (Expr.substAt before.length replacement expression) ty := by generalize hcontext : before ++ binder :: suffix = context at h induction h generalizing before suffix with | bvar hvar => rw [← hcontext] at hvar rcases hasVar_subst hvar with equal | shifted · rcases equal with ⟨rfl, rfl⟩ rw [Expr.substAt, Expr.mapVars, ite_eq_left rfl] simpa only [List.nil_append, List.append_assoc, List.length_nil] using (typed_shift (before := []) (suffix := suffix) (inserted := before) replacementTyped) · rcases shifted with ⟨notEqual, shifted⟩ rw [Expr.substAt, Expr.mapVars, ite_eq_right notEqual] exact .bvar shifted | reject => rw [Expr.substAt, Expr.mapVars]; exact .reject | discrete hv ih => rw [Expr.substAt, Expr.mapVars] exact .discrete (ih replacementTyped (before := before) (suffix := suffix) hcontext) | discreteMean hv ih => rw [Expr.substAt, Expr.mapVars] exact .discreteMean (ih replacementTyped (before := before) (suffix := suffix) hcontext) | unit => rw [Expr.substAt, Expr.mapVars]; exact .unit | bool => rw [Expr.substAt, Expr.mapVars]; exact .bool | real => rw [Expr.substAt, Expr.mapVars]; exact .real | lam h ih => rw [Expr.substAt, Expr.mapVars] exact .lam (ih replacementTyped (before := _ :: before) (suffix := suffix) (by simpa using hcontext)) | fix h ih => rw [Expr.substAt, Expr.mapVars] exact .fix (ih replacementTyped (before := _ :: _ :: before) (suffix := suffix) (by simpa using hcontext)) | app hf hx ihf ihx => rw [Expr.substAt, Expr.mapVars] exact .app (ihf replacementTyped (before := before) (suffix := suffix) hcontext) (ihx replacementTyped (before := before) (suffix := suffix) hcontext) | pair hl hr ihl ihr => rw [Expr.substAt, Expr.mapVars] exact .pair (ihl replacementTyped (before := before) (suffix := suffix) hcontext) (ihr replacementTyped (before := before) (suffix := suffix) hcontext) | fst hp ih => rw [Expr.substAt, Expr.mapVars] exact .fst (ih replacementTyped (before := before) (suffix := suffix) hcontext) | snd hp ih => rw [Expr.substAt, Expr.mapVars] exact .snd (ih replacementTyped (before := before) (suffix := suffix) hcontext) | inl hv ih => rw [Expr.substAt, Expr.mapVars] exact .inl (ih replacementTyped (before := before) (suffix := suffix) hcontext) | inr hv ih => rw [Expr.substAt, Expr.mapVars] exact .inr (ih replacementTyped (before := before) (suffix := suffix) hcontext) | matchSum hs hl hr ihs ihl ihr => rw [Expr.substAt, Expr.mapVars] exact .matchSum (ihs replacementTyped (before := before) (suffix := suffix) hcontext) (ihl replacementTyped (before := _ :: before) (suffix := suffix) (by simpa using hcontext)) (ihr replacementTyped (before := _ :: before) (suffix := suffix) (by simpa using hcontext)) | nil => rw [Expr.substAt, Expr.mapVars]; exact .nil | cons hh ht ihh iht => rw [Expr.substAt, Expr.mapVars] exact .cons (ihh replacementTyped (before := before) (suffix := suffix) hcontext) (iht replacementTyped (before := before) (suffix := suffix) hcontext) | matchList hs hn hc ihs ihn ihc => rw [Expr.substAt, Expr.mapVars] exact .matchList (ihs replacementTyped (before := before) (suffix := suffix) hcontext) (ihn replacementTyped (before := before) (suffix := suffix) hcontext) (ihc replacementTyped (before := _ :: _ :: before) (suffix := suffix) (by simpa using hcontext)) | ite hc ht he ihc iht ihe => rw [Expr.substAt, Expr.mapVars] exact .ite (ihc replacementTyped (before := before) (suffix := suffix) hcontext) (iht replacementTyped (before := before) (suffix := suffix) hcontext) (ihe replacementTyped (before := before) (suffix := suffix) hcontext) | letE hv hb ihv ihb => rw [Expr.substAt, Expr.mapVars] exact .letE (ihv replacementTyped (before := before) (suffix := suffix) hcontext) (ihb replacementTyped (before := _ :: before) (suffix := suffix) (by simpa using hcontext)) | sub hv h ih => exact .sub (ih replacementTyped (before := before) (suffix := suffix) hcontext) h | neg hv ih => rw [Expr.substAt, Expr.mapVars] exact .neg (ih replacementTyped (before := before) (suffix := suffix) hcontext) | add hl hr ihl ihr => rw [Expr.substAt, Expr.mapVars] exact .add (ihl replacementTyped (before := before) (suffix := suffix) hcontext) (ihr replacementTyped (before := before) (suffix := suffix) hcontext) | mul hl hr ihl ihr => rw [Expr.substAt, Expr.mapVars] exact .mul (ihl replacementTyped (before := before) (suffix := suffix) hcontext) (ihr replacementTyped (before := before) (suffix := suffix) hcontext) | div hl hr ihl ihr => rw [Expr.substAt, Expr.mapVars] exact .div (ihl replacementTyped (before := before) (suffix := suffix) hcontext) (ihr replacementTyped (before := before) (suffix := suffix) hcontext) | lt hl hr ihl ihr => rw [Expr.substAt, Expr.mapVars] exact .lt (ihl replacementTyped (before := before) (suffix := suffix) hcontext) (ihr replacementTyped (before := before) (suffix := suffix) hcontext) | uniform hl hr ihl ihr | gaussian hl hr ihl ihr | beta hl hr ihl ihr | gamma hl hr ihl ihr => rw [Expr.substAt, Expr.mapVars] first | exact .uniform (ihl replacementTyped (before := before) (suffix := suffix) hcontext) (ihr replacementTyped (before := before) (suffix := suffix) hcontext) | exact .gaussian (ihl replacementTyped (before := before) (suffix := suffix) hcontext) (ihr replacementTyped (before := before) (suffix := suffix) hcontext) | exact .beta (ihl replacementTyped (before := before) (suffix := suffix) hcontext) (ihr replacementTyped (before := before) (suffix := suffix) hcontext) | exact .gamma (ihl replacementTyped (before := before) (suffix := suffix) hcontext) (ihr replacementTyped (before := before) (suffix := suffix) hcontext) | uniformMean hl hr ihl ihr | gaussianMean hl hr ihl ihr | betaMean hl hr ihl ihr | gammaMean hl hr ihl ihr => rw [Expr.substAt, Expr.mapVars] first | exact .uniformMean (ihl replacementTyped (before := before) (suffix := suffix) hcontext) (ihr replacementTyped (before := before) (suffix := suffix) hcontext) | exact .gaussianMean (ihl replacementTyped (before := before) (suffix := suffix) hcontext) (ihr replacementTyped (before := before) (suffix := suffix) hcontext) | exact .betaMean (ihl replacementTyped (before := before) (suffix := suffix) hcontext) (ihr replacementTyped (before := before) (suffix := suffix) hcontext) | exact .gammaMean (ihl replacementTyped (before := before) (suffix := suffix) hcontext) (ihr replacementTyped (before := before) (suffix := suffix) hcontext) | poisson hv ih | bernoulli hv ih | exponential hv ih => rw [Expr.substAt, Expr.mapVars] first | exact .poisson (ih replacementTyped (before := before) (suffix := suffix) hcontext) | exact .bernoulli (ih replacementTyped (before := before) (suffix := suffix) hcontext) | exact .exponential (ih replacementTyped (before := before) (suffix := suffix) hcontext) | poissonMean hv ih | bernoulliMean hv ih | exponentialMean hv ih => rw [Expr.substAt, Expr.mapVars] first | exact .poissonMean (ih replacementTyped (before := before) (suffix := suffix) hcontext) | exact .bernoulliMean (ih replacementTyped (before := before) (suffix := suffix) hcontext) | exact .exponentialMean (ih replacementTyped (before := before) (suffix := suffix) hcontext)theorem typed_substHead (bodyTyped : Typed (binder :: suffix) body ty) (replacementTyped : Typed suffix replacement binder) : Typed suffix (Expr.substHead body replacement) ty := by simpa [Expr.substHead] using typed_substAt (before := []) bodyTyped replacementTypedtheorem typed_substTwo (bodyTyped : Typed (argumentTy :: functionTy :: suffix) body resultTy) (argumentTyped : Typed suffix argument argumentTy) (functionTyped : Typed suffix function functionTy) : Typed suffix (Expr.substTwo body argument function) resultTy := by rw [Expr.substTwo] apply typed_substHead · exact typed_substAt (before := [argumentTy]) bodyTyped functionTyped · exact argumentTypedinductive ActionTyped (ty : Ty) : Action → Prop | stuck : ActionTyped ty .stuck | next : Typed [] expression ty → ActionTyped ty (.next expression) | sample : (∀ value, Typed [] (continuation value) ty) → ActionTyped ty (.sample site fiber continuation)theorem ActionTyped.wrap (actionTyped : ActionTyped childTy action) (wrapTyped : ∀ expression, Typed [] expression childTy → Typed [] (context expression) resultTy) : ActionTyped resultTy (action.wrap context) := by cases actionTyped with | stuck => exact .stuck | next typed => exact .next (wrapTyped _ typed) | sample typed => exact .sample fun value ↦ wrapTyped _ (typed value)@[simp] theorem noVar_nil : ¬ HasVar [] index ty := by intro h cases htheorem ActionTyped.sub (typed : ActionTyped a action) (h : Ty.Sub a b) : ActionTyped b action := by cases typed with | stuck => exact .stuck | next ht => exact .next (ht.sub h) | sample ht => exact .sample (fun v ↦ (ht v).sub h)theorem typed_arr_value (typed : Typed context expression (.arr argument result)) (value : expression.isValue = true) : (∃ a r body, expression = .lam body ∧ Ty.Sub argument a ∧ Ty.Sub r result ∧ Typed (a :: context) body r) ∨ (∃ a r body, expression = .fix body ∧ Ty.Sub argument a ∧ Ty.Sub r result ∧ Typed (a :: .arr a r :: context) body r) := by generalize ht : Ty.arr argument result = ty at typed induction typed generalizing argument result case sub h sub ih => cases sub <;> cases ht rcases ih value rfl with ⟨a, r, body, he, ha, hr, hb⟩ | ⟨a, r, body, he, ha, hr, hb⟩ · exact Or.inl ⟨a, r, body, he, Ty.Sub.trans (by assumption) ha, Ty.Sub.trans hr (by assumption), hb⟩ · exact Or.inr ⟨a, r, body, he, Ty.Sub.trans (by assumption) ha, Ty.Sub.trans hr (by assumption), hb⟩ all_goals cases ht <;> simp_all only [Expr.isValue, Bool.false_eq_true, Expr.lam.injEq, exists_eq_left', exists_and_left, reduceCtorEq, false_and, exists_const, exists_false, or_false, Expr.fix.injEq, false_or, not_isEmpty_of_nonempty, IsEmpty.exists_iff, exists_const_iff, and_true, and_self, or_self, IsEmpty.forall_iff, implies_true] all_goals exact ⟨_, Ty.Sub.refl _, _, Ty.Sub.refl _, by assumption⟩theorem typed_prod_value (typed : Typed context expression (.prod leftTy rightTy)) (value : expression.isValue = true) : ∃ left right, expression = .pair left right ∧ Typed context left leftTy ∧ Typed context right rightTy := by generalize ht : Ty.prod leftTy rightTy = ty at typed induction typed generalizing leftTy rightTy case sub h sub ih => cases sub <;> cases ht obtain ⟨l, r, he, hl, hr⟩ := ih value rfl exact ⟨l, r, he, hl.sub (by assumption), hr.sub (by assumption)⟩ all_goals cases ht <;> simp_all [Expr.isValue]theorem typed_sum_value (typed : Typed context expression (.sum leftTy rightTy)) (value : expression.isValue = true) : (∃ body, expression = .inl body ∧ Typed context body leftTy) ∨ (∃ body, expression = .inr body ∧ Typed context body rightTy) := by generalize ht : Ty.sum leftTy rightTy = ty at typed induction typed generalizing leftTy rightTy case sub h sub ih => cases sub <;> cases ht rcases ih value rfl with ⟨b, he, hb⟩ | ⟨b, he, hb⟩ · exact Or.inl ⟨b, he, hb.sub (by assumption)⟩ · exact Or.inr ⟨b, he, hb.sub (by assumption)⟩ all_goals cases ht <;> simp_all [Expr.isValue]theorem typed_list_value (typed : Typed context expression (.list element)) (value : expression.isValue = true) : expression = .nil ∨ ∃ head tail, expression = .cons head tail ∧ Typed context head element ∧ Typed context tail (.list element) := by generalize ht : Ty.list element = ty at typed induction typed generalizing element case sub h sub ih => cases sub <;> cases ht rcases ih value rfl with he | ⟨h, t, he, hh, ht⟩ · exact Or.inl he · exact Or.inr ⟨h, t, he, hh.sub (by assumption), ht.sub (.list (by assumption))⟩ all_goals cases ht <;> simp_all [Expr.isValue]theorem typed_bool_value (typed : Typed context expression .bool) (value : expression.isValue = true) : ∃ result, expression = .bool result := by generalize ht : Ty.bool = ty at typed induction typed case sub h sub ih => cases sub <;> cases ht exact ih value rfl all_goals cases ht <;> simp_all [Expr.isValue]theorem typed_real_value (typed : Typed context expression (.float affinity)) (value : expression.isValue = true) : ∃ result, expression = .real result := by generalize ht : Ty.float affinity = ty at typed induction typed generalizing affinity case sub h sub ih => cases sub <;> cases ht <;> exact ih value rfl all_goals cases ht <;> simp_all [Expr.isValue]theorem typed_realList_value (typed : Typed context expression (.list (.float affinity))) (value : expression.isValue = true) : ∃ values, realListValue? expression = some values := by induction expression with | cons head tail _ ih => obtain impossible | ⟨h, t, eq, headTyped, tailTyped⟩ := typed_list_value typed value · cases impossible cases eq simp only [Expr.isValue, Bool.and_eq_true] at value obtain ⟨v, rfl⟩ := typed_real_value headTyped value.1 obtain ⟨vs, eq⟩ := ih tailTyped value.2 exact ⟨v :: vs, by simp [realListValue?, realValue?, eq]⟩ | nil => exact ⟨[], rfl⟩ | _ => obtain eq | ⟨_, _, eq, _⟩ := typed_list_value typed value <;> cases eqtheorem reduce_typed_closed (typed : Typed [] expression ty) : ActionTyped ty (reduce expression) := by generalize hcontext : ([] : List Ty) = context at typed induction typed with | bvar hvar => rw [← hcontext] at hvar exact (noVar_nil hvar).elim | reject => rw [reduce]; exact .next .reject | discrete probabilitiesTyped ih | discreteMean probabilitiesTyped ih => cases hcontext rw [reduce] split · obtain ⟨values, eq⟩ := typed_realList_value probabilitiesTyped (by assumption) simp only [eq] exact .sample fun value ↦ .real · first | exact (ih rfl).wrap fun next nextTyped ↦ .discrete nextTyped | exact (ih rfl).wrap fun next nextTyped ↦ .discreteMean nextTyped | unit => rw [reduce]; exact .next .unit | bool => rw [reduce]; exact .next .bool | real => rw [reduce]; exact .next .real | lam bodyTyped ih => cases hcontext rw [reduce] exact .next (.lam bodyTyped) | fix bodyTyped ih => cases hcontext rw [reduce] exact .next (.fix bodyTyped) | app functionTyped argumentTyped ihf iha => cases hcontext rename_i function argumentTy result operand rw [MeasurableActionFamily.reduce_app_eq] by_cases functionValue : function.isValue = true · simp only [functionValue, ↓reduceIte] by_cases argumentValue : operand.isValue = true · simp only [argumentValue, ↓reduceIte] rcases typed_arr_value functionTyped functionValue with function | function · rcases function with ⟨a, r, body, rfl, ha, hr, bodyTyped⟩ simpa using ActionTyped.next ((typed_substHead bodyTyped (argumentTyped.sub ha)).sub hr) · rcases function with ⟨a, r, body, rfl, ha, hr, bodyTyped⟩ simpa using ActionTyped.next ((typed_substTwo bodyTyped (argumentTyped.sub ha) (.fix bodyTyped)).sub hr) · simp only [argumentValue] exact (iha rfl).wrap fun next nextTyped ↦ .app functionTyped nextTyped · simp only [functionValue] exact (ihf rfl).wrap fun next nextTyped ↦ .app nextTyped argumentTyped | pair leftTyped rightTyped ihl ihr => cases hcontext rw [reduce] split · split · exact .next (.pair leftTyped rightTyped) · exact (ihr rfl).wrap fun next nextTyped ↦ .pair leftTyped nextTyped · exact (ihl rfl).wrap fun next nextTyped ↦ .pair nextTyped rightTyped | fst pairTyped ih => cases hcontext rename_i pair leftTy rightTy rw [MeasurableActionFamily.reduce_fst_eq] by_cases pairValue : pair.isValue = true · simp only [pairValue, ↓reduceIte] rcases typed_prod_value pairTyped pairValue with ⟨left, right, rfl, leftTyped, rightTyped⟩ simpa using ActionTyped.next leftTyped · simp only [pairValue] exact (ih rfl).wrap fun next nextTyped ↦ .fst nextTyped | snd pairTyped ih => cases hcontext rename_i pair leftTy rightTy rw [MeasurableActionFamily.reduce_snd_eq] by_cases pairValue : pair.isValue = true · simp only [pairValue, ↓reduceIte] rcases typed_prod_value pairTyped pairValue with ⟨left, right, rfl, leftTyped, rightTyped⟩ simpa using ActionTyped.next rightTyped · simp only [pairValue] exact (ih rfl).wrap fun next nextTyped ↦ .snd nextTyped | inl valueTyped ih => cases hcontext rw [reduce] split · exact .next (.inl valueTyped) · exact (ih rfl).wrap fun next nextTyped ↦ .inl nextTyped | inr valueTyped ih => cases hcontext rw [reduce] split · exact .next (.inr valueTyped) · exact (ih rfl).wrap fun next nextTyped ↦ .inr nextTyped | matchSum scrutineeTyped leftTyped rightTyped ihs ihl ihr => cases hcontext rename_i scrutinee leftTy rightTy left result right rw [MeasurableActionFamily.reduce_matchSum_eq] by_cases scrutineeValue : scrutinee.isValue = true · simp only [scrutineeValue, ↓reduceIte] rcases typed_sum_value scrutineeTyped scrutineeValue with sum | sum · rcases sum with ⟨value, rfl, valueTyped⟩ simpa using ActionTyped.next (typed_substHead leftTyped valueTyped) · rcases sum with ⟨value, rfl, valueTyped⟩ simpa using ActionTyped.next (typed_substHead rightTyped valueTyped) · simp only [scrutineeValue] exact (ihs rfl).wrap fun next nextTyped ↦ .matchSum nextTyped leftTyped rightTyped | nil => rw [reduce]; exact .next .nil | cons headTyped tailTyped ihh iht => cases hcontext rw [reduce] split · split · exact .next (.cons headTyped tailTyped) · exact (iht rfl).wrap fun next nextTyped ↦ .cons headTyped nextTyped · exact (ihh rfl).wrap fun next nextTyped ↦ .cons nextTyped tailTyped | matchList scrutineeTyped nilTyped consTyped ihs ihn ihc => cases hcontext rename_i scrutinee element nilCase result consCase rw [MeasurableActionFamily.reduce_matchList_eq] by_cases scrutineeValue : scrutinee.isValue = true · simp only [scrutineeValue, ↓reduceIte] rcases typed_list_value scrutineeTyped scrutineeValue with nil | cons · rw [nil] simpa using ActionTyped.next nilTyped · rcases cons with ⟨head, tail, rfl, headTyped, tailTyped⟩ simpa using ActionTyped.next (typed_substTwo consTyped headTyped tailTyped) · simp only [scrutineeValue] exact (ihs rfl).wrap fun next nextTyped ↦ .matchList nextTyped nilTyped consTyped | ite conditionTyped thenTyped elseTyped ihc iht ihe => cases hcontext rename_i condition thenBranch result elseBranch rw [MeasurableActionFamily.reduce_ite_eq] by_cases conditionValue : condition.isValue = true · simp only [conditionValue, ↓reduceIte] rcases typed_bool_value conditionTyped conditionValue with ⟨result, rfl⟩ cases result · simpa using ActionTyped.next elseTyped · simpa using ActionTyped.next thenTyped · simp only [conditionValue] exact (ihc rfl).wrap fun next nextTyped ↦ .ite nextTyped thenTyped elseTyped | letE valueTyped bodyTyped ihv ihb => cases hcontext rename_i value valueTy body result rw [MeasurableActionFamily.reduce_let_eq] by_cases valueCondition : value.isValue = true · simp only [valueCondition, ↓reduceIte] exact .next (typed_substHead bodyTyped valueTyped) · simp only [valueCondition] exact (ihv rfl).wrap fun next nextTyped ↦ .letE nextTyped bodyTyped | sub valueTyped h ih => cases hcontext exact (ih rfl).sub h | neg valueTyped ih => cases hcontext rename_i value affinity rw [MeasurableActionFamily.reduce_neg_eq] by_cases valueCondition : value.isValue = true · simp only [valueCondition, ↓reduceIte] rcases typed_real_value valueTyped valueCondition with ⟨coordinate, rfl⟩ simpa using ActionTyped.next (Typed.real (value := -coordinate)) · simp only [valueCondition] exact (ih rfl).wrap fun next nextTyped ↦ .neg nextTyped | add leftTyped rightTyped ihl ihr => cases hcontext rename_i left affinity right rw [MeasurableActionFamily.reduce_add_eq] by_cases leftValue : left.isValue = true · simp only [leftValue, ↓reduceIte] by_cases rightValue : right.isValue = true · simp only [rightValue, ↓reduceIte] rcases typed_real_value leftTyped leftValue with ⟨left, rfl⟩ rcases typed_real_value rightTyped rightValue with ⟨right, rfl⟩ exact .next .real · simp only [rightValue] exact (ihr rfl).wrap fun next nextTyped ↦ .add leftTyped nextTyped · simp only [leftValue] exact (ihl rfl).wrap fun next nextTyped ↦ .add nextTyped rightTyped | mul leftTyped rightTyped ihl ihr => cases hcontext rename_i left right affinity rw [MeasurableActionFamily.reduce_mul_eq] by_cases leftValue : left.isValue = true · simp only [leftValue, ↓reduceIte] by_cases rightValue : right.isValue = true · simp only [rightValue, ↓reduceIte] rcases typed_real_value leftTyped leftValue with ⟨left, rfl⟩ rcases typed_real_value rightTyped rightValue with ⟨right, rfl⟩ exact .next .real · simp only [rightValue] exact (ihr rfl).wrap fun next nextTyped ↦ .mul leftTyped nextTyped · simp only [leftValue] exact (ihl rfl).wrap fun next nextTyped ↦ .mul nextTyped rightTyped | div leftTyped rightTyped ihl ihr => cases hcontext rename_i left affinity right rw [MeasurableActionFamily.reduce_div_eq] by_cases leftValue : left.isValue = true · simp only [leftValue, ↓reduceIte] by_cases rightValue : right.isValue = true · simp only [rightValue, ↓reduceIte] rcases typed_real_value leftTyped leftValue with ⟨left, rfl⟩ rcases typed_real_value rightTyped rightValue with ⟨right, rfl⟩ by_cases h : right = 0 · simp only [realValue?, h, ↓reduceIte]; exact .stuck · simp only [realValue?, h, ↓reduceIte]; exact .next .real · simp only [rightValue] exact (ihr rfl).wrap fun next nextTyped ↦ .div leftTyped nextTyped · simp only [leftValue] exact (ihl rfl).wrap fun next nextTyped ↦ .div nextTyped rightTyped | lt leftTyped rightTyped ihl ihr => cases hcontext rename_i left right rw [MeasurableActionFamily.reduce_lt_eq] by_cases leftValue : left.isValue = true · simp only [leftValue, ↓reduceIte] by_cases rightValue : right.isValue = true · simp only [rightValue, ↓reduceIte] rcases typed_real_value leftTyped leftValue with ⟨left, rfl⟩ rcases typed_real_value rightTyped rightValue with ⟨right, rfl⟩ exact .next .bool · simp only [rightValue] exact (ihr rfl).wrap fun next nextTyped ↦ .lt leftTyped nextTyped · simp only [leftValue] exact (ihl rfl).wrap fun next nextTyped ↦ .lt nextTyped rightTyped | uniform leftTyped rightTyped ihl ihr | uniformMean leftTyped rightTyped ihl ihr => cases hcontext rename_i left affinity right rw [MeasurableActionFamily.reduce_uniform_eq] by_cases leftValue : left.isValue = true · simp only [leftValue, ↓reduceIte] by_cases rightValue : right.isValue = true · simp only [rightValue, ↓reduceIte] rcases typed_real_value leftTyped leftValue with ⟨left, rfl⟩ rcases typed_real_value rightTyped rightValue with ⟨right, rfl⟩ exact .sample fun value ↦ .real · simp only [rightValue] first | exact (ihr rfl).wrap fun next nextTyped ↦ .uniform leftTyped nextTyped | exact (ihr rfl).wrap fun next nextTyped ↦ .uniformMean leftTyped nextTyped · simp only [leftValue] first | exact (ihl rfl).wrap fun next nextTyped ↦ .uniform nextTyped rightTyped | exact (ihl rfl).wrap fun next nextTyped ↦ .uniformMean nextTyped rightTyped | gaussian leftTyped rightTyped ihl ihr | gaussianMean leftTyped rightTyped ihl ihr => cases hcontext rename_i left affinity right rw [MeasurableActionFamily.reduce_gaussian_eq] by_cases leftValue : left.isValue = true · simp only [leftValue, ↓reduceIte] by_cases rightValue : right.isValue = true · simp only [rightValue, ↓reduceIte] rcases typed_real_value leftTyped leftValue with ⟨left, rfl⟩ rcases typed_real_value rightTyped rightValue with ⟨right, rfl⟩ exact .sample fun value ↦ .real · simp only [rightValue] first | exact (ihr rfl).wrap fun next nextTyped ↦ .gaussian leftTyped nextTyped | exact (ihr rfl).wrap fun next nextTyped ↦ .gaussianMean leftTyped nextTyped · simp only [leftValue] first | exact (ihl rfl).wrap fun next nextTyped ↦ .gaussian nextTyped rightTyped | exact (ihl rfl).wrap fun next nextTyped ↦ .gaussianMean nextTyped rightTyped | poisson valueTyped ih | poissonMean valueTyped ih => cases hcontext rename_i value affinity rw [MeasurableActionFamily.reduce_poisson_eq] by_cases valueCondition : value.isValue = true · simp only [valueCondition, ↓reduceIte] rcases typed_real_value valueTyped valueCondition with ⟨coordinate, rfl⟩ exact .sample fun value ↦ .real · simp only [valueCondition] first | exact (ih rfl).wrap fun next nextTyped ↦ .poisson nextTyped | exact (ih rfl).wrap fun next nextTyped ↦ .poissonMean nextTyped | bernoulli valueTyped ih | bernoulliMean valueTyped ih => cases hcontext rename_i value affinity rw [MeasurableActionFamily.reduce_bernoulli_eq] by_cases valueCondition : value.isValue = true · simp only [valueCondition, ↓reduceIte] rcases typed_real_value valueTyped valueCondition with ⟨coordinate, rfl⟩ exact .sample fun value ↦ .real · simp only [valueCondition] first | exact (ih rfl).wrap fun next nextTyped ↦ .bernoulli nextTyped | exact (ih rfl).wrap fun next nextTyped ↦ .bernoulliMean nextTyped | exponential valueTyped ih | exponentialMean valueTyped ih => cases hcontext rename_i value affinity rw [MeasurableActionFamily.reduce_exponential_eq] by_cases valueCondition : value.isValue = true · simp only [valueCondition, ↓reduceIte] rcases typed_real_value valueTyped valueCondition with ⟨coordinate, rfl⟩ exact .sample fun value ↦ .real · simp only [valueCondition] first | exact (ih rfl).wrap fun next nextTyped ↦ .exponential nextTyped | exact (ih rfl).wrap fun next nextTyped ↦ .exponentialMean nextTyped | beta leftTyped rightTyped ihl ihr | betaMean leftTyped rightTyped ihl ihr => cases hcontext rename_i left right affinity rw [MeasurableActionFamily.reduce_beta_eq] by_cases leftValue : left.isValue = true · simp only [leftValue, ↓reduceIte] by_cases rightValue : right.isValue = true · simp only [rightValue, ↓reduceIte] rcases typed_real_value leftTyped leftValue with ⟨left, rfl⟩ rcases typed_real_value rightTyped rightValue with ⟨right, rfl⟩ exact .sample fun value ↦ .real · simp only [rightValue] first | exact (ihr rfl).wrap fun next nextTyped ↦ .beta leftTyped nextTyped | exact (ihr rfl).wrap fun next nextTyped ↦ .betaMean leftTyped nextTyped · simp only [leftValue] first | exact (ihl rfl).wrap fun next nextTyped ↦ .beta nextTyped rightTyped | exact (ihl rfl).wrap fun next nextTyped ↦ .betaMean nextTyped rightTyped | gamma leftTyped rightTyped ihl ihr | gammaMean leftTyped rightTyped ihl ihr => cases hcontext rename_i left affinity right rw [MeasurableActionFamily.reduce_gamma_eq] by_cases leftValue : left.isValue = true · simp only [leftValue, ↓reduceIte] by_cases rightValue : right.isValue = true · simp only [rightValue, ↓reduceIte] rcases typed_real_value leftTyped leftValue with ⟨left, rfl⟩ rcases typed_real_value rightTyped rightValue with ⟨right, rfl⟩ exact .sample fun value ↦ .real · simp only [rightValue] first | exact (ihr rfl).wrap fun next nextTyped ↦ .gamma leftTyped nextTyped | exact (ihr rfl).wrap fun next nextTyped ↦ .gammaMean leftTyped nextTyped · simp only [leftValue] first | exact (ihl rfl).wrap fun next nextTyped ↦ .gamma nextTyped rightTyped | exact (ihl rfl).wrap fun next nextTyped ↦ .gammaMean nextTyped rightTypedtheorem domainSafeAt_of_value (fuel : Nat) (value : expression.isValue = true) : DomainSafeAt fuel expression := by cases fuel with | zero => trivial | succ fuel => rw [DomainSafeAt, ite_eq_left value]; trivialend Typingend Determinize.Proof.Paper