Documentation

PolyFun.Control.Semantics.Measure

Pushforwards of certified meanings #

A certified meaning f : CertifiedMeaning input output agrees with its native implementation on every encoded input: f.meaning (input x) = output (f.implementation x). Pushing a measure on native inputs forward along the encoded meaning f.meaning ∘ input therefore gives the encoding of the implementation's pushforward (Control.Semantics.CertifiedMeaning.map_meaning). A correspondence on an admissible set gives the same equation when almost every input is admissible (Control.Semantics.CorrespondsOn.map_meaning_ae).

A decoded certificate, whose output encoding is DomainResult.valueEmbedding, returns a value at every input. Pushed forward along its encoded meaning, a measure on native inputs therefore has the implementation's pushforward as its values and no failure mass (Control.Semantics.CertifiedMeaning.success_map_meaning, Control.Semantics.CertifiedMeaning.failureMass_map_meaning). A correspondence gives the same when almost every input is admissible (Control.Semantics.CorrespondsOn.success_map_meaning_ae, Control.Semantics.CorrespondsOn.failureMass_map_meaning_ae).

Under a lawful measure semantics, the output measure of a computation mx pushed forward along the encoded meaning is the encoding of the output measure of f.implementation <$> mx (Control.Semantics.CertifiedMeaning.evalDist_map_meaning, Control.Semantics.CorrespondsOn.evalDist_map_meaning_ae).

The statements assume measurability of the output encoding and of the implementation only. The decoded forms need the implementation to be measurable only almost everywhere. The input encoding and the semantic carrier of inputs need no measurable structure, because the encoded meaning equals output ∘ f.implementation on every input, or on almost every input.

Measures on native inputs #

theorem Control.Semantics.CertifiedMeaning.map_meaning {A : Type u_1} {B : Type u_2} {D : Type u_3} {E : Type u_4} [MeasurableSpace A] [MeasurableSpace B] [MeasurableSpace E] {input : A ↪ D} {output : B ↪ E} (f : CertifiedMeaning input output) (μ : MeasureTheory.Measure A) (houtput : Measurable ⇑output) (himplementation : Measurable f.implementation) :

Pushing a measure on native inputs forward along the encoded meaning gives the encoding of the implementation's pushforward.

theorem Control.Semantics.CorrespondsOn.map_meaning_ae {A : Type u_1} {B : Type u_2} {D : Type u_3} {E : Type u_4} [MeasurableSpace A] [MeasurableSpace B] [MeasurableSpace E] {input : A ↪ D} {output : B ↪ E} {valid : A → Prop} {meaning : D → E} {implementation : A → B} (h : CorrespondsOn input output valid meaning implementation) {μ : MeasureTheory.Measure A} (hvalid : ∀ᵐ (x : A) ∂μ, valid x) (houtput : Measurable ⇑output) (himplementation : Measurable implementation) :
MeasureTheory.Measure.map (meaning ∘ ⇑input) μ = MeasureTheory.Measure.map (⇑output) (MeasureTheory.Measure.map implementation μ)

A correspondence on the admissible inputs gives the pushforward equation of CertifiedMeaning.map_meaning when almost every input is admissible.

Decoded meanings: values and failure #

A decoded certificate's encoded meaning pushes a measure on native inputs to a measure whose values are the implementation's pushforward.

A decoded certificate's encoded meaning pushes a measure on native inputs to a measure with no failure mass: it neither diverges nor fails at any native input.

theorem Control.Semantics.CorrespondsOn.success_map_meaning_ae {A : Type u_1} {D : Type u_2} {B : Type u_3} {ε : Type u_4} [MeasurableSpace A] [MeasurableSpace B] {input : A ↪ D} {valid : A → Prop} {meaning : D → DomainResult ε B} {implementation : A → B} (h : CorrespondsOn input DomainResult.valueEmbedding valid meaning implementation) {μ : MeasureTheory.Measure A} (hvalid : ∀ᵐ (x : A) ∂μ, valid x) (himplementation : AEMeasurable implementation μ) :

A decoded correspondence gives the values of CertifiedMeaning.success_map_meaning when almost every input is admissible.

theorem Control.Semantics.CorrespondsOn.failureMass_map_meaning_ae {A : Type u_1} {D : Type u_2} {B : Type u_3} {ε : Type u_4} [MeasurableSpace A] [MeasurableSpace B] {input : A ↪ D} {valid : A → Prop} {meaning : D → DomainResult ε B} {implementation : A → B} (h : CorrespondsOn input DomainResult.valueEmbedding valid meaning implementation) {μ : MeasureTheory.Measure A} (hvalid : ∀ᵐ (x : A) ∂μ, valid x) (himplementation : AEMeasurable implementation μ) :

A decoded correspondence gives no failure mass when almost every input is admissible.

Output measures of computations #

theorem Control.Semantics.CertifiedMeaning.evalDist_map_meaning {m : Type u → Type v} [Monad m] [LawfulMonad m] [EvalDistSemantics m] [LawfulEvalDistSemantics m] {A B : Type u} {D : Type u_1} {E : Type u_2} [MeasurableSpace A] [MeasurableSpace B] [MeasurableSpace E] {input : A ↪ D} {output : B ↪ E} (f : CertifiedMeaning input output) (mx : m A) (houtput : Measurable ⇑output) (himplementation : Measurable f.implementation) :

The output measure of a computation, pushed forward along the encoded meaning, is the encoding of the output measure of the implementation run on its result.

theorem Control.Semantics.CorrespondsOn.evalDist_map_meaning_ae {m : Type u → Type v} [Monad m] [LawfulMonad m] [EvalDistSemantics m] [LawfulEvalDistSemantics m] {A B : Type u} {D : Type u_1} {E : Type u_2} [MeasurableSpace A] [MeasurableSpace B] [MeasurableSpace E] {input : A ↪ D} {output : B ↪ E} {valid : A → Prop} {meaning : D → E} {implementation : A → B} (h : CorrespondsOn input output valid meaning implementation) {mx : m A} (hvalid : ∀ᵐ (x : A) ∂evalDist mx, valid x) (houtput : Measurable ⇑output) (himplementation : Measurable implementation) :
MeasureTheory.Measure.map (meaning ∘ ⇑input) (evalDist mx) = MeasureTheory.Measure.map (⇑output) (evalDist (implementation <$> mx))

A correspondence gives the equation of CertifiedMeaning.evalDist_map_meaning when almost every output of the computation is admissible.