Ordinary semantics and source typing #
This file proves measurability of the direct output evaluator using expression kernels and transports source typing to the symbolic language.
theorem
Determinize.Proof.Paper.cumulativeKernel_apply
(fuel : ℕ)
(expression : Spec.Paper.Expr)
:
(Determinize.Proof.Paper.cumulativeKernel✝ fuel) expression = Cumulative.outputMeasure fuel expression
The direct evaluator is represented by a measurable kernel in its expression input.
theorem
Determinize.Proof.Paper.cumulativeOutputMeasure_eq
(fuel : ℕ)
(expression : Spec.Paper.Expr)
:
cumulativeOutputMeasure Determinize.Proof.Paper.paperStepKernel✝ fuel expression = Cumulative.outputMeasure fuel expression
theorem
Determinize.Proof.Paper.exactOutputMeasure_eq
(depth : ℕ)
(expression : Spec.Paper.Expr)
:
exactOutputMeasure Determinize.Proof.Paper.paperStepKernel✝ depth expression = Spec.Paper.outputMeasureAt depth expression
theorem
Determinize.Proof.Paper.cumulativeOutputMeasure_eq_sum
(fuel : ℕ)
(expression : Spec.Paper.Expr)
:
Cumulative.outputMeasure fuel expression = ∑ depth ∈ Finset.range (fuel + 1), Spec.Paper.outputMeasureAt depth expression
theorem
Determinize.Proof.Paper.bigStepMeasure_eq
(expression : Spec.Paper.Expr)
:
bigStepMeasure Determinize.Proof.Paper.paperStepKernel✝ expression = Spec.Paper.bigStepMeasure expression
theorem
Determinize.Proof.Paper.measurable_sample_cumulative
(fuel : ℕ)
(expression : Spec.Paper.Expr)
(site : Spec.Paper.DistributionAction × Spec.Paper.Op)
(fiber : MeasureTheory.Measure ℝ)
(continuation : ℝ → Spec.Paper.Expr)
(action : Spec.Paper.reduce expression = Spec.Paper.Action.sample site fiber continuation)
:
Measurable fun (x : ℝ) => Cumulative.outputMeasure fuel (continuation x)
theorem
Determinize.Proof.Paper.direct_cumulative_mono
(expression : Spec.Paper.Expr)
:
Monotone fun (fuel : ℕ) => Cumulative.outputMeasure fuel expression
theorem
Determinize.Proof.Paper.typed_determinize
{context : List Spec.Paper.Ty}
{expression : Spec.Paper.Expr}
{ty : Spec.Paper.Ty}
(typed : Spec.Paper.Typed context expression ty)
:
Spec.Paper.Typed context expression.determinize ty
theorem
Determinize.Proof.Paper.domainSafe_determinize
{source : Spec.Paper.Expr}
(typed : Spec.Paper.Typed [] source (Spec.Paper.Ty.float Spec.Paper.Affinity.E))
(safe : Spec.Paper.DomainSafe source)
:
Spec.Paper.DomainSafe source.determinize
Typing preservation's companion for validity: the determinization of a well-typed source that does not get stuck does not get stuck either.