import Determinize.Spec.Syntaximport Mathlib.MeasureTheory.Measure.GiryMonad/-!# Paper operational semanticsThe reducer evaluates the operands of a primitive left to right and then draws from its fiber.Division by zero is stuck. The output semantics integrates sampled reals directly, withoutmeasures on expressions.-/namespace Determinize.Spec.Paperopen MeasureTheory ProbabilityTheoryopen scoped ENNReal ProbabilityTheory/-- A pointwise reduction action. -/inductive Action where | next (expression : Expr) | sample (site : DistributionAction × Op) (fiber : Measure ℝ) (continuation : ℝ → Expr) | stuck/-- Place the result of an action in an evaluation context: the successor expression, or everycontinuation of a sample. -/def Action.wrap (context : Expr → Expr) : Action → Action | .next expression => .next (context expression) | .sample site fiber continuation => .sample site fiber (context ∘ continuation) | .stuck => .stuck/-- The value of a real literal; `none` for any other expression. -/def realValue? : Expr → Option ℝ | .real value => some value | _ => none/-- Read an evaluated list of numeric probabilities. -/def realListValue? : Expr → Option (List ℝ) | .nil => some [] | .cons head tail => match realValue? head, realListValue? tail with | some value, some values => some (value :: values) | _, _ => none | _ => none/-- Conventional left-to-right call-by-value reduction, with values absorbing. -/noncomputable def reduce : Expr → Action | .bvar _ => .stuck | .reject => .next .reject | .unit => .next .unit | expression@(.bool _) => .next expression | expression@(.real _) => .next expression | expression@(.lam _) => .next expression | expression@(.fix _) => .next expression | expression@.nil => .next expression | expression@(.pair left right) => if left.isValue then if right.isValue then .next expression else (reduce right).wrap (fun next ↦ .pair left next) else (reduce left).wrap (fun next ↦ .pair next right) | expression@(.inl operand) => if operand.isValue then .next expression else (reduce operand).wrap .inl | expression@(.inr operand) => if operand.isValue then .next expression else (reduce operand).wrap .inr | expression@(.cons head tail) => if head.isValue then if tail.isValue then .next expression else (reduce tail).wrap (fun next ↦ .cons head next) else (reduce head).wrap (fun next ↦ .cons next tail) | .app function argument => if function.isValue then if argument.isValue then match function with | .lam body => .next (body.substHead argument) | fix@(.fix body) => .next (body.substTwo argument fix) | _ => .stuck else (reduce argument).wrap (fun next ↦ .app function next) else (reduce function).wrap (fun next ↦ .app next argument) | .fst pair => if pair.isValue then match pair with | .pair left _ => .next left | _ => .stuck else (reduce pair).wrap .fst | .snd pair => if pair.isValue then match pair with | .pair _ right => .next right | _ => .stuck else (reduce pair).wrap .snd | .matchSum scrutinee left right => if scrutinee.isValue then match scrutinee with | .inl value => .next (left.substHead value) | .inr value => .next (right.substHead value) | _ => .stuck else (reduce scrutinee).wrap (fun next ↦ .matchSum next left right) | .matchList scrutinee nilCase consCase => if scrutinee.isValue then match scrutinee with | .nil => .next nilCase | .cons head tail => .next (consCase.substTwo head tail) | _ => .stuck else (reduce scrutinee).wrap (fun next ↦ .matchList next nilCase consCase) | .ite condition thenBranch elseBranch => if condition.isValue then match condition with | .bool true => .next thenBranch | .bool false => .next elseBranch | _ => .stuck else (reduce condition).wrap (fun next ↦ .ite next thenBranch elseBranch) | .letE value body => if value.isValue then .next (body.substHead value) else (reduce value).wrap (fun next ↦ .letE next body) | .neg body => if body.isValue then match body with | .real value => .next (.real (-value)) | _ => .stuck else (reduce body).wrap .neg | .add left right => if left.isValue then if right.isValue then match realValue? left, realValue? right with | some x, some y => .next (.real (x + y)) | _, _ => .stuck else (reduce right).wrap (.add left) else (reduce left).wrap (fun next ↦ .add next right) | .mul left right => if left.isValue then if right.isValue then match realValue? left, realValue? right with | some x, some y => .next (.real (x * y)) | _, _ => .stuck else (reduce right).wrap (.mul left) else (reduce left).wrap (fun next ↦ .mul next right) | .div left right => if left.isValue then if right.isValue then match realValue? left, realValue? right with | some x, some y => if y = 0 then .stuck else .next (.real (x / y)) | _, _ => .stuck else (reduce right).wrap (.div left) else (reduce left).wrap (fun next ↦ .div next right) | .lt left right => if left.isValue then if right.isValue then match realValue? left, realValue? right with | some x, some y => .next (.bool (x < y)) | _, _ => .stuck else (reduce right).wrap (.lt left) else (reduce left).wrap (fun next ↦ .lt next right) | .uniform action lower upper => if lower.isValue then if upper.isValue then match realValue? lower, realValue? upper with | some a, some b => .sample (action, .uniform) (uniformFiber action a b) .real | _, _ => .stuck else (reduce upper).wrap (.uniform action lower) else (reduce lower).wrap (fun next ↦ .uniform action next upper) | .gaussian action mean variance => if mean.isValue then if variance.isValue then match realValue? mean, realValue? variance with | some m, some v => .sample (action, .gaussian) (gaussianFiber action m v) .real | _, _ => .stuck else (reduce variance).wrap (.gaussian action mean) else (reduce mean).wrap (fun next ↦ .gaussian action next variance) | .poisson action rate => if rate.isValue then match realValue? rate with | some r => .sample (action, .poisson) (poissonFiber action r) .real | none => .stuck else (reduce rate).wrap (.poisson action) | .discrete action probabilities => if probabilities.isValue then match realListValue? probabilities with | some values => .sample (action, .discrete values.length) (discreteFiber action values) .real | none => .stuck else (reduce probabilities).wrap (.discrete action) | .bernoulli action probability => if probability.isValue then match realValue? probability with | some r => .sample (action, .bernoulli) (bernoulliFiber action r) .real | none => .stuck else (reduce probability).wrap (.bernoulli action) | .exponential action rate => if rate.isValue then match realValue? rate with | some r => .sample (action, .exponential) (exponentialFiber action r) .real | none => .stuck else (reduce rate).wrap (.exponential action) | .beta action alpha beta => if alpha.isValue then if beta.isValue then match realValue? alpha, realValue? beta with | some a, some b => .sample (action, .beta) (betaFiber action a b) .real | _, _ => .stuck else (reduce beta).wrap (.beta action alpha) else (reduce alpha).wrap (fun next ↦ .beta action next beta) | .gamma action shape rate => if shape.isValue then if rate.isValue then match realValue? shape, realValue? rate with | some k, some r => .sample (action, .gamma) (gammaFiber action k r) .real | _, _ => .stuck else (reduce rate).wrap (.gamma action shape) else (reduce shape).wrap (fun next ↦ .gamma action next rate)/-- Output from executions first returning a real at exactly `depth` reduction steps. -/noncomputable def outputMeasureAt : Nat → Expr → Measure ℝ | 0, .real value => Measure.dirac value | 0, _ => 0 | depth + 1, expression => if expression.isValue then 0 else match reduce expression with | .next next => outputMeasureAt depth next | .sample _ fiber continuation => fiber.bind fun value ↦ outputMeasureAt depth (continuation value) | .stuck => 0/-- The output law, without conditioning on termination. -/noncomputable def bigStepMeasure (program : Expr) : Measure ℝ := Measure.sum fun depth ↦ outputMeasureAt depth program/-- Probability of executing `depth` steps and still not being a value.Stuck executions contribute zero; rejection keeps taking steps. -/noncomputable def runningProbabilityAt : Nat → Expr → ℝ≥0∞ | 0, expression => if expression.isValue then 0 else 1 | depth + 1, expression => if expression.isValue then 0 else match reduce expression with | .next next => runningProbabilityAt depth next | .sample _ fiber continuation => ∫⁻ value, runningProbabilityAt depth (continuation value) ∂fiber | .stuck => 0/-- Probability of continuing forever, including rejection's infinite self-loop. -/noncomputable def divergenceProbability (program : Expr) : ℝ≥0∞ := ⨅ depth, runningProbabilityAt depth program/-- Operations remain within their domains through the given reduction depth.For typed programs, failures are invalid distribution parameters or division by zero. -/def DomainSafeAt : Nat → Expr → Prop | 0, _ => True | fuel + 1, expression => if expression.isValue then True else match reduce expression with | .next next => DomainSafeAt fuel next | .sample _ fiber continuation => fiber Set.univ = 1 ∧ ∀ᵐ value ∂fiber, DomainSafeAt fuel (continuation value) | .stuck => False/-- Every operation reached at a finite depth has valid arguments almost surely. -/def DomainSafe (program : Expr) : Prop := ∀ fuel, DomainSafeAt fuel programend Determinize.Spec.Paper