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 #
A second-order polynomial upper bound for every component of ExecutionCost.
- work : Complexity.SecondOrderPolynomial label
Backend-relative local work.
- queries : Complexity.SecondOrderPolynomial label
Number of visible interactions.
- traffic : Complexity.SecondOrderPolynomial label
Total encoded position-response traffic.
- peakStateSize : Complexity.SecondOrderPolynomial label
Peak encoded hidden-state size.
- peakHeadSize : Complexity.SecondOrderPolynomial label
Peak encoded one-step readout size.
Instances For
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
Equations
Regard a first-order polynomial as one which does not inspect its length environment.
Equations
Instances For
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
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
Equations
Replace the base input-size variable in every component.
Equations
- One or more equations did not get rendered due to their size.
Instances For
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
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
Sequentially accumulated costs fit the conservative polynomial sum.
Evaluation is monotone in encoded input size when every length function is monotone.
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
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
One family of admitted responses and monotone encoded-response size envelopes.
Replies admitted at each typed position.
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
Expose a response model as the length environment of a second-order polynomial.
Equations
- model.modulus (PFunctor.DynSystem.DynComputation.ResponseModulus.responseSize a) = model.responseSize a
Instances For
Every length function exposed by a response model is monotone.
A pinned position labelling and a nonempty collection of admissible response models.
- labelOf : p.A → label
Label assigned to each interface position.
- admissible : ResponseResourceModel Q interface self.labelOf → Prop
Response environments admitted by the contract.
- model_nonempty : ∃ (model : ResponseResourceModel Q interface self.labelOf), self.admissible model
At least one global finite response envelope satisfies the contract.
Instances For
Response environments carrying evidence that they satisfy a contract.
Equations
- contract.Model = { model : PFunctor.DynSystem.DynComputation.ResponseResourceModel Q interface contract.labelOf // contract.admissible model }
Instances For
Forget contract admissibility evidence.
Equations
- model.resourceModel = ↑model
Instances For
The second-order length environment supplied by a compatible response model.
Equations
- model.modulus = model.resourceModel.modulus
Instances For
Every compatible response model supplies monotone length functions.
Polynomial run and program witnesses #
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.
- polynomial : ExecutionCostPolynomial (ResponseModulus label)
One bound shared by every response model admitted by the contract.
- runsWithin (model : contract.Model) : R.RunsWithinUnder model.resourceModel.allows fun (value : input) => self.polynomial.eval model.modulus (Q.size bd.input value)
Every conforming finite prefix satisfies the shared bound.
Instances For
The input-indexed execution bound selected by one compatible response model.
Equations
Instances For
Restate the certificate's pathwise theorem through its named input-indexed bound.
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.
- realization : QuantitativeRealization Q bd
The selected executable realization.
- implements : self.realization.machine.Implements program
Semantic agreement with the free interaction syntax.
- outputRecovery : Q.PolyOutputSizeRecovery bd
Returned payload size is recoverable from the charged tagged readout size.
- runBound : PolynomialRunBound self.realization contract
The realization's response-relative execution bound.
Instances For
A second-order polynomial bounding returned payload size through the charged peak readout.
Equations
- witness.outputSizePolynomial = (PFunctor.ExecutionCostPolynomial.ofFirstOrder witness.outputRecovery.polynomial).comp witness.runBound.polynomial.peakHeadSize
Instances For
Every return reached by a conforming execution has polynomially bounded encoded payload size.
Transport a program witness across extensional equality of whole program families.
Equations
- witness.congrProgram hprogram = hprogram ▸ witness
Instances For
A program witness retains ordinary quantitative realizability.
A program witness supplies the corresponding exact bound under each compatible model.
If a response model admits every typed reply, the query component bounds the full free syntax.
Immediately returning programs #
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.
- result : Q.PolyRealizer bd.input bd.out function
Executable result computation with polynomial work and output growth.
- head : Q.PolyRealizer bd.out bd.head Sum.inl
Executable resolved-state readout, including its sum tag.
- outputRecovery : Q.PolyOutputSizeRecovery bd
Returned payload recovery from the tagged readout representation.
- update : Q.Realizer (bd.stateIdx bd.out) (StepClass.HasOption.option bd.out) (ofFn function).update?
Executable evidence for the unreachable partial update.
Instances For
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
Assemble the quantitative realization of an immediately returning function.
Equations
- One or more equations did not get rendered due to their size.
Instances For
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
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.
The assembled realization implements the corresponding pure FreeM program.
Every finite prefix of the pure realization satisfies its derived polynomial bound.
Package a pure certificate as a run-only polynomial bound under any response contract.
Equations
- certificate.runBound contract = { polynomial := certificate.polynomial, runsWithin := ⋯ }
Instances For
Package a pure certificate together with its semantic program witness.
Equations
- certificate.programWitness contract = { realization := certificate.realization, implements := ⋯, outputRecovery := certificate.outputRecovery, runBound := certificate.runBound contract }
Instances For
Ranked resource potentials #
Local resource potentials combined with a decreasing, progress-bearing query rank.
- toRankedRunCertificate : RankedRunCertificate R allows
Backend-independent termination and non-vacuous progress evidence.
- potential : R.machine.State → ExecutionCost
Resource potential available at each hidden state.
Stopping a prefix at any state fits that state's potential.
- query_le {state : R.machine.State} {position : p.A} {next : p.B position → R.machine.State} : R.machine.view state = Sum.inr ⟨position, next⟩ → ∀ (direction : p.B position), allows position direction → queryStepCost R state position direction + self.potential (next direction) ≤ self.potential state
One admitted transition and the successor potential fit the source potential.
- init_le (value : input) : ExecutionCost.ofWork (Q.cost R.initCode value) + self.potential (R.machine.init value) ≤ bound value
Initialization work and the initial potential fit the advertised bound.
- rank_init_le (value : input) : self.toRankedRunCertificate.rank (R.machine.init value) ≤ (bound value).queries
The query component of the advertised bound dominates the initial rank.
Instances For
Transition cost plus the final observation of a conforming trace fits its start potential.
The decreasing rank gives branchwise resolution from every hidden state.
A ranked local potential supplies the complete non-vacuous pathwise run bound.
Ranked polynomial program certificates #
A polynomial program witness presented through model-relative ranked local potentials.
- realization : QuantitativeRealization Q bd
The selected executable realization.
- implements : self.realization.machine.Implements program
Semantic agreement with the free interaction syntax.
- outputRecovery : Q.PolyOutputSizeRecovery bd
Returned payload recovery from the charged tagged readout.
- polynomial : ExecutionCostPolynomial (ResponseModulus label)
One polynomial shared by every compatible response model.
- resourcePotential (model : contract.Model) : RankedResource.PotentialCertificate self.realization model.resourceModel.allows fun (value : input) => self.polynomial.eval model.modulus (Q.size bd.input value)
Local ranked evidence specialized to each compatible model.
Instances For
Forget local ranked evidence to the realization-only polynomial run bound.
Equations
- certificate.runBound = { polynomial := certificate.polynomial, runsWithin := ⋯ }
Instances For
Forget local ranked evidence to the standard polynomial program witness.
Equations
- certificate.programWitness = { realization := certificate.realization, implements := ⋯, outputRecovery := certificate.outputRecovery, runBound := certificate.runBound }
Instances For
Polynomial sequential-composition certificates #
A response-model-uniform polynomial envelope for every reachable second-phase run.
- polynomial : ExecutionCostPolynomial (ResponseModulus label)
Shared polynomial envelope for the reached second phase.
- certificate (model : contract.Model) : SeqCompHandoffBound R₁ model.resourceModel.allows (second.bound model)
The exact handoff certificate under each compatible response model.
- bound_le (model : contract.Model) (input : input) : (self.certificate model).bound input ≤ self.polynomial.eval model.modulus (Q.size bd.input input)
Every model-specific handoff envelope fits the shared polynomial.
Instances For
A response-model-uniform polynomial allowance for structural composition overhead.
- polynomial : ExecutionCostPolynomial (ResponseModulus label)
Shared polynomial envelope for structural wiring and phase switching.
- certificate (model : contract.Model) : SeqCompCostCertificate R₁ R₂ model.resourceModel.allows
The exact composite/source cost comparison under each compatible response model.
- overhead_le (model : contract.Model) (input : input) : (self.certificate model).overhead input ≤ self.polynomial.eval model.modulus (Q.size bd.input input)
Every model-specific structural allowance fits the shared polynomial.
Instances For
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
- first.seqComp second handoff cost = { polynomial := first.polynomial + handoff.polynomial + cost.polynomial, runsWithin := ⋯ }
Instances For
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.