import Determinize.Proof.Primitives.Lawsimport Determinize.Proof.Symbolic.Environmentimport Determinize.Spec.Semanticsimport Determinize.Proof.Semantics.ExpressionSpace/-!# Semantic objects used by the proofThis module defines the measurable skeleton representation, symbolic samplehistories, certified one-step kernel, and exact-depth output semantics. The operationalreducer and operation-domain safety are reviewer-facing definitions in `Spec.Semantics`.-/namespace Determinize.Spec.Paperopen MeasureTheory ProbabilityTheoryopen scoped ENNReal ProbabilityTheory/-- Interpret one reduction action as a measure of successor expressions. -/noncomputable def Action.measure : Action → Measure Expr | .next expression => Measure.dirac expression | .sample _ fiber continuation => fiber.map continuation | .stuck => 0/-- The measurable transition used by the proof's expression kernels. -/noncomputable def stepMeasure (expression : Expr) : Measure Expr := (reduce expression).measure@[match_pattern] abbrev Skeleton.real : Skeleton := Expr.real ()namespace Exprdef realArity {Literal : Type} : Expr Literal → Nat | .real _ => 1 | .lam x | .fix x | .fst x | .snd x | .inl x | .inr x | .neg x => x.realArity | .app l r | .pair l r | .cons l r | .add l r | .mul l r | .div l r | .lt l r => l.realArity + r.realArity | .matchSum x l r | .ite x l r => x.realArity + l.realArity + r.realArity | .matchList x n c => x.realArity + n.realArity + c.realArity | .letE x b => x.realArity + b.realArity | .uniform _ l r | .gaussian _ l r | .beta _ l r | .gamma _ l r => l.realArity + r.realArity | .poisson _ x | .bernoulli _ x | .exponential _ x | .discrete _ x => x.realArity | _ => 0end Exprend Determinize.Spec.Papernamespace Determinize.Proof.Paperopen MeasureTheory ProbabilityTheoryopen Determinize.Spec.Paperopen scoped ENNReal ProbabilityTheorynamespace Symbolic/-- An affine expression in the ordered E samples. -/abbrev Affine (sampleCount : Nat) := ℝ × (Fin sampleCount → ℝ)def Affine.eval (expression : Affine sampleCount) (environment : Env sampleCount) : ℝ := expression.1 + ∑ i, expression.2 i * environment inamespace Affine/-! The linear structure of affine expressions: negation, sum and scaling are pointwise; thenewest sample is prepended with `Fin.cons` and dropped with `Fin.tail`. -/def neg (expression : Affine n) : Affine n := (-expression.1, fun index ↦ -expression.2 index)def add (left right : Affine n) : Affine n := (left.1 + right.1, fun index ↦ left.2 index + right.2 index)def smul (scalar : ℝ) (expression : Affine n) : Affine n := (scalar * expression.1, fun index ↦ scalar * expression.2 index)/-- The same expression over one more sample, which it does not use. -/def weaken (expression : Affine n) : Affine (n + 1) := (expression.1, Fin.cons 0 expression.2)/-- The newest sample itself. -/def fresh (n : Nat) : Affine (n + 1) := (0, Fin.cons 1 0)/-- Drop the coefficient of the newest sample. -/def tail (expression : Affine (n + 1)) : Affine n := (expression.1, Fin.tail expression.2)@[simp] theorem eval_neg (expression : Affine n) (environment : Env n) : (neg expression).eval environment = -expression.eval environment := by simp only [neg, eval, neg_mul, Finset.sum_neg_distrib] ring@[simp] theorem eval_add (left right : Affine n) (environment : Env n) : (add left right).eval environment = left.eval environment + right.eval environment := by simp only [add, eval, add_mul, Finset.sum_add_distrib] ringtheorem eval_smul (scalar : ℝ) (expression : Affine n) (environment : Env n) : (smul scalar expression).eval environment = scalar * expression.eval environment := by simp only [smul, eval, mul_assoc, ← Finset.mul_sum] ring@[simp] theorem eval_weaken (expression : Affine n) (head : ℝ) (environment : Env n) : (weaken expression).eval (Env.cons head environment) = expression.eval environment := by simp only [weaken, eval, Fin.sum_univ_succ, Env.cons_zero, Env.cons_succ, Fin.cons_zero, Fin.cons_succ, zero_mul, zero_add]@[simp] theorem eval_fresh (n : Nat) (head : ℝ) (environment : Env n) : (fresh n).eval (Env.cons head environment) = head := by simp only [fresh, eval, Fin.sum_univ_succ, Env.cons_zero, Env.cons_succ, Fin.cons_zero, Fin.cons_succ, Pi.zero_apply, one_mul, zero_mul, Finset.sum_const_zero, add_zero, zero_add]end Affine/-- Ordered symbolic E-sample environment from the paper. -/inductive SampleEnv (laws : Determinize.Proof.Paper.PrimitiveLaws) : Nat → Type where | nil : SampleEnv laws 0 | snoc (history : SampleEnv laws n) (op : Determinize.Spec.Paper.Op) (affineArgs : Fin (Determinize.Spec.Paper.affineArity op) → Affine n) (generalArgs : Fin (Determinize.Spec.Paper.generalArity op) → ℝ) : SampleEnv laws (n + 1)namespace SampleEnvnoncomputable def actualMeasure (laws : Determinize.Proof.Paper.PrimitiveLaws) : {n : Nat} → SampleEnv laws n → Measure (Env n) | 0, .nil => Measure.dirac Env.empty | _ + 1, .snoc history op affineArgs generalArgs => (actualMeasure laws history).bind fun environment ↦ (laws.kernel op (fun i ↦ (affineArgs i).eval environment, generalArgs)).map (fun value ↦ Env.cons value environment)/-- Every recorded primitive call is in-domain almost surely under its prefix law. -/noncomputable def DomainSafe (laws : Determinize.Proof.Paper.PrimitiveLaws) : {n : Nat} → SampleEnv laws n → Prop | 0, .nil => True | _ + 1, .snoc history op affineArgs generalArgs => DomainSafe laws history ∧ ∀ᵐ environment ∂actualMeasure laws history, Determinize.Spec.Paper.InDomain op (fun i ↦ (affineArgs i).eval environment, generalArgs)noncomputable def meanEnvironment (laws : Determinize.Proof.Paper.PrimitiveLaws) : {n : Nat} → SampleEnv laws n → Env n | 0, .nil => Env.empty | _ + 1, .snoc history op affineArgs generalArgs => let environment := meanEnvironment laws history let params := (fun i ↦ (affineArgs i).eval environment, generalArgs) Env.cons (Determinize.Spec.Paper.meanValue op params) environmentend SampleEnvend Symbolic/-- Measurability and subprobability laws for the specified pointwise reduction. -/structure StepKernel where kernel : Kernel Expr Expr kernel_eq_stepMeasure : ∀ expression, kernel expression = stepMeasure expression kernel_sfinite : IsSFiniteKernel kernel mass_le_one : ∀ expression, kernel expression Set.univ ≤ 1 sample_continuation_measurable : ∀ expression {site} fiber continuation, reduce expression = .sample site fiber continuation → Measurable continuation terminal_measurable : MeasurableSet terminalFloatSet terminal_value_measurable : Measurable terminalFloatValuenoncomputable def nStepMeasure (stepKernel : StepKernel) : Nat → Expr → Measure Expr | 0, expression => Measure.dirac expression | fuel + 1, expression => stepKernel.kernel ∘ₘ nStepMeasure stepKernel fuel expression/-- Output that terminates for the first time at exactly this reduction depth. -/noncomputable def exactOutputMeasure (stepKernel : StepKernel) : Nat → Expr → Measure ℝ | 0, .real value => Measure.dirac value | 0, _ => 0 | fuel + 1, expression => if expression.isValue then 0 else (stepKernel.kernel expression).bind (exactOutputMeasure stepKernel fuel)noncomputable def cumulativeOutputMeasure (stepKernel : StepKernel) (fuel : Nat) (program : Expr) : Measure ℝ := ((nStepMeasure stepKernel fuel program).restrict terminalFloatSet).map terminalFloatValue/-- The paper's big-step meaning is the pointwise limit of absorbing value mass. -/noncomputable def bigStepMeasure (stepKernel : StepKernel) (program : Expr) : Measure ℝ := ⨆ fuel, cumulativeOutputMeasure stepKernel fuel programend Determinize.Proof.Paper