AFTD Auto-Formalizing Theoretical Domains

fifo_rank

def

The 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 page, or 0 if absent.

Statement

def fifo_rank {α : Type*} [DecidableEq α] {k : ℕ} (q : FifoQueue α k) (x : α) : ℕ
Defined in
arXiv:2610.18767 Section 3.2
Verified
20 Oct 2026
Axioms
none listed
Built on 1
  • FifoQueueA first-in first-out (FIFO) cache queue of capacity k over page type α, represented as a duplicate-free list of length k.
Used by 5
  • 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

For a type α with decidable equality, a natural number k, a FIFO queue q : FifoQueue α k, and an element x : α, fifo_rank q x is defined as the natural number equal to q.pages.idxOf x + 1 (one plus the 0-based index of x in q.pages) if x ∈ q.pages, and 0 otherwise.

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

/-- Rank of a page in the FIFO queue from 1 (oldest) to k (newest). -/
def fifo_rank {α : Type*} [DecidableEq α] {k : ℕ} (q : FifoQueue α k) (x : α) : ℕ := if x ∈ q.pages then q.pages.idxOf x + 1 else 0
See it in the graphDiscuss this resultChallenge it