Cost laws for structural backend code #
PolyFun.Realizability.Quantitative.Closure supplies executable structural code (HasProd,
HasSum, HasOption, IsDistributive) but no law bounding its work. This file adds:
- the cost-law mixins
HasCompositionCost,HasProdCost,HasSumCost,HasOptionCostandIsDistributiveCost. Each bounds the own work of a structural primitive, excluding the work of the code it wraps, by a monotone function of the encoded size of the data the primitive touches: its input, the intermediate value of a composition, or the shared input that pairing duplicates. Size laws bound the encodings of pairs, injections andsomeby their components plus a constant; structOverhead, the sum of the mixins' work envelopes, a single monotone function used to state carry costs compactly;- derived cost bounds for
HasProd.withInput,HasProd.pairRight,HasProd.pairLeft,IsDistributive.elimContext, the option strengthHasOption.strength, and the carry combinatorsexchange,rotate,carryReadout,carryReadoutWithandcarryUpdate, which charge the named primitive countscarryReadoutCount,carryReadoutWithCountandcarryUpdateCount.
The laws are additive: wrapped black-box code is charged exactly its own cost, and each
primitive adds an envelope of the sizes it touches. Only test fixtures instantiate them. The
single-tape backend of ComplexityBackends has no executable structural code, and its
composeOverhead evaluates the second machine's time polynomial at an inflated input size, so it
is not additive. cost_pair_le charges pairing at the shared input's size only; a backend that
copies both results into one pair encoding also pays for the results' sizes, which this law does
not admit.
Cost-law mixins #
Work laws for identity code and for the connection overhead of composition.
composeOverhead_le charges the connection by the size of the intermediate value, so composed
code costs its parts plus a function of what is passed between them.
Envelope for identity work and composition glue, as a function of an encoded size.
The envelope is monotone.
- cost_identity_le {A : Type u} (a : C.Str A) (x : A) : Q.cost (Q.identity a) x ≤ overhead Q (Q.size a x)
Identity code costs at most the envelope at its input size.
- composeOverhead_le {A B D : Type u} {a : C.Str A} {b : C.Str B} {d : C.Str D} {f : A → B} {g : B → D} (rf : Q.Realizer a b f) (rg : Q.Realizer b d g) (x : A) : Q.composeOverhead rf rg x ≤ overhead Q (Q.size b (f x))
Composition glue costs at most the envelope at the intermediate size.
Instances
Size and work laws for product code: projections cost the envelope at the pair's size, and pairing costs its two parts plus the envelope at the size of the shared, duplicated input.
- sizeOverhead : ℕ
Constant size overhead of the pinned pair encoding.
- size_prod_le {A B : Type u} (a : C.Str A) (b : C.Str B) (x : A) (y : B) : Q.size (StepClass.HasProd.prod a b) (x, y) ≤ Q.size a x + Q.size b y + sizeOverhead Q
A pair is encoded within its components plus the constant overhead.
Work envelope of the product primitives.
The envelope is monotone.
- cost_fst_le {A B : Type u} (a : C.Str A) (b : C.Str B) (z : A × B) : Q.cost (HasProd.fst a b) z ≤ overhead Q (Q.size (StepClass.HasProd.prod a b) z)
The first projection costs at most the envelope at the pair's size.
- cost_snd_le {A B : Type u} (a : C.Str A) (b : C.Str B) (z : A × B) : Q.cost (HasProd.snd a b) z ≤ overhead Q (Q.size (StepClass.HasProd.prod a b) z)
The second projection costs at most the envelope at the pair's size.
- cost_pair_le {A B D : Type u} {a : C.Str A} {b : C.Str B} {d : C.Str D} {f : A → B} {g : A → D} (rf : Q.Realizer a b f) (rg : Q.Realizer a d g) (x : A) : Q.cost (HasProd.pair rf rg) x ≤ Q.cost rf x + Q.cost rg x + overhead Q (Q.size a x)
Pairing costs its parts plus the envelope at the shared input's size.
Instances
Size and work laws for sum code. Injections neither shrink nor grow a payload by more than a constant; case analysis costs the selected branch plus the envelope at the scrutinee's size.
- sizeOverhead : ℕ
Constant size overhead of the pinned tag.
- size_inl_le {A B : Type u} (a : C.Str A) (b : C.Str B) (x : A) : Q.size (StepClass.HasSum.sum a b) (Sum.inl x) ≤ Q.size a x + sizeOverhead Q
A left injection grows its payload by at most the tag overhead.
- size_inr_le {A B : Type u} (a : C.Str A) (b : C.Str B) (y : B) : Q.size (StepClass.HasSum.sum a b) (Sum.inr y) ≤ Q.size b y + sizeOverhead Q
A right injection grows its payload by at most the tag overhead.
- le_size_inl {A B : Type u} (a : C.Str A) (b : C.Str B) (x : A) : Q.size a x ≤ Q.size (StepClass.HasSum.sum a b) (Sum.inl x)
A left injection does not shrink its payload.
- le_size_inr {A B : Type u} (a : C.Str A) (b : C.Str B) (y : B) : Q.size b y ≤ Q.size (StepClass.HasSum.sum a b) (Sum.inr y)
A right injection does not shrink its payload.
Work envelope of the sum primitives.
The envelope is monotone.
- cost_inl_le {A B : Type u} (a : C.Str A) (b : C.Str B) (x : A) : Q.cost (HasSum.inl a b) x ≤ overhead Q (Q.size a x)
A left injection costs at most the envelope at its payload's size.
- cost_inr_le {A B : Type u} (a : C.Str A) (b : C.Str B) (y : B) : Q.cost (HasSum.inr a b) y ≤ overhead Q (Q.size b y)
A right injection costs at most the envelope at its payload's size.
- cost_elim_le {A B D : Type u} {a : C.Str A} {b : C.Str B} {d : C.Str D} {f : A → D} {g : B → D} (rf : Q.Realizer a d f) (rg : Q.Realizer b d g) (z : A ⊕ B) : Q.cost (HasSum.elim rf rg) z ≤ Sum.elim (Q.cost rf) (Q.cost rg) z + overhead Q (Q.size (StepClass.HasSum.sum a b) z)
Case analysis costs the selected branch plus the envelope at the scrutinee's size.
Instances
Size and work laws for the optional-value code that product-state machines use.
- sizeOverhead : ℕ
Constant size overhead of the pinned option tag.
- size_some_le {A : Type u} (a : C.Str A) (x : A) : Q.size (StepClass.HasOption.option a) (some x) ≤ Q.size a x + sizeOverhead Q
A present value grows its payload by at most the tag overhead.
Work envelope of the option primitives.
The envelope is monotone.
- cost_some_le {A : Type u} (a : C.Str A) (x : A) : Q.cost (HasOption.some a) x ≤ overhead Q (Q.size a x)
Wrapping a present value costs at most the envelope at its payload's size.
- cost_none_le {A B : Type u} (a : C.Str A) (b : C.Str B) (x : A) : Q.cost (HasOption.none a b) x ≤ overhead Q (Q.size a x)
The constantly absent value costs at most the envelope at its input's size.
- cost_map_le {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} (code : Q.Realizer a b f) (z : Option A) : Q.cost (HasOption.map code) z ≤ z.elim 0 (Q.cost code) + overhead Q (Q.size (StepClass.HasOption.option a) z)
Mapping over an optional value costs the mapped code on a present value plus the envelope at the input's size.
- cost_bindContext_le {A B E : Type u} {a : C.Str A} {b : C.Str B} {e : C.Str E} {k : A × E → Option B} (code : Q.Realizer (StepClass.HasProd.prod a e) (StepClass.HasOption.option b) k) (z : Option A × E) : Q.cost (HasOption.bindContext code) z ≤ (z.1.elim 0 fun (x : A) => Q.cost code (x, z.2)) + overhead Q (Q.size (StepClass.HasProd.prod (StepClass.HasOption.option a) e) z)
A contextual bind costs its continuation on a present value plus the envelope at the input's size.
Instances
Work law for executable distributivity.
Work envelope of the distributivity primitive.
The envelope is monotone.
- cost_distribute_le {A B E : Type u} (a : C.Str A) (b : C.Str B) (e : C.Str E) (z : (A ⊕ B) × E) : Q.cost (IsDistributive.distribute a b e) z ≤ overhead Q (Q.size (StepClass.HasProd.prod (StepClass.HasSum.sum a b) e) z)
Distribution costs at most the envelope at its input's size.
Instances
The combined structural envelope #
The sum of all structural work envelopes: one monotone function bounding the own work of every structural primitive at a given encoded size.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Derived cost bounds #
Retaining an input costs the wrapped code plus identity and pairing at the input's size.
Running code on the first component while carrying the second costs the code plus two projections and one pairing at the pair's size, and composition glue at the first component's size.
Running code on the second component while carrying the first: the mirror of
cost_pairRight_le.
Case analysis in a context, left branch: the branch code plus distribution, case analysis and glue, each at the size of the distributed scrutinee.
Case analysis in a context, right branch.
The option strength on a present value costs some at the payload pair's size plus the
contextual bind at the input's size.
Primitive counts #
The carry bounds charge a fixed number of structural primitives, each at the combined envelope
structOverhead. Naming the counts lets statements, derived carries and documentation share one
definition.
Structural primitives charged by HasProd.pairRight or HasProd.pairLeft: two projections,
one pairing and one composition glue.
Equations
Instances For
Structural primitives charged by IsDistributive.elimContext: distribution, case analysis and
one glue.
Equations
Instances For
Structural primitives charged by HasOption.strength on a present value: some and the
contextual bind.
Equations
Instances For
Structural primitives charged by exchange or rotate: seven pairings and projections and two
glues.
Equations
Instances For
Structural primitives charged by carryReadoutWith beyond its two wrapped codes: pairRight,
the glue into case analysis, elimContext, and an injection with its glue.
Equations
Instances For
Structural primitives charged by carryReadout beyond its wrapped code: those of
carryReadoutWith, plus the projection that drops the carried value on the query branch.
Equations
Instances For
Structural primitives charged by carryUpdate beyond its wrapped code: exchange, two glues,
pairRight and the option strength.
Equations
Instances For
Cost bounds for the carry combinators #
The rotation costs at most nine product primitives and glues.
The exchange costs at most nine product primitives and glues, at the sizes of its input and of the inner pair.
Attaching a carried value to a readout costs the wrapped code plus at most
carryReadoutCount structural primitives, each charged the combined envelope at the input,
readout and carried sizes.
Stepping a partial transition while carrying a value costs the wrapped code plus at most
carryUpdateCount structural primitives, each charged the combined envelope at a size bounded by
the source and target states, the carried value and the index.
Attaching a carried value and post-processing the other summand costs the readout code, the
post-processing code on the branch taken, and at most carryReadoutWithCount structural
primitives, each charged the combined envelope at the input, readout, carried and output sizes.