Source lean/Determinize/Proof/Traces/Detailed.lean
import Determinize.Spec.Semanticsimport Determinize.Spec.Traces.Semanticsimport Mathlib.MeasureTheory.Constructions.BorelSpace.Basicimport Mathlib.Logic.Equiv.Optionimport Mathlib.Probability.Kernel.Composition.MeasureCompProdimport Mathlib.MeasureTheory.Integral.Bochner.Basic/-!# Internal traces with one entry per reduction stepA trace records one entry per reduction step: a generation-affinity primitive andits sampled value, or `none` for a step without a generation-affinity draw. Itslength is the first termination depth. Expectation-affinity sampled values are not recorded.-/namespace Determinize.Proof.StepTracesopen MeasureTheory ProbabilityTheory Determinize.Spec.Paperabbrev Event := Option (Op × ℝ)instance : MeasurableSpace Event :=  MeasurableSpace.comap (Equiv.optionEquivSumPUnit.{0} (Op × ℝ)) inferInstanceabbrev Trace := List Eventabbrev Output := Trace × ℝ/-- Measurability is generated by trace length and individual events. -/instance : MeasurableSpace Trace :=  MeasurableSpace.comap (fun trace : Trace ↦    (trace.length, fun index : Nat ↦ trace.getD index none)) inferInstancedef generationEvent : DistributionAction × Op → ℝ → Event  | (.sample .G, op), value => some (op, value)  | _, _ => nonedef prepend (entry : Event) (output : Output) : Output :=  (entry :: output.1, output.2)/-- Joint trace/output law of executions first returning a real at exactly `depth`. -/noncomputable def exactMeasure : Nat → Expr → Measure Output  | 0, .real value => Measure.dirac ([], value)  | 0, _ => 0  | depth + 1, expression =>    if expression.isValue then 0    else match reduce expression with      | .next next => (exactMeasure depth next).map (prepend none)      | .sample modeTag fiber continuation => fiber.bind fun value ↦          (exactMeasure depth (continuation value)).map (prepend (generationEvent modeTag value))      | .stuck => 0/-- Joint operational law of terminating traces and returned expectation-affinity reals. -/noncomputable def jointMeasure (program : Expr) : Measure (Trace × ℝ) :=  Measure.sum fun depth ↦ exactMeasure depth program/-- Erasing terminating traces recovers the ordinary output semantics. -/def Correspondence : Prop :=  ∀ program : Expr, (jointMeasure program).map Prod.snd = bigStepMeasure programend Determinize.Proof.StepTraces