Index  Comments

I've lately been mulling over the design of an ``undo and redo'' system, a recollection system. The underlying system should provide this, but I'm not aware of any which do. It seems clear to me that the programs and languages used to write them are fundamentally based around relatively unstructured state manipulation in a way making them unsuitable for this, requiring new methods for writing them.

In any case, I've given a decent amount of thought to how a library could be designed for the common languages to make writing such a recollection system easier, as this thinking also helps the greater system in general, although I'm entirely unsatisfied with mine end result, and no longer believe the original idea of a transparent library for such is reasonable; the end result is but an empty shell.

Those fundamental ideas of a recollection system are being able to make persistent changes, and also to return to previous states when desired; the simplest and least efficient means for this is saving the entirety of all state transitions in an ordered set, to be explored as wanted. A more efficient method is saving only the deltas, but this approach fails to encompass higher changes which affect a structure in a simple but far way. As an example, it is better to save the lone element of an array changed, rather than that entire array, yet inserting an element and so shifting all others requires a yet higher system to concisely encode the change. Mine end result was a system for encoding such.

Unfortunately, there's little draw in but a shell of an interface that must be filled in before use. I named my two primitives CHANGE and RECALL. Different systems enable slightly different interfaces for each, primarily in how the history is maintained; it would be best for it to be implicit, though many languages inhibit extending their base types so, which is where most of the work such a library could have already finished lies. This basic design also doesn't support multiple histories needing coordination well, and requiring this to be done manually. If one were to encode changes, and build machinery for changing and recalling based on them, ideally there should be support for ensuring the machinery is correct; the natural result is one encodes the changes to allow for the machinery to be made to derive CHANGE and RECALL from that same information, but this simply becomes a new language.

To make an example, consider changing an element of an ordered sequence, with inserting and deleting several elements. The CHANGE interface for that former would simply accept the sequence, index, and new element; its addition to that history would store the index and previous element; and its RECALL interface would simply restore that previous element in the correct location. Assuming that uniform data is used for insertion and deletion, all necessary for the history is the index of the beginning of the change and the data knocked off the ends or deleted; all other information be easily derived.

In sum, I currently see no satisfying way to create a general library for any of the languages I use which would enable them to automatically derive a recollection system, meaning every program I write must include a custom such system, even if there be a minor underlying structure behind every piece.

A proper way to create such a system gives no program the right to opt-out of it. Be deterministic, a program can have an input stream maintained, and greater efficiency could be achieved by storing a checkpoint consisting of a full copy every so often. Another proper method for such requires that a program register all observable state changes with a greater system, which handles it transparently.