Documentation

PolyFun.PFunctor.Free.Cost.Support

Charges restricted to reachable results and to the calls made #

Sequencing laws need the continuation only where x can return. IsChargeBound.bind_of_le_supp and IsChargeBound.bind_supp take the continuation bound on the structural support x.supp, and costWith_le_cost_add_supp / cost_bind_le_supp restrict the worst-case cost of the continuation the same way.

x.CallsIn S says that every call of x is at a position in S. Under it, charges and handlers matter only on S:

callsIn_iff_isChargeBound reads CallsIn as the zero budget for the indicator of the excluded positions.

Restricted sequencing #

theorem PFunctor.FreeM.IsChargeBound.bind_of_le_supp {P : PFunctor.{uA, uB}} {α : Type v} {ω : Type w} [Add ω] [Zero ω] [Preorder ω] {c : P.A → ω} {B L s : ω} {β : Type v'} {x : P.FreeM α} {f : α → P.FreeM β} (hx : x.IsChargeBound c L s) (hL : L ≤ B) (hf : ∀ a ∈ x.supp, ∀ s' ≤ L, (f a).IsChargeBound c B s') :
(x.bind f).IsChargeBound c B s

Sequencing on reachable results. If x stays within L ≤ B and the continuation at every result x can return stays within B from any amount at most L, then x >>= f stays within B.

theorem PFunctor.FreeM.IsChargeBound.bind_of_le_of_wpFold {P : PFunctor.{uA, uB}} {α : Type v} {ω : Type w} [Add ω] [Zero ω] [Preorder ω] {c : P.A → ω} {B L s : ω} {β : Type v'} {x : P.FreeM α} {f : α → P.FreeM β} {I : α → Prop} (hx : x.IsChargeBound c L s) (hI : wpFold (OpSpec.demonic P) x I) (hL : L ≤ B) (hf : ∀ (a : α), I a → ∀ s' ≤ L, (f a).IsChargeBound c B s') :
(x.bind f).IsChargeBound c B s

Sequencing at an invariant. If x stays within L ≤ B, every result of x satisfies I, and the continuation at every result satisfying I stays within B from any amount at most L, then x >>= f stays within B. Reachable results are the case I := (· ∈ x.supp) (IsChargeBound.bind_of_le_supp).

theorem PFunctor.FreeM.IsChargeBound.bind_of_wpFold {P : PFunctor.{uA, uB}} {α : Type v} {ω : Type w} [AddMonoid ω] [Preorder ω] [AddLeftMono ω] [AddRightMono ω] [CanonicallyOrderedAdd ω] {c : P.A → ω} {s : ω} {β : Type v'} {x : P.FreeM α} {f : α → P.FreeM β} {I : α → Prop} {B₁ B₂ : ω} (hx : x.IsChargeBound c B₁ s) (hI : wpFold (OpSpec.demonic P) x I) (hf : ∀ (a : α), I a → (f a).IsChargeBound c B₂) :
(x.bind f).IsChargeBound c (B₁ + B₂) s

Budgets add under sequencing at an invariant.

theorem PFunctor.FreeM.IsChargeBound.bind_supp {P : PFunctor.{uA, uB}} {α : Type v} {ω : Type w} [AddMonoid ω] [Preorder ω] [AddLeftMono ω] [AddRightMono ω] [CanonicallyOrderedAdd ω] {c : P.A → ω} {s : ω} {β : Type v'} {x : P.FreeM α} {f : α → P.FreeM β} {B₁ B₂ : ω} (hx : x.IsChargeBound c B₁ s) (hf : ∀ a ∈ x.supp, (f a).IsChargeBound c B₂) :
(x.bind f).IsChargeBound c (B₁ + B₂) s

Budgets add under sequencing on reachable results.

theorem PFunctor.FreeM.costWith_le_cost_add_supp {P : PFunctor.{uA, uB}} {α : Type v} {ω : Type w} [AddMonoid ω] [CompleteLattice ω] [AddLeftMono ω] [AddRightMono ω] {c : P.A → ω} (x : P.FreeM α) (k : α → ω) :
costWith c x k ≤ cost c x + ⨆ a ∈ x.supp, k a

The leaf costs split off over reachable results only.

theorem PFunctor.FreeM.cost_bind_le_supp {P : PFunctor.{uA, uB}} {α : Type v} {ω : Type w} [AddMonoid ω] [CompleteLattice ω] [AddLeftMono ω] [AddRightMono ω] {c : P.A → ω} {β : Type v'} (x : P.FreeM α) (f : α → P.FreeM β) :
cost c (x.bind f) ≤ cost c x + ⨆ a ∈ x.supp, cost c (f a)

The cost of a sequence is at most the cost of the first part plus the worst continuation at a reachable result.

Provenance #

def PFunctor.FreeM.CallsIn {P : PFunctor.{uA, uB}} {α : Type v} (x : P.FreeM α) (S : Set P.A) :

Every call of x is at a position in S.

Equations
Instances For
    @[simp]
    theorem PFunctor.FreeM.callsIn_pure {P : PFunctor.{uA, uB}} {α : Type v} {S : Set P.A} (a : α) :
    theorem PFunctor.FreeM.callsIn_liftBind_iff {P : PFunctor.{uA, uB}} {α : Type v} {S : Set P.A} (a : P.A) (r : P.B a → P.FreeM α) :
    (liftBind a r).CallsIn S ↔ a ∈ S ∧ ∀ (b : P.B a), (r b).CallsIn S
    theorem PFunctor.FreeM.callsIn_iff_isChargeBound {P : PFunctor.{uA, uB}} {α : Type v} {S : Set P.A} [DecidablePred fun (x : P.A) => x ∈ S] (x : P.FreeM α) :
    x.CallsIn S ↔ x.IsChargeBound (fun (a : P.A) => if a ∈ S then 0 else 1) 0

    CallsIn is the zero budget for the indicator of the positions outside S.

    def PFunctor.FreeM.MayCall {P : PFunctor.{uA, uB}} {α : Type v} :
    P.FreeM α → P.A → Prop

    x.MayCall a: a call at a occurs in the tree of x, on any branch.

    Equations
    Instances For
      @[simp]
      theorem PFunctor.FreeM.mayCall_pure {P : PFunctor.{uA, uB}} {α : Type v} (x : α) (a : P.A) :
      theorem PFunctor.FreeM.mayCall_liftBind_iff {P : PFunctor.{uA, uB}} {α : Type v} (a' : P.A) (r : P.B a' → P.FreeM α) (a : P.A) :
      (liftBind a' r).MayCall a ↔ a = a' ∨ ∃ (b : P.B a'), (r b).MayCall a
      theorem PFunctor.FreeM.callsIn_iff_forall_mayCall {P : PFunctor.{uA, uB}} {α : Type v} {S : Set P.A} (x : P.FreeM α) :
      x.CallsIn S ↔ ∀ (a : P.A), x.MayCall a → a ∈ S

      A program calls only in S exactly when every call occurring in its tree lies in S.

      A program calls only in the set of calls occurring in it; it is the least such set (callsIn_iff_forall_mayCall).

      theorem PFunctor.FreeM.IsChargeBound.congr_charge {P : PFunctor.{uA, uB}} {α : Type v} {ω : Type w} {S : Set P.A} [Add ω] [LE ω] [Zero ω] {c c' : P.A → ω} {B s : ω} {x : P.FreeM α} (hS : x.CallsIn S) (hc : ∀ a ∈ S, c a = c' a) :

      Charges agreeing on the positions a program calls give the same bound.

      theorem PFunctor.FreeM.costWith_congr_charge {P : PFunctor.{uA, uB}} {α : Type v} {ω : Type w} {S : Set P.A} [Add ω] [CompleteLattice ω] {c c' : P.A → ω} {x : P.FreeM α} (hS : x.CallsIn S) (hc : ∀ a ∈ S, c a = c' a) (k : α → ω) :
      costWith c x k = costWith c' x k

      Charges agreeing on the positions a program calls give the same cost.

      theorem PFunctor.FreeM.liftM_congr_of_callsIn {P : PFunctor.{uA, uB}} {S : Set P.A} {m : Type uB → Type v'} [Monad m] {α : Type uB} {h h' : (a : P.A) → m (P.B a)} {x : P.FreeM α} (hS : x.CallsIn S) (hh : ∀ a ∈ S, h a = h' a) :

      Handlers agreeing on the positions a program calls run it the same way.

      theorem PFunctor.FreeM.IsChargeBound.liftM_of_callsIn {P : PFunctor.{uA, uB}} {ω : Type w} {S : Set P.A} [AddMonoid ω] [Preorder ω] [AddLeftMono ω] [AddRightMono ω] {Q : PFunctor.{uA₂, uB₂}} {α : Type uB} (h : (a : P.A) → Q.FreeM (P.B a)) {c : P.A → ω} {d : Q.A → ω} {B s : ω} (hstep : ∀ a ∈ S, (h a).IsChargeBound d (c a)) {x : P.FreeM α} (hS : x.CallsIn S) (hx : x.IsChargeBound c B s) :

      Free-handler transfer on the positions called. Step certificates are needed only on S.