Documentation

PolyFun.Realizability.Quantitative.Resource

Resource contracts for quantitative realizations #

This module gives ExecutionCost an inspectable second-order polynomial bound and describes the response-size environments under which an open quantitative realization runs. The definitions are generic in a polynomial-functor interface and a quantitative backend. They do not select a machine model or assert a complexity class.

PolynomialRunBound concerns one already chosen realization and is deliberately independent of semantic FreeM syntax. PolynomialProgramWitness adds implementation and returned-output recovery as a separate layer. Local pure, ranked-potential, and sequential-composition certificates construct these bounds without replacing backend costs by an asserted meter.

Execution-cost polynomials #

structure PFunctor.ExecutionCostPolynomial (label : Type x) :

A second-order polynomial upper bound for every component of ExecutionCost.

Instances For
    def PFunctor.instDecidableEqExecutionCostPolynomial.decEq {label✝ : Type u_1} [DecidableEq label✝] (x✝ x✝¹ : ExecutionCostPolynomial label✝) :
    Decidable (x✝ = x✝¹)
    Equations
    • One or more equations did not get rendered due to their size.
    Instances For
      Equations
      • One or more equations did not get rendered due to their size.
      Instances For

        Regard a first-order polynomial as one which does not inspect its length environment.

        Equations
        Instances For
          @[simp]
          theorem PFunctor.ExecutionCostPolynomial.eval_ofFirstOrder {label : Type x} (bound : Complexity.FirstOrderPolynomial) (length : label → ℕ → ℕ) (inputSize : ℕ) :
          Complexity.SecondOrderPolynomial.eval length inputSize (ofFirstOrder bound) = bound.eval inputSize
          def PFunctor.ExecutionCostPolynomial.eval {label : Type x} (bound : ExecutionCostPolynomial label) (length : label → ℕ → ℕ) (inputSize : ℕ) :

          Evaluate every resource component at an input size and length environment.

          Equations
          • One or more equations did not get rendered due to their size.
          Instances For
            @[simp]
            theorem PFunctor.ExecutionCostPolynomial.eval_work {label : Type x} (bound : ExecutionCostPolynomial label) (length : label → ℕ → ℕ) (inputSize : ℕ) :
            (bound.eval length inputSize).work = Complexity.SecondOrderPolynomial.eval length inputSize bound.work
            @[simp]
            theorem PFunctor.ExecutionCostPolynomial.eval_queries {label : Type x} (bound : ExecutionCostPolynomial label) (length : label → ℕ → ℕ) (inputSize : ℕ) :
            (bound.eval length inputSize).queries = Complexity.SecondOrderPolynomial.eval length inputSize bound.queries
            @[simp]
            theorem PFunctor.ExecutionCostPolynomial.eval_traffic {label : Type x} (bound : ExecutionCostPolynomial label) (length : label → ℕ → ℕ) (inputSize : ℕ) :
            (bound.eval length inputSize).traffic = Complexity.SecondOrderPolynomial.eval length inputSize bound.traffic
            @[simp]
            theorem PFunctor.ExecutionCostPolynomial.eval_peakStateSize {label : Type x} (bound : ExecutionCostPolynomial label) (length : label → ℕ → ℕ) (inputSize : ℕ) :
            (bound.eval length inputSize).peakStateSize = Complexity.SecondOrderPolynomial.eval length inputSize bound.peakStateSize
            @[simp]
            theorem PFunctor.ExecutionCostPolynomial.eval_peakHeadSize {label : Type x} (bound : ExecutionCostPolynomial label) (length : label → ℕ → ℕ) (inputSize : ℕ) :
            (bound.eval length inputSize).peakHeadSize = Complexity.SecondOrderPolynomial.eval length inputSize bound.peakHeadSize

            A constant execution-cost bound.

            Equations
            • One or more equations did not get rendered due to their size.
            Instances For

              A conservative sequential sum of two execution-cost bounds.

              The additive components add exactly. Polynomial addition upper-bounds the max used by the two peak components.

              Equations
              • One or more equations did not get rendered due to their size.
              Instances For

                Replace the base input-size variable in every component.

                Equations
                • One or more equations did not get rendered due to their size.
                Instances For
                  def PFunctor.ExecutionCostPolynomial.reindex {label : Type x} {target : Type y} (bound : ExecutionCostPolynomial label) (map : label → target) :

                  Relabel every length-function symbol in an execution-cost bound.

                  Equations
                  • One or more equations did not get rendered due to their size.
                  Instances For
                    def PFunctor.ExecutionCostPolynomial.subst {label : Type x} {target : Type y} (bound : ExecutionCostPolynomial label) (replacement : label → Complexity.SecondOrderPolynomial target) :

                    Substitute a second-order transformer for every source length-function symbol.

                    Equations
                    • One or more equations did not get rendered due to their size.
                    Instances For
                      @[simp]
                      theorem PFunctor.ExecutionCostPolynomial.eval_const {label : Type x} (cost : ExecutionCost) (length : label → ℕ → ℕ) (inputSize : ℕ) :
                      (const cost).eval length inputSize = cost
                      @[simp]
                      theorem PFunctor.ExecutionCostPolynomial.eval_comp {label : Type x} (bound : ExecutionCostPolynomial label) (inputBound : Complexity.SecondOrderPolynomial label) (length : label → ℕ → ℕ) (inputSize : ℕ) :
                      (bound.comp inputBound).eval length inputSize = bound.eval length (Complexity.SecondOrderPolynomial.eval length inputSize inputBound)
                      @[simp]
                      theorem PFunctor.ExecutionCostPolynomial.eval_reindex {label : Type x} {target : Type y} (bound : ExecutionCostPolynomial label) (map : label → target) (length : target → ℕ → ℕ) (inputSize : ℕ) :
                      (bound.reindex map).eval length inputSize = bound.eval (fun (symbol : label) => length (map symbol)) inputSize
                      @[simp]
                      theorem PFunctor.ExecutionCostPolynomial.eval_subst {label : Type x} {target : Type y} (bound : ExecutionCostPolynomial label) (replacement : label → Complexity.SecondOrderPolynomial target) (length : target → ℕ → ℕ) (inputSize : ℕ) :
                      (bound.subst replacement).eval length inputSize = bound.eval (fun (symbol : label) (size : ℕ) => Complexity.SecondOrderPolynomial.eval length size (replacement symbol)) inputSize
                      theorem PFunctor.ExecutionCostPolynomial.add_eval_le_eval_add {label : Type x} (left right : ExecutionCostPolynomial label) (length : label → ℕ → ℕ) (inputSize : ℕ) :
                      left.eval length inputSize + right.eval length inputSize ≤ (left + right).eval length inputSize

                      Sequentially accumulated costs fit the conservative polynomial sum.

                      theorem PFunctor.ExecutionCostPolynomial.eval_mono_input {label : Type x} (bound : ExecutionCostPolynomial label) {length : label → ℕ → ℕ} (hLength : Complexity.SecondOrderPolynomial.MonotoneLengths length) {smaller larger : ℕ} (hle : smaller ≤ larger) :
                      bound.eval length smaller ≤ bound.eval length larger

                      Evaluation is monotone in encoded input size when every length function is monotone.

                      theorem PFunctor.ExecutionCostPolynomial.eval_mono_lengths {label : Type x} (bound : ExecutionCostPolynomial label) {smaller larger : label → ℕ → ℕ} (hLarger : Complexity.SecondOrderPolynomial.MonotoneLengths larger) (hle : ∀ (symbol : label) (size : ℕ), smaller symbol size ≤ larger symbol size) (inputSize : ℕ) :
                      bound.eval smaller inputSize ≤ bound.eval larger inputSize

                      Evaluation is monotone under pointwise enlargement of monotone length functions.

                      Response-size environments #

                      The response-length function exposed for each labelled interface.

                      • responseSize {label : Type x} (interface : label) : ResponseModulus label

                        Encoded dependent-response length as a function of encoded position length.

                      Instances For
                        def PFunctor.DynSystem.DynComputation.instDecidableEqResponseModulus.decEq {label✝ : Type u_1} [DecidableEq label✝] (x✝ x✝¹ : ResponseModulus label✝) :
                        Decidable (x✝ = x✝¹)
                        Equations
                        • One or more equations did not get rendered due to their size.
                        Instances For
                          Equations
                          • One or more equations did not get rendered due to their size.
                          Instances For
                            structure PFunctor.DynSystem.DynComputation.ResponseResourceModel {p : PFunctor.{u, u}} {C : StepClass} {label : Type x} (Q : QuantitativeStepClass C) (interface : InterfaceBoundary C p) (labelOf : p.A → label) :
                            Type (max u x)

                            One family of admitted responses and monotone encoded-response size envelopes.

                            • allows (position : p.A) : p.B position → Prop

                              Replies admitted at each typed position.

                            • responseSize : label → ℕ → ℕ

                              Encoded response length for each labelled interface.

                            • responseSize_monotone (interface : label) : Monotone (self.responseSize interface)

                              Every response-size envelope is monotone in encoded position size.

                            • responseSize_le (position : p.A) (answer : p.B position) : self.allows position answer → Q.size interface.idx ⟨position, answer⟩ ≤ self.responseSize (labelOf position) (Q.size interface.pos position)

                              Every admitted dependent response fits its selected envelope.

                            Instances For
                              def PFunctor.DynSystem.DynComputation.ResponseResourceModel.modulus {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} {interface : InterfaceBoundary C p} {labelOf : p.A → label} (model : ResponseResourceModel Q interface labelOf) :
                              ResponseModulus label → ℕ → ℕ

                              Expose a response model as the length environment of a second-order polynomial.

                              Equations
                              Instances For
                                @[simp]
                                theorem PFunctor.DynSystem.DynComputation.ResponseResourceModel.modulus_responseSize {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} {interface : InterfaceBoundary C p} {labelOf : p.A → label} (model : ResponseResourceModel Q interface labelOf) (interface✝ : label) (size : ℕ) :
                                model.modulus (ResponseModulus.responseSize interface✝) size = model.responseSize interface✝ size

                                Every length function exposed by a response model is monotone.

                                A pinned position labelling and a nonempty collection of admissible response models.

                                Instances For
                                  @[reducible, inline]
                                  abbrev PFunctor.DynSystem.DynComputation.ResponseResourceContract.Model {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} {interface : InterfaceBoundary C p} (contract : ResponseResourceContract Q interface label) :
                                  Type (max 0 u x)

                                  Response environments carrying evidence that they satisfy a contract.

                                  Equations
                                  Instances For
                                    @[reducible, inline]
                                    abbrev PFunctor.DynSystem.DynComputation.ResponseResourceContract.Model.resourceModel {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} {interface : InterfaceBoundary C p} {contract : ResponseResourceContract Q interface label} (model : contract.Model) :
                                    ResponseResourceModel Q interface contract.labelOf

                                    Forget contract admissibility evidence.

                                    Equations
                                    Instances For
                                      @[reducible, inline]
                                      abbrev PFunctor.DynSystem.DynComputation.ResponseResourceContract.Model.modulus {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} {interface : InterfaceBoundary C p} {contract : ResponseResourceContract Q interface label} (model : contract.Model) :
                                      ResponseModulus label → ℕ → ℕ

                                      The second-order length environment supplied by a compatible response model.

                                      Equations
                                      Instances For

                                        Every compatible response model supplies monotone length functions.

                                        Polynomial run and program witnesses #

                                        structure PFunctor.DynSystem.DynComputation.PolynomialRunBound {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} (R : QuantitativeRealization Q bd) (contract : ResponseResourceContract Q bd.interface label) :

                                        A second-order polynomial bound on one already selected quantitative realization.

                                        This structure contains no semantic FreeM program and no output-recovery policy. It can therefore be reused when the same realization is related to syntax in more than one way.

                                        Instances For
                                          def PFunctor.DynSystem.DynComputation.PolynomialRunBound.bound {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {R : QuantitativeRealization Q bd} {contract : ResponseResourceContract Q bd.interface label} (certificate : PolynomialRunBound R contract) (model : contract.Model) :
                                          input → ExecutionCost

                                          The input-indexed execution bound selected by one compatible response model.

                                          Equations
                                          Instances For
                                            @[simp]
                                            theorem PFunctor.DynSystem.DynComputation.PolynomialRunBound.bound_apply {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {R : QuantitativeRealization Q bd} {contract : ResponseResourceContract Q bd.interface label} (certificate : PolynomialRunBound R contract) (model : contract.Model) (value : input) :
                                            certificate.bound model value = certificate.polynomial.eval model.modulus (Q.size bd.input value)
                                            theorem PFunctor.DynSystem.DynComputation.PolynomialRunBound.runsWithin_bound {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {R : QuantitativeRealization Q bd} {contract : ResponseResourceContract Q bd.interface label} (certificate : PolynomialRunBound R contract) (model : contract.Model) :
                                            R.RunsWithinUnder model.resourceModel.allows (certificate.bound model)

                                            Restate the certificate's pathwise theorem through its named input-indexed bound.

                                            structure PFunctor.DynSystem.DynComputation.PolynomialProgramWitness {p : PFunctor.{u, u}} {C : StepClass} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} (Q : QuantitativeStepClass C) (bd : Boundary C p input output) (contract : ResponseResourceContract Q bd.interface label) (program : input → p.FreeM output) :
                                            Type (max (max (max (u + 1) v) w) x)

                                            A polynomially resource-bounded realization together with its semantic program witness.

                                            The run bound remains a separate field so closure constructions can operate on it without reproving implementation or returned-output recovery.

                                            Instances For
                                              def PFunctor.DynSystem.DynComputation.PolynomialProgramWitness.outputSizePolynomial {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {contract : ResponseResourceContract Q bd.interface label} {program : input → p.FreeM output} (witness : PolynomialProgramWitness Q bd contract program) :

                                              A second-order polynomial bounding returned payload size through the charged peak readout.

                                              Equations
                                              Instances For
                                                @[simp]
                                                theorem PFunctor.DynSystem.DynComputation.PolynomialProgramWitness.eval_outputSizePolynomial {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {contract : ResponseResourceContract Q bd.interface label} {program : input → p.FreeM output} (witness : PolynomialProgramWitness Q bd contract program) (model : contract.Model) (value : input) :
                                                theorem PFunctor.DynSystem.DynComputation.PolynomialProgramWitness.returnedSize_le {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {contract : ResponseResourceContract Q bd.interface label} {program : input → p.FreeM output} (witness : PolynomialProgramWitness Q bd contract program) (model : contract.Model) (value : input) {finish : witness.realization.machine.State} (trace : witness.realization.ExecutionTrace (witness.realization.machine.init value) finish) (htrace : QuantitativeRealization.ExecutionTrace.Conforms model.resourceModel.allows trace) (result : output) (view_eq : witness.realization.machine.view finish = Sum.inl result) :

                                                Every return reached by a conforming execution has polynomially bounded encoded payload size.

                                                def PFunctor.DynSystem.DynComputation.PolynomialProgramWitness.congrProgram {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {contract : ResponseResourceContract Q bd.interface label} {program program' : input → p.FreeM output} (witness : PolynomialProgramWitness Q bd contract program) (hprogram : program = program') :
                                                PolynomialProgramWitness Q bd contract program'

                                                Transport a program witness across extensional equality of whole program families.

                                                Equations
                                                Instances For
                                                  theorem PFunctor.DynSystem.DynComputation.PolynomialProgramWitness.isQuantitativelyRealizableBy {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {contract : ResponseResourceContract Q bd.interface label} {program : input → p.FreeM output} (witness : PolynomialProgramWitness Q bd contract program) :

                                                  A program witness retains ordinary quantitative realizability.

                                                  theorem PFunctor.DynSystem.DynComputation.PolynomialProgramWitness.isQuantitativelyRealizableWithinUnder {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {contract : ResponseResourceContract Q bd.interface label} {program : input → p.FreeM output} (witness : PolynomialProgramWitness Q bd contract program) (model : contract.Model) :

                                                  A program witness supplies the corresponding exact bound under each compatible model.

                                                  theorem PFunctor.DynSystem.DynComputation.PolynomialProgramWitness.isTotalRollBound {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {contract : ResponseResourceContract Q bd.interface label} {program : input → p.FreeM output} (witness : PolynomialProgramWitness Q bd contract program) (model : contract.Model) (hAllows : ∀ (position : p.A) (answer : p.B position), model.resourceModel.allows position answer) (value : input) :
                                                  (program value).IsTotalRollBound (witness.runBound.bound model value).queries

                                                  If a response model admits every typed reply, the query component bounds the full free syntax.

                                                  Immediately returning programs #

                                                  structure PFunctor.DynSystem.DynComputation.PureResourceCertificate {p : PFunctor.{u, u}} {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} (Q : QuantitativeStepClass C) (bd : Boundary C p input output) (function : input → output) :

                                                  Executable polynomial data for an immediately returning function.

                                                  The partial update realizer is required for a complete realization but needs no resource bound: an immediately returning machine never invokes it.

                                                  Instances For
                                                    def PFunctor.DynSystem.DynComputation.PureResourceCertificate.ofPolyRealizer {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {function : input → output} (model : Q.PolynomialModel) (result : Q.PolyRealizer bd.input bd.out function) :

                                                    Construct pure-program data from one result realizer and an explicit polynomial model.

                                                    Equations
                                                    • One or more equations did not get rendered due to their size.
                                                    Instances For
                                                      def PFunctor.DynSystem.DynComputation.PureResourceCertificate.realization {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {function : input → output} (certificate : PureResourceCertificate Q bd function) :

                                                      Assemble the quantitative realization of an immediately returning function.

                                                      Equations
                                                      • One or more equations did not get rendered due to their size.
                                                      Instances For
                                                        def PFunctor.DynSystem.DynComputation.PureResourceCertificate.polynomial {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {function : input → output} {resourceLabel : Type x} (certificate : PureResourceCertificate Q bd function) :

                                                        The first-order work and size certificates lifted into all execution-cost components.

                                                        Equations
                                                        • One or more equations did not get rendered due to their size.
                                                        Instances For
                                                          theorem PFunctor.DynSystem.DynComputation.PureResourceCertificate.eval_polynomial {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {function : input → output} {resourceLabel : Type x} (certificate : PureResourceCertificate Q bd function) (length : resourceLabel → ℕ → ℕ) (inputSize : ℕ) :
                                                          certificate.polynomial.eval length inputSize = { work := certificate.result.work.eval inputSize + certificate.head.work.eval (certificate.result.outputSize.eval inputSize), queries := 0, traffic := 0, peakStateSize := certificate.result.outputSize.eval inputSize, peakHeadSize := certificate.head.outputSize.eval (certificate.result.outputSize.eval inputSize) }

                                                          Evaluate the derived bound using only the public work and size certificates of its code. The resolved readout is charged at the result code's output-size bound.

                                                          theorem PFunctor.DynSystem.DynComputation.PureResourceCertificate.implements {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {function : input → output} (certificate : PureResourceCertificate Q bd function) :
                                                          certificate.realization.machine.Implements fun (input : input) => FreeM.pure (function input)

                                                          The assembled realization implements the corresponding pure FreeM program.

                                                          theorem PFunctor.DynSystem.DynComputation.PureResourceCertificate.runsWithin {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {function : input → output} {resourceLabel : Type x} (certificate : PureResourceCertificate Q bd function) (allows : (position : p.A) → p.B position → Prop) (length : resourceLabel → ℕ → ℕ) :
                                                          certificate.realization.RunsWithinUnder allows fun (input_1 : input) => certificate.polynomial.eval length (Q.size bd.input input_1)

                                                          Every finite prefix of the pure realization satisfies its derived polynomial bound.

                                                          def PFunctor.DynSystem.DynComputation.PureResourceCertificate.runBound {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {function : input → output} (certificate : PureResourceCertificate Q bd function) (contract : ResponseResourceContract Q bd.interface label) :
                                                          PolynomialRunBound certificate.realization contract

                                                          Package a pure certificate as a run-only polynomial bound under any response contract.

                                                          Equations
                                                          Instances For
                                                            def PFunctor.DynSystem.DynComputation.PureResourceCertificate.programWitness {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {function : input → output} (certificate : PureResourceCertificate Q bd function) (contract : ResponseResourceContract Q bd.interface label) :
                                                            PolynomialProgramWitness Q bd contract fun (input : input) => FreeM.pure (function input)

                                                            Package a pure certificate together with its semantic program witness.

                                                            Equations
                                                            Instances For

                                                              Ranked resource potentials #

                                                              structure PFunctor.DynSystem.DynComputation.RankedResource.PotentialCertificate {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} (R : QuantitativeRealization Q bd) (allows : (position : p.A) → p.B position → Prop) (bound : input → ExecutionCost) :

                                                              Local resource potentials combined with a decreasing, progress-bearing query rank.

                                                              Instances For
                                                                theorem PFunctor.DynSystem.DynComputation.RankedResource.PotentialCertificate.traceCost_add_terminal_le {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {R : QuantitativeRealization Q bd} {allows : (position : p.A) → p.B position → Prop} {bound : input → ExecutionCost} (certificate : PotentialCertificate R allows bound) {start finish : R.machine.State} (trace : R.ExecutionTrace start finish) (htrace : QuantitativeRealization.ExecutionTrace.Conforms allows trace) :
                                                                trace.cost + terminalCost R finish ≤ certificate.potential start

                                                                Transition cost plus the final observation of a conforming trace fits its start potential.

                                                                theorem PFunctor.DynSystem.DynComputation.RankedResource.PotentialCertificate.resolvesInUnder {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {R : QuantitativeRealization Q bd} {allows : (position : p.A) → p.B position → Prop} {bound : input → ExecutionCost} (certificate : PotentialCertificate R allows bound) (state : R.machine.State) :
                                                                R.machine.ResolvesInUnder allows (certificate.toRankedRunCertificate.rank state) state

                                                                The decreasing rank gives branchwise resolution from every hidden state.

                                                                theorem PFunctor.DynSystem.DynComputation.RankedResource.PotentialCertificate.runsWithinUnder {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {R : QuantitativeRealization Q bd} {allows : (position : p.A) → p.B position → Prop} {bound : input → ExecutionCost} (certificate : PotentialCertificate R allows bound) :
                                                                R.RunsWithinUnder allows bound

                                                                A ranked local potential supplies the complete non-vacuous pathwise run bound.

                                                                Ranked polynomial program certificates #

                                                                structure PFunctor.DynSystem.DynComputation.RankedResourceCertificate {p : PFunctor.{u, u}} {C : StepClass} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} (Q : QuantitativeStepClass C) (bd : Boundary C p input output) (contract : ResponseResourceContract Q bd.interface label) (program : input → p.FreeM output) :
                                                                Type (max (max (max (u + 1) v) w) x)

                                                                A polynomial program witness presented through model-relative ranked local potentials.

                                                                Instances For
                                                                  def PFunctor.DynSystem.DynComputation.RankedResourceCertificate.runBound {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {contract : ResponseResourceContract Q bd.interface label} {program : input → p.FreeM output} (certificate : RankedResourceCertificate Q bd contract program) :
                                                                  PolynomialRunBound certificate.realization contract

                                                                  Forget local ranked evidence to the realization-only polynomial run bound.

                                                                  Equations
                                                                  Instances For
                                                                    def PFunctor.DynSystem.DynComputation.RankedResourceCertificate.programWitness {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {contract : ResponseResourceContract Q bd.interface label} {program : input → p.FreeM output} (certificate : RankedResourceCertificate Q bd contract program) :
                                                                    PolynomialProgramWitness Q bd contract program

                                                                    Forget local ranked evidence to the standard polynomial program witness.

                                                                    Equations
                                                                    Instances For

                                                                      Polynomial sequential-composition certificates #

                                                                      structure PFunctor.DynSystem.DynComputation.PolynomialSeqCompHandoffBound {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} {final : Type u} {middleOut : C.Str final} (R₁ : QuantitativeRealization Q bd) (R₂ : QuantitativeRealization Q (bd.mid middleOut)) (contract : ResponseResourceContract Q bd.interface label) (second : PolynomialRunBound R₂ contract) :
                                                                      Type (max u x)

                                                                      A response-model-uniform polynomial envelope for every reachable second-phase run.

                                                                      Instances For
                                                                        structure PFunctor.DynSystem.DynComputation.PolynomialSeqCompCostCertificate {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} [Q.HasComposition] [Q.HasProd] [Q.HasSum] [Q.HasOption] [Q.IsDistributive] {final : Type u} {middleOut : C.Str final} (R₁ : QuantitativeRealization Q bd) (R₂ : QuantitativeRealization Q (bd.mid middleOut)) (contract : ResponseResourceContract Q bd.interface label) :
                                                                        Type (max u x)

                                                                        A response-model-uniform polynomial allowance for structural composition overhead.

                                                                        Instances For
                                                                          def PFunctor.DynSystem.DynComputation.PolynomialRunBound.seqComp {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} [Q.HasComposition] [Q.HasProd] [Q.HasSum] [Q.HasOption] [Q.IsDistributive] {final : Type u} {middleOut : C.Str final} {R₁ : QuantitativeRealization Q bd} {R₂ : QuantitativeRealization Q (bd.mid middleOut)} {contract : ResponseResourceContract Q bd.interface label} (first : PolynomialRunBound R₁ contract) (second : PolynomialRunBound R₂ contract) (handoff : PolynomialSeqCompHandoffBound R₁ R₂ contract second) (cost : PolynomialSeqCompCostCertificate R₁ R₂ contract) :
                                                                          PolynomialRunBound (R₁.seqComp R₂) contract

                                                                          Polynomial run bounds compose using the exact phase decomposition from bounded closure.

                                                                          The first-phase, handoff, and structural bounds are accumulated conservatively. The two peak components may therefore be loose, but remain sound because ExecutionCost combines peaks by max.

                                                                          Equations
                                                                          Instances For
                                                                            def PFunctor.DynSystem.DynComputation.PolynomialProgramWitness.bind {p : PFunctor.{u, u}} {C : StepClass} {Q : QuantitativeStepClass C} {label : Type x} [C.HasProd] [C.HasSum] [C.HasOption] [DecidableEq p.A] {input output : Type u} {bd : Boundary C p input output} [Q.HasComposition] [Q.HasProd] [Q.HasSum] [Q.HasOption] [Q.IsDistributive] {final : Type u} {middleOut : C.Str final} {contract : ResponseResourceContract Q bd.interface label} {program₁ : input → p.FreeM output} {program₂ : output → p.FreeM final} (first : PolynomialProgramWitness Q bd contract program₁) (second : PolynomialProgramWitness Q (bd.mid middleOut) contract program₂) (handoff : PolynomialSeqCompHandoffBound first.realization second.realization contract second.runBound) (cost : PolynomialSeqCompCostCertificate first.realization second.realization contract) :
                                                                            PolynomialProgramWitness Q (bd.withOut middleOut) contract fun (input : input) => (program₁ input).bind program₂

                                                                            Compose program witnesses along FreeM.bind, keeping semantic implementation separate from the resource decomposition certificates needed by the two execution phases.

                                                                            Equations
                                                                            • One or more equations did not get rendered due to their size.
                                                                            Instances For