Undo-Stack Protocol¶
Protocol — instantiates Constraint-Guided Backtracking
A state-preserving protocol that records each step as a reversible entry and restores the exact prior coherent state when a step must be undone.
The Undo-Stack Protocol is the state-fidelity substrate beneath a reversible search: a discipline in which every forward step is recorded as a paired do/undo entry pushed onto a stack, so that popping an entry restores the exact, coherent state that preceded it — no residue, no half-applied change. Where the search decides which branch to abandon and when, this protocol makes a different and narrower guarantee: that abandoning a branch lands you on a clean, fully reconstructed prior state rather than a subtly corrupted one. Its single idea is reversibility by construction — each step carries the recipe to invert itself, so any earlier point can be reproduced precisely on demand. It says nothing about which move to make; it makes retreat safe.
Example¶
A vector-illustration editor implements Ctrl-Z through this protocol. Every user action pushes an inverse: "moved shape 12 by (40, 0)" pushes "move by (−40, 0)"; "changed fill to blue" pushes "restore fill to grey"; "deleted layer 3" pushes "reinsert layer 3 with its contents." Pressing undo pops the top entry and applies its inverse, snapping the canvas back one step.
The protocol's real subtlety is the context boundary. Undoing "delete layer 3" must also restore that layer's linked references, its z-order position, and any objects that pointed at it — otherwise the canvas looks restored but is quietly broken. So the reversible unit is drawn to enclose everything that must move together. The depth limit is the other subtlety: the stack keeps the last, say, 100 entries; older ones fall off, so you can undo recent work but not unwind to the blank document. Trace it: the user deletes a group, recolors a path, nudges a shape — three entries. Two presses of Ctrl-Z reverse the nudge and the recolor exactly; the group stays deleted until a third press. Throughout, the protocol promises exactness of restoration, never a judgment about whether deleting the group was wise.
How it works¶
- Record a reversible entry per step. On each change, capture either a full snapshot or (more cheaply) the inverse operation, and push it onto the stack.
- Draw the context boundary. Define the unit that must be saved and restored together, so an undo never leaves dangling links or partial state.
- Restore on demand. To undo, pop the top entry and apply its inverse, reproducing the prior coherent state bit-for-bit.
- Bound the stack. Cap its depth; drop the oldest entries past the limit so memory stays fixed and very deep unwinds are refused rather than attempted half-way.
Tuning parameters¶
- Reversible-unit granularity — one entry per keystroke or one per user-visible command. Finer units allow precise undo but bloat the stack.
- Context-boundary width — how much surrounding state is enclosed in a reversible unit. Too narrow leaves corruption; too wide makes every step expensive.
- Snapshot vs. delta — store a full state copy (simple, memory-heavy) or an inverse operation (compact, but must be exactly correct).
- Depth limit — how many steps back the stack can restore. Deeper costs memory; shallower risks refusing a needed unwind.
- Persistence — whether the stack survives a crash or session end, which decides if reversibility outlives the process.
When it helps, and when it misleads¶
Its strength is that it makes exploration cheap and safe: because every step is reversible by construction, the search can commit boldly and retreat without fear of leaving the workspace in a broken intermediate state. It is the difference between "we can try this and take it back" and "we dare not touch it."
Its defining failure mode is reversibility in appearance only — an "undo" that restores the tracked state but cannot recall a side effect that escaped the context boundary: an email already sent, a file written to disk, a payment posted to an external system. The stack faithfully reverts the canvas while the world outside stays changed. This is why irreversible external effects need a compensating action rather than a pop.[n1] The guarding discipline is to keep genuinely irreversible effects outside the reversible envelope entirely — stage them, gate them behind an explicit commit — so the protocol only ever promises to undo what it truly can.
How it implements the components¶
The Undo-Stack Protocol fills the state-fidelity side of the archetype — the parts that guarantee a retreat lands somewhere coherent:
partial_solution_state— it holds the current prefix as a restorable object and can reproduce any recent earlier version of it exactly.preserved_context_boundary— the reversible unit defines precisely what is inside the envelope (restored together on undo) versus what stays put, so no step leaves dangling or half-applied state.rollback_depth_limit— the stack's depth cap bounds how far back restoration can reach, trading memory for reach and refusing unwinds that exceed it.
It does not choose the next move, keep the ledger of choices, or decide when a branch has failed and how far to step back — extension_operator, decision_stack, and rollback_rule drive Recursive Depth-First Backtracking, the nearest twin. That method picks the move and the moment to retreat; this protocol only guarantees the retreat is exact.
Related¶
- Instantiates: Constraint-Guided Backtracking — the protocol is the reversible-state substrate the archetype's rollback rhythm assumes.
- Sibling mechanisms: Recursive Depth-First Backtracking · Forward-Checking Table · Chronological Backtracking Log · Decision-Tree Search Diagram · Hypothesis-Tree Review · Constraint-Satisfaction Solver Pass
Editorial Notes¶
Form Classification¶
Form family: Protocol, Workflow & Routine
Rationale: Undo Stack Protocol is defined in the frozen evidence as: A state-preserving protocol that records each step as a reversible entry and restores the exact prior coherent state when a step must be undone. Its operative deployed or enacted form is therefore Protocol, Workflow & Routine.
Nearest alternative: Control, Automation & Runtime — Control, Automation & Runtime can support this mechanism, but the evidence centers the concrete operation described above rather than the alternative family's defining operation.
Review outcome: Adjudicated after independent review; medium confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Single lineage
Present-day reach: Universal
Rationale: Vitek and Jagannathan, A Formalization of Undo and Redo documents that the primary computer-science treatment formalizes undo and redo as state-transforming operations with histories. This is direct, mechanism-specific evidence for computer science as the best-evidenced historical home of the operation—A state-preserving protocol that records each step as a reversible entry and restores the exact prior coherent state when a step must be undone.—rather than evidence merely that the operation is useful there. The retained alternates record genuine adjacent lineages; later portability is represented separately by domain_reach=universal.
Related originating lineages:
- Engineering & Design — Engineering design, reliability, and systems-safety practice supplies a parallel or contributing lineage for the mechanism's defining operation: a state-preserving protocol that records each step as a reversible entry and restores the exact prior coherent state when a step must be undone.
- Organizational & Management Science — Organizational Management supplies a historically relevant adjacent lineage or formative practice for the operation—A state-preserving protocol that records each step as a reversible entry and restores the exact prior coherent state when a step must be undone.—but the adjudicated evidence more directly locates the defining lineage in computer science.
- Systems Thinking & Cybernetics — Systems science's feedback, boundaries, control, and regulation tradition contributes a separate formative lineage to the mechanism's undo stack protocol logic.
Review resolution: The blind reviewers disagree on primary lineage (organizational_management versus computer_science). The defining operation is: A state-preserving protocol that records each step as a reversible entry and restores the exact prior coherent state when a step must be undone. The researched Vitek and Jagannathan, A Formalization of Undo and Redo establishes that the primary computer-science treatment formalizes undo and redo as state-transforming operations with histories. That source therefore supports computer science as the historical origin. organizational management remains in the uncapped alternates where it contributes a formative practice, but application or governance is not itself proof of origin. origin_mode=single_lineage records lineage construction; domain_reach=universal separately records later applicability.
Encyclopedia synthesis: The exact catalogued form synthesizes established practice rather than reproducing a single standard historical label.
Review outcome: Researched adjudication after independent review; high confidence.
Sources consulted:
Notes¶
The protocol is the mirror image of the decision stack rather than the same object: the decision stack records which commitments were made, while the undo stack records how to reverse each one's effect on state. A robust search keeps both — the first to know what to retreat from, the second to guarantee the retreat is clean.
[n1] The saga pattern handles a step whose effect cannot literally be popped by running a compensating action — a second operation that offsets the first (issue a refund rather than un-charge a card). It is the standard answer when a "reversible" step reaches outside the context boundary into an irreversible external effect. ↩