Expected charge of free programs #
PFunctor.OpSpec.expectedCharge ν c reads a call at a as costing c a, followed by the expected
value of its continuation under the answer measure ν a: c a + ∫⁻ b, k b ∂ν a. Its fold at the
zero leaf cost, wpFold (OpSpec.expectedCharge ν c) x fun _ => 0, is the expected charge of x.
The spec is the worst-case reading OpSpec.charge c, whose fold is FreeM.cost c x, with the
integral in place of the supremum.
Main statements #
FreeM.wpFold_expectedCharge_eq_add: over discrete answers the leaf costs split off, so the expected charge-to-go is the expected charge plus the expectation of the leaf costs, which is their integral under the measure fold (FreeM.wpFold_expectedCharge_eq_add_lintegral).FreeM.wpFold_expectedCharge_le_costWith: under subprobability answers the expected charge is at most the worst-case charge.FreeM.lintegral_measureFold_withPathCharge: under probability answers over discrete answer types, the expected charge is the integral of the charge of the completed path under the measure fold ofwithPathCharge c x. The charge of a call is paid before the call, so the identity needs answer measures of total mass one.FreeM.expectedQueryCount_eq_wpFoldis the unit charge underPFunctor.AnswerMeasure.FreeM.wpFold_expectedCharge_liftM_le: expected-cost transfer. If each implementation of a free handler has expected charge at mostc a, the simulated program has expected charge at most the source program's expected charge underc, with each call answered by the measure fold of its implementation. It is an instance ofFreeM.wpFold_liftM_le, andFreeM.wpFold_expectedCharge_liftMis the exact form.
The expected-charge spec #
The expected-charge reading of answer measures ν: a call at a costs c a, followed by the
expected value of its continuation under ν a.
Instances For
The expected-charge reading is monotone in the continuation.
Under subprobability answers, the expected charge of a call is at most its worst-case charge.
Expected and worst-case charge #
Over discrete answers, the leaf costs split off: the expected charge-to-go is the expected charge plus the expectation of the leaf costs. Integration is additive on the measurable continuations that discrete answers give.
Over discrete answers, the expected charge-to-go of a measurable leaf cost is the expected charge plus the integral of the leaf cost under the measure fold.
Under subprobability answers, the expected charge-to-go is at most the worst-case charge-to-go.
Under subprobability answers, the expected charge is at most the worst-case charge.
The charge of the completed path #
Under probability answers, folding the integration spec over a program run with the charge of
its path, read through an additive map φ into ℝ≥0∞, gives the expected charge φ ∘ c of the
program. The charge of a call is paid before the call in the expected-charge reading and on the
completed path in withPathCharge, so the two agree because every answer measure has total mass
one.
Expected charge. Under probability answers over discrete answer types, the expected charge
of a program is the integral of the charge of its completed path under the measure fold of
withPathCharge c x.
The expected number of calls on a completed path is the expected charge of the unit charge.
Expected-cost transfer #
Expected-cost transfer. If each implementation of a free handler has expected charge at
most c a, then the simulated program's expected charge-to-go is at most the source program's
under the charge c, with each call answered by the measure fold of its implementation. Discrete
answers on both interfaces make the leaf costs split off each implementation
(wpFold_expectedCharge_eq_add_lintegral), which gives the per-call obligation of
wpFold_liftM_le.
Expected-cost transfer, exact form. The simulated program's expected charge-to-go is the source program's, with each call charged the expected charge of its implementation and answered by the measure fold of its implementation.