Source lean/Determinize/Proof/Traces/Semantics.lean
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