Source lean/Determinize/Spec/Inference.lean
import Determinize.Spec.Frontend/-!# Affinity inference`Frontend.infer` fills the omitted sample affinities of a resolved program `input : Input`.A *completion* of `input` is an annotated program that fills exactly those affinities and isclosed and well typed at some type. Completions of the same input differ only in the affinitiesof their free sample sites; they are compared site by site in the order `G ≤ E` of`Ty.Sub.general`. The greatest completion has the most E sites, which determinization replacesby the most means.`Theorems.inference_correctness` states that `infer` fails only on inputs without a completion, andotherwise returns a completion, typed at the returned type, that lies above every completion: thegreatest completion.The statement does not depend on how `infer` works. It determines the output program uniquely,but not the output type.-/namespace Determinize.Specopen Paper/-- `program` fills exactly the omitted affinities of `input`, and is closed and well typed.The type is existential: a completion counts even when it is typed only at a type other thanthe one `infer` returns. -/def Completion (input : Input) (program : Annotated) : Prop :=  input.Matches program ∧ ∃ ty, Typed [] (interpret program) ty/-- `lower` and `upper` are the same program, except that at every site the affinity of `lower`is below that of `upper` in the order `G ≤ E`. -/def AffinityLE : Annotated → Annotated → Prop :=  Expr.Sitewise fun affinity affinity' ↦ Ty.Sub (.float affinity) (.float affinity')end Determinize.Spec