FifoQueue
structure
A first-in first-out (FIFO) cache queue of capacity k over page type α, represented as a duplicate-free list of length k.
Statement
structure FifoQueue (α : Type*) (k : ℕ)
- Defined in
- arXiv:2610.18767 Section 3.1
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Used by 7
- fifo_rankThe rank of a page in a FIFO queue of size k, ranging from 1 for the oldest page (next to be evicted) to k for the most recently fetched…
- fifo_fetchUpdating a FIFO queue of size k ≥ 1 upon fetching a new page v: the oldest page (front of the queue) is evicted and v is appended to the…
- rank_potential_offline_fetch_boundAt an offline fetch, the increase in rank potential is at most k (Lemma 3.3(i)).
- rank_potentialThe rank potential function Φ for FIFO paging, defined as the sum of ranks of all pages currently in the online FIFO cache but absent from…
- rank_potential_zero_of_subsetIf all pages in the online FIFO cache are present in the offline cache, the rank potential Φ is zero; in particular, the initial potential…
- rank_potential_online_payment_boundFor any type α with decidable equality, any k ≥ 1, any FIFO queue q of capacity k, any offline cache cOpt of cardinality k, and any page v…
- rank_potential_offline_evict_hole_boundAt an offline fetch, if the evicted page is outside the online cache, the change in rank potential is at most 0 (Lemma 3.3(ii)).
Read back from the Lean
A structure FifoQueue, parameterized by a type α and a natural number k, consisting of:
1. pages: a list of elements of type α,
2. length_eq: a proof that the length of pages is equal to k,
3. nodup: a proof that pages contains no duplicate elements (List.Nodup pages).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A FIFO cache queue of capacity k storing k distinct pages. -/ structure FifoQueue (α : Type*) (k : ℕ) where pages : List α length_eq : pages.length = k nodup : pages.Nodup