AFTD Auto-Formalizing Theoretical Domains

fifo_fetch

def

Updating 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 back.

Statement

def fifo_fetch {α : Type*} [DecidableEq α] {k : ℕ} (hk : 1 ≤ k) (q : FifoQueue α k) (v : α) (hv : v ∉ q.pages) : FifoQueue α k
Defined in
arXiv:2610.18767 Section 3.1
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 1
  • 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…

Read back from the Lean

Given a type α with decidable equality, an implicit natural number k, a proof that 1 ≤ k, a FIFO queue q : FifoQueue α k, an element v : α, and a proof that v ∉ q.pages, fifo_fetch defines a new FifoQueue α k whose pages list is obtained by removing the first element (head) of q.pages and appending v to the end (tail ++ [v]).

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

/-- FIFO queue update upon fetching a page: evict head, append to tail. -/
def fifo_fetch {α : Type*} [DecidableEq α] {k : ℕ} (hk : 1 ≤ k) (q : FifoQueue α k) (v : α) (hv : v ∉ q.pages) : FifoQueue α k :=
  have hlen : q.pages.length = k := q.length_eq
  have h_ne : q.pages ≠ [] := by intro h; rw [h] at hlen; simp at hlen; omega
  match h_cons : q.pages with
  | [] => False.elim (h_ne h_cons)
  | head :: tail =>
    { pages := tail ++ [v]
      length_eq := by
        have h1 : (head :: tail).length = k := by rw [← h_cons, hlen]
        simp only [List.length_cons] at h1
        simp only [List.length_append, List.length_singleton]
        omega
      nodup := by
        have hnd : (head :: tail).Nodup := by rw [← h_cons]; exact q.nodup
        rw [List.nodup_cons] at hnd
        rw [List.nodup_append]
        refine ⟨hnd.2, List.nodup_singleton v, ?_⟩
        intro x hx y hy
        simp only [List.mem_singleton] at hy
        subst hy
        intro heq; subst heq
        have : x ∈ q.pages := by rw [h_cons]; exact List.mem_cons_of_mem head hx
        exact hv this }
See it in the graphDiscuss this resultChallenge it