Patch replay: reversing per-operation inverses restores every successful execution
Proof verified
complete
What this target establishes
Scope metadata is the contributor’s assessment; independent reviews and the exact proposition provide the evidence.
- Obligations
- undo
- Cost metric
- none
- Model
- Undo of a successfully executed sequence by reversing the operation identifiers.
- Assumptions
- Every successful individual step has an undo restoring its original state. The whole forward execution succeeds; undo has sufficient stored information.
- Implementation correspondence
- abstract model
- Limitations
- Does not construct inverse data for destructive operations; no concurrent merge guarantee.
Known inverse law for partial patch interpreters. Assume each operation can be undone on every state where it succeeds. If replay of a sequence succeeds, replaying its operation identifiers in reverse order with the undo interpreter succeeds and restores the initial state. Per-operation inversion is an explicit obligation; whole-sequence restoration is the conclusion.
This requires an undo interpreter with sufficient information to restore deleted or replaced data. It does not imply arbitrary destructive patches are invertible without stored preimages. Miraldo and Swierstra's Agda structural-patch development supplies related inverse lemmas. This is an independent small Lean proof of a standard law, not a full Agda or Darcs refinement, concurrency theorem or performance claim. The cited repository's separate Algebra.lagda associativity proof contains holes at this commit; it is not claimed as a completed proof. Prepared with Codex; platform checking assigns proof status.
Formal statement
∀ (State Op : Type) (step undo : Op → State → Option State), (∀ op s t, step op s = some t → undo op t = some s) → ∀ (ops : List Op) (s t : State), ops.foldl (fun prior op => prior.bind (step op)) (some s) = some t → ops.reverse.foldl (fun prior op => prior.bind (undo op)) (some t) = some s
Lean core · approved, fixed dependencies · download challenge
Exact version and statement fingerprint
Lean 62b6a2291302d4bbeace37642a066b7510d0145c
Statement SHA-256 7eb0403369b434619d07390f94496fc80e3574bd928139f27d64d4949609b082
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.