Source lean/Determinize/Proof/Frontend/Soundness.lean
import Determinize.Proof.Frontend.Groundimport Determinize.Proof.Frontend.Typing/-!# Soundness of generation (Lemma S)Every ground substitution that solves the subtyping constraints of a draft types its read-backprogram at the instance of the draft's type, and the read-back program fills exactly the omittedaffinities of the input. Each cast becomes one subsumption step.-/namespace Determinize.Proof.Frontendopen Determinize.Frontend Spec.Paper Ground/-- Lemma S. -/theorem generate_sound (σ : Ground) : ∀ (e : Input) (Γ : List UType) (n : Nat) (d : Draft)    (n' : Nat), (generate Γ e).run n = .ok (d, n') → σ.Solves d.relations →      e.Matches (d.program σ.affinities) ∧        Typed (Γ.map σ.inst) (interpret (d.program σ.affinities)) (σ.inst d.ty) := by  intro e  induction e with  | bvar i =>    intro Γ n d n' h _    rw [generate] at h    cases hi : Γ[i]? with    | none => simp [hi, throw, throwThe, MonadExceptOf.throw, StateT.run, StateT.lift, bind,        Except.bind] at h    | some t =>      simp only [hi, StateT.run_pure, pure_eq_ok, Prod.mk.injEq] at h      obtain ⟨rfl, rfl⟩ := h      read_back      exact ⟨rfl, .bvar (hasVar_iff.2 (by simp [hi]))⟩  | reject =>    intro Γ n d n' h _    unfold_generate h    obtain ⟨rfl, rfl⟩ := h    read_back    exact ⟨trivial, .reject⟩  | unit =>    intro Γ n d n' h _    unfold_generate h    obtain ⟨rfl, rfl⟩ := h    read_back    exact ⟨trivial, .unit⟩  | bool b =>    intro Γ n d n' h _    unfold_generate h    obtain ⟨rfl, rfl⟩ := h    read_back    exact ⟨rfl, .bool⟩  | real q =>    intro Γ n d n' h _    unfold_generate h    obtain ⟨rfl, rfl⟩ := h    read_back    exact ⟨rfl, .real⟩  | nil =>    intro Γ n d n' h _    unfold_generate h    obtain ⟨rfl, rfl⟩ := h    read_back    exact ⟨trivial, .nil⟩  | lam b ih =>    intro Γ n d n' h hσ    unfold_generate h    obtain ⟨⟨db, n₁⟩, hb, rfl, rfl⟩ := h    relations at hσ    obtain ⟨mb, tb⟩ := ih _ _ _ _ hb hσ    read_back    exact ⟨mb, .lam tb⟩  | fix b ih =>    intro Γ n d n' h hσ    unfold_generate h    obtain ⟨⟨db, n₁⟩, hb, rfl, rfl⟩ := h    relations at hσ    obtain ⟨sb, hσb⟩ := hσ    obtain ⟨mb, tb⟩ := ih _ _ _ _ hb hσb    read_back    exact ⟨mb, .fix (tb.sub sb)⟩  | app f x ihf ihx =>    intro Γ n d n' h hσ    unfold_generate h    obtain ⟨⟨df, n₁⟩, hf, ⟨dx, n₂⟩, hx, rfl, rfl⟩ := h    relations at hσ    obtain ⟨⟨sf, hσf⟩, sx, hσx⟩ := hσ    obtain ⟨mf, tf⟩ := ihf _ _ _ _ hf hσf    obtain ⟨mx, tx⟩ := ihx _ _ _ _ hx hσx    read_back    exact ⟨⟨mf, mx⟩, .app (tf.sub sf) (tx.sub sx)⟩  | pair a b iha ihb =>    intro Γ n d n' h hσ    unfold_generate h    obtain ⟨⟨da, n₁⟩, ha, ⟨db, n₂⟩, hb, rfl, rfl⟩ := h    relations at hσ    obtain ⟨hσa, hσb⟩ := hσ    obtain ⟨ma, ta⟩ := iha _ _ _ _ ha hσa    obtain ⟨mb, tb⟩ := ihb _ _ _ _ hb hσb    read_back    exact ⟨⟨ma, mb⟩, .pair ta tb⟩  | fst p ih =>    intro Γ n d n' h hσ    unfold_generate h    obtain ⟨⟨dp, n₁⟩, hp, rfl, rfl⟩ := h    relations at hσ    obtain ⟨sp, hσp⟩ := hσ    obtain ⟨mp, tp⟩ := ih _ _ _ _ hp hσp    read_back    exact ⟨mp, .fst (tp.sub sp)⟩  | snd p ih =>    intro Γ n d n' h hσ    unfold_generate h    obtain ⟨⟨dp, n₁⟩, hp, rfl, rfl⟩ := h    relations at hσ    obtain ⟨sp, hσp⟩ := hσ    obtain ⟨mp, tp⟩ := ih _ _ _ _ hp hσp    read_back    exact ⟨mp, .snd (tp.sub sp)⟩  | inl v ih =>    intro Γ n d n' h hσ    unfold_generate h    obtain ⟨⟨dv, n₁⟩, hv, rfl, rfl⟩ := h    relations at hσ    obtain ⟨mv, tv⟩ := ih _ _ _ _ hv hσ    read_back    exact ⟨mv, .inl tv⟩  | inr v ih =>    intro Γ n d n' h hσ    unfold_generate h    obtain ⟨⟨dv, n₁⟩, hv, rfl, rfl⟩ := h    relations at hσ    obtain ⟨mv, tv⟩ := ih _ _ _ _ hv hσ    read_back    exact ⟨mv, .inr tv⟩  | matchSum s a b ihs iha ihb =>    intro Γ n d n' h hσ    unfold_generate h    obtain ⟨⟨ds, n₁⟩, hs, ⟨da, n₂⟩, ha, ⟨db, n₃⟩, hb, rfl, rfl⟩ := h    relations at hσ    obtain ⟨⟨ss, hσs⟩, ⟨sa, hσa⟩, sb, hσb⟩ := hσ    obtain ⟨ms, ts⟩ := ihs _ _ _ _ hs hσs    obtain ⟨ma, ta⟩ := iha _ _ _ _ ha hσa    obtain ⟨mb, tb⟩ := ihb _ _ _ _ hb hσb    read_back    exact ⟨⟨ms, ma, mb⟩, .matchSum (ts.sub ss) (ta.sub sa) (tb.sub sb)⟩  | cons hd tl ihh iht =>    intro Γ n d n' h hσ    unfold_generate h    obtain ⟨⟨dh, n₁⟩, hh, ⟨dt, n₂⟩, ht, rfl, rfl⟩ := h    relations at hσ    obtain ⟨⟨sh, hσh⟩, st, hσt⟩ := hσ    obtain ⟨mh, th⟩ := ihh _ _ _ _ hh hσh    obtain ⟨mt, tt⟩ := iht _ _ _ _ ht hσt    read_back    exact ⟨⟨mh, mt⟩, .cons (th.sub sh) (tt.sub st)⟩  | matchList s nc cc ihs ihn ihc =>    intro Γ n d n' h hσ    unfold_generate h    obtain ⟨⟨ds, n₁⟩, hs, ⟨dn, n₂⟩, hn, ⟨dc, n₃⟩, hc, rfl, rfl⟩ := h    relations at hσ    obtain ⟨⟨ss, hσs⟩, ⟨sn, hσn⟩, sc, hσc⟩ := hσ    obtain ⟨ms, ts⟩ := ihs _ _ _ _ hs hσs    obtain ⟨mn, tn⟩ := ihn _ _ _ _ hn hσn    obtain ⟨mc, tc⟩ := ihc _ _ _ _ hc hσc    read_back    exact ⟨⟨ms, mn, mc⟩, .matchList (ts.sub ss) (tn.sub sn) (tc.sub sc)⟩  | ite c a b ihc iha ihb =>    intro Γ n d n' h hσ    unfold_generate h    obtain ⟨⟨dc, n₁⟩, hc, ⟨da, n₂⟩, ha, ⟨db, n₃⟩, hb, rfl, rfl⟩ := h    relations at hσ    obtain ⟨⟨sc, hσc⟩, ⟨sa, hσa⟩, sb, hσb⟩ := hσ    obtain ⟨mc, tc⟩ := ihc _ _ _ _ hc hσc    obtain ⟨ma, ta⟩ := iha _ _ _ _ ha hσa    obtain ⟨mb, tb⟩ := ihb _ _ _ _ hb hσb    read_back    exact ⟨⟨mc, ma, mb⟩, .ite (tc.sub sc) (ta.sub sa) (tb.sub sb)⟩  | letE v b ihv ihb =>    intro Γ n d n' h hσ    unfold_generate h    obtain ⟨⟨dv, n₁⟩, hv, ⟨db, n₂⟩, hb, rfl, rfl⟩ := h    relations at hσ    obtain ⟨hσv, hσb⟩ := hσ    obtain ⟨mv, tv⟩ := ihv _ _ _ _ hv hσv    obtain ⟨mb, tb⟩ := ihb _ _ _ _ hb hσb    read_back    exact ⟨⟨mv, mb⟩, .letE tv tb⟩  | neg b ih =>    intro Γ n d n' h hσ    unfold_generate h    obtain ⟨⟨db, n₁⟩, hb, rfl, rfl⟩ := h    relations at hσ    obtain ⟨sb, hσb⟩ := hσ    obtain ⟨mb, tb⟩ := ih _ _ _ _ hb hσb    read_back    exact ⟨mb, .neg (tb.sub sb)⟩  | add a b iha ihb =>    intro Γ n d n' h hσ    unfold_generate h    obtain ⟨⟨da, n₁⟩, ha, ⟨db, n₂⟩, hb, rfl, rfl⟩ := h    relations at hσ    obtain ⟨⟨sa, hσa⟩, sb, hσb⟩ := hσ    obtain ⟨ma, ta⟩ := iha _ _ _ _ ha hσa    obtain ⟨mb, tb⟩ := ihb _ _ _ _ hb hσb    read_back    exact ⟨⟨ma, mb⟩, .add (ta.sub sa) (tb.sub sb)⟩  | mul a b iha ihb =>    intro Γ n d n' h hσ    unfold_generate h    obtain ⟨⟨da, n₁⟩, ha, ⟨db, n₂⟩, hb, rfl, rfl⟩ := h    relations at hσ    obtain ⟨⟨sa, hσa⟩, sb, hσb⟩ := hσ    obtain ⟨ma, ta⟩ := iha _ _ _ _ ha hσa    obtain ⟨mb, tb⟩ := ihb _ _ _ _ hb hσb    read_back    exact ⟨⟨ma, mb⟩, .mul (ta.sub sa) (tb.sub sb)⟩  | div a b iha ihb =>    intro Γ n d n' h hσ    unfold_generate h    obtain ⟨⟨da, n₁⟩, ha, ⟨db, n₂⟩, hb, rfl, rfl⟩ := h    relations at hσ    obtain ⟨⟨sa, hσa⟩, sb, hσb⟩ := hσ    obtain ⟨ma, ta⟩ := iha _ _ _ _ ha hσa    obtain ⟨mb, tb⟩ := ihb _ _ _ _ hb hσb    read_back    exact ⟨⟨ma, mb⟩, .div (ta.sub sa) (tb.sub sb)⟩  | lt a b iha ihb =>    intro Γ n d n' h hσ    unfold_generate h    obtain ⟨⟨da, n₁⟩, ha, ⟨db, n₂⟩, hb, rfl, rfl⟩ := h    relations at hσ    obtain ⟨⟨sa, hσa⟩, sb, hσb⟩ := hσ    obtain ⟨ma, ta⟩ := iha _ _ _ _ ha hσa    obtain ⟨mb, tb⟩ := ihb _ _ _ _ hb hσb    read_back    exact ⟨⟨ma, mb⟩, .lt (ta.sub sa) (tb.sub sb)⟩  | uniform r a b iha ihb =>    intro Γ n d n' h hσ    cases r <;>    · unfold_generate h      obtain ⟨⟨da, n₁⟩, ha, ⟨db, n₂⟩, hb, rfl, rfl⟩ := h      relations at hσ      obtain ⟨⟨sa, hσa⟩, sb, hσb⟩ := hσ      obtain ⟨ma, ta⟩ := iha _ _ _ _ ha hσa      obtain ⟨mb, tb⟩ := ihb _ _ _ _ hb hσb      read_back      exact ⟨⟨by simp [UType.affinity, AffinityTerm.eval], ma, mb⟩,        .uniform (ta.sub sa) (tb.sub sb)⟩  | gaussian r a b iha ihb =>    intro Γ n d n' h hσ    cases r <;>    · unfold_generate h      obtain ⟨⟨da, n₁⟩, ha, ⟨db, n₂⟩, hb, rfl, rfl⟩ := h      relations at hσ      obtain ⟨⟨sa, hσa⟩, sb, hσb⟩ := hσ      obtain ⟨ma, ta⟩ := iha _ _ _ _ ha hσa      obtain ⟨mb, tb⟩ := ihb _ _ _ _ hb hσb      read_back      exact ⟨⟨by simp [UType.affinity, AffinityTerm.eval], ma, mb⟩,        .gaussian (ta.sub sa) (tb.sub sb)⟩  | beta r a b iha ihb =>    intro Γ n d n' h hσ    cases r <;>    · unfold_generate h      obtain ⟨⟨da, n₁⟩, ha, ⟨db, n₂⟩, hb, rfl, rfl⟩ := h      relations at hσ      obtain ⟨⟨sa, hσa⟩, sb, hσb⟩ := hσ      obtain ⟨ma, ta⟩ := iha _ _ _ _ ha hσa      obtain ⟨mb, tb⟩ := ihb _ _ _ _ hb hσb      read_back      exact ⟨⟨by simp [UType.affinity, AffinityTerm.eval], ma, mb⟩,        .beta (ta.sub sa) (tb.sub sb)⟩  | gamma r a b iha ihb =>    intro Γ n d n' h hσ    cases r <;>    · unfold_generate h      obtain ⟨⟨da, n₁⟩, ha, ⟨db, n₂⟩, hb, rfl, rfl⟩ := h      relations at hσ      obtain ⟨⟨sa, hσa⟩, sb, hσb⟩ := hσ      obtain ⟨ma, ta⟩ := iha _ _ _ _ ha hσa      obtain ⟨mb, tb⟩ := ihb _ _ _ _ hb hσb      read_back      exact ⟨⟨by simp [UType.affinity, AffinityTerm.eval], ma, mb⟩,        .gamma (ta.sub sa) (tb.sub sb)⟩  | discrete r p ih =>    intro Γ n d n' h hσ    cases r <;>    · unfold_generate h      obtain ⟨⟨dp, n₁⟩, hp, rfl, rfl⟩ := h      relations at hσ      obtain ⟨sp, hσp⟩ := hσ      obtain ⟨mp, tp⟩ := ih _ _ _ _ hp hσp      read_back      exact ⟨⟨by simp [UType.affinity, AffinityTerm.eval], mp⟩,        .discrete (tp.sub sp)⟩  | poisson r a ih =>    intro Γ n d n' h hσ    cases r <;>    · unfold_generate h      obtain ⟨⟨da, n₁⟩, ha, rfl, rfl⟩ := h      relations at hσ      obtain ⟨sa, hσa⟩ := hσ      obtain ⟨ma, ta⟩ := ih _ _ _ _ ha hσa      read_back      exact ⟨⟨by simp [UType.affinity, AffinityTerm.eval], ma⟩,        .poisson (ta.sub sa)⟩  | bernoulli r a ih =>    intro Γ n d n' h hσ    cases r <;>    · unfold_generate h      obtain ⟨⟨da, n₁⟩, ha, rfl, rfl⟩ := h      relations at hσ      obtain ⟨sa, hσa⟩ := hσ      obtain ⟨ma, ta⟩ := ih _ _ _ _ ha hσa      read_back      exact ⟨⟨by simp [UType.affinity, AffinityTerm.eval], ma⟩,        .bernoulli (ta.sub sa)⟩  | exponential r a ih =>    intro Γ n d n' h hσ    cases r <;>    · unfold_generate h      obtain ⟨⟨da, n₁⟩, ha, rfl, rfl⟩ := h      relations at hσ      obtain ⟨sa, hσa⟩ := hσ      obtain ⟨ma, ta⟩ := ih _ _ _ _ ha hσa      read_back      exact ⟨⟨by simp [UType.affinity, AffinityTerm.eval], ma⟩,        .exponential (ta.sub sa)⟩end Determinize.Proof.Frontend