Patch replay: concatenation equals sequential application, including failures
Proof verified
complete
What this target establishes
Scope metadata is the contributor’s assessment; independent reviews and the exact proposition provide the evidence.
- Obligations
- composition
- Cost metric
- none
- Model
- Generic sequential partial patch interpreter over arbitrary state and operation types.
- Assumptions
- Operations return Option State; failure propagates.
- Implementation correspondence
- abstract model
- Limitations
- No concurrency, diff minimality or native implementation refinement.
Known patch replay law, restated in a small portable Lean model. Applying xs followed by ys must equal applying their concatenation. The interpreter step is partial: it returns Option State, and a failed application propagates through every subsequent step. No successful replay or equality is assumed. The theorem is generic over state and operation types and concerns sequential replay, not patch compaction or concurrency.
External antecedent: Gomes et al.'s Isabelle CRDT Convergence theory defines apply_operations by composing partial state transformers. This is a fresh Lean proof of a standard fold law, not a translation of their entire algorithms and not a novel result. It establishes no runtime, wire-format or native implementation guarantee. Prepared with Codex; the platform checker determines verification status.
Formal statement
∀ (State Op : Type) (step : Op → State → Option State) (xs ys : List Op) (s : State), (xs ++ ys).foldl (fun prior op => prior.bind (step op)) (some s) = ys.foldl (fun prior op => prior.bind (step op)) (xs.foldl (fun prior op => prior.bind (step op)) (some s))
Lean core · approved, fixed dependencies · download challenge
Exact version and statement fingerprint
Lean 62b6a2291302d4bbeace37642a066b7510d0145c
Statement SHA-256 405706bdf2b7cbf8188e349dff34155b0f8a90a54f1b0d67c9f99700b9ef94c2
Policy oa-lean-v1
Platform statement-check output
OA_statement : Prop
Review the meaning
A checked proof establishes this exact proposition. Statement reviews assess whether it expresses the description above.