Research / 2026

Metered verified primitives: data stores whose cost is known before they run

Draft · the definitions and theorems on this page are machine-checked in Lean; independent review is in progress.

A data primitive as a specification, an executor that reports a usage vector, and a bound computed before execution, tied by three laws. A gate that refuses over-budget requests is sound, atomic and never charges more than the limit, and the laws are closed under composition, so a store assembled from primitives inherits both its meaning and its price.

Resource boundsRefinementOrdered indexes
3 laws
state, answer and usage bound: all a primitive must prove, and all a composite inherits
≤ L
charge of every request under a limit L, whether the gate accepts it or refuses it
h + 1 + ⌈e/b⌉
pages read by a range scan of e entries in a tree of height h with leaves holding at least b entries

A database can be described by a function. Given a state and a request, it returns the next state and an answer. For a key–value map the function is three lines long, and for an ordered index it is “filter the sorted rows by the interval, then take the first nn”. An implementation is correct when it computes that function. This is the usual refinement view, and it says nothing about what a request costs.

Some settings need the cost too, and they need it before the request runs. A service that shares one machine among many clients has to decide whether a request fits a budget before letting it consume that budget. A system that bills per request has to state the price in a form a client can check. In both cases the useful object is a bound: a function of the state and the request, computable without executing the request, that dominates what execution will consume.

This article gives a small theory of such objects. A metered verified primitive is a specification, an executor that also reports a usage vector, and a bound, tied by three laws. A gate that runs a primitive only when its priced bound fits a limit is sound and atomic, and it never charges more than the limit. The main result is that the laws are closed under the usual ways of combining stores: reindexing requests, post-processing answers, dependent sequential composition, choice, and products of states. So a data model assembled from primitives inherits both its meaning and its price. The instances are an ordered index, whose correctness rests on a convexity lemma about sorted lists and whose cost bound comes from a row limit in the request, and a document store with a secondary index, built only from the combinators.

Everything below is one Lean 4 file in core Lean, with no imports and no unproved steps. The code blocks, read in order, are that file.

Usage vectors and linear gas

Cost has several dimensions: index seeks, rows stepped over, pages written. Collapsing them into one number too early loses the ability to change prices without redoing proofs. So usage is a vector, and price is applied last.

Usage and gas. A usage vector over kk resources is u∈Nku \in \mathbb N^k. Vectors add pointwise and are ordered componentwise: u≤vu \le v iff ui≤viu_i \le v_i for every ii. A price vector w∈Nkw \in \mathbb N^k assigns a price to each resource, and the gas of uu under ww is the inner product

gasw(u)  =  ⟨w,u⟩  =  ∑i<kwi ui.\mathrm{gas}_w(u) \;=\; \langle w, u \rangle \;=\; \sum_{i \lt k} w_i\, u_i .

Gas is a monotone linear functional. For all w,w′,u,vw, w', u, v:

  1. gasw(u+v)=gasw(u)+gasw(v)\mathrm{gas}_w(u + v) = \mathrm{gas}_w(u) + \mathrm{gas}_w(v),
  2. u≤v  ⟹  gasw(u)≤gasw(v)u \le v \implies \mathrm{gas}_w(u) \le \mathrm{gas}_w(v),
  3. w≤w′  ⟹  gasw(u)≤gasw′(u)w \le w' \implies \mathrm{gas}_w(u) \le \mathrm{gas}_{w'}(u),
  4. gasw(0)=0\mathrm{gas}_w(0) = 0.

Proof. Each is an induction on kk, using distributivity and monotonicity of multiplication on N\mathbb N. ∎

The third property is what makes a usage bound reusable: a bound proved once in usage space is a gas bound under every price table, and raising any price can only raise the gas of a fixed usage. The second is what turns “usage ≤ bound” into “gas ≤ priced bound”.

/-! Metered verified primitives: core Lean 4.16, no imports. -/

/-- A usage vector: one natural-number counter per resource. -/
def Usage (k : Nat) : Type := Fin k → Nat

namespace Usage

def zero : Usage k := fun _ => 0

instance : Add (Usage k) := ⟨fun u v i => u i + v i⟩
instance : LE (Usage k) := ⟨fun u v => ∀ i, u i ≤ v i⟩

theorem add_apply (u v : Usage k) (i : Fin k) : (u + v) i = u i + v i := rfl

theorem le_refl (u : Usage k) : u ≤ u := fun _ => Nat.le_refl _

theorem le_trans {u v x : Usage k} (h₁ : u ≤ v) (h₂ : v ≤ x) : u ≤ x :=
  fun i => Nat.le_trans (h₁ i) (h₂ i)

theorem add_le_add {u u' v v' : Usage k} (h₁ : u ≤ u') (h₂ : v ≤ v') :
    u + v ≤ u' + v' :=
  fun i => Nat.add_le_add (h₁ i) (h₂ i)

theorem zero_le (u : Usage k) : zero ≤ u := fun _ => Nat.zero_le _

/-- The inner product `⟨w, u⟩ = Σ wᵢ uᵢ`, by recursion on the dimension. -/
def dot : (k : Nat) → (Fin k → Nat) → (Fin k → Nat) → Nat
  | 0, _, _ => 0
  | k + 1, w, u => w 0 * u 0 + dot k (fun i => w i.succ) (fun i => u i.succ)

/-- Gas of a usage vector under a price vector `w`. -/
def gas (w u : Usage k) : Nat := dot k w u

theorem dot_add : ∀ (k : Nat) (w u v : Fin k → Nat),
    dot k w (fun i => u i + v i) = dot k w u + dot k w v
  | 0, _, _, _ => rfl
  | k + 1, w, u, v => by
    have ih := dot_add k (fun i => w i.succ) (fun i => u i.succ) (fun i => v i.succ)
    show w 0 * (u 0 + v 0) + dot k (fun i => w i.succ) (fun i => u i.succ + v i.succ)
      = (w 0 * u 0 + dot k _ _) + (w 0 * v 0 + dot k _ _)
    rw [ih, Nat.mul_add]; omega

theorem dot_mono : ∀ (k : Nat) (w u v : Fin k → Nat), (∀ i, u i ≤ v i) →
    dot k w u ≤ dot k w v
  | 0, _, _, _, _ => Nat.le_refl _
  | k + 1, _, _, _, h =>
    Nat.add_le_add (Nat.mul_le_mul_left _ (h 0))
      (dot_mono k _ _ _ (fun i => h i.succ))

theorem dot_mono_prices : ∀ (k : Nat) (w w' u : Fin k → Nat), (∀ i, w i ≤ w' i) →
    dot k w u ≤ dot k w' u
  | 0, _, _, _, _ => Nat.le_refl _
  | k + 1, _, _, _, h =>
    Nat.add_le_add (Nat.mul_le_mul_right _ (h 0))
      (dot_mono_prices k _ _ _ (fun i => h i.succ))

theorem dot_zero : ∀ (k : Nat) (w : Fin k → Nat), dot k w (fun _ => 0) = 0
  | 0, _ => rfl
  | k + 1, w => by
    show w 0 * 0 + dot k _ (fun _ => 0) = 0
    rw [dot_zero k, Nat.mul_zero]

/-- Gas is additive. -/
theorem gas_add (w u v : Usage k) : gas w (u + v) = gas w u + gas w v :=
  dot_add k w u v

/-- Gas is monotone in usage. -/
theorem gas_mono (w : Usage k) {u v : Usage k} (h : u ≤ v) : gas w u ≤ gas w v :=
  dot_mono k w u v h

/-- Gas is monotone in prices. -/
theorem gas_mono_prices {w w' : Usage k} (u : Usage k) (h : w ≤ w') :
    gas w u ≤ gas w' u :=
  dot_mono_prices k w w' u h

theorem gas_zero (w : Usage k) : gas w zero = 0 := dot_zero k w

end Usage

open Usage

The primitive interface and its laws

Metered verified primitive. Over kk resources, a state type σ\sigma, a request type α\alpha and an answer type β\beta, a metered verified primitive PP consists of

specP:σ×α→σ×β(the meaning)execP:σ×α→σ×β×Nk(the implementation, reporting usage)boundP:σ×α→Nk(the price list)\begin{aligned} \mathrm{spec}_P &: \sigma \times \alpha \to \sigma \times \beta &&(\text{the meaning}) \\ \mathrm{exec}_P &: \sigma \times \alpha \to \sigma \times \beta \times \mathbb N^k &&(\text{the implementation, reporting usage}) \\ \mathrm{bound}_P &: \sigma \times \alpha \to \mathbb N^k &&(\text{the price list}) \end{aligned}

satisfying, for every state ss and request aa:

  1. state refinement: execP(s,a)\mathrm{exec}_P(s,a) and specP(s,a)\mathrm{spec}_P(s,a) have the same next state,
  2. answer refinement: they have the same answer,
  3. usage bound: the usage reported by execP(s,a)\mathrm{exec}_P(s,a) is ≤boundP(s,a)\le \mathrm{bound}_P(s,a).

The specification is the definition of what the store means. The executor is free to use any data structure and any algorithm, so long as it computes the same function. The bound is a separate, typically much cheaper function. In the instances below it reads only the request, or the request and a small part of the state.

The interface deliberately puts the usage inside the executor’s result rather than measuring it from outside. Each primitive declares what its counters mean, and law 3 is a statement about those counters. Whether a counter faithfully reflects some physical quantity is a modelling question about that primitive, taken up for the index in the page-bound section below.

-- continues the definitions above
/-- A metered verified primitive over `k` resources: a specification, an
executor that also reports usage, and a usage bound computed from the state
and the request without running the executor. -/
structure Prim (k : Nat) (σ α β : Type) where
  spec  : σ → α → σ × β
  exec  : σ → α → σ × β × Usage k
  bound : σ → α → Usage k
  exec_state  : ∀ s a, (exec s a).1 = (spec s a).1
  exec_answer : ∀ s a, (exec s a).2.1 = (spec s a).2
  exec_usage  : ∀ s a, (exec s a).2.2 ≤ bound s a

Metering with refusal

A gate runs a primitive under a price vector ww and a limit LL. It prices the bound first. If gasw(boundP(s,a))≤L\mathrm{gas}_w(\mathrm{bound}_P(s,a)) \le L it runs the executor and charges the gas of the usage actually reported. Otherwise it refuses: the state stays ss, there is no answer, and the charge is a fixed refusal fee capped at the limit, min⁡(fee,L)\min(\mathit{fee}, L). The refusal branch does not mention the executor at all, so a refused request does no work beyond pricing its bound.

The gate. For every primitive PP, prices ww, limit LL, fee, state ss and request aa, let oo be the gate’s outcome.

  1. Faithful acceptance. If the priced bound fits, oo has state and answer exactly specP(s,a)\mathrm{spec}_P(s,a), and its charge is the gas of the reported usage.
  2. Refusal. If L<gasw(boundP(s,a))L \lt \mathrm{gas}_w(\mathrm{bound}_P(s,a)), then oo has state ss and no answer.
  3. Soundness. Whenever oo has an answer bb, then bb and oo‘s state are exactly those of specP(s,a)\mathrm{spec}_P(s,a).
  4. Charge limit. The charge is ≤L\le L in every case, and ≤gasw(boundP(s,a))\le \mathrm{gas}_w(\mathrm{bound}_P(s,a)) when the request is accepted.
  5. Atomicity. The state of oo is either the specified next state or ss; there is no third possibility.

Proof. Case on the test. In the accepting branch, laws 1 and 2 give faithful acceptance, and law 3 with monotonicity of gas gives charge≤gasw(bound)≤L\text{charge} \le \mathrm{gas}_w(\mathrm{bound}) \le L. In the refusing branch the state is ss, the answer is absent and min⁡(fee,L)≤L\min(\mathit{fee}, L) \le L. Soundness and atomicity follow from the two cases. ∎

Two choices here are deliberate. The client pays for what it used, not for the worst case it was admitted under: the bound is an admission test, and law 3 guarantees the admission test was conservative. And refusal is cheap and side-effect free, which is what makes it safe to try a request whose cost the client is unsure of.

The gate also has a composable form, meter, which is itself a primitive. Its specification answers none when the bound does not fit, and its bound is the primitive’s bound when it fits and zero otherwise. So a gated store can be composed further, and the priced bound of a gated primitive never exceeds the limit. The two forms agree on state and answer in every case, and on the charge of an accepted request (run_eq_meter). They differ only on refusal: meter reports zero usage there, so the composable gate charges no refusal fee, while run charges min⁡(fee,L)\min(\mathit{fee}, L). A refusal fee is a property of the outermost gate, not of a component.

-- continues the definitions above
structure Outcome (σ β : Type) where
  state  : σ
  answer : Option β
  charge : Nat

namespace Prim

variable {k : Nat} {σ α β γ δ : Type}

/-- Accept iff the priced bound fits the limit `L`; a refusal leaves the state
untouched and charges `min fee L`. The refusal branch does not use `exec`. -/
def run (P : Prim k σ α β) (w : Usage k) (L fee : Nat) (s : σ) (a : α) : Outcome σ β :=
  if gas w (P.bound s a) ≤ L then
    ⟨(P.exec s a).1, some (P.exec s a).2.1, gas w (P.exec s a).2.2⟩
  else ⟨s, none, min fee L⟩

theorem run_accepted (P : Prim k σ α β) (w : Usage k) (L fee : Nat) (s : σ) (a : α)
    (h : gas w (P.bound s a) ≤ L) :
    (P.run w L fee s a).state = (P.spec s a).1 ∧
    (P.run w L fee s a).answer = some (P.spec s a).2 ∧
    (P.run w L fee s a).charge = gas w (P.exec s a).2.2 := by
  unfold run; rw [if_pos h]
  exact ⟨P.exec_state s a, by rw [P.exec_answer], rfl⟩

theorem run_refused (P : Prim k σ α β) (w : Usage k) (L fee : Nat) (s : σ) (a : α)
    (h : L < gas w (P.bound s a)) :
    (P.run w L fee s a).state = s ∧ (P.run w L fee s a).answer = none := by
  unfold run; rw [if_neg (Nat.not_le.mpr h)]
  exact ⟨rfl, rfl⟩

theorem run_charge_le_bound (P : Prim k σ α β) (w : Usage k) (L fee : Nat) (s : σ) (a : α)
    (h : gas w (P.bound s a) ≤ L) :
    (P.run w L fee s a).charge ≤ gas w (P.bound s a) := by
  rw [(P.run_accepted w L fee s a h).2.2]
  exact gas_mono w (P.exec_usage s a)

theorem run_charge_le (P : Prim k σ α β) (w : Usage k) (L fee : Nat) (s : σ) (a : α) :
    (P.run w L fee s a).charge ≤ L := by
  by_cases h : gas w (P.bound s a) ≤ L
  · exact Nat.le_trans (P.run_charge_le_bound w L fee s a h) h
  · simp only [run, if_neg h]; exact Nat.min_le_right _ _

/-- Soundness: whatever answer the gate returns is the specified one, with the
specified state. -/
theorem run_sound (P : Prim k σ α β) (w : Usage k) (L fee : Nat) (s : σ) (a : α) (b : β)
    (h : (P.run w L fee s a).answer = some b) :
    (P.run w L fee s a).state = (P.spec s a).1 ∧ b = (P.spec s a).2 := by
  by_cases hg : gas w (P.bound s a) ≤ L
  · have ⟨h1, h2, _⟩ := P.run_accepted w L fee s a hg
    rw [h2] at h
    exact ⟨h1, (Option.some.inj h).symm⟩
  · simp only [run, if_neg hg] at h; cases h

/-- Atomicity: the state either moves exactly as specified or does not move. -/
theorem run_atomic (P : Prim k σ α β) (w : Usage k) (L fee : Nat) (s : σ) (a : α) :
    (P.run w L fee s a).state = (P.spec s a).1 ∨ (P.run w L fee s a).state = s := by
  by_cases hg : gas w (P.bound s a) ≤ L
  · exact Or.inl (P.run_accepted w L fee s a hg).1
  · exact Or.inr (P.run_refused w L fee s a (Nat.lt_of_not_le hg)).1

/-- The gate is itself a metered verified primitive. -/
def meter (P : Prim k σ α β) (w : Usage k) (L : Nat) : Prim k σ α (Option β) where
  spec s a := if gas w (P.bound s a) ≤ L then ((P.spec s a).1, some (P.spec s a).2)
    else (s, none)
  exec s a := if gas w (P.bound s a) ≤ L then
      ((P.exec s a).1, some (P.exec s a).2.1, (P.exec s a).2.2)
    else (s, none, zero)
  bound s a := if gas w (P.bound s a) ≤ L then P.bound s a else zero
  exec_state s a := by
    by_cases h : gas w (P.bound s a) ≤ L
    · simp only [if_pos h]; exact P.exec_state s a
    · simp only [if_neg h]
  exec_answer s a := by
    by_cases h : gas w (P.bound s a) ≤ L
    · simp only [if_pos h]; rw [P.exec_answer]
    · simp only [if_neg h]
  exec_usage s a := by
    by_cases h : gas w (P.bound s a) ≤ L
    · simp only [if_pos h]; exact P.exec_usage s a
    · simp only [if_neg h]; exact Usage.le_refl _

theorem meter_bound_gas_le (P : Prim k σ α β) (w : Usage k) (L : Nat) (s : σ) (a : α) :
    gas w ((P.meter w L).bound s a) ≤ L := by
  show gas w (if gas w (P.bound s a) ≤ L then P.bound s a else zero) ≤ L
  by_cases h : gas w (P.bound s a) ≤ L
  · rw [if_pos h]; exact h
  · rw [if_neg h, gas_zero]; exact Nat.zero_le _

/-- `run` and `meter` agree on state and answer in every case, and on the charge
of an accepted request. On refusal `meter` reports zero usage, while `run`
charges `min fee L`. -/
theorem run_eq_meter (P : Prim k σ α β) (w : Usage k) (L fee : Nat) (s : σ) (a : α) :
    (P.run w L fee s a).state = ((P.meter w L).spec s a).1 ∧
    (P.run w L fee s a).answer = ((P.meter w L).spec s a).2 ∧
    (gas w (P.bound s a) ≤ L →
      (P.run w L fee s a).charge = gas w ((P.meter w L).exec s a).2.2) := by
  by_cases h : gas w (P.bound s a) ≤ L
  · refine ⟨?_, ?_, fun _ => ?_⟩ <;>
      simp only [run, meter, if_pos h, P.exec_state, P.exec_answer]
  · refine ⟨?_, ?_, fun h' => absurd h' h⟩ <;> simp only [run, meter, if_neg h]

Composition closure

The point of an interface with laws is that the laws can be proved once for each way of combining things. Six constructions suffice for the stores in this article, and three more are derived from them.

Combinators. For primitives P:σ×α→σ×βP : \sigma \times \alpha \to \sigma \times \beta and Q:σ×γ→σ×δQ : \sigma \times \gamma \to \sigma \times \delta (and QQ over a state τ\tau where noted):

  • comap P gP\,g reindexes requests by g:γ→αg : \gamma \to \alpha;
  • map P hP\,h post-processes answers by h:β→δh : \beta \to \delta;
  • bind P Q fP\,Q\,f runs PP on aa, then runs QQ on the new state with request f(a,b)f(a, b), where bb is PP‘s answer, and returns both answers;
  • alt P QP\,Q accepts a request of either kind, α+γ\alpha + \gamma, on one state;
  • onFst PP and onSnd PP run PP on one component of a product state, leaving the other untouched.

Derived: seq P Q=bind (comap P π1) Q fP\,Q = \mathrm{bind}\,(\mathrm{comap}\,P\,\pi_1)\,Q\,f with f((a,c),_)=cf((a, c), \_) = c, on pairs of independent requests; sum P Q=alt(onFst P,onSnd Q)P\,Q = \mathrm{alt}(\mathrm{onFst}\,P, \mathrm{onSnd}\,Q) over σ×τ\sigma \times \tau; prod P Q=seq(onFst P,onSnd Q)P\,Q = \mathrm{seq}(\mathrm{onFst}\,P, \mathrm{onSnd}\,Q).

Composition closure. Each combinator applied to metered verified primitives is again a metered verified primitive. Its bound is, respectively, boundP(s,g c)\mathrm{bound}_P(s, g\,c); boundP\mathrm{bound}_P; and for bind

boundbind P Q f(s,a)  =  boundP(s,a)+boundQ(s′,f(a,b)),where (s′,b)=specP(s,a),\begin{gathered} \mathrm{bound}_{\mathrm{bind}\,P\,Q\,f}(s, a) \;=\; \mathrm{bound}_P(s, a) + \mathrm{bound}_Q\big(s', f(a, b)\big), \\ \text{where } (s', b) = \mathrm{spec}_P(s, a), \end{gathered}

the bound of whichever side an alt\mathrm{alt} request selects, and the bound on the touched component for onFst and onSnd. Consequently boundprod P Q((s,t),(a,c))=boundP(s,a)+boundQ(t,c)\mathrm{bound}_{\mathrm{prod}\,P\,Q}((s,t),(a,c)) = \mathrm{bound}_P(s,a) + \mathrm{bound}_Q(t,c).

Proof. The three laws are proved inside each definition, so the type checker will not accept a combinator without them. For bind, state and answer refinement rewrite the executor’s intermediate state and answer to the specified ones, after which QQ‘s refinement laws apply; the usage law is uP+uQ≤boundP+boundQu_P + u_Q \le \mathrm{bound}_P + \mathrm{bound}_Q by componentwise addition of the two usage laws, with QQ‘s bound taken at the specified intermediate state, which equals the executed one. The other cases are a case split or a projection. ∎

Composed with the gate theorem, this is the main result: any store assembled from primitives by these combinators, and run through the gate, is sound and atomic and is charged at most its limit, with no new proof obligations. Correctness and cost are inherited together, because they are one structure.

The bind bound mentions the specified intermediate state, so pricing a composite this way evaluates the first step’s specification. That is often cheap, but it is not free, and for a pre-execution price list one wants more: a bound that depends on the request only.

Cap. PP is capped by B:α→NkB : \alpha \to \mathbb N^k when boundP(s,a)≤B(a)\mathrm{bound}_P(s, a) \le B(a) for every state ss.

Caps compose. If PP is capped by BB, then comap P g\mathrm{comap}\,P\,g is capped by B∘gB \circ g, and map P h\mathrm{map}\,P\,h, onFst P\mathrm{onFst}\,P and onSnd P\mathrm{onSnd}\,P are capped by BB; any cap may be weakened to a pointwise larger one. If PP is capped by B1B_1 and QQ by B2B_2, then seq P Q\mathrm{seq}\,P\,Q is capped by (a,c)↦B1(a)+B2(c)(a,c) \mapsto B_1(a) + B_2(c), alt P Q\mathrm{alt}\,P\,Q by the case split of B1B_1 and B2B_2, and bind P Q f\mathrm{bind}\,P\,Q\,f by a↦B1(a)+D(a)a \mapsto B_1(a) + D(a) for any DD with B2(f(a,b))≤D(a)B_2(f(a,b)) \le D(a) for all bb. If PP is capped by BB and gasw(B(a))≤L\mathrm{gas}_w(B(a)) \le L, the gate accepts aa in every state and returns the specified answer.

Proof. Componentwise addition and transitivity of ≤\le, then monotonicity of gas. ∎

The last clause is the useful one for a client. A cap is a price list that can be published: a request whose capped price fits the limit will be served, whatever the store currently holds.

-- continues the definitions above
/-- Reindex requests. -/
def comap (P : Prim k σ α β) (g : γ → α) : Prim k σ γ β where
  spec s c := P.spec s (g c)
  exec s c := P.exec s (g c)
  bound s c := P.bound s (g c)
  exec_state s c := P.exec_state s (g c)
  exec_answer s c := P.exec_answer s (g c)
  exec_usage s c := P.exec_usage s (g c)

/-- Post-process answers. -/
def map (P : Prim k σ α β) (h : β → δ) : Prim k σ α δ where
  spec s a := ((P.spec s a).1, h (P.spec s a).2)
  exec s a := ((P.exec s a).1, h (P.exec s a).2.1, (P.exec s a).2.2)
  bound := P.bound
  exec_state s a := P.exec_state s a
  exec_answer s a := by show h (P.exec s a).2.1 = h (P.spec s a).2; rw [P.exec_answer]
  exec_usage s a := P.exec_usage s a

/-- Dependent sequential composition: the second request is computed from the first
request and its answer. -/
def bind (P : Prim k σ α β) (Q : Prim k σ γ δ) (f : α → β → γ) : Prim k σ α (β × δ) where
  spec s a :=
    ((Q.spec (P.spec s a).1 (f a (P.spec s a).2)).1,
     ((P.spec s a).2, (Q.spec (P.spec s a).1 (f a (P.spec s a).2)).2))
  exec s a :=
    ((Q.exec (P.exec s a).1 (f a (P.exec s a).2.1)).1,
     ((P.exec s a).2.1, (Q.exec (P.exec s a).1 (f a (P.exec s a).2.1)).2.1),
     (P.exec s a).2.2 + (Q.exec (P.exec s a).1 (f a (P.exec s a).2.1)).2.2)
  bound s a := P.bound s a + Q.bound (P.spec s a).1 (f a (P.spec s a).2)
  exec_state s a := by
    show (Q.exec (P.exec s a).1 (f a (P.exec s a).2.1)).1 = _
    rw [P.exec_state, P.exec_answer, Q.exec_state]
  exec_answer s a := by
    show ((P.exec s a).2.1, (Q.exec (P.exec s a).1 (f a (P.exec s a).2.1)).2.1) = _
    rw [P.exec_state, P.exec_answer, Q.exec_answer]
  exec_usage s a := by
    show (P.exec s a).2.2 + (Q.exec (P.exec s a).1 (f a (P.exec s a).2.1)).2.2 ≤ _
    rw [P.exec_state, P.exec_answer]
    exact add_le_add (P.exec_usage s a) (Q.exec_usage _ _)

/-- Plain sequential composition of two independent requests. -/
def seq (P : Prim k σ α β) (Q : Prim k σ γ δ) : Prim k σ (α × γ) (β × δ) :=
  bind (P.comap Prod.fst) Q (fun a _ => a.2)

/-- Choice on one state: a request of either kind. -/
def alt (P : Prim k σ α β) (Q : Prim k σ γ δ) : Prim k σ (α ⊕ γ) (β ⊕ δ) where
  spec s
    | .inl a => ((P.spec s a).1, .inl (P.spec s a).2)
    | .inr c => ((Q.spec s c).1, .inr (Q.spec s c).2)
  exec s
    | .inl a => ((P.exec s a).1, .inl (P.exec s a).2.1, (P.exec s a).2.2)
    | .inr c => ((Q.exec s c).1, .inr (Q.exec s c).2.1, (Q.exec s c).2.2)
  bound s
    | .inl a => P.bound s a
    | .inr c => Q.bound s c
  exec_state s r := by
    cases r with
    | inl a => exact P.exec_state s a
    | inr c => exact Q.exec_state s c
  exec_answer s r := by
    cases r with
    | inl a => show Sum.inl _ = Sum.inl _; rw [P.exec_answer]
    | inr c => show Sum.inr _ = Sum.inr _; rw [Q.exec_answer]
  exec_usage s r := by
    cases r with
    | inl a => exact P.exec_usage s a
    | inr c => exact Q.exec_usage s c

/-- Run a primitive on the left component of a product state. -/
def onFst (P : Prim k σ α β) : Prim k (σ × τ) α β where
  spec s a := (((P.spec s.1 a).1, s.2), (P.spec s.1 a).2)
  exec s a := (((P.exec s.1 a).1, s.2), (P.exec s.1 a).2.1, (P.exec s.1 a).2.2)
  bound s a := P.bound s.1 a
  exec_state s a := by show (_, s.2) = (_, s.2); rw [P.exec_state]
  exec_answer s a := P.exec_answer s.1 a
  exec_usage s a := P.exec_usage s.1 a

/-- Run a primitive on the right component of a product state. -/
def onSnd (P : Prim k σ α β) : Prim k (τ × σ) α β where
  spec s a := ((s.1, (P.spec s.2 a).1), (P.spec s.2 a).2)
  exec s a := ((s.1, (P.exec s.2 a).1), (P.exec s.2 a).2.1, (P.exec s.2 a).2.2)
  bound s a := P.bound s.2 a
  exec_state s a := by show (s.1, _) = (s.1, _); rw [P.exec_state]
  exec_answer s a := P.exec_answer s.2 a
  exec_usage s a := P.exec_usage s.2 a

/-- Disjoint union of request types over the product of the states. -/
def sum (P : Prim k σ α β) (Q : Prim k τ γ δ) : Prim k (σ × τ) (α ⊕ γ) (β ⊕ δ) :=
  alt (onFst P) (onSnd Q)

/-- Both requests, one per component. -/
def prod (P : Prim k σ α β) (Q : Prim k τ γ δ) : Prim k (σ × τ) (α × γ) (β × δ) :=
  seq (onFst P) (onSnd Q)

theorem bind_bound (P : Prim k σ α β) (Q : Prim k σ γ δ) (f : α → β → γ) (s : σ) (a : α) :
    (bind P Q f).bound s a = P.bound s a + Q.bound (P.spec s a).1 (f a (P.spec s a).2) := rfl

theorem seq_bound (P : Prim k σ α β) (Q : Prim k σ γ δ) (s : σ) (a : α × γ) :
    (seq P Q).bound s a = P.bound s a.1 + Q.bound (P.spec s a.1).1 a.2 := rfl

theorem sum_bound_inl (P : Prim k σ α β) (Q : Prim k τ γ δ) (s : σ × τ) (a : α) :
    (sum P Q).bound s (.inl a) = P.bound s.1 a := rfl

theorem sum_bound_inr (P : Prim k σ α β) (Q : Prim k τ γ δ) (s : σ × τ) (c : γ) :
    (sum P Q).bound s (.inr c) = Q.bound s.2 c := rfl

theorem prod_bound (P : Prim k σ α β) (Q : Prim k τ γ δ) (s : σ × τ) (a : α × γ) :
    (prod P Q).bound s a = P.bound s.1 a.1 + Q.bound s.2 a.2 := rfl

theorem prod_spec (P : Prim k σ α β) (Q : Prim k τ γ δ) (s : σ × τ) (a : α × γ) :
    (prod P Q).spec s a =
      (((P.spec s.1 a.1).1, (Q.spec s.2 a.2).1), ((P.spec s.1 a.1).2, (Q.spec s.2 a.2).2)) :=
  rfl

/-- `P` has a state-independent cap `B`. -/
def Capped (P : Prim k σ α β) (B : α → Usage k) : Prop := ∀ s a, P.bound s a ≤ B a

theorem bind_capped {P : Prim k σ α β} {Q : Prim k σ γ δ} {f : α → β → γ}
    {B₁ : α → Usage k} {B₂ : γ → Usage k} {D : α → Usage k}
    (h₁ : P.Capped B₁) (h₂ : Q.Capped B₂) (hf : ∀ a b, B₂ (f a b) ≤ D a) :
    (bind P Q f).Capped (fun a => B₁ a + D a) :=
  fun s a => add_le_add (h₁ s a) (Usage.le_trans (h₂ _ _) (hf _ _))

theorem seq_capped {P : Prim k σ α β} {Q : Prim k σ γ δ} {B₁ : α → Usage k}
    {B₂ : γ → Usage k} (h₁ : P.Capped B₁) (h₂ : Q.Capped B₂) :
    (seq P Q).Capped (fun a => B₁ a.1 + B₂ a.2) :=
  fun s a => add_le_add (h₁ s a.1) (h₂ _ _)

theorem alt_capped {P : Prim k σ α β} {Q : Prim k σ γ δ} {B₁ : α → Usage k}
    {B₂ : γ → Usage k} (h₁ : P.Capped B₁) (h₂ : Q.Capped B₂) :
    (alt P Q).Capped (fun r => match r with | .inl a => B₁ a | .inr c => B₂ c) := by
  intro s r; cases r with
  | inl a => exact h₁ s a
  | inr c => exact h₂ s c

theorem comap_capped {P : Prim k σ α β} {B : α → Usage k} (hP : P.Capped B) (g : γ → α) :
    (P.comap g).Capped (fun c => B (g c)) :=
  fun s c => hP s (g c)

theorem map_capped {P : Prim k σ α β} {B : α → Usage k} (hP : P.Capped B) (h : β → δ) :
    (P.map h).Capped B :=
  hP

theorem onFst_capped {τ : Type} {P : Prim k σ α β} {B : α → Usage k} (hP : P.Capped B) :
    (P.onFst : Prim k (σ × τ) α β).Capped B :=
  fun s a => hP s.1 a

theorem onSnd_capped {τ : Type} {P : Prim k σ α β} {B : α → Usage k} (hP : P.Capped B) :
    (P.onSnd : Prim k (τ × σ) α β).Capped B :=
  fun s a => hP s.2 a

/-- A cap can always be weakened. -/
theorem Capped.mono {P : Prim k σ α β} {B B' : α → Usage k} (hP : P.Capped B)
    (h : ∀ a, B a ≤ B' a) : P.Capped B' :=
  fun s a => Usage.le_trans (hP s a) (h a)

/-- The gas of a capped composite is decided before anything runs: if the
priced cap fits, the gate accepts. -/
theorem run_accepts_of_capped {P : Prim k σ α β} {B : α → Usage k} (hP : P.Capped B)
    (w : Usage k) (L fee : Nat) (s : σ) (a : α) (h : gas w (B a) ≤ L) :
    (P.run w L fee s a).answer = some (P.spec s a).2 :=
  (P.run_accepted w L fee s a (Nat.le_trans (gas_mono w (hP s a)) h)).2.1

end Prim

An ordered index: convexity gives correctness, the limit gives the cost

An ordered index holds rows (key,id)(\mathit{key}, \mathit{id}) sorted by key and answers range requests: the rows with lo≤key≤hi\mathit{lo} \le \mathit{key} \le \mathit{hi}, at most lim\mathit{lim} of them, in key order. The specification is the obvious one, a filter followed by a take. The executor should do better than filter the whole list: it should seek to the first key ≥lo\ge \mathit{lo}, then step forward until a key exceeds hi\mathit{hi} or lim\mathit{lim} rows have been taken. That executor costs one seek and at most lim\mathit{lim} steps, a bound that depends on the request alone.

Two separate facts are at work. Seek-then-step is correct because the selected rows are contiguous in key order, which is a statement about convex predicates in general. Its cost is bounded because the step loop stops after lim\mathit{lim} rows, which does not depend on convexity at all.

Sorted and convex. For a relation RR on ι\iota, a list is sorted by RR when every element is RR-related to every later element. A predicate pp is convex for RR when R(a,b)R(a,b), R(b,c)R(b,c), p(a)p(a) and p(c)p(c) imply p(b)p(b).

Convex predicates select one run. If pp is convex for RR and ll is sorted by RR, then

filter  p  l  =  takeWhile  p  (dropWhile  (¬p)  l),\mathrm{filter}\;p\;l \;=\; \mathrm{takeWhile}\;p\;\big(\mathrm{dropWhile}\;(\neg p)\;l\big),

and there are lists pre,suf\mathit{pre}, \mathit{suf} with l=pre+ ⁣ ⁣+filter  p  l+ ⁣ ⁣+sufl = \mathit{pre} \mathbin{+\!\!+} \mathrm{filter}\;p\;l \mathbin{+\!\!+} \mathit{suf}. Transitivity of RR is not needed.

Proof. Induction on ll. While the head fails pp, both sides drop it. Once the head aa satisfies pp, every later element bb satisfies R(a,b)R(a,b), since the list is sorted by RR. If such a bb fails pp but a later cc satisfies it, then R(b,c)R(b,c) holds by sortedness, and convexity forces p(b)p(b), a contradiction. So after the first failure nothing more is selected, and the filter equals the take-while. ∎

For a general convex pp, the run is reached by dropWhile (¬p)\mathrm{dropWhile}\,(\neg p), which walks the prefix one element at a time; that is not a seek, and its length depends on the data. Seek-then-step gets a request-only bound when the start of the run can be located by a monotone seek predicate, one that holds on a prefix of every sorted list. Intervals have one: key<lo\mathit{key} \lt \mathit{lo}. An interval [lo,hi][\mathit{lo}, \mathit{hi}] on keys is convex for the key order, and on a key-sorted list the monotone seek reaches the same run as dropWhile (¬p)\mathrm{dropWhile}\,(\neg p), so by the convexity theorem the seek-then-scan computes exactly the range filter. This is how the file proves the index’s answer law. The scan reports the number of rows it examined, which is what the step counter means, and that number is at most lim\mathit{lim}. Moving an id from one key to another is a removal and an insertion, at most two seeks and two writes. With three resources (seeks, steps, writes), the index is a primitive with

bound(range  lo  hi  lim)=(1,lim,0),bound(upd  old  new  id)=(2,0,2).\mathrm{bound}(\mathrm{range}\;\mathit{lo}\;\mathit{hi}\;\mathit{lim}) = (1, \mathit{lim}, 0), \qquad \mathrm{bound}(\mathrm{upd}\;\mathit{old}\;\mathit{new}\;\mathit{id}) = (2, 0, 2).

The state carries its sortedness invariant as a proof, so every state the primitive can reach is sorted, and the answer law can use it.

-- continues the definitions above
/-- `l` is sorted by a relation: every element is related to every later one. -/
def SortedBy {ι : Type} (R : ι → ι → Prop) : List ι → Prop
  | [] => True
  | a :: t => (∀ x ∈ t, R a x) ∧ SortedBy R t

/-- `p` is an interval for `R`: if `a R b R c` and `p` holds at `a` and `c`,
it holds at `b`. -/
def Convex {ι : Type} (R : ι → ι → Prop) (p : ι → Bool) : Prop :=
  ∀ a b c, R a b → R b c → p a = true → p c = true → p b = true

theorem filter_eq_nil_of {ι : Type} (p : ι → Bool) :
    ∀ (l : List ι), (∀ x ∈ l, p x = false) → l.filter p = []
  | [], _ => rfl
  | a :: t, h => by
    rw [List.filter, h a (List.mem_cons_self a t)]
    exact filter_eq_nil_of p t (fun x hx => h x (List.mem_cons_of_mem a hx))

theorem filter_eq_takeWhile_of_head {ι : Type} {R : ι → ι → Prop} {p : ι → Bool}
    (hp : Convex R p) : ∀ (a : ι) (t : List ι), SortedBy R t → (∀ x ∈ t, R a x) →
    p a = true → t.filter p = t.takeWhile p
  | _, [], _, _, _ => rfl
  | a, b :: t, hs, ha, hpa => by
    cases hb : p b with
    | true =>
      rw [List.filter, hb, List.takeWhile, hb]
      exact congrArg (b :: ·) (filter_eq_takeWhile_of_head hp b t hs.2 hs.1 hb)
    | false =>
      rw [List.filter, hb, List.takeWhile, hb]
      apply filter_eq_nil_of
      intro x hx
      cases hpx : p x with
      | false => rfl
      | true =>
        have := hp a b x (ha b (List.mem_cons_self b t)) (hs.1 x hx) hpa hpx
        rw [hb] at this; cases this

/-- **Convexity.** On a sorted list, the elements selected by an interval
predicate are exactly one run: skip the non-selected prefix, then take while
selected. -/
theorem filter_eq_run {ι : Type} {R : ι → ι → Prop} {p : ι → Bool} (hp : Convex R p) :
    ∀ (l : List ι), SortedBy R l →
      l.filter p = (l.dropWhile (fun x => !p x)).takeWhile p
  | [], _ => rfl
  | a :: t, hs => by
    cases ha : p a with
    | false =>
      rw [List.filter, ha, List.dropWhile]
      simp only [ha, Bool.not_false]
      exact filter_eq_run hp t hs.2
    | true =>
      rw [List.filter, ha, List.dropWhile]
      simp only [ha, Bool.not_true]
      rw [List.takeWhile, ha]
      exact congrArg (a :: ·) (filter_eq_takeWhile_of_head hp a t hs.2 hs.1 ha)

theorem takeWhile_append_dropWhile' {ι : Type} (q : ι → Bool) :
    ∀ l : List ι, l.takeWhile q ++ l.dropWhile q = l
  | [] => rfl
  | a :: t => by
    cases h : q a with
    | true => rw [List.takeWhile, List.dropWhile, h]; exact congrArg (a :: ·) (takeWhile_append_dropWhile' q t)
    | false => rw [List.takeWhile, List.dropWhile, h]; rfl

/-- **Contiguity.** The selected elements form one segment of the list. -/
theorem filter_contiguous {ι : Type} {R : ι → ι → Prop} {p : ι → Bool} (hp : Convex R p)
    (l : List ι) (hs : SortedBy R l) :
    ∃ pre suf, l = pre ++ l.filter p ++ suf := by
  refine ⟨l.takeWhile (fun x => !p x),
    (l.dropWhile (fun x => !p x)).dropWhile p, ?_⟩
  rw [filter_eq_run hp l hs, List.append_assoc, takeWhile_append_dropWhile',
    takeWhile_append_dropWhile']

/-- Three resources: seeks, steps, writes. -/
def u3 (a b c : Nat) : Usage 3
  | ⟨0, _⟩ => a
  | ⟨1, _⟩ => b
  | ⟨_ + 2, _⟩ => c

theorem u3_le {a b c a' b' c' : Nat} (ha : a ≤ a') (hb : b ≤ b') (hc : c ≤ c') :
    u3 a b c ≤ u3 a' b' c'
  | ⟨0, _⟩ => ha
  | ⟨1, _⟩ => hb
  | ⟨_ + 2, _⟩ => hc

theorem u3_add (a b c a' b' c' : Nat) :
    u3 a b c + u3 a' b' c' = u3 (a + a') (b + b') (c + c') := by
  funext i
  match i with
  | ⟨0, _⟩ => rfl
  | ⟨1, _⟩ => rfl
  | ⟨_ + 2, _⟩ => rfl

theorem gas_u3 (w : Usage 3) (a b c : Nat) :
    gas w (u3 a b c) = w 0 * a + (w 1 * b + (w 2 * c + 0)) := rfl

/-- Index rows `(key, id)`, ordered by key. -/
abbrev Row := Nat × Nat

def KeyLE (a b : Row) : Prop := a.1 ≤ b.1

def inRange (lo hi : Nat) (r : Row) : Bool := decide (lo ≤ r.1) && decide (r.1 ≤ hi)

theorem inRange_convex (lo hi : Nat) : Convex KeyLE (inRange lo hi) := by
  intro a b c hab hbc ha hc
  simp only [inRange, Bool.and_eq_true, decide_eq_true_eq] at *
  unfold KeyLE at hab hbc
  omega

theorem takeWhile_congr' {ι : Type} {p q : ι → Bool} :
    ∀ (l : List ι), (∀ x ∈ l, p x = q x) → l.takeWhile p = l.takeWhile q
  | [], _ => rfl
  | a :: t, h => by
    have ha := h a (List.mem_cons_self a t)
    cases hq : q a with
    | true =>
      simp only [List.takeWhile, ha, hq]
      exact congrArg (a :: ·) (takeWhile_congr' t (fun x hx => h x (List.mem_cons_of_mem a hx)))
    | false => simp only [List.takeWhile, ha, hq]

theorem dropWhile_eq_nil_of {ι : Type} (q : ι → Bool) :
    ∀ (l : List ι), (∀ x ∈ l, q x = true) → l.dropWhile q = []
  | [], _ => rfl
  | a :: t, h => by
    rw [List.dropWhile, h a (List.mem_cons_self a t)]
    exact dropWhile_eq_nil_of q t (fun x hx => h x (List.mem_cons_of_mem a hx))

/-- After the seek, every remaining key is at least `lo`. -/
theorem seek_ge (lo : Nat) : ∀ (l : List Row), SortedBy KeyLE l →
    ∀ x ∈ l.dropWhile (fun r => decide (r.1 < lo)), lo ≤ x.1
  | [], _, _, hx => nomatch hx
  | a :: t, hs, x, hx => by
    by_cases h : a.1 < lo
    · rw [List.dropWhile, decide_eq_true h] at hx
      exact seek_ge lo t hs.2 x hx
    · rw [List.dropWhile, decide_eq_false h] at hx
      cases hx with
      | head => omega
      | tail _ hx => have := hs.1 x hx; unfold KeyLE at this; omega

/-- On a sorted list the monotone seek (skip keys below `lo`) reaches the run
selected by the interval: taking while in range from there gives the same list
as the generic walk `dropWhile (not in range)`. -/
theorem seek_run (lo hi : Nat) : ∀ (l : List Row), SortedBy KeyLE l →
    (l.dropWhile (fun r => decide (r.1 < lo))).takeWhile (inRange lo hi)
      = (l.dropWhile (fun r => !inRange lo hi r)).takeWhile (inRange lo hi)
  | [], _ => rfl
  | a :: t, hs => by
    by_cases h : a.1 < lo
    · have e : inRange lo hi a = false := by simp [inRange]; intro h'; omega
      simp only [List.dropWhile, decide_eq_true h, e, Bool.not_false]
      exact seek_run lo hi t hs.2
    · by_cases h2 : a.1 ≤ hi
      · have e : inRange lo hi a = true := by simp [inRange]; omega
        simp only [List.dropWhile, decide_eq_false h, e, Bool.not_true]
      · have e : inRange lo hi a = false := by simp [inRange, h2]
        have hall : ∀ x ∈ t, (!inRange lo hi x) = true := by
          intro x hx; have := hs.1 x hx; unfold KeyLE at this
          have : ¬ x.1 ≤ hi := by omega
          simp [inRange, this]
        simp only [List.dropWhile, decide_eq_false h, e, Bool.not_false]
        rw [dropWhile_eq_nil_of _ t hall]
        simp only [List.takeWhile, e]

/-- **Seek-then-scan is the range filter.** Correctness comes from convexity:
the interval selects one run (`filter_eq_run`), and the seek reaches its start. -/
theorem seek_scan_eq (lo hi : Nat) (l : List Row) (hs : SortedBy KeyLE l) :
    (l.dropWhile (fun r => decide (r.1 < lo))).takeWhile (fun r => decide (r.1 ≤ hi))
      = l.filter (inRange lo hi) := by
  have hc : ∀ x ∈ l.dropWhile (fun r => decide (r.1 < lo)),
      decide (x.1 ≤ hi) = inRange lo hi x := by
    intro x hx
    have := seek_ge lo l hs x hx
    simp [inRange, this]
  rw [takeWhile_congr' _ hc, seek_run lo hi l hs,
    ← filter_eq_run (inRange_convex lo hi) l hs]

/-- The scan: at most `m` examined rows, counted. -/
def scan (hi : Nat) : Nat → List Row → List Row × Nat
  | 0, _ => ([], 0)
  | _ + 1, [] => ([], 0)
  | m + 1, r :: rs =>
    if r.1 ≤ hi then (r :: (scan hi m rs).1, (scan hi m rs).2 + 1) else ([], 1)

theorem scan_fst (hi : Nat) : ∀ (m : Nat) (l : List Row),
    (scan hi m l).1 = (l.takeWhile (fun r => decide (r.1 ≤ hi))).take m
  | 0, _ => by simp [scan]
  | _ + 1, [] => rfl
  | m + 1, r :: rs => by
    by_cases h : r.1 ≤ hi
    · simp only [scan, if_pos h, List.takeWhile, decide_eq_true h, List.take_succ_cons]
      rw [scan_fst hi m rs]
    · simp only [scan, if_neg h, List.takeWhile, decide_eq_false h, List.take_nil]

theorem scan_snd_le (hi : Nat) : ∀ (m : Nat) (l : List Row), (scan hi m l).2 ≤ m
  | 0, _ => Nat.le_refl _
  | _ + 1, [] => Nat.zero_le _
  | m + 1, r :: rs => by
    by_cases h : r.1 ≤ hi
    · simp only [scan, if_pos h]; have := scan_snd_le hi m rs; omega
    · simp only [scan, if_neg h]; omega

/-- Sorted insertion and removal. -/
def ins (x : Row) : List Row → List Row
  | [] => [x]
  | y :: ys => if x.1 ≤ y.1 then x :: y :: ys else y :: ins x ys

theorem mem_ins {x z : Row} : ∀ {l : List Row}, z ∈ ins x l → z = x ∨ z ∈ l
  | [], h => by simp [ins] at h; exact Or.inl h
  | y :: ys, h => by
    unfold ins at h
    split at h
    · cases h with
      | head => exact Or.inl rfl
      | tail _ h => exact Or.inr h
    · cases h with
      | head => exact Or.inr (List.mem_cons_self _ _)
      | tail _ h =>
        cases mem_ins h with
        | inl h => exact Or.inl h
        | inr h => exact Or.inr (List.mem_cons_of_mem _ h)

theorem ins_sorted (x : Row) : ∀ (l : List Row), SortedBy KeyLE l → SortedBy KeyLE (ins x l)
  | [], _ => by
    show (∀ z ∈ ([] : List Row), KeyLE x z) ∧ True
    exact ⟨fun _ h => (nomatch h), trivial⟩
  | y :: ys, hs => by
    unfold ins
    split
    · next h =>
      refine ⟨?_, hs⟩
      intro z hz
      cases hz with
      | head => exact h
      | tail _ hz => exact Nat.le_trans h (hs.1 z hz)
    · next h =>
      refine ⟨?_, ins_sorted x ys hs.2⟩
      intro z hz
      cases mem_ins hz with
      | inl e => subst e; unfold KeyLE; omega
      | inr hz => exact hs.1 z hz

theorem filter_sorted {ι : Type} {R : ι → ι → Prop} (p : ι → Bool) :
    ∀ (l : List ι), SortedBy R l → SortedBy R (l.filter p)
  | [], _ => trivial
  | a :: t, hs => by
    cases h : p a with
    | false => rw [List.filter, h]; exact filter_sorted p t hs.2
    | true =>
      rw [List.filter, h]
      exact ⟨fun x hx => hs.1 x (List.mem_filter.mp hx).1, filter_sorted p t hs.2⟩

def erase (x : Row) (l : List Row) : List Row := l.filter (fun y => !decide (y = x))

/-- The index state carries its sortedness invariant. -/
def Idx : Type := { l : List Row // SortedBy KeyLE l }

def Idx.empty : Idx := ⟨[], trivial⟩

inductive IReq where
  /-- rows with `lo ≤ key ≤ hi`, at most `lim` of them -/
  | range (lo hi lim : Nat)
  /-- move row id `id` from key `old` to key `new` (either may be absent) -/
  | upd (old new : Option Nat) (id : Nat)

def Idx.move (old new : Option Nat) (id : Nat) (s : Idx) : Idx :=
  let s₁ : Idx := match old with
    | none => s
    | some o => ⟨erase (o, id) s.1, filter_sorted _ _ s.2⟩
  match new with
  | none => s₁
  | some n => ⟨ins (n, id) s₁.1, ins_sorted _ _ s₁.2⟩

def ocount : Option Nat → Nat
  | none => 0
  | some _ => 1

theorem ocount_le (o : Option Nat) : ocount o ≤ 1 := by cases o <;> simp [ocount]

def index : Prim 3 Idx IReq (List Row) where
  spec s
    | .range lo hi lim => (s, (s.1.filter (inRange lo hi)).take lim)
    | .upd old new id => (Idx.move old new id s, [])
  exec s
    | .range lo hi lim =>
      let r := scan hi lim (s.1.dropWhile (fun r => decide (r.1 < lo)))
      (s, r.1, u3 1 r.2 0)
    | .upd old new id =>
      (Idx.move old new id s, [], u3 (ocount old + ocount new) 0 (ocount old + ocount new))
  bound _
    | .range _ _ lim => u3 1 lim 0
    | .upd _ _ _ => u3 2 0 2
  exec_state s q := by cases q <;> rfl
  exec_answer s q := by
    cases q with
    | range lo hi lim =>
      show (scan hi lim _).1 = _
      rw [scan_fst, seek_scan_eq lo hi s.1 s.2]
    | upd => rfl
  exec_usage s q := by
    cases q with
    | range lo hi lim => exact u3_le (Nat.le_refl _) (scan_snd_le _ _ _) (Nat.le_refl _)
    | upd old new id =>
      have := ocount_le old; have := ocount_le new
      exact u3_le (by omega) (Nat.le_refl _) (by omega)

/-- The index's bound reads the request only. -/
def IReq.cap : IReq → Usage 3
  | .range _ _ lim => u3 1 lim 0
  | .upd _ _ _ => u3 2 0 2

theorem index_capped : index.Capped IReq.cap := by
  intro s q; cases q <;> exact Usage.le_refl _

From one seek to pages

In the list model a seek is one abstract operation. In a balanced search tree stored in fixed-size pages it is a root-to-leaf descent, and the steps that follow cross leaf boundaries. The link between the abstract counters and pages is a separate, purely arithmetic fact.

Page bound for a range scan. In a tree of height hh, suppose a scan starts at offset o≤s0o \le s_0 in a first leaf holding s0s_0 entries and reads ee entries in all, counted from that offset (the first min⁡(e,s0−o)\min(e, s_0 - o) of them in the first leaf), and every leaf after the first holds at least b≥1b \ge 1 entries. Then the scan reads at most

h+1+⌈e/b⌉h + 1 + \left\lceil e / b \right\rceil

pages: the hh interior pages and the first leaf on the seek path, then the later leaves. The bound is monotone in ee: if e≤lime \le \mathit{lim}, the scan reads at most h+1+⌈lim/b⌉h + 1 + \lceil \mathit{lim}/b \rceil pages.

Proof. Let nn be the number of later leaves visited while the e′=e−(s0−o)e' = e - (s_0 - o) entries left after the first leaf remain to be read (truncated at zero). Every visited leaf except possibly the last consumes at least bb entries, and the last is entered with at least one entry still to read, so b(n−1)<e′b(n-1) \lt e', that is b⋅n<e′+bb \cdot n \lt e' + b, by induction on the leaf list. Since e′≤ee' \le e, n≤⌊(e+b−1)/b⌋=⌈e/b⌉n \le \lfloor (e + b - 1)/b \rfloor = \lceil e/b \rceil, and the same argument with e′≤lime' \le \mathit{lim} gives the monotone form. ∎

This theorem is an arithmetic model of a tree; it is not derived from the list executor. Read together with the index, it says: if a tree executor reads one entry per step counted by the index, so that ee is at most the step count and hence at most lim\mathit{lim}, then a range request whose abstract usage is (1,lim,0)(1, \mathit{lim}, 0) touches at most h+1+⌈lim/b⌉h + 1 + \lceil \mathit{lim}/b \rceil pages in any tree satisfying the occupancy hypothesis. The premise about the tree executor is part of the model, not a lemma in the file. That hypothesis is the classical B-tree invariant (every non-root node at least half full) and has to be maintained by the tree’s insertion and deletion algorithms; a tree that deletes lazily without merging leaves can violate it, and then the page count of a scan is no longer bounded by its entry count.

-- continues the definitions above
/-- Leaves visited while reading `k` more entries, starting at a leaf
boundary, given the sizes of the following leaves. -/
def leafRun : Nat → List Nat → Nat
  | 0, _ => 0
  | _ + 1, [] => 0
  | k + 1, s :: rest => 1 + leafRun (k + 1 - s) rest

theorem leafRun_mul_lt (b : Nat) (hb : 0 < b) : ∀ (k : Nat) (sizes : List Nat),
    (∀ s ∈ sizes, b ≤ s) → b * leafRun k sizes < k + b
  | 0, _, _ => by simp [leafRun]; exact hb
  | _ + 1, [], _ => by simp [leafRun]; omega
  | k + 1, s :: rest, h => by
    have hs := h s (List.mem_cons_self s rest)
    have ih := leafRun_mul_lt b hb (k + 1 - s) rest
      (fun x hx => h x (List.mem_cons_of_mem s hx))
    show b * (1 + leafRun (k + 1 - s) rest) < k + 1 + b
    rw [Nat.mul_add, Nat.mul_one]
    by_cases hk : s ≤ k + 1
    · omega
    · have e : k + 1 - s = 0 := by omega
      rw [e] at ih ⊢
      simp [leafRun]

/-- Pages read by a range scan of `k` entries in a tree of height `h`: the
seek path (`h` interior pages and the first leaf), then the later leaves. -/
def rangePages (h o k : Nat) : List Nat → Nat
  | [] => h + 1
  | s₀ :: rest => h + 1 + leafRun (k - (s₀ - o)) rest

/-- **Page bound.** If every leaf after the first holds at least `b ≥ 1`
entries, a range scan of `k` entries reads at most `h + 1 + ⌈k / b⌉` pages. -/
theorem rangePages_le (h o k b : Nat) (hb : 0 < b) (leaves : List Nat)
    (hmin : ∀ s ∈ leaves.tail, b ≤ s) :
    rangePages h o k leaves ≤ h + 1 + (k + b - 1) / b := by
  cases leaves with
  | nil => simp [rangePages]
  | cons s₀ rest =>
    show h + 1 + leafRun (k - (s₀ - o)) rest ≤ _
    have hr := leafRun_mul_lt b hb (k - (s₀ - o)) rest hmin
    have hd : leafRun (k - (s₀ - o)) rest ≤ (k + b - 1) / b := by
      rw [Nat.le_div_iff_mul_le hb, Nat.mul_comm]
      omega
    omega

/-- **Monotone form.** A scan of at most `lim` entries reads at most
`h + 1 + ⌈lim / b⌉` pages. -/
theorem rangePages_le_of_le (h o k lim b : Nat) (hb : 0 < b) (hk : k ≤ lim)
    (leaves : List Nat) (hmin : ∀ s ∈ leaves.tail, b ≤ s) :
    rangePages h o k leaves ≤ h + 1 + (lim + b - 1) / b := by
  cases leaves with
  | nil => simp [rangePages]
  | cons s₀ rest =>
    show h + 1 + leafRun (k - (s₀ - o)) rest ≤ _
    have hr := leafRun_mul_lt b hb (k - (s₀ - o)) rest hmin
    have hd : leafRun (k - (s₀ - o)) rest ≤ (lim + b - 1) / b := by
      rw [Nat.le_div_iff_mul_le hb, Nat.mul_comm]
      omega
    omega

An example composite: a document store with a secondary index

The second primitive is a key–value map from document ids to one numeric field. Every request answers the value held before it: get returns the current value, and put and del return the value they overwrite. A lookup or a write is one seek, and a write is also one write.

-- continues the definitions above
def KV : Type := Nat → Option Nat

def KV.empty : KV := fun _ => none

def KV.set (m : KV) (k : Nat) (v : Option Nat) : KV := fun j => if j = k then v else m j

inductive KReq where
  | get (k : Nat)
  | put (k v : Nat)
  | del (k : Nat)

/-- Every request answers the value held before it. -/
def kvSpec (m : KV) : KReq → KV × Option Nat
  | .get k => (m, m k)
  | .put k v => (m.set k (some v), m k)
  | .del k => (m.set k none, m k)

def kvUsage : KReq → Usage 3
  | .get _ => u3 1 0 0
  | .put _ _ => u3 1 0 1
  | .del _ => u3 1 0 1

def kv : Prim 3 KV KReq (Option Nat) where
  spec := kvSpec
  exec m q := ((kvSpec m q).1, (kvSpec m q).2, kvUsage q)
  bound _ q := kvUsage q
  exec_state _ _ := rfl
  exec_answer _ _ := rfl
  exec_usage _ q := Usage.le_refl (kvUsage q)

theorem kv_get_put (m : KV) (k v : Nat) :
    (kv.spec (kv.spec m (.put k v)).1 (.get k)).2 = some v := by
  show (if k = k then some v else m k) = some v
  rw [if_pos rfl]

Answering the old value is what makes the secondary index composable. A document store keeps the map and the index side by side, in the product state KV×Idx\mathit{KV} \times \mathit{Idx}. A write first goes to the map, through onFst. The map’s answer, the old field value, is then turned by a function reindex into an index request that moves the document from its old key to its new one, through onSnd. That is exactly a bind. A read goes to the index alone. Choice between the two is alt, and the request and answer types of the store are fitted with comap and map.

  1. request
    put id v
  2. onFst kv
    store the field
    answers old value
  3. reindex
    old ↦ index move
    upd old (some v) id
  4. onSnd index
    move the row
    erase, then insert
  5. bound
    (1,0,1) + (2,0,2)
    ≤ (3, 0, 3)
Fig. 1A write to the document store is a bind of two primitives on disjoint halves of the state. The map's answer, the overwritten value, determines the index request.

No law is proved for the store itself. It is a metered verified primitive because every combinator returns one, and its cap is derived from the caps of the parts by the cap lemmas, one per combinator: the map and the index are capped by their request-only bounds, onFst and onSnd keep those caps, bind adds the map’s cap to the index’s cap for a move, alt splits by request kind, and comap and map carry the result to the store’s request and answer types. A put or del is capped by three seeks and three writes, and a find by one seek and lim\mathit{lim} steps.

-- continues the definitions above
/-- Writes: the store answers the old field value, which tells the index what
to move. -/
def reindex : KReq → Option Nat → IReq
  | .get k, _ => .upd none none k
  | .put k v, old => .upd old (some v) k
  | .del k, old => .upd old none k

def writes : Prim 3 (KV × Idx) KReq (Option Nat × List Row) :=
  Prim.bind kv.onFst index.onSnd reindex

/-- Reads go to the index alone. -/
def reads : Prim 3 (KV × Idx) IReq (List Row) := index.onSnd

inductive DReq where
  | put (id v : Nat)
  | del (id : Nat)
  | find (lo hi lim : Nat)

def DReq.route : DReq → KReq ⊕ IReq
  | .put id v => .inl (.put id v)
  | .del id => .inl (.del id)
  | .find lo hi lim => .inr (.range lo hi lim)

def DReq.cap : DReq → Usage 3
  | .put _ _ => u3 3 0 3
  | .del _ => u3 3 0 3
  | .find _ _ lim => u3 1 lim 0

def docAnswer : (Option Nat × List Row) ⊕ List Row → List Row
  | .inl _ => []
  | .inr l => l

/-- The document store: a metered verified primitive by the closure theorems. -/
def docs : Prim 3 (KV × Idx) DReq (List Row) :=
  ((Prim.alt writes reads).comap DReq.route).map docAnswer

theorem kv_capped : kv.Capped kvUsage := fun _ q => Usage.le_refl (kvUsage q)

/-- Every write turns into an index move, so the second step is capped by
`(2, 0, 2)` whatever the map answered. -/
theorem writes_capped : writes.Capped (fun q => kvUsage q + u3 2 0 2) :=
  Prim.bind_capped (D := fun _ => u3 2 0 2)
    (Prim.onFst_capped kv_capped) (Prim.onSnd_capped index_capped)
    (fun q _ => by cases q <;> exact Usage.le_refl _)

theorem reads_capped : reads.Capped IReq.cap := Prim.onSnd_capped index_capped

/-- The store's cap, derived from the caps of its parts. -/
theorem docs_capped : docs.Capped DReq.cap :=
  (Prim.map_capped (Prim.comap_capped (Prim.alt_capped writes_capped reads_capped)
    DReq.route) docAnswer).mono (fun q => by
      cases q with
      | put id v =>
        show u3 1 0 1 + u3 2 0 2 ≤ u3 3 0 3
        rw [u3_add]; exact Usage.le_refl _
      | del id =>
        show u3 1 0 1 + u3 2 0 2 ≤ u3 3 0 3
        rw [u3_add]; exact Usage.le_refl _
      | find lo hi lim => exact Usage.le_refl _)

The index stays exact

The closure theorem says the executor computes the store’s specification. It does not say the specification is the one wanted, namely that find returns the documents whose field lies in the range. That is a property of the specification alone, and it holds on every reachable state.

Exactness of the secondary index. Call a state (m,i)(m, i) consistent when, for every value vv and id, (v,id)(v, \mathit{id}) is a row of ii iff m(id)=vm(\mathit{id}) = v. Call it invariant when it is also duplicate-free: no row of ii occurs twice. The empty state is invariant, and every request maps an invariant state to an invariant state. On an invariant state, find  lo  hi  lim\mathrm{find}\;\mathit{lo}\;\mathit{hi}\;\mathit{lim} answers the first lim\mathit{lim} rows of the list sel\mathit{sel} of selected rows, where sel\mathit{sel} is duplicate-free and its members are exactly the pairs (v,id)(v, \mathit{id}) with m(id)=vm(\mathit{id}) = v and lo≤v≤hi\mathit{lo} \le v \le \mathit{hi}; the answer is sorted by key, duplicate-free, and has length min⁡(lim,∣sel∣)\min(\mathit{lim}, |\mathit{sel}|). Every state reachable from empty by gated requests, under any prices, limits and fees, is invariant.

Proof. A move from old\mathit{old} to new\mathit{new} leaves exactly the rows that equal (new,id)(\mathit{new}, \mathit{id}) or were present and differ from (old,id)(\mathit{old}, \mathit{id}). For a put or delete of id\mathit{id}, the old value comes from the map, so by consistency the removed row is the only row for id\mathit{id}; rows for other ids are untouched. Removal is a filter and preserves freedom from duplicates; the inserted row (new,id)(\mathit{new}, \mathit{id}) is absent after the removal, again by consistency, so insertion preserves it too. The find clause is the filter’s membership lemma combined with consistency, and sortedness of the answer comes from the index state’s sortedness invariant, which filter and take preserve. Reachability is an induction over gated steps: by atomicity each step either moves to the specified state, which is invariant, or stays put. ∎

Combine this with the gate, under prices of 10 per seek and 1 per step, on a state ss reachable from empty. If 10+lim≤L10 + \mathit{lim} \le L, the gate accepts find  lo  hi  lim\mathrm{find}\;\mathit{lo}\;\mathit{hi}\;\mathit{lim}, leaves ss unchanged, charges at most 10+lim10 + \mathit{lim}, and returns the first min⁡(lim,n)\min(\mathit{lim}, n) of the nn matching documents, in field order and without repetition, whatever the store holds. If L<10+limL \lt 10 + \mathit{lim}, it refuses and the state is unchanged. Both cases are gated_find in the run below; the description of the answer comes from reachable_inv, docs_find and docs_find_shape.

-- continues the definitions above
theorem mem_ins_iff {x z : Row} {l : List Row} : z ∈ ins x l ↔ z = x ∨ z ∈ l := by
  refine ⟨mem_ins, ?_⟩
  induction l with
  | nil => intro h; cases h with
    | inl e => subst e; exact List.mem_singleton.mpr rfl
    | inr h => exact nomatch h
  | cons y ys ih =>
    intro h
    unfold ins
    split
    · cases h with
      | inl e => subst e; exact List.mem_cons_self _ _
      | inr h => exact List.mem_cons_of_mem _ h
    · cases h with
      | inl e => exact List.mem_cons_of_mem _ (ih (Or.inl e))
      | inr h =>
        cases h with
        | head => exact List.mem_cons_self _ _
        | tail _ h => exact List.mem_cons_of_mem _ (ih (Or.inr h))

theorem mem_move (old new : Option Nat) (id : Nat) (s : Idx) (a b : Nat) :
    (a, b) ∈ (Idx.move old new id s).1 ↔
      (some a = new ∧ b = id) ∨ ((a, b) ∈ s.1 ∧ ¬ (some a = old ∧ b = id)) := by
  cases old <;> cases new <;> simp [Idx.move, erase, mem_ins_iff, List.mem_filter, Decidable.imp_iff_not_or]

def docs0 : KV × Idx := (KV.empty, Idx.empty)

/-- The index holds exactly the pairs `(field, id)` of the stored documents. -/
def Consistent (s : KV × Idx) : Prop := ∀ v id, (v, id) ∈ s.2.1 ↔ s.1 id = some v

theorem consistent_empty : Consistent docs0 := by
  intro v id; simp [docs0, Idx.empty, KV.empty]

/-- Every request keeps the secondary index exact. -/
theorem docs_consistent (s : KV × Idx) (q : DReq) (h : Consistent s) :
    Consistent (docs.spec s q).1 := by
  cases q with
  | put i v =>
    show Consistent (s.1.set i (some v), Idx.move (s.1 i) (some v) i s.2)
    intro v' i'
    show _ ↔ (if i' = i then some v else s.1 i') = some v'
    rw [mem_move]
    by_cases e : i' = i
    · subst e
      rw [if_pos rfl]
      constructor
      · rintro (⟨hv, _⟩ | ⟨hm, hn⟩)
        · exact hv.symm
        · exact absurd ⟨((h v' i').mp hm).symm, rfl⟩ hn
      · intro hv; exact Or.inl ⟨hv.symm, rfl⟩
    · rw [if_neg e]
      constructor
      · rintro (⟨_, hi⟩ | ⟨hm, _⟩)
        · exact absurd hi e
        · exact (h v' i').mp hm
      · intro hm; exact Or.inr ⟨(h v' i').mpr hm, fun hc => e hc.2⟩
  | del i =>
    show Consistent (s.1.set i none, Idx.move (s.1 i) none i s.2)
    intro v' i'
    show _ ↔ (if i' = i then none else s.1 i') = some v'
    rw [mem_move]
    by_cases e : i' = i
    · subst e
      rw [if_pos rfl]
      constructor
      · rintro (⟨hv, _⟩ | ⟨hm, hn⟩)
        · cases hv
        · exact absurd ⟨((h v' i').mp hm).symm, rfl⟩ hn
      · intro hv; cases hv
    · rw [if_neg e]
      constructor
      · rintro (⟨_, hi⟩ | ⟨hm, _⟩)
        · exact absurd hi e
        · exact (h v' i').mp hm
      · intro hm; exact Or.inr ⟨(h v' i').mpr hm, fun hc => e hc.2⟩
  | find lo hi lim => exact h

/-- On a consistent state, `find` answers exactly the documents whose field
lies in `[lo, hi]`, in field order, up to `lim` of them. -/
theorem docs_find (s : KV × Idx) (lo hi lim : Nat) (h : Consistent s) :
    (docs.spec s (.find lo hi lim)).2 = (s.2.1.filter (inRange lo hi)).take lim ∧
    ∀ v id, (v, id) ∈ s.2.1.filter (inRange lo hi) ↔
      s.1 id = some v ∧ lo ≤ v ∧ v ≤ hi := by
  refine ⟨rfl, fun v id => ?_⟩
  rw [List.mem_filter, h v id]
  simp [inRange]

/-- No row occurs twice. -/
def NoDup : List Row → Prop
  | [] => True
  | a :: t => a ∉ t ∧ NoDup t

theorem nodup_filter (p : Row → Bool) : ∀ (l : List Row), NoDup l → NoDup (l.filter p)
  | [], _ => trivial
  | a :: t, h => by
    cases hp : p a with
    | false => rw [List.filter, hp]; exact nodup_filter p t h.2
    | true =>
      rw [List.filter, hp]
      exact ⟨fun hm => h.1 (List.mem_filter.mp hm).1, nodup_filter p t h.2⟩

theorem nodup_take : ∀ (n : Nat) (l : List Row), NoDup l → NoDup (l.take n)
  | 0, _, _ => trivial
  | _ + 1, [], _ => trivial
  | n + 1, _ :: t, h => ⟨fun hm => h.1 (List.mem_of_mem_take hm), nodup_take n t h.2⟩

theorem sorted_take {ι : Type} {R : ι → ι → Prop} :
    ∀ (n : Nat) (l : List ι), SortedBy R l → SortedBy R (l.take n)
  | 0, _, _ => trivial
  | _ + 1, [], _ => trivial
  | n + 1, _ :: t, h => ⟨fun x hx => h.1 x (List.mem_of_mem_take hx), sorted_take n t h.2⟩

theorem nodup_ins (x : Row) : ∀ (l : List Row), x ∉ l → NoDup l → NoDup (ins x l)
  | [], _, _ => by
    show x ∉ ([] : List Row) ∧ True
    exact ⟨fun h => (nomatch h), trivial⟩
  | y :: ys, hx, h => by
    unfold ins
    split
    · exact ⟨hx, h⟩
    · refine ⟨fun hm => ?_, nodup_ins x ys (fun h' => hx (List.mem_cons_of_mem _ h')) h.2⟩
      cases mem_ins hm with
      | inl e => subst e; exact hx (List.mem_cons_self _ _)
      | inr hm => exact h.1 hm

theorem move_some (old : Option Nat) (n id : Nat) (s : Idx) :
    (Idx.move old (some n) id s).1 = ins (n, id) (Idx.move old none id s).1 := by
  cases old <;> rfl

theorem nodup_move_none (old : Option Nat) (id : Nat) (s : Idx) (h : NoDup s.1) :
    NoDup (Idx.move old none id s).1 := by
  cases old with
  | none => exact h
  | some o => exact nodup_filter _ _ h

/-- The full invariant: the index is consistent with the map and duplicate-free. -/
def Inv (s : KV × Idx) : Prop := Consistent s ∧ NoDup s.2.1

theorem inv_empty : Inv docs0 := ⟨consistent_empty, trivial⟩

theorem docs_inv (s : KV × Idx) (q : DReq) (h : Inv s) : Inv (docs.spec s q).1 := by
  refine ⟨docs_consistent s q h.1, ?_⟩
  cases q with
  | put i v =>
    show NoDup (Idx.move (s.1 i) (some v) i s.2).1
    rw [move_some]
    refine nodup_ins _ _ (fun hm => ?_) (nodup_move_none _ _ _ h.2)
    rw [mem_move] at hm
    rcases hm with ⟨hv, _⟩ | ⟨hm, hn⟩
    · cases hv
    · exact hn ⟨((h.1 v i).mp hm).symm, rfl⟩
  | del i => exact nodup_move_none _ _ _ h.2
  | find lo hi lim => exact h.2

/-- On an invariant state, the matching rows are duplicate-free, and the answer
is key-sorted, duplicate-free and has length `min lim (number of matches)`. -/
theorem docs_find_shape (s : KV × Idx) (lo hi lim : Nat) (h : Inv s) :
    NoDup (s.2.1.filter (inRange lo hi)) ∧
    NoDup (docs.spec s (.find lo hi lim)).2 ∧
    SortedBy KeyLE (docs.spec s (.find lo hi lim)).2 ∧
    (docs.spec s (.find lo hi lim)).2.length = min lim (s.2.1.filter (inRange lo hi)).length :=
  ⟨nodup_filter _ _ h.2,
   nodup_take lim _ (nodup_filter _ _ h.2),
   sorted_take lim _ (filter_sorted _ _ s.2.2),
   List.length_take _ _⟩

/-- States reachable from empty through the gate, under any prices, limits and fees. -/
inductive Reachable : KV × Idx → Prop
  | empty : Reachable docs0
  | step {s : KV × Idx} (w : Usage 3) (L fee : Nat) (q : DReq) :
      Reachable s → Reachable (docs.run w L fee s q).state

/-- Every gated run preserves the invariant: an accepted request moves to the
specified state, and a refused one does not move. -/
theorem reachable_inv {s : KV × Idx} (h : Reachable s) : Inv s := by
  induction h with
  | empty => exact inv_empty
  | step w L fee q _ ih =>
    cases Prim.run_atomic docs w L fee _ q with
    | inl e => rw [e]; exact docs_inv _ q ih
    | inr e => rw [e]; exact ih

A run

Prices are 10 per seek, 1 per step and 20 per write, and the refusal fee is 5. Three documents are stored with field values 30, 10 and 20, then document 1 is changed to 15. Then come three find requests, the second under a limit of 15. Every other request runs under a limit of 100.

-- continues the definitions above
/-- Prices: a seek 10, a step 1, a write 20. -/
def prices : Usage 3 := u3 10 1 20

def step (L : Nat) (s : KV × Idx) (q : DReq) : Outcome (KV × Idx) (List Row) :=
  docs.run prices L 5 s q

/-- A gated `find` under these prices: accepted with charge at most `10 + lim`
when `10 + lim ≤ L`, refused without effect otherwise. -/
theorem gated_find (s : KV × Idx) (L fee lo hi lim : Nat) :
    (10 + lim ≤ L →
      (docs.run prices L fee s (.find lo hi lim)).state = s ∧
      (docs.run prices L fee s (.find lo hi lim)).answer =
        some ((s.2.1.filter (inRange lo hi)).take lim) ∧
      (docs.run prices L fee s (.find lo hi lim)).charge ≤ 10 + lim) ∧
    (L < 10 + lim →
      (docs.run prices L fee s (.find lo hi lim)).state = s ∧
      (docs.run prices L fee s (.find lo hi lim)).answer = none) := by
  have hb : gas prices (docs.bound s (.find lo hi lim)) = 10 + lim := by
    show 10 * 1 + (1 * lim + (20 * 0 + 0)) = 10 + lim
    omega
  refine ⟨fun hL => ?_, fun hL => ?_⟩
  · have hg : gas prices (docs.bound s (.find lo hi lim)) ≤ L := hb ▸ hL
    have ⟨h1, h2, _⟩ := docs.run_accepted prices L fee s _ hg
    exact ⟨h1, h2, hb ▸ docs.run_charge_le_bound prices L fee s _ hg⟩
  · exact docs.run_refused prices L fee s _ (hb ▸ hL)

def demo : List (Option (List Row) × Nat) :=
  let o1 := step 100 docs0 (.put 1 30)
  let o2 := step 100 o1.state (.put 2 10)
  let o3 := step 100 o2.state (.put 3 20)
  let o4 := step 100 o3.state (.put 1 15)
  let o5 := step 100 o4.state (.find 12 25 10)
  let o6 := step 15 o5.state (.find 12 25 10)
  let o7 := step 100 o6.state (.find 0 99 2)
  [o1, o2, o3, o4, o5, o6, o7].map (fun o => (o.answer, o.charge))

#eval demo
-- [(some [], 60), (some [], 60), (some [], 60), (some [], 90),
--  (some [(15, 1), (20, 3)], 12), (none, 5), (some [(10, 2), (15, 1)], 12)]

Each line can be checked against the bounds.

  • Puts of new documents cost 60. The map’s write is one seek and one write, 10+2010 + 20. The old value is absent, so the index only inserts, which is another 10+2010 + 20. The cap of 90 is the worst case, in which the index must also remove a row.
  • Changing document 1 costs 90. The map answers the old value 30, so the index removes (30,1)(30, 1) and inserts (15,1)(15, 1). This is the case the cap was priced for.
  • find 12 25 10 costs 12. It is one seek and two steps, and it returns the documents with fields 15 and 20, in field order. The cap was 10+10=2010 + 10 = 20, and the client pays for the two steps actually taken.
  • The same request under a limit of 15 is refused. Its capped gas, 20, exceeds the limit. Nothing runs, the state is unchanged, and the charge is the fee of 5.
  • find 0 99 2 costs 12. The row limit of 2 stops the scan after two rows, so the answer is the first two documents in field order.

What the theory does not claim

Cost is logical. The counters are seeks, steps and writes as each primitive defines them, and gas is a weighted sum of those counters. Nothing here measures or bounds time on a machine. The page bound connects one counter to a quantity closer to hardware, under an explicit occupancy hypothesis, and it is still a count, not a duration.

The counters are part of the model. Law 3 relates the reported usage to the bound. Whether the reported usage counts what a particular implementation does is a property of that primitive’s executor. In the index, for a range request the step counter is exactly the number of rows the scan examines. The seek is charged as one operation, which in the list model is a dropWhile over a prefix; the page bound is what justifies charging it as h+1h + 1 pages in a tree. Likewise a move is charged as one seek and one write per side, while in the list model its removal is a filter over the whole index and its insertion a walk to the insertion point; again it is the tree page model, a descent to one leaf, that justifies the constant per side. The key–value map charges a constant per request, which is a modelling choice about an abstract map rather than a theorem about one.

Bounds are worst case per request. A bound dominates every execution of one request in one state. There is no amortisation across requests, so an operation that is occasionally expensive (a node split, say) must be priced at its worst case every time, or modelled as a separate primitive.

Pricing a dependent composite evaluates a specification. The bound of a bind depends on the specified intermediate state. Admission without that evaluation needs a cap, and caps exist only when the second step’s bound can be dominated independently of the first step’s answer, as with the document store’s writes.

The gate decides admission before running and does not interrupt. An accepted request runs to completion; a refused one does not run. A request that does not admit a useful bound before execution, such as an unrestricted scan whose length depends on data, has to be given a request-level limit, as find is by lim\mathit{lim}, before it can be a primitive.

Only these combinators are covered. Iteration with a data-dependent number of rounds, and requests that interleave, are outside the closure theorem. A loop with a fixed number of rounds is likewise outside the closure theorem as stated; a fixed unrolling is a nest of seq (or of bind, when a round’s request depends on earlier answers), to which the cap theorem for seq or for bind applies at each level.

Prior work

Mechanised verification of storage structures is well established. Toward a Verified Relational Database Management System (POPL 2010) verified a relational engine, including B+ tree indexes, in Coq, and Storage Systems are Distributed Systems (So Verify Them That Way!) (OSDI 2020) verified a key–value store built on a Bε-tree. Using Crash Hoare Logic for Certifying the FSCQ File System (SOSP 2015) is a standard example of verifying a storage system against a functional specification including crash behaviour. The B-tree occupancy invariant used for the page bound goes back to Organization and Maintenance of Large Ordered Indices (Acta Informatica, 1972).

On the query side, HoTTSQL: Proving Query Rewrites with Univalent SQL Semantics (PLDI 2017) proves rewrite rules correct against a formal semantics, and Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler (SIGMOD 2017) verifies a query compiler. Those two works establish that a plan computes the query. Cost-based plan choice dates from Access Path Selection in a Relational Database Management System (SIGMOD 1979), whose cost estimates guide the choice of plan but are heuristic, not proved bounds. The theory here pairs the first kind of result with the second kind of quantity: a proved bound on what an execution consumes.

Bounding resource use by typing and program logics is the subject of Static Prediction of Heap Space Usage for First-Order Functional Programs (POPL 2003), Multivariate Amortized Resource Analysis (POPL 2011) and Amortised Resource Analysis with Separation Logic (ESOP 2010). Lightweight Semiformal Time Complexity Analysis for Purely Functional Data Structures (POPL 2008) carries cost in a type-theoretic annotation monad, which is close in spirit to an executor that returns its usage. Charging a prescribed price per abstract operation, checked against a limit before or during execution, is the gas model of smart-contract virtual machines, given a complete executable formal semantics of such a machine in the K framework (IEEE Computer Security Foundations Symposium, 2018). The gate above differs in admitting the request before it runs, on a proved upper bound on its usage, so an accepted request is never interrupted for running out of gas; like the gas model, it then charges the usage actually reported.