Documentation

Determinize.Frontend.Unify

Unification of type shapes #

A shape is a type without its affinities. Structural subtyping relates only types of the same shape, 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 from the equations and every decomposition makes them smaller. Proof/Frontend/Unify.lean proves that it returns a most general unifier whenever there is a unifier.

Instances For
    Equations
    Instances For
      Equations
      • One or more equations did not get rendered due to their size.
      Instances For

        The substitution of t for the variable i.

        Equations
        Instances For
          theorem Determinize.Frontend.Shape.vars_subst_single {i : ℕ} {t : Shape} (fresh : i ∉ t.vars) (s : Shape) :
          (subst (single i t) s).vars ⊆ (s.vars ∪ t.vars).erase i

          Apply a substitution to both sides of every equation.

          Equations
          • One or more equations did not get rendered due to their size.
          Instances For

            The variables of a list of equations.

            Equations
            Instances For

              The total size of a list of equations.

              Equations
              Instances For
                theorem Determinize.Frontend.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

                Decomposition keeps the variables and makes the equations smaller.

                @[irreducible]

                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.

                Equations
                Instances For