Source lean/Determinize/Proof/Frontend/Ground.lean
import Determinize.Spec.Inferenceimport Determinize.Frontend.Inferimport Determinize.Proof.Semantics.Subtyping/-!# Ground substitutions for generationThe drafts that `generate` produces have types over type variables and affinity variables. A`Ground` substitution replaces all of them; `Solves` says that it satisfies every subtypingconstraint of a draft. Lemma S (`Proof/Frontend/Soundness.lean`) types the read-back programunder every solution, and Lemma C (`Proof/Frontend/Completeness.lean`) builds a solution from atyped completion.Generation draws fresh variables from a counter, so Lemma C extends a substitution on thevariables at or above the counter, and must know that this does not disturb what is alreadyestablished. `Agree n σ σ'` says that two substitutions agree on the variables below `n`, and`Robust n σ P` that `P` holds for every substitution that agrees with `σ` below `n`.The file also collects the monad lemmas for unfolding `generate`, and shows that the read-backprogram is monotone in the affinities (`program_le`).-/namespace Determinize.Proof.Frontendopen Determinize.Frontend Spec Spec.Paper/-! ## Unfolding `generate` -/theorem bind_eq_ok {ε α β : Type} {x : Except ε α} {f : α → Except ε β} {b : β} :    x >>= f = .ok b ↔ ∃ a, x = .ok a ∧ f a = .ok b := by  cases x <;> simp [bind, Except.bind]theorem ok_bind {ε α β : Type} {a : α} {f : α → Except ε β} :    (Except.ok a : Except ε α) >>= f = f a := rfltheorem pure_eq_ok {ε α : Type} {a b : α} : (pure a : Except ε α) = .ok b ↔ a = b := by  simp [pure, Except.pure]/-- Unfold one call of `generate` in a hypothesis `(generate Γ e).run n = .ok (d, n')` into thesuccessful runs of its steps. -/macro "unfold_generate" h:ident : tactic => `(tactic| (  rw [generate] at $h:ident  simp only [site, StateT.run_bind, StateT.run_pure, fresh, freshFloat, StateT.run_modifyGet,    pure_bind, bind_eq_ok, pure_eq_ok, Prod.mk.injEq] at $h:ident))/-- Unfold one call of `generate` in a goal `(generate Γ e).run n = …`, keeping `site`. -/macro "unfold_generate" : tactic => `(tactic| (  rw [generate]  simp only [StateT.run_bind, StateT.run_pure, fresh, freshFloat, StateT.run_modifyGet,    pure_bind]))/-! ## Ground substitutions -//-- A type for every type variable and an affinity for every affinity variable. -/structure Ground where  types : Nat → Ty  affinities : AffinityVar → Affinitynamespace Grounddef inst (σ : Ground) (u : UType) : Ty := u.instantiate σ.types σ.affinities/-- `σ` makes the first type of every relation a subtype of the second. -/def Solves (σ : Ground) (relations : List (UType × UType)) : Prop :=  ∀ p ∈ relations, Ty.Sub (σ.inst p.1) (σ.inst p.2)theorem solves_nil (σ : Ground) : σ.Solves [] := fun _ h ↦ nomatch htheorem solves_cons {σ : Ground} {p : UType × UType} {rest : List (UType × UType)} :    σ.Solves (p :: rest) ↔ Ty.Sub (σ.inst p.1) (σ.inst p.2) ∧ σ.Solves rest := by  simp [Solves]theorem solves_append {σ : Ground} {front rest : List (UType × UType)} :    σ.Solves (front ++ rest) ↔ σ.Solves front ∧ σ.Solves rest := by  simp only [Solves, List.mem_append]  exact ⟨fun h ↦ ⟨fun c m ↦ h c (.inl m), fun c m ↦ h c (.inr m)⟩,    fun h c m ↦ m.elim (h.1 c) (h.2 c)⟩@[simp] theorem inst_var (σ : Ground) (i : Nat) : σ.inst (.var i) = σ.types i := rfl@[simp] theorem inst_unit (σ : Ground) : σ.inst .unit = .unit := rfl@[simp] theorem inst_bool (σ : Ground) : σ.inst .bool = .bool := rfl@[simp] theorem inst_float (σ : Ground) (a : AffinityTerm AffinityVar) :    σ.inst (.float a) = .float (a.eval σ.affinities) := rfl@[simp] theorem inst_prod (σ : Ground) (a b : UType) :    σ.inst (.prod a b) = .prod (σ.inst a) (σ.inst b) := rfl@[simp] theorem inst_sum (σ : Ground) (a b : UType) :    σ.inst (.sum a b) = .sum (σ.inst a) (σ.inst b) := rfl@[simp] theorem inst_list (σ : Ground) (a : UType) : σ.inst (.list a) = .list (σ.inst a) := rfl@[simp] theorem inst_arr (σ : Ground) (a b : UType) :    σ.inst (.arr a b) = .arr (σ.inst a) (σ.inst b) := rfl@[simp] theorem inst_general (σ : Ground) : σ.inst general = .float .G := rfldef setType (σ : Ground) (i : Nat) (A : Ty) : Ground :=  ⟨Function.update σ.types i A, σ.affinities⟩def setAffinity (σ : Ground) (i : Nat) (m : Affinity) : Ground :=  ⟨σ.types, Function.update σ.affinities (.generated i) m⟩/-- `σ` and `σ'` agree on the type variables and generated affinity variables below `n`. -/def Agree (n : Nat) (σ σ' : Ground) : Prop :=  ∀ i < n, σ'.types i = σ.types i ∧ σ'.affinities (.generated i) = σ.affinities (.generated i)theorem Agree.refl (n : Nat) (σ : Ground) : σ.Agree n σ := fun _ _ ↦ ⟨rfl, rfl⟩theorem Agree.type {n : Nat} {σ σ' : Ground} (h : σ.Agree n σ') {i : Nat} (hi : i < n) :    σ'.types i = σ.types i := (h i hi).1theorem Agree.affinity {n : Nat} {σ σ' : Ground} (h : σ.Agree n σ') {i : Nat} (hi : i < n) :    σ'.affinities (.generated i) = σ.affinities (.generated i) := (h i hi).2/-- Agreement below `n` followed by agreement below a larger `n₁`. -/theorem Agree.step {n n₁ : Nat} {σ σ₁ σ' : Ground} (a : σ.Agree n σ₁) (h : σ₁.Agree n₁ σ')    (le : n ≤ n₁) : σ.Agree n σ' := fun i hi ↦  ⟨(h.type (by omega)).trans (a.type hi), (h.affinity (by omega)).trans (a.affinity hi)⟩theorem Agree.setType {n i : Nat} {σ σ' : Ground} (h : σ.Agree n σ') (hi : n ≤ i) (A : Ty) :    σ.Agree n (σ'.setType i A) := fun j hj ↦ by  have : j ≠ i := by omega  simpa [Ground.setType, Function.update_of_ne this] using h j hjtheorem Agree.setAffinity {n i : Nat} {σ σ' : Ground} (h : σ.Agree n σ') (hi : n ≤ i)    (m : Affinity) : σ.Agree n (σ'.setAffinity i m) := fun j hj ↦ by  have : AffinityVar.generated j ≠ .generated i := by simp; omega  simpa [Ground.setAffinity, Function.update_of_ne this] using h j hj@[simp] theorem setType_types (σ : Ground) (i : Nat) (A : Ty) (j : Nat) :    (σ.setType i A).types j = if j = i then A else σ.types j := by  simp [Ground.setType, Function.update_apply]@[simp] theorem setType_affinities (σ : Ground) (i : Nat) (A : Ty) :    (σ.setType i A).affinities = σ.affinities := rfl@[simp] theorem setAffinity_types (σ : Ground) (i : Nat) (m : Affinity) :    (σ.setAffinity i m).types = σ.types := rfl@[simp] theorem setAffinity_generated (σ : Ground) (i : Nat) (m : Affinity) (j : Nat) :    (σ.setAffinity i m).affinities (.generated j) =      if j = i then m else σ.affinities (.generated j) := by  simp [Ground.setAffinity, Function.update_apply]end Groundopen Ground/-- Split the relations of a draft node into those of its children and casts, and instantiatethe cast types. -/syntax "relations" (Lean.Parser.Tactic.location)? : tacticmacro_rules  | `(tactic| relations $[$loc]?) => `(tactic|    simp only [Draft.relations, List.flatMap_cons, List.flatMap_nil, List.append_nil, solves_cons,      solves_append, solves_nil, Draft.ty, inst_var, inst_unit, inst_bool, inst_float, inst_prod,      inst_sum, inst_list, inst_arr, inst_general, AffinityTerm.eval] $[$loc]?)/-- The read-back of a draft node. -/macro "read_back" : tactic => `(tactic|  simp only [Draft.program, List.map, Draft.rebuild, Draft.ty])/-- `P` holds for every substitution that agrees with `σ` below `n`. -/def Robust (n : Nat) (σ : Ground) (P : Ground → Prop) : Prop := ∀ σ', σ.Agree n σ' → P σ'theorem Robust.extend {n n₁ : Nat} {σ σ₁ : Ground} {P : Ground → Prop} (h : Robust n σ P)    (a : σ.Agree n σ₁) (le : n ≤ n₁) : Robust n₁ σ₁ P :=  fun σ' h' ↦ h σ' (a.step h' le)/-- The instances of a context are pointwise subtypes of `Γ'`. -/def Context (Γ : List UType) (Γ' : List Ty) (σ : Ground) : Prop :=  List.Forall₂ Ty.Sub (Γ.map σ.inst) Γ'theorem Robust.cons {n : Nat} {σ : Ground} {Γ : List UType} {Γ' : List Ty} {t : UType} {A : Ty}    (hΓ : Robust n σ (Context Γ Γ')) (ht : Robust n σ fun σ' ↦ Ty.Sub (σ'.inst t) A) :    Robust n σ (Context (t :: Γ) (A :: Γ')) :=  fun σ' h ↦ List.Forall₂.cons (ht σ' h) (hΓ σ' h)/-- A variable of a context is found in the corresponding position. -/theorem context_getElem? {Γ : List UType} {Γ' : List Ty} {σ : Ground} (h : Context Γ Γ' σ)    {i : Nat} {A : Ty} (hA : Γ'[i]? = some A) : ∃ t, Γ[i]? = some t ∧ Ty.Sub (σ.inst t) A := by  induction Γ generalizing Γ' i with  | nil => cases h; simp at hA  | cons t Γ ih =>    change List.Forall₂ _ (σ.inst t :: Γ.map σ.inst) Γ' at h    cases h with    | cons head rest =>      cases i with      | zero =>        simp only [List.getElem?_cons_zero, Option.some.injEq] at hA        subst hA        exact ⟨t, rfl, head⟩      | succ i => exact ih rest (by simpa using hA)/-! ## Monotonicity of read-back -//-- Induction on drafts, with a hypothesis for every child of a node. -/theorem Draft.induction {P : Draft → Prop}    (node : ∀ e t children, (∀ c ∈ children, P c) → P (.node e t children))    (cast : ∀ body t, P body → P (.cast body t)) (d : Draft) : P d :=  Draft.rec (motive_1 := P) (motive_2 := fun children ↦ ∀ c ∈ children, P c)    (fun e t children ih ↦ node e t children ih) (fun body t ih ↦ cast body t ih)    (fun _ h ↦ nomatch h)    (fun _ _ head tail c h ↦ (List.mem_cons.1 h).elim (· ▸ head) (tail c)) dtheorem affinity_le {ρ ρ' : AffinityVar → Affinity}    (h : ∀ v, Ty.Sub (.float (ρ v)) (.float (ρ' v))) (t : UType) :    Ty.Sub (.float (t.affinity ρ)) (.float (t.affinity ρ')) := by  cases t with  | float a => cases a with    | var v => exact h v    | fixed m => exact .refl _  | _ => exact .refl _theorem rebuild_le (e : Input) {m m' : Affinity} (hm : Ty.Sub (.float m) (.float m'))    {children children' : List Annotated} (h : List.Forall₂ AffinityLE children children') :    AffinityLE (Draft.rebuild e m children) (Draft.rebuild e m' children') := by  unfold AffinityLE at *  match h with  | .nil => cases e <;> simp [Draft.rebuild, Expr.Sitewise]  | .cons ha .nil => cases e <;> simp [Draft.rebuild, Expr.Sitewise, ha, hm]  | .cons ha (.cons hb .nil) => cases e <;> simp [Draft.rebuild, Expr.Sitewise, ha, hb, hm]  | .cons ha (.cons hb (.cons hc .nil)) =>    cases e <;> simp [Draft.rebuild, Expr.Sitewise, ha, hb, hc]  | .cons _ (.cons _ (.cons _ (.cons _ _))) => simp [Draft.rebuild, Expr.Sitewise]/-- Read-back is monotone: larger affinities give a larger program. -/theorem program_le {ρ ρ' : AffinityVar → Affinity}    (h : ∀ v, Ty.Sub (.float (ρ v)) (.float (ρ' v))) (d : Draft) :    AffinityLE (d.program ρ) (d.program ρ') := by  induction d using Draft.induction with  | node e t children ih =>    rw [Draft.program, Draft.program]    refine rebuild_le e (affinity_le h t) ?_    rw [List.forall₂_map_left_iff, List.forall₂_map_right_iff]    exact List.forall₂_same.2 ih  | cast body t ih => rw [Draft.program, Draft.program]; exact ihend Determinize.Proof.Frontend