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.
Equations
- One or more equations did not get rendered due to their size.
- Determinize.Frontend.instDecidableEqShape.decEq (Determinize.Frontend.Shape.var a) (Determinize.Frontend.Shape.var b) = if h : a = b then h ▸ isTrue ⋯ else isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (Determinize.Frontend.Shape.var index) Determinize.Frontend.Shape.unit = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (Determinize.Frontend.Shape.var index) Determinize.Frontend.Shape.bool = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (Determinize.Frontend.Shape.var index) Determinize.Frontend.Shape.float = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (Determinize.Frontend.Shape.var index) (left.prod right) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (Determinize.Frontend.Shape.var index) (left.sum right) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (Determinize.Frontend.Shape.var index) element.list = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (Determinize.Frontend.Shape.var index) (argument.arr result) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.unit (Determinize.Frontend.Shape.var index) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.unit Determinize.Frontend.Shape.unit = isTrue ⋯
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.unit Determinize.Frontend.Shape.bool = isFalse Determinize.Frontend.instDecidableEqShape.decEq._proof_11
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.unit Determinize.Frontend.Shape.float = isFalse Determinize.Frontend.instDecidableEqShape.decEq._proof_12
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.unit (left.prod right) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.unit (left.sum right) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.unit element.list = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.unit (argument.arr result) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.bool (Determinize.Frontend.Shape.var index) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.bool Determinize.Frontend.Shape.unit = isFalse Determinize.Frontend.instDecidableEqShape.decEq._proof_18
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.bool Determinize.Frontend.Shape.bool = isTrue ⋯
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.bool Determinize.Frontend.Shape.float = isFalse Determinize.Frontend.instDecidableEqShape.decEq._proof_19
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.bool (left.prod right) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.bool (left.sum right) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.bool element.list = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.bool (argument.arr result) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.float (Determinize.Frontend.Shape.var index) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.float Determinize.Frontend.Shape.unit = isFalse Determinize.Frontend.instDecidableEqShape.decEq._proof_25
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.float Determinize.Frontend.Shape.bool = isFalse Determinize.Frontend.instDecidableEqShape.decEq._proof_26
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.float Determinize.Frontend.Shape.float = isTrue ⋯
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.float (left.prod right) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.float (left.sum right) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.float element.list = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq Determinize.Frontend.Shape.float (argument.arr result) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (left.prod right) (Determinize.Frontend.Shape.var index) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (left.prod right) Determinize.Frontend.Shape.unit = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (left.prod right) Determinize.Frontend.Shape.bool = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (left.prod right) Determinize.Frontend.Shape.float = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (left.prod right) (left_1.sum right_1) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (left.prod right) element.list = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (left.prod right) (argument.arr result) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (left.sum right) (Determinize.Frontend.Shape.var index) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (left.sum right) Determinize.Frontend.Shape.unit = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (left.sum right) Determinize.Frontend.Shape.bool = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (left.sum right) Determinize.Frontend.Shape.float = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (left.sum right) (left_1.prod right_1) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (left.sum right) element.list = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (left.sum right) (argument.arr result) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq element.list (Determinize.Frontend.Shape.var index) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq element.list Determinize.Frontend.Shape.unit = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq element.list Determinize.Frontend.Shape.bool = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq element.list Determinize.Frontend.Shape.float = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq element.list (left.prod right) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq element.list (left.sum right) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq a.list b.list = if h : a = b then h ▸ have inst := Determinize.Frontend.instDecidableEqShape.decEq a a; isTrue ⋯ else isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq element.list (argument.arr result) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (argument.arr result) (Determinize.Frontend.Shape.var index) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (argument.arr result) Determinize.Frontend.Shape.unit = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (argument.arr result) Determinize.Frontend.Shape.bool = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (argument.arr result) Determinize.Frontend.Shape.float = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (argument.arr result) (left.prod right) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (argument.arr result) (left.sum right) = isFalse ⋯
- Determinize.Frontend.instDecidableEqShape.decEq (argument.arr result) element.list = isFalse ⋯
Instances For
Equations
- One or more equations did not get rendered due to their size.
Instances For
Equations
Equations
Replace every variable i by σ i.
Equations
- Determinize.Frontend.Shape.subst σ (Determinize.Frontend.Shape.var a) = σ a
- Determinize.Frontend.Shape.subst σ Determinize.Frontend.Shape.unit = Determinize.Frontend.Shape.unit
- Determinize.Frontend.Shape.subst σ Determinize.Frontend.Shape.bool = Determinize.Frontend.Shape.bool
- Determinize.Frontend.Shape.subst σ Determinize.Frontend.Shape.float = Determinize.Frontend.Shape.float
- Determinize.Frontend.Shape.subst σ (a.prod a_1) = (Determinize.Frontend.Shape.subst σ a).prod (Determinize.Frontend.Shape.subst σ a_1)
- Determinize.Frontend.Shape.subst σ (a.sum a_1) = (Determinize.Frontend.Shape.subst σ a).sum (Determinize.Frontend.Shape.subst σ a_1)
- Determinize.Frontend.Shape.subst σ a.list = (Determinize.Frontend.Shape.subst σ a).list
- Determinize.Frontend.Shape.subst σ (a.arr a_1) = (Determinize.Frontend.Shape.subst σ a).arr (Determinize.Frontend.Shape.subst σ a_1)
Instances For
The substitution of t for the variable i.
Equations
- Determinize.Frontend.Shape.single i t j = if j = i then t else Determinize.Frontend.Shape.var j
Instances For
Equations
Instances For
The number of constructors.
Equations
Instances For
For two shapes that are not variables, the equations between their children, or none if
their head constructors differ.
Equations
- Determinize.Frontend.Shape.unit.children Determinize.Frontend.Shape.unit = some []
- Determinize.Frontend.Shape.bool.children Determinize.Frontend.Shape.bool = some []
- Determinize.Frontend.Shape.float.children Determinize.Frontend.Shape.float = some []
- (a.prod b).children (c.prod d) = some [(a, c), (b, d)]
- (a.sum b).children (c.sum d) = some [(a, c), (b, d)]
- (a.arr b).children (c.arr d) = some [(a, c), (b, d)]
- a.list.children b.list = some [(a, b)]
- x✝¹.children x✝ = none
Instances For
The variables of a list of equations.
Equations
- Determinize.Frontend.equationVars equations = List.foldr (fun (e : Determinize.Frontend.Shape × Determinize.Frontend.Shape) (acc : Finset ℕ) => e.1.vars ∪ e.2.vars ∪ acc) ∅ equations
Instances For
The total size of a list of equations.
Equations
- Determinize.Frontend.equationSize equations = (List.map (fun (e : Determinize.Frontend.Shape × Determinize.Frontend.Shape) => e.1.size + e.2.size) equations).sum
Instances For
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
- One or more equations did not get rendered due to their size.
- Determinize.Frontend.unify [] = some Determinize.Frontend.Shape.var
- Determinize.Frontend.unify ((s, t) :: rest) = match _h : s.children t with | some children => Determinize.Frontend.unify (children ++ rest) | none => none