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