AFTD Auto-Formalizing Theoretical Domains

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
See it in the graphDiscuss this resultChallenge it