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
- Determinize.Proof.Frontend.Unifies θ equations = ∀ e ∈ equations, Determinize.Frontend.Shape.subst θ e.1 = Determinize.Frontend.Shape.subst θ e.2
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 #
Every unifier δ factors through the result θ of unify: applying θ first and then δ
is the same as applying δ.
unify succeeds on every equations that have a unifier.
The result of unify is idempotent.
unify fails only on equations without a unifier.
The most general unifier theorem: unify succeeds exactly on the equations that have a
unifier, and every unifier factors through its result.