Documentation

PolyFun.Realizability.Quantitative.CostLaws

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 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.

  • overhead : ℕ → ℕ

    Envelope for identity work and composition glue, as a function of an encoded size.

  • monotone_overhead : Monotone (overhead Q)

    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.

    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.

      Instances

        Size and work laws for the optional-value code that product-state machines use.

        Instances

          Work law for executable distributivity.

          Instances

            The combined structural envelope #

            def PFunctor.QuantitativeStepClass.structOverhead {C : StepClass} (Q : QuantitativeStepClass C) [Q.HasComposition] [P : C.HasProd] [S : C.HasSum] [O : C.HasOption] [QP : Q.HasProd] [QS : Q.HasSum] [QO : Q.HasOption] [QD : Q.IsDistributive] [CC : Q.HasCompositionCost] [PC : Q.HasProdCost] [SC : Q.HasSumCost] [OC : Q.HasOptionCost] [DC : Q.IsDistributiveCost] (n : ℕ) :

            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
              theorem PFunctor.QuantitativeStepClass.sum_overhead_le {C : StepClass} (Q : QuantitativeStepClass C) [Q.HasComposition] [P : C.HasProd] [S : C.HasSum] [O : C.HasOption] [QP : Q.HasProd] [QS : Q.HasSum] [QO : Q.HasOption] [QD : Q.IsDistributive] [CC : Q.HasCompositionCost] [PC : Q.HasProdCost] [SC : Q.HasSumCost] [OC : Q.HasOptionCost] [DC : Q.IsDistributiveCost] {m n : ℕ} (h : m ≤ n) :

              Derived cost bounds #

              theorem PFunctor.QuantitativeStepClass.cost_withInput_le {C : StepClass} (Q : QuantitativeStepClass C) [Q.HasComposition] [CC : Q.HasCompositionCost] [P : C.HasProd] [QP : Q.HasProd] [PC : Q.HasProdCost] {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} (code : Q.Realizer a b f) (x : A) :

              Retaining an input costs the wrapped code plus identity and pairing at the input's size.

              theorem PFunctor.QuantitativeStepClass.cost_pairRight_le {C : StepClass} (Q : QuantitativeStepClass C) [Q.HasComposition] [CC : Q.HasCompositionCost] [P : C.HasProd] [QP : Q.HasProd] [PC : Q.HasProdCost] {A B D : Type u} {a : C.Str A} {b : C.Str B} {d : C.Str D} {f : A → B} (code : Q.Realizer a b f) (x : A) (y : D) :

              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.

              theorem PFunctor.QuantitativeStepClass.cost_pairLeft_le {C : StepClass} (Q : QuantitativeStepClass C) [Q.HasComposition] [CC : Q.HasCompositionCost] [P : C.HasProd] [QP : Q.HasProd] [PC : Q.HasProdCost] {A B D : Type u} {a : C.Str A} {b : C.Str B} {d : C.Str D} {f : A → B} (code : Q.Realizer a b f) (y : D) (x : A) :

              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 #

                            theorem PFunctor.QuantitativeStepClass.cost_rotate_le {C : StepClass} (Q : QuantitativeStepClass C) [Q.HasComposition] [P : C.HasProd] [QP : Q.HasProd] [CC : Q.HasCompositionCost] [PC : Q.HasProdCost] {A E I : Type u} (a : C.Str A) (e : C.Str E) (i : C.Str I) (x : A) (y : E) (j : I) :

                            The rotation costs at most nine product primitives and glues.

                            theorem PFunctor.QuantitativeStepClass.cost_exchange_le {C : StepClass} (Q : QuantitativeStepClass C) [Q.HasComposition] [P : C.HasProd] [QP : Q.HasProd] [CC : Q.HasCompositionCost] [PC : Q.HasProdCost] {A E I : Type u} (a : C.Str A) (e : C.Str E) (i : C.Str I) (x : A) (y : E) (j : I) :

                            The exchange costs at most nine product primitives and glues, at the sizes of its input and of the inner pair.

                            theorem PFunctor.QuantitativeStepClass.cost_carryReadout_le {C : StepClass} (Q : QuantitativeStepClass C) [Q.HasComposition] [P : C.HasProd] [S : C.HasSum] [O : C.HasOption] [QP : Q.HasProd] [QS : Q.HasSum] [QO : Q.HasOption] [QD : Q.IsDistributive] [CC : Q.HasCompositionCost] [PC : Q.HasProdCost] [SC : Q.HasSumCost] [OC : Q.HasOptionCost] [DC : Q.IsDistributiveCost] {A B D E : Type u} {a : C.Str A} {b : C.Str B} {d : C.Str D} (e : C.Str E) {f : A → B ⊕ D} (code : Q.Realizer a (StepClass.HasSum.sum b d) f) (x : A) (y : E) :

                            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.

                            theorem PFunctor.QuantitativeStepClass.cost_carryUpdate_le {C : StepClass} (Q : QuantitativeStepClass C) [Q.HasComposition] [P : C.HasProd] [S : C.HasSum] [O : C.HasOption] [QP : Q.HasProd] [QS : Q.HasSum] [QO : Q.HasOption] [QD : Q.IsDistributive] [CC : Q.HasCompositionCost] [PC : Q.HasProdCost] [SC : Q.HasSumCost] [OC : Q.HasOptionCost] [DC : Q.IsDistributiveCost] {A I E : Type u} {a : C.Str A} {i : C.Str I} (e : C.Str E) {g : A × I → Option A} (code : Q.Realizer (StepClass.HasProd.prod a i) (StepClass.HasOption.option a) g) (x : A) (y : E) (j : I) {x' : A} (hg : g (x, j) = some x') :

                            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.

                            theorem PFunctor.QuantitativeStepClass.cost_carryReadoutWith_le {C : StepClass} (Q : QuantitativeStepClass C) [Q.HasComposition] [P : C.HasProd] [S : C.HasSum] [O : C.HasOption] [QP : Q.HasProd] [QS : Q.HasSum] [QO : Q.HasOption] [QD : Q.IsDistributive] [CC : Q.HasCompositionCost] [PC : Q.HasProdCost] [SC : Q.HasSumCost] [OC : Q.HasOptionCost] [DC : Q.IsDistributiveCost] {A B D D' E : Type u} {a : C.Str A} {b : C.Str B} {d : C.Str D} {d' : C.Str D'} {e : C.Str E} {f : A → B ⊕ D} {g : D × E → D'} (code : Q.Realizer a (StepClass.HasSum.sum b d) f) (right : Q.Realizer (StepClass.HasProd.prod d e) d' g) (x : A) (y : E) :
                            Q.cost (Q.carryReadoutWith code right) (x, y) ≤ Q.cost code x + Sum.elim (fun (x : B) => 0) (fun (q : D) => Q.cost right (q, y)) (f x) + carryReadoutWithCount * Q.structOverhead (Q.size a x + Q.size (StepClass.HasSum.sum b d) (f x) + Q.size e y + Q.size (StepClass.HasSum.sum (StepClass.HasProd.prod b e) d') (Sum.elim (fun (value : B) => Sum.inl (value, y)) (fun (q : D) => Sum.inr (g (q, y))) (f x)) + HasProdCost.sizeOverhead Q + HasSumCost.sizeOverhead Q)

                            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.