Documentation

Determinize.Proof.Frontend.Unify

Correctness of shape unification #

unify succeeds exactly when the equations have a unifier (unify_complete, unify_sound), and then returns a most general one: every unifier δ factors through the result θ, as (θ i).subst δ = δ i for every variable i (unify_mostGeneral). In particular θ is idempotent. unify_mgu collects these facts. Termination is part of the definition.

θ makes the two sides of every equation equal.

Equations
Instances For

    Substitutions #

    A variable is no larger than any shape it occurs in, after any substitution.

    The occurs check: a variable is strictly smaller than any other shape it occurs in.

    Unifiers #

    A unifier of i = t is unchanged by first substituting t for i.

    Both orientations of the equation between a variable and a shape.

    The algorithm #

    theorem Determinize.Proof.Frontend.unify_mostGeneral {equations : List (Frontend.Shape × Frontend.Shape)} {θ δ : ℕ → Frontend.Shape} (h : Frontend.unify equations = some θ) (hδ : Unifies δ equations) (i : ℕ) :
    Frontend.Shape.subst δ (θ i) = δ i

    Every unifier δ factors through the result θ of unify: applying θ first and then δ is the same as applying δ.

    theorem Determinize.Proof.Frontend.unify_complete {equations : List (Frontend.Shape × Frontend.Shape)} {δ : ℕ → Frontend.Shape} (hδ : Unifies δ equations) :
    ∃ (θ : ℕ → Frontend.Shape), Frontend.unify equations = some θ

    unify succeeds on every equations that have a unifier.

    The result of unify is idempotent.

    unify fails only on equations without a unifier.

    theorem Determinize.Proof.Frontend.unify_mgu (equations : List (Frontend.Shape × Frontend.Shape)) :
    ((∃ (δ : ℕ → Frontend.Shape), Unifies δ equations) ↔ ∃ (θ : ℕ → Frontend.Shape), Frontend.unify equations = some θ) ∧ ∀ (θ : ℕ → Frontend.Shape), Frontend.unify equations = some θ → Unifies θ equations ∧ ∀ (δ : ℕ → Frontend.Shape), Unifies δ equations → ∀ (i : ℕ), Frontend.Shape.subst δ (θ i) = δ i

    The most general unifier theorem: unify succeeds exactly on the equations that have a unifier, and every unifier factors through its result.