Documentation

Determinize.Proof.Frontend.Decompose

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′):

The shape of a ground type is its erasure shapeOf, and subtyping preserves it.

Shapes #

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 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
Instances For

    A decorated shape approximates every type of that shape whose affinities the leaf variables read off.

    theorem Determinize.Proof.Frontend.approx_decorate {θ : ℕ → Frontend.Shape} {types : ℕ → Spec.Paper.Ty} {ρ : Frontend.AffinityVar → Spec.Paper.Affinity} (factor : ∀ (α : ℕ), Frontend.Shape.subst (fun (β : ℕ) => shapeOf (types β)) (θ α) = shapeOf (types α)) (leaves : ∀ (α : ℕ) (p : List ℕ), ρ (Frontend.AffinityVar.leaf α p) = affinityAt (types α) p) (u : Frontend.UType) :

    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.