Readable pending work: queue proofs and the gap-list construction

10 October 2026. Primary-proof review and editorial assessment 185. This pass compares two established queue constructions with the Lab’s current native interface. It adds no recognition theorem and preserves the two-maxima target.

Contents

What the comparison resolves

A queue can make an unfinished representation readable without executing every queued task. That distinction is central here: the gap-list producer needs bounded FIFO operations on opaque payloads, while the reuse worker separately pays for comparisons. Neither cost can silently absorb the other. The maintained proof now separates those roles and links the complete checker dependency chain.

Two primary arguments

Hood and Melville: explicit copying

Robert Hood and Robert Melville, Real Time Queue Operations in Pure LISP, Cornell TR80-433, July 1980. Primary report. The retained eight-page report was re-read, including the recopy argument and appendix image. SHA-256: f2e94253671f72484ce3798ab631fadefb3bb784ed030079097132303ffb15a9.

The interface supplies a queue and a ready element; it supports insertion, deletion and front observation. Two-list reversal gives aggregate linear cost but an unbounded single-operation pause. Recopying instead starts when the rear has $n+1$ elements and the front has $n$ . Two passes need $2n+1$ incremental steps. Two steps at the triggering update and each subsequent update finish before the old front can disappear. New insertions use a separate rear; the readable front and copy bookkeeping track deletions. The resulting head/rear balance permits another cycle. The fixed-record appendix uses only unit arithmetic and zero/one tests, explicitly realizable with unary lists. This is strict construction from a fixed empty queue, not a memoizing evaluator. The argument charges each operation, so choosing an old valid version does not require amortized credit from a different branch. It does not supply arbitrary queue concatenation or discover an element from an ordinary name.

Okasaki: dependency pre-evaluation

Chris Okasaki, Simple and efficient purely functional queues and deques, JFP 5(4), 583–592, October 1995, DOI and primary PDF. Sections 2–7 and Figures 1–5 were read.

Lazy rotation combines append with reversal, but laziness alone leaves nested tail dependencies and logarithmic worst-case removal. The constant-time queue adds a schedule pointer $S$ into the front $L$ , with $|S|=|L|-|R|$ . Each update advances pre-evaluation; before another rotation, the dependency tails have already been evaluated and memoized. For deques, balanced sides and two schedules handle rotations in either direction. Removing from one side can accelerate the next rotation, so deletion advances both schedules twice; insertion advances them once. With $j$ the shorter side and $k$ the longer, the schedule-length bound is $\max(2j+2-k,0)$ . Bounded chunks make the rotation’s local steps constant. The theorem assumes memoized streams and specified evaluation strictness; it is not automatically an immutable old-top machine implementation.

Contract comparison and transfer audit

Obligation	Explicit-copy queue	Scheduled lazy queue	Current Lab construction
Ready input	Queue root and payload	Queue root and payload	Roots prepared during ordinary names and target bits
Pending representation	Explicit recopy state	Suspended stream dependencies	Gap capsules and separate comparison receipts
Readability	Old front remains available	Required tails pre-evaluated	One-level capsule view; candidate-specific query reader
Timing resource	Operations before front exhaustion	Schedule progress before next rotation	Actual input bits and the query length at which a candidate matters
Persistence mechanism	Immutable state returned by each operation	Shared memoized evaluation	Immutable roots, old-version forks and bounded local allocation
Missing import	Payload execution and arbitrary concatenation	Native realization of memoized forcing	Different-maxima candidate birth and inherited comparison debt

Written audit, not a new theorem. Section 15 uses a strict FIFO to capture an already encountered prefix. Closing that prefix around an explicit successor is not concatenation of two arbitrary queues. Each view removes one frame and retains the remaining queue; it never recursively follows a capsule tip into another capsule. The successor’s right gap is a ready unary root. Only the left gap is newly copied, paid one cell per actual target bit. These are the exact places where replacing an explicit queue by an unproved lazy-list implementation would change the resource argument.

The local schedule must retain its state when a row is suspended and later restored by its ordinary name. A branch from an old version copies only bounded root/control fields. It receives its own subsequent operation budget. No old storage is mutated and no branch may claim work performed only in another branch. The existing native simultaneous-record compiler remains a separate prerequisite: fixed degree, radius, labels and control, fixed initialization, charged routing and allocation, and no EOF work. The primary queue theorems do not by themselves prove that compiler.

For reuse, enqueueing a descriptor is bounded; deciding whether its row contains candidate width $m$ is a separate incremental job. The bound in section 12 uses distinct ordinary names to fund these jobs, and the $m$ -symbol query to finish relevant residual work. Constant-time queue maintenance cannot establish that comparison bound. This separates two tempting but invalid transfers: counting stored descriptors as completed comparisons, and treating an abstract persistent queue as an implementation of arbitrary named-row joins.

Consequence for the next research test

With common maximum, every missing candidate comes from the first selected nonempty row. With different maxima, a larger row can create a relevant candidate above the earlier envelope. A proposed implementation must account for that candidate’s creation and any copied queue from the instant it becomes available. Earlier input cannot be credited again merely because a new worker holds the old queue root. A fixed bound on maxima limits promotions, but does not alone settle the residual-work inequality or align a newly created query reader.

This is an operation-level checklist for the existing target, not a claimed obstruction to every representation. The successful controls remain the gap-list splice, fixed-candidate bounded-exception receipt, pending ball reader, and prior replay/affine/causal constructions at their stated contracts. Independent-store joins still require their own routing and resource-preserving reduction.

Contribution assessment. Incremental recopying, readable pending queues and scheduled pre-evaluation are established mechanisms. The Lab’s written result is an adaptation to an ordinary-input, immutable local recognition contract, combining gap exports with candidate-specific comparison budgets. This comparison supports that classification with high confidence. It does not establish literature priority for the combined recognition theorem; the concrete remaining comparison is with real-time persistent ordered-set and catenable-sequence representations under the same access contract. No failed search is used as novelty evidence.

Reviewed scope: the current proof, assessments 180–184, their linked code pages, the program overview and source index. Concrete fixes: the proof’s stale assessment range now includes 184; its opening has a compact argument/evidence guide; imported Python helpers have explicit readable links; assessments 183–184’s raw asymptotic, inequality and set notation now renders through KaTeX. Source-code bytes and stable mathematical anchors are unchanged. No homepage research date, paper ranking or claim admission changes.

The evidence chain is gap exports, bounded-exception receipts, single-hole numeral helpers, and pending ball comparisons. Each code reading includes highlighted source, line anchors and an exact raw download. These finite audits remain corroboration; this editorial pass does not recount their experiments or claim a native compiler replay.

Generated HTML, equation rendering, links, anchors and byte-preserving source readers are checked before publication. Browser viewport inspection remains unavailable under the current managed Sites workflow; it is not inferred from a successful build. Primary PDFs and extracted text remain outside public source. Exact build, deployment and source-parity receipts belong to integration state.

Durable continuation

Scheduled completion 90 combines the literature and editorial duties and counts once. Mathematical completion 120, window 4 and last reassessment 116 remain unchanged. Next scheduled 91 is research; literature review 95 and editorial 96 follow. This is distinct from the six-result mathematical reassessment.

NEXT: Test two arbitrary final maxima with at most two arbitrary missing levels per row. Combine the existing pending maximum reader with the ready gap-list exports, charging new candidate creation, copied comparison-queue debt and query-reader alignment. If successful, carry the same proof through fixed bounds on maxima and holes. Keep growing exception budgets, general radial profiles and independent-store joins separate.