Source lean/Determinize/Proof/Frontend/Unify.lean
import Determinize.Frontend.Unify/-!# Correctness of shape unification`unify` succeeds exactly when the equations have a unifier (`unify_complete`, `unify_sound`), andthen returns a most general one: every unifier `δ` factors through the result `θ`, as`(θ i).subst δ = δ i` for every variable `i` (`unify_mostGeneral`). In particular `θ` isidempotent. `unify_mgu` collects these facts. Termination is part of the definition.-/namespace Determinize.Proof.Frontendopen Determinize.Frontend/-- `θ` makes the two sides of every equation equal. -/def Unifies (θ : Nat → Shape) (equations : List (Shape × Shape)) : Prop :=  ∀ e ∈ equations, e.1.subst θ = e.2.subst θ/-! ## Substitutions -/theorem Shape.subst_subst (σ τ : Nat → Shape) (s : Shape) :    (s.subst σ).subst τ = s.subst fun i ↦ (σ i).subst τ := by  induction s <;> simp_all [Shape.subst]theorem Shape.subst_congr {σ τ : Nat → Shape} {s : Shape} (h : ∀ i ∈ s.vars, σ i = τ i) :    s.subst σ = s.subst τ := by  induction s <;> simp_all [Shape.subst, Shape.vars]theorem Shape.subst_var (s : Shape) : s.subst .var = s := by  induction s <;> simp_all [Shape.subst]theorem Shape.subst_single_of_not_mem {i : Nat} {s t : Shape} (h : i ∉ s.vars) :    s.subst (Shape.single i t) = s := by  rw [← Shape.subst_var s, Shape.subst_subst]  refine Shape.subst_congr fun j hj ↦ ?_  have : j ≠ i := fun e ↦ h (e ▸ hj)  simp [Shape.single, this, Shape.subst]/-- A variable is no larger than any shape it occurs in, after any substitution. -/theorem Shape.size_le_subst {σ : Nat → Shape} {i : Nat} {t : Shape} (h : i ∈ t.vars) :    (σ i).size ≤ (t.subst σ).size := by  induction t with  | var j => simp only [Shape.vars, Finset.mem_singleton] at h; subst h; rfl  | unit | bool | float => simp [Shape.vars] at h  | prod a b iha ihb | sum a b iha ihb | arr a b iha ihb =>    simp only [Shape.vars, Finset.mem_union] at h    simp only [Shape.subst, Shape.size]    rcases h with h | h    · have := iha h; omega    · have := ihb h; omega  | list a ih =>    simp only [Shape.vars] at h; simp only [Shape.subst, Shape.size]; have := ih h; omega/-- The occurs check: a variable is strictly smaller than any other shape it occurs in. -/theorem Shape.size_lt_subst {σ : Nat → Shape} {i : Nat} {t : Shape} (h : i ∈ t.vars)    (ne : t ≠ .var i) : (σ i).size < (t.subst σ).size := by  cases t with  | var j => simp only [Shape.vars, Finset.mem_singleton] at h; exact absurd (h ▸ rfl) ne  | unit | bool | float => simp [Shape.vars] at h  | prod a b | sum a b | arr a b =>    simp only [Shape.vars, Finset.mem_union] at h    simp only [Shape.subst, Shape.size]    rcases h with h | h    · have := Shape.size_le_subst (σ := σ) h; omega    · have := Shape.size_le_subst (σ := σ) h; omega  | list a => simp only [Shape.vars] at h; simp only [Shape.subst, Shape.size]              have := Shape.size_le_subst (σ := σ) h; omega/-! ## Unifiers -/theorem unifies_nil (θ : Nat → Shape) : Unifies θ [] := by simp [Unifies]theorem unifies_cons {θ : Nat → Shape} {s t : Shape} {rest : List (Shape × Shape)} :    Unifies θ ((s, t) :: rest) ↔ s.subst θ = t.subst θ ∧ Unifies θ rest := by  simp [Unifies]theorem unifies_append {θ : Nat → Shape} {front rest : List (Shape × Shape)} :    Unifies θ (front ++ rest) ↔ Unifies θ front ∧ Unifies θ rest := by  simp only [Unifies, List.mem_append]  exact ⟨fun h ↦ ⟨fun e m ↦ h e (.inl m), fun e m ↦ h e (.inr m)⟩,    fun h e m ↦ m.elim (h.1 e) (h.2 e)⟩theorem unifies_substEquations {θ σ : Nat → Shape} {equations : List (Shape × Shape)} :    Unifies θ (substEquations σ equations) ↔ Unifies (fun i ↦ (σ i).subst θ) equations := by  simp only [Unifies, substEquations, List.forall_mem_map, Shape.subst_subst]theorem unifies_children {s t : Shape} {children : List (Shape × Shape)}    (h : s.children t = some children) (θ : Nat → Shape) :    s.subst θ = t.subst θ ↔ Unifies θ children := by  cases s <;> cases t <;> simp only [Shape.children, Option.some.injEq, reduceCtorEq] at h <;>    subst h <;> simp [Unifies, Shape.subst]theorem not_unifies_children {s t : Shape} (h : s.children t = none)    (hs : ∀ i, s = .var i → False) (ht : ∀ i, t = .var i → False) (θ : Nat → Shape) :    s.subst θ ≠ t.subst θ := by  cases s <;> cases t <;> simp_all [Shape.children, Shape.subst]/-- A unifier of `i = t` is unchanged by first substituting `t` for `i`. -/theorem single_absorbed {δ : Nat → Shape} {i : Nat} {t : Shape} (h : δ i = t.subst δ) (j : Nat) :    (Shape.single i t j).subst δ = δ j := by  by_cases e : j = i  · subst e; simp [Shape.single, h]  · simp [Shape.single, e, Shape.subst]/-- Both orientations of the equation between a variable and a shape. -/theorem unifies_var_cons {θ : Nat → Shape} {i : Nat} {t : Shape} {rest : List (Shape × Shape)} :    Unifies θ ((t, .var i) :: rest) ↔ Unifies θ ((.var i, t) :: rest) := by  simp only [unifies_cons, eq_comm]/-! ## The algorithm -//-- The elimination step: a most general unifier of the substituted equations, composed withthe substitution of `t` for `i`, is one of the original equations. -/private theorem eliminate_sound {i : Nat} {t : Shape} {rest : List (Shape × Shape)}    (fresh : i ∉ t.vars) {θ : Nat → Shape} (h : Unifies θ (substEquations (.single i t) rest)) :    Unifies (fun j ↦ (Shape.single i t j).subst θ) ((.var i, t) :: rest) := by  refine unifies_cons.2 ⟨?_, unifies_substEquations.1 h⟩  change (Shape.single i t i).subst θ = t.subst fun j ↦ (Shape.single i t j).subst θ  rw [← Shape.subst_subst, Shape.subst_single_of_not_mem fresh, Shape.single, ite_eq_left rfl]theorem unify_sound {equations : List (Shape × Shape)} {θ : Nat → Shape}    (h : unify equations = some θ) : Unifies θ equations := by  induction equations using unify.induct generalizing θ with  | case1 => simp only [unify, Option.some.injEq] at h; subst h; exact unifies_nil _  | case2 i rest ih | case5 i rest _ ih =>    rw [unify.eq_2, ite_eq_left rfl] at h    exact unifies_cons.2 ⟨rfl, ih h⟩  | case3 i t rest ne occurs =>    rw [unify.eq_2, ite_eq_right ne, ite_eq_left occurs] at h; cases h  | case4 i t rest ne fresh ih =>    rw [unify.eq_2, ite_eq_right ne, ite_eq_right fresh] at h    obtain ⟨θ', h', rfl⟩ := Option.map_eq_some_iff.1 h    exact eliminate_sound fresh (ih h')  | case6 t i rest notVar ne occurs =>    rw [unify.eq_3 _ _ _ notVar, ite_eq_right ne, ite_eq_left occurs] at h; cases h  | case7 t i rest notVar ne fresh ih =>    rw [unify.eq_3 _ _ _ notVar, ite_eq_right ne, ite_eq_right fresh] at h    obtain ⟨θ', h', rfl⟩ := Option.map_eq_some_iff.1 h    exact unifies_var_cons.2 (eliminate_sound fresh (ih h'))  | case8 s t rest hs ht children eq ih =>    rw [unify.eq_4 _ _ _ hs ht, eq] at h    obtain ⟨front, back⟩ := unifies_append.1 (ih h)    exact unifies_cons.2 ⟨(unifies_children eq θ).2 front, back⟩  | case9 s t rest hs ht eq =>    rw [unify.eq_4 _ _ _ hs ht, eq] at h; cases h/-- A unifier of the equations also unifies them after the elimination of `i`. -/private theorem eliminate_preserves {δ : Nat → Shape} {i : Nat} {t : Shape}    {rest : List (Shape × Shape)} (h : Unifies δ ((.var i, t) :: rest)) :    Unifies δ (substEquations (.single i t) rest) := by  obtain ⟨head, rest⟩ := unifies_cons.1 h  refine unifies_substEquations.2 ?_  rwa [funext (single_absorbed head)]/-- Every unifier `δ` factors through the result `θ` of `unify`: applying `θ` first and then `δ`is the same as applying `δ`. -/theorem unify_mostGeneral {equations : List (Shape × Shape)} {θ δ : Nat → Shape}    (h : unify equations = some θ) (hδ : Unifies δ equations) : ∀ i, (θ i).subst δ = δ i := by  induction equations using unify.induct generalizing θ with  | case1 => simp only [unify, Option.some.injEq] at h; subst h; intro i; rfl  | case2 i rest ih | case5 i rest _ ih =>    rw [unify.eq_2, ite_eq_left rfl] at h    exact ih h (unifies_cons.1 hδ).2  | case3 i t rest ne occurs =>    rw [unify.eq_2, ite_eq_right ne, ite_eq_left occurs] at h; cases h  | case4 i t rest ne fresh ih =>    rw [unify.eq_2, ite_eq_right ne, ite_eq_right fresh] at h    obtain ⟨θ', h', rfl⟩ := Option.map_eq_some_iff.1 h    intro j    rw [Shape.subst_subst, funext (ih h' (eliminate_preserves hδ))]    exact single_absorbed (unifies_cons.1 hδ).1 j  | case6 t i rest notVar ne occurs =>    rw [unify.eq_3 _ _ _ notVar, ite_eq_right ne, ite_eq_left occurs] at h; cases h  | case7 t i rest notVar ne fresh ih =>    rw [unify.eq_3 _ _ _ notVar, ite_eq_right ne, ite_eq_right fresh] at h    obtain ⟨θ', h', rfl⟩ := Option.map_eq_some_iff.1 h    have hδ := unifies_var_cons.1 hδ    intro j    rw [Shape.subst_subst, funext (ih h' (eliminate_preserves hδ))]    exact single_absorbed (unifies_cons.1 hδ).1 j  | case8 s t rest hs ht children eq ih =>    rw [unify.eq_4 _ _ _ hs ht, eq] at h    obtain ⟨head, rest⟩ := unifies_cons.1 hδ    exact ih h (unifies_append.2 ⟨(unifies_children eq δ).1 head, rest⟩)  | case9 s t rest hs ht eq =>    rw [unify.eq_4 _ _ _ hs ht, eq] at h; cases h/-- `unify` succeeds on every equations that have a unifier. -/theorem unify_complete {equations : List (Shape × Shape)} {δ : Nat → Shape}    (hδ : Unifies δ equations) : ∃ θ, unify equations = some θ := by  induction equations using unify.induct with  | case1 => exact ⟨_, unify.eq_1⟩  | case2 i rest ih | case5 i rest _ ih =>    rw [unify.eq_2, ite_eq_left rfl]    exact ih (unifies_cons.1 hδ).2  | case3 i t rest ne occurs =>    exact absurd (unifies_cons.1 hδ).1 fun e ↦ by      have := Shape.size_lt_subst (σ := δ) occurs ne      simp only [Shape.subst] at e; rw [e] at this; exact lt_irrefl _ this  | case4 i t rest ne fresh ih =>    rw [unify.eq_2, ite_eq_right ne, ite_eq_right fresh]    obtain ⟨θ', h'⟩ := ih (eliminate_preserves hδ)    exact ⟨_, by rw [h']; rfl⟩  | case6 t i rest notVar ne occurs =>    exact absurd (unifies_cons.1 (unifies_var_cons.1 hδ)).1 fun e ↦ by      have := Shape.size_lt_subst (σ := δ) occurs ne      simp only [Shape.subst] at e; rw [e] at this; exact lt_irrefl _ this  | case7 t i rest notVar ne fresh ih =>    rw [unify.eq_3 _ _ _ notVar, ite_eq_right ne, ite_eq_right fresh]    obtain ⟨θ', h'⟩ := ih (eliminate_preserves (unifies_var_cons.1 hδ))    exact ⟨_, by rw [h']; rfl⟩  | case8 s t rest hs ht children eq ih =>    rw [unify.eq_4 _ _ _ hs ht, eq]    obtain ⟨head, rest⟩ := unifies_cons.1 hδ    exact ih (unifies_append.2 ⟨(unifies_children eq δ).1 head, rest⟩)  | case9 s t rest hs ht eq =>    exact absurd (unifies_cons.1 hδ).1 (not_unifies_children eq hs ht δ)/-- The result of `unify` is idempotent. -/theorem unify_idempotent {equations : List (Shape × Shape)} {θ : Nat → Shape}    (h : unify equations = some θ) (i : Nat) : (θ i).subst θ = θ i :=  unify_mostGeneral h (unify_sound h) i/-- `unify` fails only on equations without a unifier. -/theorem unify_eq_none {equations : List (Shape × Shape)} (h : unify equations = none)    (δ : Nat → Shape) : ¬ Unifies δ equations := fun hδ ↦ by  obtain ⟨θ, h'⟩ := unify_complete hδ  rw [h] at h'; cases h'/-- The most general unifier theorem: `unify` succeeds exactly on the equations that have aunifier, and every unifier factors through its result. -/theorem unify_mgu (equations : List (Shape × Shape)) :    ((∃ δ, Unifies δ equations) ↔ ∃ θ, unify equations = some θ) ∧      ∀ θ, unify equations = some θ →        Unifies θ equations ∧ ∀ δ, Unifies δ equations → ∀ i, (θ i).subst δ = δ i :=  ⟨⟨fun ⟨_, hδ⟩ ↦ unify_complete hδ, fun ⟨θ, h⟩ ↦ ⟨θ, unify_sound h⟩⟩,    fun _ h ↦ ⟨unify_sound h, fun _ hδ ↦ unify_mostGeneral h hδ⟩⟩end Determinize.Proof.Frontend