Source lean/Determinize/Frontend/Unify.lean
import Mathlib.Data.Finset.Card/-!# Unification of type shapesA shape is a type without its affinities. Structural subtyping relates only types of the sameshape, so inference first unifies the shapes of the two sides of every subtyping constraint.`unify` is Robinson's algorithm. It terminates because every elimination removes a variable fromthe equations and every decomposition makes them smaller. `Proof/Frontend/Unify.lean` proves thatit returns a most general unifier whenever there is a unifier.-/namespace Determinize.Frontendinductive Shape where  | var (index : Nat)  | unit | bool | float  | prod (left right : Shape)  | sum (left right : Shape)  | list (element : Shape)  | arr (argument result : Shape)deriving DecidableEq, Repr, Inhabitednamespace Shape/-- Replace every variable `i` by `σ i`. -/def subst (σ : Nat → Shape) : Shape → Shape  | var i => σ i  | unit => unit  | bool => bool  | float => float  | prod a b => prod (a.subst σ) (b.subst σ)  | sum a b => sum (a.subst σ) (b.subst σ)  | list a => list (a.subst σ)  | arr a b => arr (a.subst σ) (b.subst σ)/-- The substitution of `t` for the variable `i`. -/def single (i : Nat) (t : Shape) (j : Nat) : Shape :=  if j = i then t else var jdef vars : Shape → Finset Nat  | var i => {i}  | unit | bool | float => ∅  | prod a b | sum a b | arr a b => a.vars ∪ b.vars  | list a => a.vars/-- The number of constructors. -/def size : Shape → Nat  | var _ | unit | bool | float => 1  | prod a b | sum a b | arr a b => a.size + b.size + 1  | list a => a.size + 1/-- For two shapes that are not variables, the equations between their children, or `none` iftheir head constructors differ. -/def children : Shape → Shape → Option (List (Shape × Shape))  | unit, unit | bool, bool | float, float => some []  | prod a b, prod c d | sum a b, sum c d | arr a b, arr c d => some [(a, c), (b, d)]  | list a, list b => some [(a, b)]  | _, _ => nonetheorem vars_subst_single {i : Nat} {t : Shape} (fresh : i ∉ t.vars) :    ∀ s : Shape, (s.subst (single i t)).vars ⊆ (s.vars ∪ t.vars).erase i  | var j => by    by_cases h : j = i    · subst h      intro k hk      simp only [subst, single, ite_eq_left] at hk      exact Finset.mem_erase.2 ⟨fun e ↦ fresh (e ▸ hk), Finset.mem_union_right _ hk⟩    · simp [subst, single, h, vars]  | unit | bool | float => by simp [subst, vars]  | prod a b | sum a b | arr a b => by    have ha := vars_subst_single fresh a    have hb := vars_subst_single fresh b    simp only [subst, vars]    intro k hk    rcases Finset.mem_union.1 hk with hk | hk    · have := ha hk; simp only [Finset.mem_erase, Finset.mem_union] at this ⊢; tauto    · have := hb hk; simp only [Finset.mem_erase, Finset.mem_union] at this ⊢; tauto  | list a => by simpa [subst, vars] using vars_subst_single fresh aend Shape/-- Apply a substitution to both sides of every equation. -/def substEquations (σ : Nat → Shape) (equations : List (Shape × Shape)) : List (Shape × Shape) :=  equations.map fun e ↦ (e.1.subst σ, e.2.subst σ)/-- The variables of a list of equations. -/def equationVars (equations : List (Shape × Shape)) : Finset Nat :=  equations.foldr (fun e acc ↦ e.1.vars ∪ e.2.vars ∪ acc) ∅/-- The total size of a list of equations. -/def equationSize (equations : List (Shape × Shape)) : Nat :=  (equations.map fun e ↦ e.1.size + e.2.size).sum/-- Decomposition keeps the variables and makes the equations smaller. -/theorem Shape.children_vars {s t : Shape} {equations : List (Shape × Shape)}    (h : s.children t = some equations) :    equationVars equations = s.vars ∪ t.vars ∧ equationSize equations < s.size + t.size := by  cases s <;> cases t <;> simp only [children, Option.some.injEq, reduceCtorEq] at h <;> subst h <;>    refine ⟨?_, ?_⟩ <;> simp only [equationVars, Finset.union_assoc, List.foldr_nil, vars,      Finset.union_idempotent, equationSize, List.map_nil, List.sum_nil, size, Nat.reduceAdd,      Nat.zero_lt_succ, List.foldr_cons, Finset.union_empty, List.map_cons, List.sum_cons,      Nat.add_zero] <;>    first | omega | (ext; simp; tauto)private theorem equationVars_map_single {i : Nat} {t : Shape} (fresh : i ∉ t.vars)    (rest : List (Shape × Shape)) :    equationVars (substEquations (.single i t) rest) ⊆ (equationVars rest ∪ t.vars).erase i := by  induction rest with  | nil => simp [equationVars, substEquations]  | cons e rest ih =>    simp only [equationVars, substEquations, List.map_cons, List.foldr_cons] at ih ⊢    have h₁ := Shape.vars_subst_single fresh e.1    have h₂ := Shape.vars_subst_single fresh e.2    intro k hk    simp only [Finset.mem_union] at hk    rcases hk with (hk | hk) | hk    · have := h₁ hk; simp only [Finset.mem_erase, Finset.mem_union] at this ⊢; tauto    · have := h₂ hk; simp only [Finset.mem_erase, Finset.mem_union] at this ⊢; tauto    · have := ih hk; simp only [Finset.mem_erase, Finset.mem_union] at this ⊢; tauto/-- Eliminating a variable removes it from the equations. -/private theorem eliminate_decreases {i : Nat} {t : Shape} (fresh : i ∉ t.vars)    {rest : List (Shape × Shape)} {all : Finset Nat} (mem : i ∈ all)    (contains : t.vars ∪ equationVars rest ⊆ all) :    (equationVars (substEquations (.single i t) rest)).card < all.card := by  refine lt_of_le_of_lt (Finset.card_le_card ((equationVars_map_single fresh rest).trans ?_))    (Finset.card_lt_card (Finset.erase_ssubset mem))  exact Finset.erase_subset_erase i (by rwa [Finset.union_comm])private theorem equationSize_cons (s t : Shape) (rest : List (Shape × Shape)) :    equationSize ((s, t) :: rest) = s.size + t.size + equationSize rest := by  simp [equationSize]private theorem equationSize_append (front rest : List (Shape × Shape)) :    equationSize (front ++ rest) = equationSize front + equationSize rest := by  simp [equationSize]private theorem equationVars_append (front rest : List (Shape × Shape)) :    equationVars (front ++ rest) = equationVars front ∪ equationVars rest := by  induction front with  | nil => simp [equationVars]  | cons e front ih =>    simp only [List.cons_append, equationVars, List.foldr_cons] at ih ⊢    rw [ih]; simp only [Finset.union_assoc]/-- Robinson's unification algorithm. The result `θ` is a most general unifier: every unifier`δ` of the equations factors through it, as `(θ i).subst δ = δ i` for every `i`. -/def unify (equations : List (Shape × Shape)) : Option (Nat → Shape) :=  match equations with  | [] => some .var  | (.var i, t) :: rest | (t, .var i) :: rest =>    if t = .var i then unify rest    else if i ∈ t.vars then none    else      (unify (substEquations (.single i t) rest)).map fun θ j ↦ (Shape.single i t j).subst θ  | (s, t) :: rest =>    match _h : s.children t with    | some children => unify (children ++ rest)    | none => nonetermination_by ((equationVars equations).card, equationSize equations)decreasing_by  all_goals first    | -- `t = var i`: the equation disappears      exact Prod.Lex.right' _ (Finset.card_le_card Finset.subset_union_right)        (by simp only [equationSize_cons, Shape.size]; omega)    | -- elimination of `i`      exact Prod.Lex.left _ _ (eliminate_decreases ‹_› (by simp [equationVars, Shape.vars])        (fun k ↦ by simp only [equationVars, List.foldr_cons, Finset.mem_union]; tauto))    | -- decomposition      obtain ⟨vars, size⟩ := Shape.children_vars _h      refine Prod.Lex.right' _ (le_of_eq ?_) ?_      · rw [equationVars_append, vars]; rfl      · rw [equationSize_append, equationSize_cons]; exact Nat.add_lt_add_right size _end Determinize.Frontend