Affinity inference #
infer fills the omitted sample affinities of a resolved program with the greatest affinities
that make it typable. It works in phases:
- Generation (
generate): give every node a type over type variables and affinity variables, and record every use of subsumption as a cast in aDraft. The casts are the subtyping constraints (Draft.relations). A sample site gets a fresh affinity variable, or its requested affinity; an operand that the typing rules require to be G getsgeneral. - Shapes (
unify): unify the shapes of the two sides of every constraint. Structural subtyping relates only types of the same shape. - Decoration (
UType.decorate): replace every type variableαby its most general shape, with the affinity variableleaf α positionat each float. The remaining shape variables are unconstrained; read-back sets them tounit. Type variables with equal shapes still get different affinity variables. - Decomposition (
decompose): split every constraint between decorated types into atomic constraints between affinities: covariant, except in function arguments. - Affinities (
solveAffinities): the greatest solution of the atomic constraints. - Read-back (
Draft.program,Solution.type): the input with every site annotated by the solution, and its type.
Spec/Inference.lean states what infer guarantees. Every definition here is total, so that
the proofs can unfold them.
Affinity variables: one for each float created during generation, and one for each float in the decorated shape of a type variable.
- generated (index : ℕ) : AffinityVar
- leaf (typeVar : ℕ) (position : List ℕ) : AffinityVar
Instances For
Equations
- One or more equations did not get rendered due to their size.
- Determinize.Frontend.instDecidableEqAffinityVar.decEq (Determinize.Frontend.AffinityVar.generated index) (Determinize.Frontend.AffinityVar.leaf typeVar position) = isFalse ⋯
- Determinize.Frontend.instDecidableEqAffinityVar.decEq (Determinize.Frontend.AffinityVar.leaf typeVar position) (Determinize.Frontend.AffinityVar.generated index) = isFalse ⋯
Instances For
Equations
- One or more equations did not get rendered due to their size.
Instances For
Equations
Equations
- One or more equations did not get rendered due to their size.
Instances For
Equations
Equations
The type of a shape, with the affinity variable leaf position at the float at each position
(the list of child indices from the root). Shape variables stay type variables.
Equations
- One or more equations did not get rendered due to their size.
- Determinize.Frontend.Shape.decorate leaf (Determinize.Frontend.Shape.var i) = Determinize.Frontend.UType.var i
- Determinize.Frontend.Shape.decorate leaf Determinize.Frontend.Shape.unit = Determinize.Frontend.UType.unit
- Determinize.Frontend.Shape.decorate leaf Determinize.Frontend.Shape.bool = Determinize.Frontend.UType.bool
- Determinize.Frontend.Shape.decorate leaf Determinize.Frontend.Shape.float = Determinize.Frontend.UType.float (Determinize.Frontend.AffinityTerm.var (leaf []))
- Determinize.Frontend.Shape.decorate leaf a.list = (Determinize.Frontend.Shape.decorate (fun (x : List ℕ) => leaf (0 :: x)) a).list
Instances For
Equations
- (Determinize.Frontend.UType.var a).shape = Determinize.Frontend.Shape.var a
- Determinize.Frontend.UType.unit.shape = Determinize.Frontend.Shape.unit
- Determinize.Frontend.UType.bool.shape = Determinize.Frontend.Shape.bool
- (Determinize.Frontend.UType.float a).shape = Determinize.Frontend.Shape.float
- (a.prod a_1).shape = a.shape.prod a_1.shape
- (a.sum a_1).shape = a.shape.sum a_1.shape
- a.list.shape = a.shape.list
- (a.arr a_1).shape = a.shape.arr a_1.shape
Instances For
Replace every type variable α by its shape θ α, decorated with the affinity variables
of α.
Equations
- Determinize.Frontend.UType.decorate θ (Determinize.Frontend.UType.var a) = Determinize.Frontend.Shape.decorate (Determinize.Frontend.AffinityVar.leaf a) (θ a)
- Determinize.Frontend.UType.decorate θ Determinize.Frontend.UType.unit = Determinize.Frontend.UType.unit
- Determinize.Frontend.UType.decorate θ Determinize.Frontend.UType.bool = Determinize.Frontend.UType.bool
- Determinize.Frontend.UType.decorate θ (Determinize.Frontend.UType.float a) = Determinize.Frontend.UType.float a
- Determinize.Frontend.UType.decorate θ (a.prod a_1) = (Determinize.Frontend.UType.decorate θ a).prod (Determinize.Frontend.UType.decorate θ a_1)
- Determinize.Frontend.UType.decorate θ (a.sum a_1) = (Determinize.Frontend.UType.decorate θ a).sum (Determinize.Frontend.UType.decorate θ a_1)
- Determinize.Frontend.UType.decorate θ a.list = (Determinize.Frontend.UType.decorate θ a).list
- Determinize.Frontend.UType.decorate θ (a.arr a_1) = (Determinize.Frontend.UType.decorate θ a).arr (Determinize.Frontend.UType.decorate θ a_1)
Instances For
The type with every type variable and every affinity variable replaced.
Equations
- One or more equations did not get rendered due to their size.
- Determinize.Frontend.UType.instantiate types affinities (Determinize.Frontend.UType.var a) = types a
- Determinize.Frontend.UType.instantiate types affinities Determinize.Frontend.UType.unit = Determinize.Spec.Paper.Ty.unit
- Determinize.Frontend.UType.instantiate types affinities Determinize.Frontend.UType.bool = Determinize.Spec.Paper.Ty.bool
- Determinize.Frontend.UType.instantiate types affinities (Determinize.Frontend.UType.float a) = Determinize.Spec.Paper.Ty.float (Determinize.Frontend.AffinityTerm.eval affinities a)
- Determinize.Frontend.UType.instantiate types affinities a.list = (Determinize.Frontend.UType.instantiate types affinities a).list
Instances For
The affinity of a float type under ρ. Sample sites have float types; other types give G.
Equations
Instances For
The atomic constraints under which the first of two types of the same shape is a subtype of the second.
Equations
- Determinize.Frontend.decompose (Determinize.Frontend.UType.float a) (Determinize.Frontend.UType.float b) = [(a, b)]
- Determinize.Frontend.decompose (a.prod b) (c.prod d) = Determinize.Frontend.decompose a c ++ Determinize.Frontend.decompose b d
- Determinize.Frontend.decompose (a.sum b) (c.sum d) = Determinize.Frontend.decompose a c ++ Determinize.Frontend.decompose b d
- Determinize.Frontend.decompose a.list b.list = Determinize.Frontend.decompose a b
- Determinize.Frontend.decompose (a.arr b) (c.arr d) = Determinize.Frontend.decompose c a ++ Determinize.Frontend.decompose b d
- Determinize.Frontend.decompose x✝¹ x✝ = []
Instances For
Instances For
The subtyping constraints: the type of every cast body is a subtype of the cast type.
Equations
- (Determinize.Frontend.Draft.node expression t children).relations = List.flatMap Determinize.Frontend.Draft.relations children
- (body.cast t).relations = (body.ty, t) :: body.relations
Instances For
Generation #
Generation draws type and affinity variables from one counter. It fails only on an unbound variable.
Instances For
Equations
- Determinize.Frontend.fresh = modifyGet fun (n : ℕ) => (Determinize.Frontend.UType.var n, n + 1)
Instances For
Equations
- One or more equations did not get rendered due to their size.
Instances For
The type of an operand that the typing rules require to be G.
Equations
Instances For
The type of a sample site: its requested affinity, or a fresh variable.
Equations
Instances For
Phase 1: the draft of e in the context Γ.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Read-back #
The annotated node for the input node e with the given children, sampling at affinity m
if it is a sample site.
Equations
- Determinize.Frontend.Draft.rebuild (Determinize.Spec.Paper.Expr.bvar i) m [] = Determinize.Spec.Paper.Expr.bvar i
- Determinize.Frontend.Draft.rebuild Determinize.Spec.Paper.Expr.reject m [] = Determinize.Spec.Paper.Expr.reject
- Determinize.Frontend.Draft.rebuild Determinize.Spec.Paper.Expr.unit m [] = Determinize.Spec.Paper.Expr.unit
- Determinize.Frontend.Draft.rebuild (Determinize.Spec.Paper.Expr.bool b) m [] = Determinize.Spec.Paper.Expr.bool b
- Determinize.Frontend.Draft.rebuild (Determinize.Spec.Paper.Expr.real q) m [] = Determinize.Spec.Paper.Expr.real q
- Determinize.Frontend.Draft.rebuild Determinize.Spec.Paper.Expr.nil m [] = Determinize.Spec.Paper.Expr.nil
- Determinize.Frontend.Draft.rebuild e m [] = Determinize.Spec.Paper.Expr.unit
- Determinize.Frontend.Draft.rebuild body.lam m [b] = Determinize.Spec.Paper.Expr.lam b
- Determinize.Frontend.Draft.rebuild body.fix m [b] = Determinize.Spec.Paper.Expr.fix b
- Determinize.Frontend.Draft.rebuild pair.fst m [b] = Determinize.Spec.Paper.Expr.fst b
- Determinize.Frontend.Draft.rebuild pair.snd m [b] = Determinize.Spec.Paper.Expr.snd b
- Determinize.Frontend.Draft.rebuild operand.inl m [b] = Determinize.Spec.Paper.Expr.inl b
- Determinize.Frontend.Draft.rebuild operand.inr m [b] = Determinize.Spec.Paper.Expr.inr b
- Determinize.Frontend.Draft.rebuild body.neg m [b] = Determinize.Spec.Paper.Expr.neg b
- Determinize.Frontend.Draft.rebuild (Determinize.Spec.Paper.Expr.poisson site rate) m [b] = Determinize.Spec.Paper.Expr.poisson m b
- Determinize.Frontend.Draft.rebuild (Determinize.Spec.Paper.Expr.discrete site probabilities) m [b] = Determinize.Spec.Paper.Expr.discrete m b
- Determinize.Frontend.Draft.rebuild (Determinize.Spec.Paper.Expr.bernoulli site probability) m [b] = Determinize.Spec.Paper.Expr.bernoulli m b
- Determinize.Frontend.Draft.rebuild (Determinize.Spec.Paper.Expr.exponential site rate) m [b] = Determinize.Spec.Paper.Expr.exponential m b
- Determinize.Frontend.Draft.rebuild e m [b] = Determinize.Spec.Paper.Expr.unit
- Determinize.Frontend.Draft.rebuild (function.app argument) m [a, b] = Determinize.Spec.Paper.Expr.app a b
- Determinize.Frontend.Draft.rebuild (left.pair right) m [a, b] = Determinize.Spec.Paper.Expr.pair a b
- Determinize.Frontend.Draft.rebuild (head.cons tail) m [a, b] = Determinize.Spec.Paper.Expr.cons a b
- Determinize.Frontend.Draft.rebuild (value.letE body) m [a, b] = Determinize.Spec.Paper.Expr.letE a b
- Determinize.Frontend.Draft.rebuild (left.add right) m [a, b] = Determinize.Spec.Paper.Expr.add a b
- Determinize.Frontend.Draft.rebuild (left.mul right) m [a, b] = Determinize.Spec.Paper.Expr.mul a b
- Determinize.Frontend.Draft.rebuild (left.div right) m [a, b] = Determinize.Spec.Paper.Expr.div a b
- Determinize.Frontend.Draft.rebuild (left.lt right) m [a, b] = Determinize.Spec.Paper.Expr.lt a b
- Determinize.Frontend.Draft.rebuild (Determinize.Spec.Paper.Expr.uniform site lower upper) m [a, b] = Determinize.Spec.Paper.Expr.uniform m a b
- Determinize.Frontend.Draft.rebuild (Determinize.Spec.Paper.Expr.gaussian site mean variance) m [a, b] = Determinize.Spec.Paper.Expr.gaussian m a b
- Determinize.Frontend.Draft.rebuild (Determinize.Spec.Paper.Expr.beta site alpha beta) m [a, b] = Determinize.Spec.Paper.Expr.beta m a b
- Determinize.Frontend.Draft.rebuild (Determinize.Spec.Paper.Expr.gamma site shape rate) m [a, b] = Determinize.Spec.Paper.Expr.gamma m a b
- Determinize.Frontend.Draft.rebuild e m [a, b] = Determinize.Spec.Paper.Expr.unit
- Determinize.Frontend.Draft.rebuild (scrutinee.matchSum left right) m [a, b, c] = Determinize.Spec.Paper.Expr.matchSum a b c
- Determinize.Frontend.Draft.rebuild (scrutinee.matchList nilCase consCase) m [a, b, c] = Determinize.Spec.Paper.Expr.matchList a b c
- Determinize.Frontend.Draft.rebuild (condition.ite thenBranch elseBranch) m [a, b, c] = Determinize.Spec.Paper.Expr.ite a b c
- Determinize.Frontend.Draft.rebuild e m [a, b, c] = Determinize.Spec.Paper.Expr.unit
- Determinize.Frontend.Draft.rebuild e m x✝ = Determinize.Spec.Paper.Expr.unit
Instances For
The input with every sample site annotated by the affinity of its type under ρ.
Equations
- One or more equations did not get rendered due to their size.
- Determinize.Frontend.Draft.program ρ (body.cast ty) = Determinize.Frontend.Draft.program ρ body
Instances For
Inference #
The outcome of phases 1 to 5: the draft, the most general shapes of its type variables, and the greatest solution of the affinity constraints.
- draft : Draft
- affinities : AffinityVar → Spec.Paper.Affinity
Instances For
The type of a draft type in the solution. The shape variables left after decoration are
unconstrained and become unit.
Equations
- s.type t = Determinize.Frontend.UType.instantiate (fun (x : ℕ) => Determinize.Spec.Paper.Ty.unit) s.affinities (Determinize.Frontend.UType.decorate s.shapes t)
Instances For
Phases 1 to 5. Fails on an unbound variable, if the shapes have no unifier, or if the affinity constraints have no solution.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The annotated program and its type. Spec/Inference.lean states what it guarantees.
Equations
- Determinize.Frontend.infer input = do let s ← Determinize.Frontend.solveInput input pure (Determinize.Frontend.Draft.program s.affinities s.draft, s.type s.draft.ty)