Documentation

PolyFun.Realizability.Quantitative.Recost

Changing local work charges #

recost retains representations, codes and semantic functions while changing the local work charge. The same machine implements the same programs and has the same traces, query counts, traffic and peak sizes. Only work changes. Transporting work bounds requires a comparison of the old and new charges; arbitrary recosting does not preserve a run bound.

The recosted backend carries the original structural code (HasComposition, HasProd, HasSum, HasOption, IsDistributive), so composite realizations recost part by part (QuantitativeRealization.seqComp_recost). A pointwise decrease of charges is also a simulation (SimulatedBy.ofRecostLE).

def PFunctor.QuantitativeStepClass.recost {C : StepClass} (Q : QuantitativeStepClass C) (cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ) :

Replace the cost function of a backend. Realizers, sizes and admissibility are untouched.

Equations
  • One or more equations did not get rendered due to their size.
Instances For
    @[simp]
    theorem PFunctor.QuantitativeStepClass.recost_Realizer {C : StepClass} {Q : QuantitativeStepClass C} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} {A B : Type u} (a : C.Str A) (b : C.Str B) (f : A → B) :
    (Q.recost fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost').Realizer a b f = Q.Realizer a b f
    @[simp]
    theorem PFunctor.QuantitativeStepClass.recost_size {C : StepClass} {Q : QuantitativeStepClass C} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} {A : Type u} (a : C.Str A) (x : A) :
    (Q.recost fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost').size a x = Q.size a x
    @[simp]
    theorem PFunctor.QuantitativeStepClass.recost_cost {C : StepClass} {Q : QuantitativeStepClass C} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} (r : Q.Realizer a b f) (x : A) :
    (Q.recost fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost').cost r x = cost' r x

    Structure carried by a recosted backend #

    @[instance_reducible]
    instance PFunctor.QuantitativeStepClass.instHasCompositionRecost {C : StepClass} {Q : QuantitativeStepClass C} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} [Q.HasComposition] :
    (Q.recost fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost').HasComposition

    The original identity and composition code, under the new charges. The new charges are arbitrary, so the only generic connection overhead is the composite's own new charge.

    Equations
    • One or more equations did not get rendered due to their size.
    @[instance_reducible]
    instance PFunctor.QuantitativeStepClass.instHasProdRecost {C : StepClass} {Q : QuantitativeStepClass C} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} [C.HasProd] [QP : Q.HasProd] :
    (Q.recost fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost').HasProd

    The original product code.

    Equations
    • One or more equations did not get rendered due to their size.
    @[instance_reducible]
    instance PFunctor.QuantitativeStepClass.instHasSumRecost {C : StepClass} {Q : QuantitativeStepClass C} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} [C.HasSum] [QS : Q.HasSum] :
    (Q.recost fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost').HasSum

    The original sum code.

    Equations
    • One or more equations did not get rendered due to their size.
    @[instance_reducible]
    instance PFunctor.QuantitativeStepClass.instHasOptionRecost {C : StepClass} {Q : QuantitativeStepClass C} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} [C.HasProd] [C.HasOption] [QO : Q.HasOption] :
    (Q.recost fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost').HasOption

    The original optional-value code.

    Equations
    • One or more equations did not get rendered due to their size.
    @[instance_reducible]
    instance PFunctor.QuantitativeStepClass.instIsDistributiveRecost {C : StepClass} {Q : QuantitativeStepClass C} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} [C.HasProd] [C.HasSum] [QD : Q.IsDistributive] :
    (Q.recost fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost').IsDistributive

    The original distributivity code.

    Equations

    Recosting as a simulation #

    noncomputable def PFunctor.QuantitativeStepClass.SimulatedBy.ofRecostLE {C : StepClass} {Q : QuantitativeStepClass C} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} (hle : ∀ {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} (r : Q.Realizer a b f) (x : A), cost' r x ≤ Q.cost r x) :
    Q.SimulatedBy (Q.recost fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') fun {A : Type u} (a : C.Str A) => a

    A pointwise decrease of local charges is a simulation of the original backend by the recosted one, along the identity on representations. It transports PolyRealizers but no run bounds; QuantitativeRealization.runsWithinUnder_recost transports those.

    Equations
    • One or more equations did not get rendered due to their size.
    Instances For
      def PFunctor.DynSystem.DynComputation.QuantitativeRealization.recost {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} (cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ) (R : QuantitativeRealization Q bd) :
      QuantitativeRealization (Q.recost fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') bd

      The same realization over the recosted backend: same machine, state, and codes.

      Equations
      Instances For
        @[simp]
        theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.recost_machine {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} (R : QuantitativeRealization Q bd) :
        (recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') R).machine = R.machine
        @[simp]
        theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.recost_state {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} (R : QuantitativeRealization Q bd) :
        (recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') R).state = R.state
        @[simp]
        theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.recost_initCode {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} (R : QuantitativeRealization Q bd) :
        (recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') R).initCode = R.initCode
        @[simp]
        theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.recost_headCode {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} (R : QuantitativeRealization Q bd) :
        (recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') R).headCode = R.headCode
        @[simp]
        theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.recost_updateCode {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} (R : QuantitativeRealization Q bd) :
        (recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') R).updateCode = R.updateCode
        theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.recost_implements {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} (R : QuantitativeRealization Q bd) (program : α → p.FreeM β) :
        (recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') R).machine.Implements program ↔ R.machine.Implements program

        Semantic correctness does not see the cost function.

        theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.seqComp_recost {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} [Q.HasComposition] [Q.HasProd] [Q.HasSum] [Q.HasOption] [Q.IsDistributive] {D : Type u} {outRep : C.Str D} (R₁ : QuantitativeRealization Q bd) (R₂ : QuantitativeRealization Q (bd.mid outRep)) :
        recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') (R₁.seqComp R₂) = (recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') R₁).seqComp (recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') R₂)

        Recosting commutes with sequential composition: neither the machine nor any code changes, and the recosted backend carries the original structural code.

        def PFunctor.DynSystem.DynComputation.QuantitativeRealization.ExecutionTrace.recost {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} {R : QuantitativeRealization Q bd} {start finish : R.machine.State} :
        R.ExecutionTrace start finish → (QuantitativeRealization.recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') R).ExecutionTrace start finish

        Transport a trace to the recosted realization; the constructors are definitionally the same because the machine is.

        Equations
        Instances For
          @[simp]
          theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.ExecutionTrace.length_recost {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} {R : QuantitativeRealization Q bd} {start finish : R.machine.State} (trace : R.ExecutionTrace start finish) :
          trace.recost.length = trace.length
          theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.ExecutionTrace.cost_recost_queries {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} {R : QuantitativeRealization Q bd} {start finish : R.machine.State} (trace : R.ExecutionTrace start finish) :
          theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.ExecutionTrace.cost_recost_traffic {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} {R : QuantitativeRealization Q bd} {start finish : R.machine.State} (trace : R.ExecutionTrace start finish) :
          theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.ExecutionTrace.cost_recost_peakStateSize {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} {R : QuantitativeRealization Q bd} {start finish : R.machine.State} (trace : R.ExecutionTrace start finish) :
          theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.ExecutionTrace.cost_recost_peakHeadSize {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} {R : QuantitativeRealization Q bd} {start finish : R.machine.State} (trace : R.ExecutionTrace start finish) :
          @[reducible, inline]
          abbrev PFunctor.DynSystem.DynComputation.QuantitativeRealization.recostTrace {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} (R : QuantitativeRealization Q bd) (input : α) {finish : R.machine.State} (trace : R.ExecutionTrace (R.machine.init input) finish) :
          (recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') R).ExecutionTrace ((recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') R).machine.init input) finish

          The transported trace, ascribed to the recosted realization's own initial state so that component lemmas match syntactically.

          Equations
          Instances For
            theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.executionCost_recost_queries {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} (R : QuantitativeRealization Q bd) (input : α) {finish : R.machine.State} (trace : R.ExecutionTrace (R.machine.init input) finish) :
            ((recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') R).executionCost input (R.recostTrace input trace)).queries = (R.executionCost input trace).queries

            Visible queries do not see the cost function.

            theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.executionCost_recost_traffic {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} (R : QuantitativeRealization Q bd) (input : α) {finish : R.machine.State} (trace : R.ExecutionTrace (R.machine.init input) finish) :
            ((recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') R).executionCost input (R.recostTrace input trace)).traffic = (R.executionCost input trace).traffic

            Boundary traffic does not see the cost function.

            theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.executionCost_recost_peakStateSize {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} (R : QuantitativeRealization Q bd) (input : α) {finish : R.machine.State} (trace : R.ExecutionTrace (R.machine.init input) finish) :
            ((recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') R).executionCost input (R.recostTrace input trace)).peakStateSize = (R.executionCost input trace).peakStateSize

            Peak state size does not see the cost function.

            theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.executionCost_recost_peakHeadSize {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} (R : QuantitativeRealization Q bd) (input : α) {finish : R.machine.State} (trace : R.ExecutionTrace (R.machine.init input) finish) :
            ((recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') R).executionCost input (R.recostTrace input trace)).peakHeadSize = (R.executionCost input trace).peakHeadSize

            Peak head size does not see the cost function.

            Only work moves: under the zero charge every prefix charges zero work.

            theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.executionCost_recost_zero_work {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} (R : QuantitativeRealization Q bd) (input : α) {finish : R.machine.State} (trace : R.ExecutionTrace (R.machine.init input) finish) :
            ((recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} (x : Q.Realizer a b f) (x_1 : A) => 0) R).executionCost input (R.recostTrace input trace)).work = 0
            def PFunctor.DynSystem.DynComputation.QuantitativeRealization.ExecutionTrace.restore {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} {R : QuantitativeRealization Q bd} {start finish : R.machine.State} :
            (QuantitativeRealization.recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') R).ExecutionTrace start finish → R.ExecutionTrace start finish

            Restore the original charge annotations on a trace.

            Equations
            Instances For
              @[simp]
              theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.ExecutionTrace.recost_restore {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} {R : QuantitativeRealization Q bd} {start finish : R.machine.State} (trace : (QuantitativeRealization.recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') R).ExecutionTrace start finish) :
              trace.restore.recost = trace
              @[simp]
              theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.ExecutionTrace.conforms_recost {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} {R : QuantitativeRealization Q bd} {start finish : R.machine.State} (trace : R.ExecutionTrace start finish) (allows : (position : p.A) → p.B position → Prop) :
              Conforms allows trace.recost ↔ Conforms allows trace

              Recosting preserves the set of allowed response prefixes.

              @[simp]
              theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.ExecutionTrace.conforms_restore {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} {R : QuantitativeRealization Q bd} {start finish : R.machine.State} (trace : (QuantitativeRealization.recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') R).ExecutionTrace start finish) (allows : (position : p.A) → p.B position → Prop) :
              Conforms allows trace.restore ↔ Conforms allows trace

              Restoring charge annotations preserves allowed response prefixes.

              theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.ExecutionTrace.work_recost_le {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} {R : QuantitativeRealization Q bd} (hle : ∀ {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} (r : Q.Realizer a b f) (x : A), cost' r x ≤ Q.cost r x) {start finish : R.machine.State} (trace : R.ExecutionTrace start finish) :
              trace.recost.cost.work ≤ trace.cost.work

              Pointwise smaller local charges give smaller prefix work.

              theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.executionCost_recost_le {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} (R : QuantitativeRealization Q bd) (input : α) {finish : R.machine.State} (trace : R.ExecutionTrace (R.machine.init input) finish) (hle : ∀ {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} (r : Q.Realizer a b f) (x : A), cost' r x ≤ Q.cost r x) :
              (recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') R).executionCost input (R.recostTrace input trace) ≤ R.executionCost input trace

              Pointwise smaller local charges preserve the whole resource inequality.

              theorem PFunctor.DynSystem.DynComputation.QuantitativeRealization.runsWithinUnder_recost {C : StepClass} [C.HasProd] [C.HasSum] [C.HasOption] {Q : QuantitativeStepClass C} {p : PFunctor.{u, u}} [DecidableEq p.A] {α β : Type u} {bd : Boundary C p α β} {cost' : {A B : Type u} → {a : C.Str A} → {b : C.Str B} → {f : A → B} → Q.Realizer a b f → A → ℕ} (R : QuantitativeRealization Q bd) {allows : (position : p.A) → p.B position → Prop} {bound : α → ExecutionCost} (h : R.RunsWithinUnder allows bound) (hle : ∀ {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} (r : Q.Realizer a b f) (x : A), cost' r x ≤ Q.cost r x) :
              (recost (fun {A B : Type u} {a : C.Str A} {b : C.Str B} {f : A → B} => cost') R).RunsWithinUnder allows bound

              A run bound survives a decrease of local work charges, including the zero charge.