The craziest “undo” algorithm you’ve never heard of

The arrow of time may famously only point only one way, but the progress in computer science takes a weaving non-linear path through the thing we understand as time.

The current understanding of how "undo" works within computer programs is pretty fixed; all programs use "undo" and "redo" in the same way? But could "undo" and "redo" be more advanced?

To look for a more advanced version than we use today we have to look to an algorithm I first became aware of in 1989.

I presume the evolution of the "undo" function went something like this:

1. Users type things into a screen or generally do things. If they make a mistake: tough, "deal with it". Editors in the 1980s worked that way, as do most web applications today.

2. To help users overcome their mistakes, programs introduced the feature that you could "undo" the single last action you'd just taken. I certainly used "paint" programs on an 8-bit BBC micro in 1986 that had single-level undo, the most progressive web applications of our age such as gmail in 2016 offer this too.

3. But what if the undo itself was a mistake? The feature of a single "redo" function was introduced, to undo what you'd just undone.

4. What if you did two things and they were both mistakes? Infinite undo and redo was introduced, where you could undo as many steps as you want, and redo them all as well. This is where we are were with all modern desktop editors in the 90s and nearly no web applications in 2016 apart from Google Docs.

The last step in the evolution seems like it's perfect, like there's no way of accidentally losing data any more. But that's not entirely true. The authors of !Edit for RISC OS thought and over-thought things through to their logical conclusion, such as the English have a reputation for doing.

The problem is that if you do 10 actions, and undo 5 of them, all it takes is to press a single key, and now the editor thinks you've done 6 actions; the original 5 plus your new key-press. If you pressed the key as an accident (e.g. you were mashing up the keyboard hoping to hit the redo key, but missed) you have now no way of redoing the latter of your original 5 actions. They're gone forever.

In an idea which, like many an idea, seem great on the whiteboard where you can imagine all states in a nice diagram, but are catastrophes in real life where you can't, they had the idea that a collection of undo or redo operations was itself a single operation. If you'd done 10 things, undone 5, and pressed a key, you'd actually done 12 operations: the original 10, then the undo (of the 5) and then the key press. After the key-press, you could undo the key-press, and undo all the undos (one operation), then individually undo as many of the 10 as you liked, to get back to any previous state.

The madness was compounding though: if, after doing all that, you then pressed a key, you now had done 14 operations: the 12 from before, then the new undo (which included undoing the previous undo) plus your new key-press.

This was simultaneously a computer scientists fantasy and a user's absolute nightmare. To be both a computer scientist and a user, it was like being the caricature "split personality patient", able to experience both complete ecstasy at the complexity, and pure fear of the complexity, simultaneously.