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 ”. 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 resources is . Vectors add pointwise and are ordered componentwise: iff for every . A price vector assigns a price to each resource, and the gas of under is the inner product
Gas is a monotone linear functional. For all :
- ,
- ,
- ,
- .
Proof. Each is an induction on , using distributivity and monotonicity of multiplication on . ∎
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 resources, a state type , a request type and an answer type , a metered verified primitive consists of
satisfying, for every state and request :
- state refinement: and have the same next state,
- answer refinement: they have the same answer,
- usage bound: the usage reported by is .
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 and a limit . It prices the bound first. If it runs the executor and charges the gas of the usage actually reported. Otherwise it refuses: the state stays , there is no answer, and the charge is a fixed refusal fee capped at the limit, . 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 , prices , limit , fee, state and request , let be the gate’s outcome.
- Faithful acceptance. If the priced bound fits, has state and answer exactly , and its charge is the gas of the reported usage.
- Refusal. If , then has state and no answer.
- Soundness. Whenever has an answer , then and ‘s state are exactly those of .
- Charge limit. The charge is in every case, and when the request is accepted.
- Atomicity. The state of is either the specified next state or ; 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 . In the refusing branch the state is , the answer is absent and . 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 . 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 and (and over a state where noted):
- comap reindexes requests by ;
- map post-processes answers by ;
- bind runs on , then runs on the new state with request , where is ‘s answer, and returns both answers;
- alt accepts a request of either kind, , on one state;
- onFst and onSnd run on one component of a product state, leaving the other untouched.
Derived: seq with , on pairs of independent requests; sum over ; prod .
Composition closure. Each combinator applied to metered verified primitives is again a metered verified primitive. Its bound is, respectively, ; ; and for bind
the bound of whichever side an request selects, and the bound on the touched component for onFst and onSnd. Consequently .
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 ‘s refinement laws apply; the usage law is by componentwise addition of the two usage laws, with ‘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. is capped by when for every state .
Caps compose. If is capped by , then is capped by , and , and are capped by ; any cap may be weakened to a pointwise larger one. If is capped by and by , then is capped by , by the case split of and , and by for any with for all . If is capped by and , the gate accepts in every state and returns the specified answer.
Proof. Componentwise addition and transitivity of , 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 sorted by key and answers range requests: the rows with , at most 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 , then step forward until a key exceeds or rows have been taken. That executor costs one seek and at most 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 rows, which does not depend on convexity at all.
Sorted and convex. For a relation on , a list is sorted by when every element is -related to every later element. A predicate is convex for when , , and imply .
Convex predicates select one run. If is convex for and is sorted by , then
and there are lists with . Transitivity of is not needed.
Proof. Induction on . While the head fails , both sides drop it. Once the head satisfies , every later element satisfies , since the list is sorted by . If such a fails but a later satisfies it, then holds by sortedness, and convexity forces , a contradiction. So after the first failure nothing more is selected, and the filter equals the take-while. ∎
For a general convex , the run is reached by , 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: . An interval on keys is convex for the key order, and on a key-sorted list the monotone seek reaches the same run as , 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 . 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
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 , suppose a scan starts at offset in a first leaf holding entries and reads entries in all, counted from that offset (the first of them in the first leaf), and every leaf after the first holds at least entries. Then the scan reads at most
pages: the interior pages and the first leaf on the seek path, then the later leaves. The bound is monotone in : if , the scan reads at most pages.
Proof. Let be the number of later leaves visited while the entries left after the first leaf remain to be read (truncated at zero). Every visited leaf except possibly the last consumes at least entries, and the last is entered with at least one entry still to read, so , that is , by induction on the leaf list. Since , , and the same argument with 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 is at most the step count and hence at most , then a range request whose abstract usage is touches at most 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 . 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.
- onFst kvstore the field
answers old value - reindexold ↦ index move
upd old (some v) id - onSnd indexmove the row
erase, then insert - bound(1,0,1) + (2,0,2)
≤ (3, 0, 3)
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 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 consistent when, for every value and id, is a row of iff . Call it invariant when it is also duplicate-free: no row of occurs twice. The empty state is invariant, and every request maps an invariant state to an invariant state. On an invariant state, answers the first rows of the list of selected rows, where is duplicate-free and its members are exactly the pairs with and ; the answer is sorted by key, duplicate-free, and has length . Every state reachable from empty by gated requests, under any prices, limits and fees, is invariant.
Proof. A move from to leaves exactly the rows that equal or were present and differ from . For a put or delete of , the old value comes from the map, so by consistency the removed row is the only row for ; rows for other ids are untouched. Removal is a filter and preserves freedom from duplicates; the inserted row 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 reachable from empty. If , the gate accepts , leaves unchanged, charges at most , and returns the first of the matching documents, in field order and without repetition, whatever the store holds. If , 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, . The old value is absent, so the index only inserts, which is another . 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 and inserts . This is the case the cap was priced for.
find 12 25 10costs 12. It is one seek and two steps, and it returns the documents with fields 15 and 20, in field order. The cap was , 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 2costs 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 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 , 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.