Source lean/Determinize/Spec/Syntax.lean
import Determinize.Spec.Primitivesimport Determinize.Spec.Typesimport Mathlib.Tactic.DeriveCountable/-!# Reviewer-facing paper syntaxOnly sample sites carry affinity labels; subtyping is silent; literals and arithmeticare unannotated, as in the paper's grammar, and a literal types at either affinity. Types areassigned separately by `Typed`; no expression constructor contains a type annotation.Each primitive distribution is its own constructor with the paper's operands and a site. Inthe paper syntax (`Expr` with its default parameters), a site samples with an E/G affinity orcomputes the primitive’s mean without an affinity annotation. Programs may contain both samplingand mean sites; their operands may be arbitrary expressions. `Spec/Frontend.lean` reuses theconstructors with rational literals and other sites for the programs of the front end.-/namespace Determinize.Spec.Paper/-- Untyped paper expressions with de Bruijn variables. `Site` is the annotation of aprimitive distribution; in the paper syntax it is a `DistributionAction`. -/inductive Expr (Literal : Type := ℝ) (Site : Type := DistributionAction) where  | bvar (index : Nat)  | reject  | unit | bool (value : Bool) | real (value : Literal)  | lam (body : Expr Literal Site)  | fix (body : Expr Literal Site)  | app (function argument : Expr Literal Site)  | pair (left right : Expr Literal Site) | fst (pair : Expr Literal Site)  | snd (pair : Expr Literal Site) | inl (operand : Expr Literal Site)  | inr (operand : Expr Literal Site)  | matchSum (scrutinee left right : Expr Literal Site)  | nil | cons (head tail : Expr Literal Site)  | matchList (scrutinee nilCase consCase : Expr Literal Site)  | ite (condition thenBranch elseBranch : Expr Literal Site)  | letE (value body : Expr Literal Site)  | neg (body : Expr Literal Site)  | add (left right : Expr Literal Site) | mul (left right : Expr Literal Site)  | div (left right : Expr Literal Site) | lt (left right : Expr Literal Site)  | uniform (site : Site) (lower upper : Expr Literal Site)  | gaussian (site : Site) (mean variance : Expr Literal Site)  | poisson (site : Site) (rate : Expr Literal Site)  | discrete (site : Site) (probabilities : Expr Literal Site)  | bernoulli (site : Site) (probability : Expr Literal Site)  | exponential (site : Site) (rate : Expr Literal Site)  | beta (site : Site) (alpha beta : Expr Literal Site)  | gamma (site : Site) (shape rate : Expr Literal Site)deriving instance Repr, DecidableEq, Inhabited for Exprnamespace Expr/-- Whether an expression is a value: a literal, a function, the empty list, or a pair,injection or list cell of values. -/def isValue {Literal : Type} : Expr Literal → Bool  | .unit | .bool _ | .real _ | .lam _ | .fix _ | .nil => true  | .pair left right | .cons left right => left.isValue && right.isValue  | .inl operand | .inr operand => operand.isValue  | _ => false/-- Apply `replace depth index` to variables, increasing `depth` beneath binders. -/def mapVars {Literal Site : Type} (replace : Nat → Nat → Expr Literal Site) (depth : Nat) :    Expr Literal Site → Expr Literal Site  | .bvar index => replace depth index  | .unit => .unit  | .reject => .reject  | .discrete action d => .discrete action (d.mapVars replace depth)  | .bool value => .bool value  | .real value => .real value  | .lam body => .lam (body.mapVars replace (depth + 1))  | .fix body => .fix (body.mapVars replace (depth + 2))  | .app f x => .app (f.mapVars replace depth) (x.mapVars replace depth)  | .pair l r => .pair (l.mapVars replace depth) (r.mapVars replace depth)  | .fst x => .fst (x.mapVars replace depth)  | .snd x => .snd (x.mapVars replace depth)  | .inl x => .inl (x.mapVars replace depth)  | .inr x => .inr (x.mapVars replace depth)  | .matchSum x l r => .matchSum (x.mapVars replace depth)      (l.mapVars replace (depth + 1)) (r.mapVars replace (depth + 1))  | .nil => .nil  | .cons h t => .cons (h.mapVars replace depth) (t.mapVars replace depth)  | .matchList x n c => .matchList (x.mapVars replace depth)      (n.mapVars replace depth) (c.mapVars replace (depth + 2))  | .ite c t e => .ite (c.mapVars replace depth) (t.mapVars replace depth)      (e.mapVars replace depth)  | .letE x b => .letE (x.mapVars replace depth)      (b.mapVars replace (depth + 1))  | .neg x => .neg (x.mapVars replace depth)  | .add l r => .add (l.mapVars replace depth) (r.mapVars replace depth)  | .mul l r => .mul (l.mapVars replace depth) (r.mapVars replace depth)  | .div l r => .div (l.mapVars replace depth) (r.mapVars replace depth)  | .lt l r => .lt (l.mapVars replace depth) (r.mapVars replace depth)  | .uniform k l r => .uniform k (l.mapVars replace depth) (r.mapVars replace depth)  | .gaussian k l r => .gaussian k (l.mapVars replace depth) (r.mapVars replace depth)  | .poisson k x => .poisson k (x.mapVars replace depth)  | .bernoulli k x => .bernoulli k (x.mapVars replace depth)  | .exponential k x => .exponential k (x.mapVars replace depth)  | .beta k l r => .beta k (l.mapVars replace depth) (r.mapVars replace depth)  | .gamma k l r => .gamma k (l.mapVars replace depth) (r.mapVars replace depth)/-- Add `amount` to every variable index that is at least `cutoff`. -/abbrev shift {Literal Site : Type} (amount cutoff : Nat) : Expr Literal Site → Expr Literal Site :=  mapVars (fun cutoff index ↦ .bvar (if cutoff ≤ index then index + amount else index)) cutoff/-- Substitute `replacement` for the variable `depth` and lower the indices above it. -/abbrev substAt {Literal Site : Type} (depth : Nat) (replacement : Expr Literal Site) :    Expr Literal Site → Expr Literal Site :=  mapVars (fun depth index ↦ if index = depth then replacement.shift depth 0    else .bvar (if depth < index then index - 1 else index)) depth/-- Substitute `replacement` for the innermost variable of `body`. -/def substHead {Literal Site : Type} (body replacement : Expr Literal Site) : Expr Literal Site :=  substAt 0 replacement body/-- Substitute `argument` for the innermost variable of `body` and `function` for the next one,as when a recursive function is applied. -/def substTwo {Literal Site : Type} (body argument function : Expr Literal Site) :    Expr Literal Site :=  substAt 0 argument (substAt 1 function body)/-- Replace E stochastic samples by their atomic means. -/def determinize {Literal : Type} : Expr Literal → Expr Literal  | .bvar index => .bvar index  | .unit => .unit  | .reject => .reject  | .bool value => .bool value  | .real value => .real value  | .lam body => .lam body.determinize  | .fix body => .fix body.determinize  | .app function argument => .app function.determinize argument.determinize  | .pair left right => .pair left.determinize right.determinize  | .fst pairValue => .fst pairValue.determinize  | .snd pairValue => .snd pairValue.determinize  | .inl operand => .inl operand.determinize  | .inr operand => .inr operand.determinize  | .matchSum scrutinee left right =>    .matchSum scrutinee.determinize left.determinize right.determinize  | .nil => .nil  | .cons head tail => .cons head.determinize tail.determinize  | .matchList scrutinee nilCase consCase =>    .matchList scrutinee.determinize nilCase.determinize consCase.determinize  | .ite condition thenBranch elseBranch =>    .ite condition.determinize thenBranch.determinize elseBranch.determinize  | .letE value body => .letE value.determinize body.determinize  | .neg body => .neg body.determinize  | .add left right => .add left.determinize right.determinize  | .mul left right => .mul left.determinize right.determinize  | .div left right => .div left.determinize right.determinize  | .lt left right => .lt left.determinize right.determinize  | .uniform action lower upper =>    .uniform action.determinize lower.determinize upper.determinize  | .gaussian action mean variance =>    .gaussian action.determinize mean.determinize variance.determinize  | .poisson action rate => .poisson action.determinize rate.determinize  | .bernoulli action probability => .bernoulli action.determinize probability.determinize  | .discrete action d => .discrete action.determinize d.determinize  | .exponential action rate =>    .exponential action.determinize rate.determinize  | .beta action left right =>    .beta action.determinize left.determinize right.determinize  | .gamma action shape rate =>    .gamma action.determinize shape.determinize rate.determinize/-- Apply `literal` to every literal and `site` to every site. -/def map {Literal Literal' Site Site' : Type} (literal : Literal → Literal') (site : Site → Site') :    Expr Literal Site → Expr Literal' Site'  | .bvar index => .bvar index  | .unit => .unit  | .reject => .reject  | .bool value => .bool value  | .real value => .real (literal value)  | .lam body => .lam (body.map literal site)  | .fix body => .fix (body.map literal site)  | .app function argument => .app (function.map literal site) (argument.map literal site)  | .pair left right => .pair (left.map literal site) (right.map literal site)  | .fst pairValue => .fst (pairValue.map literal site)  | .snd pairValue => .snd (pairValue.map literal site)  | .inl value => .inl (value.map literal site)  | .inr value => .inr (value.map literal site)  | .matchSum scrutinee left right =>    .matchSum (scrutinee.map literal site) (left.map literal site) (right.map literal site)  | .nil => .nil  | .cons head tail => .cons (head.map literal site) (tail.map literal site)  | .matchList scrutinee nilCase consCase =>    .matchList (scrutinee.map literal site) (nilCase.map literal site) (consCase.map literal site)  | .ite condition thenBranch elseBranch =>    .ite (condition.map literal site) (thenBranch.map literal site) (elseBranch.map literal site)  | .letE value body => .letE (value.map literal site) (body.map literal site)  | .neg body => .neg (body.map literal site)  | .add left right => .add (left.map literal site) (right.map literal site)  | .mul left right => .mul (left.map literal site) (right.map literal site)  | .div left right => .div (left.map literal site) (right.map literal site)  | .lt left right => .lt (left.map literal site) (right.map literal site)  | .uniform s lower upper => .uniform (site s) (lower.map literal site) (upper.map literal site)  | .gaussian s mean variance =>    .gaussian (site s) (mean.map literal site) (variance.map literal site)  | .poisson s rate => .poisson (site s) (rate.map literal site)  | .discrete s probabilities => .discrete (site s) (probabilities.map literal site)  | .bernoulli s probability => .bernoulli (site s) (probability.map literal site)  | .exponential s rate => .exponential (site s) (rate.map literal site)  | .beta s alpha betaArg => .beta (site s) (alpha.map literal site) (betaArg.map literal site)  | .gamma s shape rate => .gamma (site s) (shape.map literal site) (rate.map literal site)end Expr/-- Typing of de Bruijn variables in a paper context. -/inductive HasVar : List Ty → Nat → Ty → Prop  | head : HasVar (ty :: context) 0 ty  | tail : HasVar context index ty → HasVar (head :: context) (index + 1) ty/-- Core typing with affinity-annotated sample sites and silent structural subtyping. -/inductive Typed : List Ty → Expr → Ty → Prop  | bvar : HasVar context index ty → Typed context (.bvar index) ty  | reject : Typed context .reject ty  | unit : Typed context .unit .unit  | bool : Typed context (.bool value) .bool  | real : Typed context (.real value) (.float affinity)  | lam : Typed (argument :: context) body result →      Typed context (.lam body) (.arr argument result)  | fix : Typed (argument :: .arr argument result :: context) body result →      Typed context (.fix body) (.arr argument result)  | app : Typed context function (.arr argument result) → Typed context operand argument →      Typed context (.app function operand) result  | pair : Typed context left leftTy → Typed context right rightTy →      Typed context (.pair left right) (.prod leftTy rightTy)  | fst : Typed context pair (.prod leftTy rightTy) → Typed context (.fst pair) leftTy  | snd : Typed context pair (.prod leftTy rightTy) → Typed context (.snd pair) rightTy  | inl : Typed context operand leftTy →      Typed context (.inl operand) (.sum leftTy rightTy)  | inr : Typed context operand rightTy →      Typed context (.inr operand) (.sum leftTy rightTy)  | matchSum : Typed context scrutinee (.sum leftTy rightTy) →      Typed (leftTy :: context) left result → Typed (rightTy :: context) right result →      Typed context (.matchSum scrutinee left right) result  | nil : Typed context .nil (.list element)  | cons : Typed context head element → Typed context tail (.list element) →      Typed context (.cons head tail) (.list element)  | matchList : Typed context scrutinee (.list element) → Typed context nilCase result →      Typed (element :: .list element :: context) consCase result →      Typed context (.matchList scrutinee nilCase consCase) result  | ite : Typed context condition .bool → Typed context thenBranch result →      Typed context elseBranch result → Typed context (.ite condition thenBranch elseBranch) result  | letE : Typed context value valueTy → Typed (valueTy :: context) body result →      Typed context (.letE value body) result  | sub : Typed context value a → Ty.Sub a b → Typed context value b  | neg : Typed context operand (.float affinity) → Typed context (.neg operand) (.float affinity)  | add : Typed context left (.float affinity) → Typed context right (.float affinity) →      Typed context (.add left right) (.float affinity)  | mul : Typed context left (.float .G) → Typed context right (.float affinity) →      Typed context (.mul left right) (.float affinity)  | div : Typed context left (.float affinity) → Typed context right (.float .G) →      Typed context (.div left right) (.float affinity)  | lt : Typed context left (.float .G) → Typed context right (.float .G) →      Typed context (.lt left right) .bool  | uniform : Typed context lower (.float affinity) → Typed context upper (.float affinity) →      Typed context (.uniform (.sample affinity) lower upper) (.float affinity)  | uniformMean : Typed context lower (.float affinity) → Typed context upper (.float affinity) →      Typed context (.uniform .mean lower upper) (.float affinity)  | gaussian : Typed context mean (.float affinity) → Typed context variance (.float .G) →      Typed context (.gaussian (.sample affinity) mean variance) (.float affinity)  | gaussianMean : Typed context mean (.float affinity) → Typed context variance (.float .G) →      Typed context (.gaussian .mean mean variance) (.float affinity)  | poisson : Typed context rate (.float affinity) →      Typed context (.poisson (.sample affinity) rate) (.float affinity)  | poissonMean : Typed context rate (.float affinity) →      Typed context (.poisson .mean rate) (.float affinity)  | discrete : Typed context probabilities (.list (.float affinity)) →      Typed context (.discrete (.sample affinity) probabilities) (.float affinity)  | discreteMean : Typed context probabilities (.list (.float affinity)) →      Typed context (.discrete .mean probabilities) (.float affinity)  | bernoulli : Typed context probability (.float affinity) →      Typed context (.bernoulli (.sample affinity) probability) (.float affinity)  | bernoulliMean : Typed context probability (.float affinity) →      Typed context (.bernoulli .mean probability) (.float affinity)  | exponential : Typed context rate (.float .G) →      Typed context (.exponential (.sample affinity) rate) (.float affinity)  | exponentialMean : Typed context rate (.float .G) →      Typed context (.exponential .mean rate) (.float affinity)  | beta : Typed context alpha (.float .G) → Typed context beta (.float .G) →      Typed context (.beta (.sample affinity) alpha beta) (.float affinity)  | betaMean : Typed context alpha (.float .G) → Typed context beta (.float .G) →      Typed context (.beta .mean alpha beta) (.float affinity)  | gamma : Typed context shape (.float affinity) → Typed context rate (.float .G) →      Typed context (.gamma (.sample affinity) shape rate) (.float affinity)  | gammaMean : Typed context shape (.float affinity) → Typed context rate (.float .G) →      Typed context (.gamma .mean shape rate) (.float affinity)end Determinize.Spec.Paper