Measured programs and budgeted carriers #
Measured programs. A MeasuredProgram Input Result ω computes a function by a free program
whose interface depends on a view of the input:
- the view is computed outside the program, and is not charged;
- calls are answered by a deterministic answering function (
answer); - each operation has a price (
cost).
run interprets the program through the deterministic answers, and is the output of the one path
they pick (run_eq_output). Realizes f says the run computes f, and CostAtMost B bounds the
charge of every completed path of every view's program, so signed prices are allowed. ofFun f
computes f with no operations at cost 0.
comp outer inner runs inner, computes outer's view from the actual intermediate result, and
runs outer. It does this on the sum of the two interfaces, each operation tagged with the view it
belongs to, keeping both price lists. It computes the composite
(run_comp, Realizes.comp), and its budgets add (CostAtMost.comp). contramap precomposes an
uncharged map on inputs. A BudgetedProgram f ω bundles a measured program realizing f with a
budget, and composes the same way.
Budgeted carriers. Budgeted c B α is the subtype of free programs within budget B. With
budgets graded by Multiplicative ω, it is a GradedMonad: gbind adds budgets.
Measured programs #
A function computed by a free program over an interface that depends on an uncharged view of the input, answered deterministically, with a price per operation.
Only the operations are charged. The view, the answering function and the code between calls are
free at this layer, so ofFun f realizes any f at cost 0: a statement of the form
∃ M, M.Realizes f ∧ M.CostAtMost B is trivial. Cost statements name the measured program, and
the uncharged parts are bounded one layer down.
- View : Type u
What the program is allowed to depend on.
- view : Input → self.View
The uncharged view of an input.
- Op : Type u
The operations the program may call.
The answers to an operation, which may depend on the view.
The program of each view.
The deterministic answers of each view.
- cost : self.Op → ω
The price of each operation.
Instances For
Run the program of the input's view, answering every call deterministically.
Equations
Instances For
The run is the output of the path the answers pick.
Every completed path of every view's program costs at most B.
Equations
- M.CostAtMost B = ∀ (v : M.View) (p : (M.program v).Path), PFunctor.FreeM.Path.charge M.cost (M.program v) p ≤ B
Instances For
A cost bound holds for every larger budget.
The program with no operations that computes f on its whole input. Its view is the input, so
the input shares the result's universe.
Equations
- One or more equations did not get rendered due to their size.
Instances For
A program with no operations costs nothing.
The answers of the composite interface, which does not depend on the view: each operation is
tagged with the view it belongs to, inner's or outer's.
Equations
Instances For
The inclusion of inner's interface at view v into the composite interface.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The inclusion of outer's interface at view v' into the composite interface.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Run inner, compute outer's view from the actual intermediate result without charging it,
and run outer, on the sum of the two interfaces, each operation tagged with its view, with both
price lists.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The composite computes the composite function.
The composite realizes the composite function.
Composite budgets add: the inner budget, then the outer one. Arguments come in the order of
comp, outer first.
Precompose with an uncharged map on inputs.
Equations
Instances For
A measured program realizing f, with a budget on every completed path.
- program : MeasuredProgram Input Result ω
The measured program.
- budget : ω
The bound on the charge of every completed path.
The program computes
f.- costAtMost : self.program.CostAtMost self.budget
Every completed path costs at most the budget.
Instances For
Every function has a budgeted program with budget 0 and no operations.
Equations
- PFunctor.FreeM.BudgetedProgram.ofFun f = { program := PFunctor.FreeM.MeasuredProgram.ofFun f, budget := 0, realizes := ⋯, costAtMost := ⋯ }
Instances For
Precompose with an uncharged map on inputs.
Equations
Instances For
Compose budgeted programs; budgets add.
Equations
Instances For
Budgeted carriers #
Free programs within budget B.
Equations
- PFunctor.FreeM.Budgeted c B α = { x : P.FreeM α // x.IsChargeBound c (Multiplicative.toAdd B) }
Instances For
Budgeted programs form a graded monad: sequencing adds budgets.
Equations
- One or more equations did not get rendered due to their size.