Source lean/Determinize/Proof/Semantics/Typing.lean
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