Source lean/Determinize/Proof/Semantics/Ordinary.lean
import Determinize.Spec.Expectationimport Determinize.Proof.Semantics.Cumulativeimport Determinize.Proof.Primitives.Kernelsimport Determinize.Proof.Symbolic.Soundness/-!# Ordinary semantics and source typingThis file proves measurability of the direct output evaluator using expressionkernels and transports source typing to the symbolic language.-/namespace Determinize.Proof.Paperopen MeasureTheory ProbabilityTheoryopen scoped ProbabilityTheoryopen Determinize.Spec.Paperprivate noncomputable abbrev paperStepKernel := MeasurableActionFamily.stepKernel primitiveLawsprivate noncomputable abbrev cumulativeKernel (fuel : Nat) :=  (MeasurableActionFamily.exactOutputKernel paperStepKernel 0) ∘ₖ    (MeasurableActionFamily.nStepKernelPack paperStepKernel fuel).kernel/-- The direct evaluator is represented by a measurable kernel in its expression input. -/theorem cumulativeKernel_apply (fuel : Nat) (expression : Expr) :    cumulativeKernel fuel expression =      Determinize.Proof.Cumulative.outputMeasure fuel expression := by  symm  induction fuel generalizing expression with  | zero =>    simp only [cumulativeKernel, MeasurableActionFamily.nStepKernelPack_zero_kernel,      Kernel.comp_id, MeasurableActionFamily.exactOutputKernel_apply]    cases expression <;> try rfl  | succ fuel ih =>    rw [cumulativeKernel, MeasurableActionFamily.cumulativeKernel_succ,      Kernel.comp_apply, paperStepKernel.kernel_eq_stepMeasure]    change Determinize.Proof.Cumulative.outputMeasure (fuel + 1) expression =      (reduce expression).measure.bind (cumulativeKernel fuel)    cases reduction : reduce expression with    | next next =>      simp only [Determinize.Proof.Cumulative.outputMeasure, reduction,        Action.measure, Measure.dirac_bind (cumulativeKernel fuel).measurable]      exact ih next    | sample modeTag fiber continuation =>      simp only [Determinize.Proof.Cumulative.outputMeasure, reduction, Action.measure]      simp_rw [ih]      have measurable := paperStepKernel.sample_continuation_measurable        expression fiber continuation reduction      ext set hs      change (fiber.bind ((cumulativeKernel fuel) ∘ continuation)) set = _      rw [Measure.bind_apply hs ((cumulativeKernel fuel).measurable.comp measurable).aemeasurable,        Measure.bind_apply hs (cumulativeKernel fuel).aemeasurable,        lintegral_map ((cumulativeKernel fuel).measurable_coe hs) measurable]      rfl    | stuck => simp [Determinize.Proof.Cumulative.outputMeasure, reduction, Action.measure]theorem cumulativeOutputMeasure_eq (fuel : Nat) (expression : Expr) :    Determinize.Proof.Paper.cumulativeOutputMeasure paperStepKernel fuel expression =      Determinize.Proof.Cumulative.outputMeasure fuel expression := by  rw [MeasurableActionFamily.cumulativeOutputMeasure_eq_kernel]  exact cumulativeKernel_apply fuel expressiontheorem exactOutputMeasure_eq (depth : Nat) (expression : Expr) :    Determinize.Proof.Paper.exactOutputMeasure paperStepKernel depth expression =      Determinize.Spec.Paper.outputMeasureAt depth expression := by  rw [← MeasurableActionFamily.exactOutputKernel_apply]  symm  induction depth generalizing expression with  | zero =>    rw [MeasurableActionFamily.exactOutputKernel_apply]    cases expression <;> rfl  | succ depth ih =>    by_cases value : expression.isValue = true    · simp [Determinize.Spec.Paper.outputMeasureAt, value,        MeasurableActionFamily.exactOutputKernel_succ_apply_of_value]    · rw [Determinize.Spec.Paper.outputMeasureAt, ite_eq_right value,        MeasurableActionFamily.exactOutputKernel_succ_apply_of_not_value          paperStepKernel depth expression value,        Kernel.comp_apply, paperStepKernel.kernel_eq_stepMeasure, stepMeasure]      cases reduction : reduce expression with      | next next =>        simp only [Action.measure,          Measure.dirac_bind            (MeasurableActionFamily.exactOutputKernel paperStepKernel depth).measurable]        exact ih next      | sample site fiber continuation =>        simp only [Action.measure]        simp_rw [ih]        have measurable := paperStepKernel.sample_continuation_measurable          expression fiber continuation reduction        ext set hs        change (fiber.bind          ((MeasurableActionFamily.exactOutputKernel paperStepKernel depth) ∘ continuation)) set = _        rw [Measure.bind_apply hs            ((MeasurableActionFamily.exactOutputKernel paperStepKernel depth).measurable.comp              measurable).aemeasurable,          Measure.bind_apply hs            (MeasurableActionFamily.exactOutputKernel paperStepKernel              depth).measurable.aemeasurable,          lintegral_map            ((MeasurableActionFamily.exactOutputKernel paperStepKernel depth).measurable_coe hs)              measurable]        rfl      | stuck => simp [Action.measure]theorem cumulativeOutputMeasure_eq_sum (fuel : Nat) (expression : Expr) :    Cumulative.outputMeasure fuel expression =      ∑ depth ∈ Finset.range (fuel + 1),          Determinize.Spec.Paper.outputMeasureAt depth expression := by  rw [← cumulativeOutputMeasure_eq,    MeasurableActionFamily.cumulativeOutputMeasure_eq_finsetSum]  simp_rw [exactOutputMeasure_eq]theorem bigStepMeasure_eq (expression : Expr) :    Determinize.Proof.Paper.bigStepMeasure paperStepKernel expression =      Determinize.Spec.Paper.bigStepMeasure expression := by  rw [MeasurableActionFamily.bigStepMeasure_eq_sum_exactOutputMeasure]  simp_rw [exactOutputMeasure_eq]  rfltheorem bigStepMeasure_eq_iSup_cumulative (expression : Expr) :    Determinize.Spec.Paper.bigStepMeasure expression =      ⨆ fuel, Cumulative.outputMeasure fuel expression := by  rw [← bigStepMeasure_eq]  unfold Determinize.Proof.Paper.bigStepMeasure  exact iSup_congr fun fuel ↦ cumulativeOutputMeasure_eq fuel expressiontheorem measurable_direct_cumulative (fuel : Nat) :    Measurable (Determinize.Proof.Cumulative.outputMeasure fuel) := by  have equality : (fun expression ↦ cumulativeKernel fuel expression) =      Determinize.Proof.Cumulative.outputMeasure fuel := funext (cumulativeKernel_apply fuel)  rw [← equality]  exact (cumulativeKernel fuel).measurabletheorem measurable_sample_cumulative (fuel : Nat) (expression : Expr)    (site : DistributionAction × Op) (fiber : Measure ℝ) (continuation : ℝ → Expr)    (action : reduce expression = .sample site fiber continuation) :    Measurable (fun x ↦ Determinize.Proof.Cumulative.outputMeasure fuel (continuation x)) :=  (measurable_direct_cumulative fuel).comp    (paperStepKernel.sample_continuation_measurable expression fiber continuation action)theorem direct_cumulative_mono (expression : Expr) :    Monotone (fun fuel ↦ Determinize.Proof.Cumulative.outputMeasure fuel expression) := by  apply monotone_nat_of_le_succ  intro fuel  rw [← cumulativeOutputMeasure_eq, ← cumulativeOutputMeasure_eq,    MeasurableActionFamily.cumulativeOutputMeasure_eq_finsetSum,    MeasurableActionFamily.cumulativeOutputMeasure_eq_finsetSum]  conv_rhs => rw [Finset.sum_range_succ]  exact Measure.le_add_right le_rfltheorem typed_determinize    (typed : Determinize.Spec.Paper.Typed context expression ty) :    Determinize.Spec.Paper.Typed context expression.determinize ty := by  induction typed with  | sub _ h ih => exact ih.sub h  | _ =>    simp only [Expr.determinize, DistributionAction.determinize]    try cases ‹Affinity›    all_goals aesop (add unsafe constructors Determinize.Spec.Paper.Typed)/-- Typing preservation's companion for validity: the determinization of a well-typed source thatdoes not get stuck does not get stuck either. -/theorem domainSafe_determinize (typed : Typed [] source (.float .E))    (safe : DomainSafe source) : DomainSafe source.determinize :=  SymbolicSoundness.TargetSafety.determinize_domainSafe_of_typed_source primitiveLaws    (MeasurableActionFamily.stepKernel primitiveLaws) source typed safeend Determinize.Proof.Paper