Source lean/Determinize/Frontend/Infer.lean
import Determinize.Frontend.Syntaximport Determinize.Frontend.Unifyimport Determinize.Frontend.Affinity/-!# Affinity inference`infer` fills the omitted sample affinities of a resolved program with the greatest affinitiesthat make it typable. It works in phases:1. *Generation* (`generate`): give every node a type over type variables and affinity variables,   and record every use of subsumption as a cast in a `Draft`. 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 gets `general`.2. *Shapes* (`unify`): unify the shapes of the two sides of every constraint. Structural subtyping   relates only types of the same shape.3. *Decoration* (`UType.decorate`): replace every type variable `α` by its most general shape,   with the affinity variable `leaf α position` at each float. The remaining shape variables are   unconstrained; read-back sets them to `unit`. Type variables with equal shapes still get   different affinity variables.4. *Decomposition* (`decompose`): split every constraint between decorated types into atomic   constraints between affinities: covariant, except in function arguments.5. *Affinities* (`solveAffinities`): the greatest solution of the atomic constraints.6. *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 thatthe proofs can unfold them.-/namespace Determinize.Frontendopen Spec.Paper/-- Affinity variables: one for each float created during generation, and one for each float inthe decorated shape of a type variable. -/inductive AffinityVar where  | generated (index : Nat)  | leaf (typeVar : Nat) (position : List Nat)deriving DecidableEq, Repr/-- Types during inference, over type variables and affinity terms. -/inductive UType where  | var (index : Nat)  | unit | bool | float (affinity : AffinityTerm AffinityVar)  | prod (a b : UType) | sum (a b : UType) | list (a : UType) | arr (a b : UType)deriving Repr, Inhabited/-- 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. -/def Shape.decorate (leaf : List Nat → AffinityVar) : Shape → UType  | .var i => .var i  | .unit => .unit  | .bool => .bool  | .float => .float (.var (leaf []))  | .prod a b => .prod (a.decorate (leaf <| 0 :: ·)) (b.decorate (leaf <| 1 :: ·))  | .sum a b => .sum (a.decorate (leaf <| 0 :: ·)) (b.decorate (leaf <| 1 :: ·))  | .list a => .list (a.decorate (leaf <| 0 :: ·))  | .arr a b => .arr (a.decorate (leaf <| 0 :: ·)) (b.decorate (leaf <| 1 :: ·))namespace UTypedef shape : UType → Shape  | var i => .var i  | unit => .unit  | bool => .bool  | float _ => .float  | prod a b => .prod a.shape b.shape  | sum a b => .sum a.shape b.shape  | list a => .list a.shape  | arr a b => .arr a.shape b.shape/-- Replace every type variable `α` by its shape `θ α`, decorated with the affinity variablesof `α`. -/def decorate (θ : Nat → Shape) : UType → UType  | var α => (θ α).decorate (.leaf α)  | unit => unit  | bool => bool  | float a => float a  | prod a b => prod (a.decorate θ) (b.decorate θ)  | sum a b => sum (a.decorate θ) (b.decorate θ)  | list a => list (a.decorate θ)  | arr a b => arr (a.decorate θ) (b.decorate θ)/-- The type with every type variable and every affinity variable replaced. -/def instantiate (types : Nat → Ty) (affinities : AffinityVar → Affinity) : UType → Ty  | var α => types α  | unit => .unit  | bool => .bool  | float a => .float (a.eval affinities)  | prod a b => .prod (a.instantiate types affinities) (b.instantiate types affinities)  | sum a b => .sum (a.instantiate types affinities) (b.instantiate types affinities)  | list a => .list (a.instantiate types affinities)  | arr a b => .arr (a.instantiate types affinities) (b.instantiate types affinities)/-- The affinity of a float type under `ρ`. Sample sites have float types; other types give G. -/def affinity (ρ : AffinityVar → Affinity) : UType → Affinity  | float a => a.eval ρ  | _ => .Gend UType/-- The atomic constraints under which the first of two types of the same shape is a subtype ofthe second. -/def decompose : UType → UType → List (AffinityConstraint AffinityVar)  | .float a, .float b => [(a, b)]  | .prod a b, .prod c d | .sum a b, .sum c d => decompose a c ++ decompose b d  | .list a, .list b => decompose a b  | .arr a b, .arr c d => decompose c a ++ decompose b d  | _, _ => []termination_by a b => sizeOf a + sizeOf b/-- The program with a type for every node, and a cast wherever its typing uses subsumption. -/inductive Draft where  | node (expression : Input) (ty : UType) (children : List Draft)  | cast (body : Draft) (ty : UType)namespace Draftdef ty : Draft → UType  | node _ t _ | cast _ t => t/-- The subtyping constraints: the type of every cast body is a subtype of the cast type. -/def relations : Draft → List (UType × UType)  | node _ _ children => children.flatMap relations  | cast body t => (body.ty, t) :: body.relationsend Draft/-! ## Generation -//-- Generation draws type and affinity variables from one counter. It fails only on an unboundvariable. -/abbrev Generate := StateT Nat (Except String)def fresh : Generate UType :=  modifyGet fun n ↦ (.var n, n + 1)def freshFloat : Generate UType :=  modifyGet fun n ↦ (.float (.var (.generated n)), n + 1)/-- The type of an operand that the typing rules require to be G. -/def general : UType := .float (.fixed .G)/-- The type of a sample site: its requested affinity, or a fresh variable. -/def site : Option Affinity → Generate UType  | some affinity => pure (.float (.fixed affinity))  | none => freshFloat/-- Phase 1: the draft of `e` in the context `Γ`. -/def generate (Γ : List UType) (e : Input) : Generate Draft := do  let node := fun t children ↦ Draft.node e t children  match e with  | .bvar i =>    let some t := Γ[i]? | throw s!"unbound core variable {i}"    return node t []  | .reject => return node (← fresh) []  | .unit => return node .unit []  | .bool _ => return node .bool []  | .real _ => return node (← freshFloat) []  | .lam b =>    let a ← fresh    let b ← generate (a :: Γ) b    return node (.arr a b.ty) [b]  | .fix b =>    let a ← fresh; let r ← fresh    let b ← generate (a :: .arr a r :: Γ) b    return node (.arr a r) [b.cast r]  | .app f x =>    let f ← generate Γ f; let x ← generate Γ x    let a ← fresh; let r ← fresh    return node r [f.cast (.arr a r), x.cast a]  | .pair a b =>    let a ← generate Γ a; let b ← generate Γ b    return node (.prod a.ty b.ty) [a, b]  | .fst p | .snd p =>    let a ← fresh; let b ← fresh    let p ← generate Γ p    return node (match e with | .fst _ => a | _ => b) [p.cast (.prod a b)]  | .inl v | .inr v =>    let v ← generate Γ v; let other ← fresh    return node (match e with | .inl _ => .sum v.ty other | _ => .sum other v.ty) [v]  | .matchSum s a b =>    let l ← fresh; let r ← fresh; let t ← fresh    let s ← generate Γ s    let a ← generate (l :: Γ) a    let b ← generate (r :: Γ) b    return node t [s.cast (.sum l r), a.cast t, b.cast t]  | .nil => return node (.list (← fresh)) []  | .cons h t =>    let a ← fresh    let h ← generate Γ h; let t ← generate Γ t    return node (.list a) [h.cast a, t.cast (.list a)]  | .matchList s n c =>    let a ← fresh; let t ← fresh    let s ← generate Γ s    let n ← generate Γ n    let c ← generate (a :: .list a :: Γ) c    return node t [s.cast (.list a), n.cast t, c.cast t]  | .ite c a b =>    let t ← fresh    let c ← generate Γ c; let a ← generate Γ a; let b ← generate Γ b    return node t [c.cast .bool, a.cast t, b.cast t]  | .letE v b =>    let v ← generate Γ v; let b ← generate (v.ty :: Γ) b    return node b.ty [v, b]  | .neg b =>    let t ← freshFloat    let b ← generate Γ b    return node t [b.cast t]  | .add a b | .mul a b | .div a b | .lt a b =>    let t ← freshFloat    let ta := match e with | .mul .. | .lt .. => general | _ => t    let tb := match e with | .div .. | .lt .. => general | _ => t    let a ← generate Γ a; let b ← generate Γ b    return node (match e with | .lt .. => .bool | _ => t) [a.cast ta, b.cast tb]  | .uniform requested a b | .gaussian requested a b | .beta requested a b  | .gamma requested a b =>    let t ← site requested    let ta := match e with | .beta .. => general | _ => t    let tb := match e with | .uniform .. => t | _ => general    let a ← generate Γ a; let b ← generate Γ b    return node t [a.cast ta, b.cast tb]  | .discrete requested probabilities =>    let t ← site requested    let probabilities ← generate Γ probabilities    return node t [probabilities.cast (.list t)]  | .poisson requested a | .bernoulli requested a | .exponential requested a =>    let t ← site requested    let ta := match e with | .poisson .. | .bernoulli .. => t | _ => general    let a ← generate Γ a    return node t [a.cast ta]/-! ## Read-back -/namespace Draft/-- The annotated node for the input node `e` with the given children, sampling at affinity `m`if it is a sample site. -/def rebuild (e : Input) (m : Affinity) : List Annotated → Annotated  | [] => match e with    | .bvar i => .bvar i    | .reject => .reject    | .unit => .unit    | .bool b => .bool b    | .real q => .real q    | .nil => .nil    | _ => .unit  | [b] => match e with    | .lam _ => .lam b    | .fix _ => .fix b    | .fst _ => .fst b    | .snd _ => .snd b    | .inl _ => .inl b    | .inr _ => .inr b    | .neg _ => .neg b    | .poisson .. => .poisson m b    | .discrete .. => .discrete m b    | .bernoulli .. => .bernoulli m b    | .exponential .. => .exponential m b    | _ => .unit  | [a, b] => match e with    | .app .. => .app a b    | .pair .. => .pair a b    | .cons .. => .cons a b    | .letE .. => .letE a b    | .add .. => .add a b    | .mul .. => .mul a b    | .div .. => .div a b    | .lt .. => .lt a b    | .uniform .. => .uniform m a b    | .gaussian .. => .gaussian m a b    | .beta .. => .beta m a b    | .gamma .. => .gamma m a b    | _ => .unit  | [a, b, c] => match e with    | .matchSum .. => .matchSum a b c    | .matchList .. => .matchList a b c    | .ite .. => .ite a b c    | _ => .unit  -- `generate` gives every node the children listed above.  | _ => .unit/-- The input with every sample site annotated by the affinity of its type under `ρ`. -/def program (ρ : AffinityVar → Affinity) : Draft → Annotated  | cast body _ => body.program ρ  | node e t children => rebuild e (t.affinity ρ) (children.map (program ρ))end Draft/-! ## Inference -//-- The outcome of phases 1 to 5: the draft, the most general shapes of its type variables, andthe greatest solution of the affinity constraints. -/structure Solution where  draft : Draft  shapes : Nat → Shape  affinities : AffinityVar → Affinity/-- The type of a draft type in the solution. The shape variables left after decoration areunconstrained and become `unit`. -/def Solution.type (s : Solution) (t : UType) : Ty :=  (t.decorate s.shapes).instantiate (fun _ ↦ .unit) s.affinities/-- Phases 1 to 5. Fails on an unbound variable, if the shapes have no unifier, or if the affinityconstraints have no solution. -/def solveInput (input : Input) : Except String Solution := do  let (draft, _) ← (generate [] input).run 0  let relations := draft.relations  let some shapes := unify (relations.map fun (s, t) ↦ (s.shape, t.shape))    | throw "incompatible or infinite type shapes"  let constraints :=    relations.flatMap fun (s, t) ↦ decompose (s.decorate shapes) (t.decorate shapes)  let some affinities := solveAffinities constraints    | throw "inconsistent E/G constraints"  return { draft, shapes, affinities }/-- The annotated program and its type. `Spec/Inference.lean` states what it guarantees. -/def infer (input : Input) : Except String (Annotated × Ty) := do  let s ← solveInput input  return (s.draft.program s.affinities, s.type s.draft.ty)end Determinize.Frontend