import Determinize.Proof.Traces.Labelsimport Determinize.Proof.Traces.Detailedimport Determinize.Proof.Semantics.Ordinary/-!# Detailed trace semantics as kernelsThe one-step law together with its recorded event (`record`, `tracedStepKernel`), the jointlaw of a detailed trace and output at an exact depth as a measurable kernel (`exactKernel`,equal to `exactMeasure`), and trace erasure (`correspondence`): forgetting the trace recoversthe ordinary output semantics.-/namespace Determinize.Proof.StepTracesopen MeasureTheory ProbabilityTheory Determinize.Spec.Paper Determinize.Proof.StepTracesopen Determinize.Proof.Paperopen scoped ProbabilityTheorynoncomputable sectiontheorem measurable_trace_length : Measurable (List.length : Trace → Nat) := measurable_fst.comp (comap_measurable _)theorem measurable_trace_event (index : Nat) : Measurable (fun trace : Trace ↦ trace.getD index none) := by have coordinates : Measurable (fun trace : Trace ↦ (trace.length, fun i : Nat ↦ trace.getD i none)) := comap_measurable _ exact (measurable_pi_apply index).comp (measurable_snd.comp coordinates)theorem measurable_trace_cons : Measurable (fun pair : Event × Trace ↦ pair.1 :: pair.2) := by apply measurable_comap_iff.mpr apply Measurable.prodMk · exact (measurable_trace_length.comp measurable_snd).add_const 1 · apply Measurable.of_eval intro index cases index with | zero => exact measurable_fst | succ index => exact (measurable_trace_event index).comp measurable_sndtheorem measurable_trace_tail : Measurable (List.tail : Trace → Trace) := by apply measurable_comap_iff.mpr apply Measurable.prodMk · simpa using measurable_trace_length.sub_const 1 · apply Measurable.of_eval intro index simpa using measurable_trace_event (index + 1)theorem measurable_trace_head : Measurable (fun trace : Trace ↦ trace.headD none) := by have same : (fun trace : Trace ↦ trace.headD none) = fun trace ↦ trace.getD 0 none := by funext trace; cases trace <;> rfl rw [same] exact measurable_trace_event 0theorem measurable_prepend : Measurable (fun pair : Event × Output ↦ prepend pair.1 pair.2) := (measurable_trace_cons.comp (measurable_fst.prodMk (measurable_fst.comp measurable_snd))).prodMk (measurable_snd.comp measurable_snd)theorem map_bind {α β γ : Type*} [MeasurableSpace α] [MeasurableSpace β] [MeasurableSpace γ] (μ : Measure α) (kernel : Kernel α β) (f : β → γ) (hf : Measurable f) : (μ.bind kernel).map f = μ.bind (fun a ↦ (kernel a).map f) := by rw [Measure.map_comp μ kernel hf] exact congrArg _ (funext fun a ↦ Kernel.map_apply kernel hf a)theorem bind_map {α β γ : Type*} [MeasurableSpace α] [MeasurableSpace β] [MeasurableSpace γ] (μ : Measure α) (f : α → β) (hf : Measurable f) (kernel : Kernel β γ) : (μ.map f).bind kernel = μ.bind (fun a ↦ kernel (f a)) := by rw [← Measure.deterministic_comp_eq_map hf, Measure.comp_assoc, Kernel.comp_deterministic_eq_comap] rfl/-- A one-step expression kernel used to prove measurability of the direct trace evaluator. -/def record : Action → Measure (Event × Expr) | .next expression => Measure.dirac (none, expression) | .sample modeTag fiber continuation => fiber.map fun value ↦ (generationEvent modeTag value, continuation value) | .stuck => 0def recordKernel {α : Type*} [MeasurableSpace α] {action : α → Action} (family : MeasurableActionFamily α action) : SFiniteKernel α (Event × Expr) := match family with | .next (successor := successor) measurable => SFiniteKernel.deterministic (fun a ↦ (none, successor a)) (measurable_const.prodMk measurable) | .sample (site := site) (continuation := continuation) draw measurable => SFiniteKernel.mapWithInput draw (fun pair ↦ (generationEvent site pair.2, continuation pair)) (((measurable_generationEvent site).comp measurable_snd).prodMk measurable) | .stuck => SFiniteKernel.zero | @MeasurableActionFamily.piecewise _ _ _ _ measurableRegion _ _ trueFamily falseFamily => SFiniteKernel.piecewise measurableRegion (recordKernel trueFamily) (recordKernel falseFamily)theorem recordKernel_apply {α : Type*} [MeasurableSpace α] {action : α → Action} (family : MeasurableActionFamily α action) (parameter : α) : (recordKernel family).kernel parameter = record (action parameter) := by classical induction family with | next measurable => rfl | sample draw measurable => exact SFiniteKernel.mapWithInput_apply _ _ _ _ | stuck => rfl | @piecewise region _ measurableRegion whenTrue whenFalse trueFamily falseFamily ihTrue ihFalse => calc _ = @ite _ (parameter ∈ region) (Classical.propDecidable _) ((recordKernel trueFamily).kernel parameter) ((recordKernel falseFamily).kernel parameter) := rfl _ = _ := by by_cases member : parameter ∈ region · simpa only [Set.piecewise, ite_eq_left member] using ihTrue · simpa only [Set.piecewise, ite_eq_right member] using ihFalseopen scoped Classical indef recordSkeletonKernel (skeleton : Skeleton) : Kernel Expr (Event × Expr) := let family := MeasurableActionFamily.reduceFamily primitiveLaws (MeasurableFamily.skeletonFiber skeleton) let localKernel := recordKernel family Kernel.piecewise (measurableSet_skeletonFiber skeleton) (localKernel.kernel.comap (MeasurableActionFamily.toSkeletonFiber skeleton) (MeasurableActionFamily.measurable_toSkeletonFiber skeleton)) 0theorem recordSkeletonKernel_apply (skeleton : Skeleton) (expression : Expr) : recordSkeletonKernel skeleton expression = if expression.skeleton = skeleton then record (reduce expression) else 0 := by classical unfold recordSkeletonKernel rw [Kernel.piecewise_apply] by_cases member : expression.skeleton = skeleton · rw [ite_eq_left (show expression ∈ SkeletonFiber skeleton from member), ite_eq_left member, Kernel.comap_apply, recordKernel_apply, MeasurableActionFamily.toSkeletonFiber_coe_of_mem _ _ member] · rw [ite_eq_right (show expression ∉ SkeletonFiber skeleton from member), ite_eq_right member] rfltheorem isSFiniteKernel_recordSkeletonKernel (skeleton : Skeleton) : IsSFiniteKernel (recordSkeletonKernel skeleton) := by classical unfold recordSkeletonKernel let family := MeasurableActionFamily.reduceFamily primitiveLaws (MeasurableFamily.skeletonFiber skeleton) let := (recordKernel family).sfinite infer_instance/-- One reduction step with its recorded event, `record (reduce expression)`, as a measurablekernel (`tracedStepKernel_apply`). -/def tracedStepKernel : SFiniteKernel Expr (Event × Expr) := haveI := isSFiniteKernel_recordSkeletonKernel ⟨Kernel.sum recordSkeletonKernel, inferInstance⟩theorem tracedStepKernel_apply (expression : Expr) : tracedStepKernel.kernel expression = record (reduce expression) := by classical change (Kernel.sum recordSkeletonKernel) expression = _ rw [Kernel.sum_apply] ext set measurableSet rw [Measure.sum_apply _ measurableSet, tsum_eq_single expression.skeleton] · rw [recordSkeletonKernel_apply, ite_eq_left rfl] · intro skeleton different rw [recordSkeletonKernel_apply, ite_eq_right (Ne.symm different)] rfltheorem tracedStep_erasure (expression : Expr) : (record (reduce expression)).map Prod.snd = Determinize.Spec.Paper.stepMeasure expression := by unfold Determinize.Spec.Paper.stepMeasure generalize reduction : reduce expression = action cases action with | next next => simp [record, Action.measure, Measure.map_dirac' measurable_snd] | stuck => simp [record, Action.measure] | sample site fiber continuation => have measurable := (MeasurableActionFamily.stepKernel primitiveLaws).sample_continuation_measurable expression fiber continuation reduction rw [record, Measure.map_map measurable_snd (show Measurable (fun value ↦ (generationEvent site value, continuation value)) from (measurable_generationEvent site).prodMk measurable)] rfl/-- Extend an exact-depth kernel by one recorded step: run `previous` on the successor and putthe event in front of the trace. -/def successorKernel (previous : SFiniteKernel Expr (Output)) : SFiniteKernel (Event × Expr) (Output) := SFiniteKernel.mapWithInput (SFiniteKernel.pullback previous Prod.snd measurable_snd) (fun pair ↦ prepend pair.1.1 pair.2) (measurable_prepend.comp ((measurable_fst.comp measurable_fst).prodMk measurable_snd))theorem successorKernel_apply (previous : SFiniteKernel Expr (Output)) (entry : Event) (expression : Expr) : (successorKernel previous).kernel (entry, expression) = (previous.kernel expression).map (prepend entry) := by rw [successorKernel, SFiniteKernel.mapWithInput_apply, MeasurableActionFamily.pullback_apply]/-- `exactMeasure depth` as a measurable kernel (`exactKernel_apply`). -/def exactKernel : (depth : Nat) → SFiniteKernel Expr (Output) | 0 => SFiniteKernel.piecewise measurableSet_terminalFloatSet (SFiniteKernel.deterministic (fun e ↦ ([], terminalFloatValue e)) (measurable_const.prodMk measurable_terminalFloatValue)) SFiniteKernel.zero | depth + 1 => by let previous := exactKernel depth let next := successorKernel previous let := next.sfinite let := tracedStepKernel.sfinite exact SFiniteKernel.piecewise MeasurableActionFamily.measurableSet_valueSet SFiniteKernel.zero ⟨next.kernel ∘ₖ tracedStepKernel.kernel, inferInstance⟩theorem exactKernel_apply (depth : Nat) (expression : Expr) : (exactKernel depth).kernel expression = exactMeasure depth expression := by classical induction depth generalizing expression with | zero => unfold exactKernel SFiniteKernel.piecewise SFiniteKernel.deterministic SFiniteKernel.zero rw [Kernel.piecewise_apply] cases expression <;> try simp [terminalFloatSet, exactMeasure, terminalFloatValue, Kernel.deterministic_apply] | succ depth ih => unfold exactKernel SFiniteKernel.piecewise SFiniteKernel.zero rw [Kernel.piecewise_apply] by_cases value : expression.isValue = true · simp [MeasurableActionFamily.valueSet, value, exactMeasure] · have notMember : expression ∉ MeasurableActionFamily.valueSet := value rw [ite_eq_right notMember, exactMeasure, ite_eq_right value, Kernel.comp_apply, tracedStepKernel_apply] cases reduction : reduce expression with | next next => rw [record, Measure.dirac_bind (successorKernel (exactKernel depth)).kernel.measurable, successorKernel_apply, ih] | sample modeTag fiber continuation => have measurable := (MeasurableActionFamily.stepKernel primitiveLaws).sample_continuation_measurable expression fiber continuation reduction rw [record, bind_map _ _ ((measurable_generationEvent modeTag).prodMk measurable)] apply Measure.bind_congr_right filter_upwards [] with value rw [successorKernel_apply, ih] | stuck => simp [record]theorem exact_succ_kernel (depth : Nat) (expression : Expr) (notValue : expression.isValue ≠ true) : exactMeasure (depth + 1) expression = (record (reduce expression)).bind (successorKernel (exactKernel depth)).kernel := by classical rw [← exactKernel_apply, exactKernel, SFiniteKernel.piecewise, Kernel.piecewise_apply, ite_eq_right (show expression ∉ MeasurableActionFamily.valueSet from notValue), Kernel.comp_apply, tracedStepKernel_apply]theorem exact_erasure (step : StepKernel) (depth : Nat) (expression : Expr) : (exactMeasure depth expression).map Prod.snd = exactOutputMeasure step depth expression := by induction depth generalizing expression with | zero => cases expression <;> try simp only [exactMeasure, Measure.map_zero, exactOutputMeasure] case real value => simp [Measure.map_dirac' measurable_snd] | succ depth ih => by_cases value : expression.isValue = true · simp [exactMeasure, exactOutputMeasure, value] · rw [exact_succ_kernel depth expression value, map_bind _ _ _ measurable_snd, exactOutputMeasure, ite_eq_right value, step.kernel_eq_stepMeasure, ← tracedStep_erasure expression] have ordinaryEq : exactOutputMeasure step depth = MeasurableActionFamily.exactOutputKernel step depth := by funext next exact (MeasurableActionFamily.exactOutputKernel_apply step depth next).symm rw [ordinaryEq, bind_map _ _ measurable_snd (MeasurableActionFamily.exactOutputKernel step depth)] apply Measure.bind_congr_right filter_upwards [] with next rw [successorKernel_apply, exactKernel_apply, Measure.map_map measurable_snd (show Measurable (prepend next.1) from measurable_prepend.comp (measurable_const.prodMk measurable_id))] exact (ih next.2).trans (MeasurableActionFamily.exactOutputKernel_apply step depth next.2).symmtheorem correspondence : Determinize.Proof.StepTraces.Correspondence := by intro program let step := MeasurableActionFamily.stepKernel primitiveLaws rw [jointMeasure, Measure.map_sum measurable_snd.aemeasurable] change Measure.sum (fun depth ↦ (exactMeasure depth program).map Prod.snd) = _ simp_rw [exact_erasure step] unfold Determinize.Spec.Paper.bigStepMeasure congr 1 funext depth exact Determinize.Proof.Paper.exactOutputMeasure_eq depth programendend Determinize.Proof.StepTraces