Decoration and decomposition #
Inference turns a subtyping constraint s <: t between types with type variables into atomic
affinity constraints: it replaces every type variable by its decorated most general shape and
decomposes the two sides. This file relates the atomic constraints to Ty.Sub, in both
directions (Lemmas S′ and C′):
decompose_sound: if two types have the same shape, a solution of their decomposition makes every instance of the first a subtype of the same instance of the second.decompose_complete: if a ground instance ofsis a subtype of the same instance oft, the affinities that the instance has at the floats of the decorated shapes solve the decomposition. The ground instance may have more structure than the decorated shapes where these have shape variables; such positions carry no constraint.
The shape of a ground type is its erasure shapeOf, and subtyping preserves it.
Shapes #
The shape of a type: the type without its affinities.
Equations
- Determinize.Proof.Frontend.shapeOf Determinize.Spec.Paper.Ty.unit = Determinize.Frontend.Shape.unit
- Determinize.Proof.Frontend.shapeOf Determinize.Spec.Paper.Ty.bool = Determinize.Frontend.Shape.bool
- Determinize.Proof.Frontend.shapeOf (Determinize.Spec.Paper.Ty.float affinity) = Determinize.Frontend.Shape.float
- Determinize.Proof.Frontend.shapeOf (a.prod b) = (Determinize.Proof.Frontend.shapeOf a).prod (Determinize.Proof.Frontend.shapeOf b)
- Determinize.Proof.Frontend.shapeOf (a.sum b) = (Determinize.Proof.Frontend.shapeOf a).sum (Determinize.Proof.Frontend.shapeOf b)
- Determinize.Proof.Frontend.shapeOf a.list = (Determinize.Proof.Frontend.shapeOf a).list
- Determinize.Proof.Frontend.shapeOf (a.arr b) = (Determinize.Proof.Frontend.shapeOf a).arr (Determinize.Proof.Frontend.shapeOf b)
Instances For
Instantiating a decorated type is instantiating the type, with each type variable replaced by the instance of its decoration.
Soundness of decomposition (Lemma S′) #
Lemma S′: a solution of the decomposition of two types of the same shape makes every instance of the first a subtype of the same instance of the second.
Completeness of decomposition (Lemma C′) #
The affinity of a type at a position, in the convention of Shape.decorate: child indices
from the root, 0 and 1 for the two children of prod, sum and arr, 0 for a list element.
Equations
- Determinize.Proof.Frontend.affinityAt (Determinize.Spec.Paper.Ty.float m) [] = m
- Determinize.Proof.Frontend.affinityAt (a.prod right) (0 :: p) = Determinize.Proof.Frontend.affinityAt a p
- Determinize.Proof.Frontend.affinityAt (a.sum right) (0 :: p) = Determinize.Proof.Frontend.affinityAt a p
- Determinize.Proof.Frontend.affinityAt a.list (0 :: p) = Determinize.Proof.Frontend.affinityAt a p
- Determinize.Proof.Frontend.affinityAt (a.arr result) (0 :: p) = Determinize.Proof.Frontend.affinityAt a p
- Determinize.Proof.Frontend.affinityAt (left.prod b) (1 :: p) = Determinize.Proof.Frontend.affinityAt b p
- Determinize.Proof.Frontend.affinityAt (left.sum b) (1 :: p) = Determinize.Proof.Frontend.affinityAt b p
- Determinize.Proof.Frontend.affinityAt (argument.arr b) (1 :: p) = Determinize.Proof.Frontend.affinityAt b p
- Determinize.Proof.Frontend.affinityAt x✝¹ x✝ = Determinize.Spec.Paper.Affinity.G
Instances For
The type T has the structure of u wherever u is not a variable or a base type, and
the affinity of u under ρ at every float of u.
Equations
- One or more equations did not get rendered due to their size.
- Determinize.Proof.Frontend.Approx ρ (Determinize.Frontend.UType.float a) x✝ = (x✝ = Determinize.Spec.Paper.Ty.float (Determinize.Frontend.AffinityTerm.eval ρ a))
- Determinize.Proof.Frontend.Approx ρ a.list x✝ = ∃ (A : Determinize.Spec.Paper.Ty), x✝ = A.list ∧ Determinize.Proof.Frontend.Approx ρ a A
- Determinize.Proof.Frontend.Approx ρ x✝¹ x✝ = True
Instances For
A decorated shape approximates every type of that shape whose affinities the leaf variables read off.
If the shapes θ factor the shapes of types, and the leaf variables read off the
affinities of types, the decoration of every type approximates its instance.
Lemma C′: the affinities of a subtyping between ground types solve the decomposition of any two types that approximate them.