Undo, Redo, Transactions, ORM, Monads, Python

Background

I am working on a program that (in my dreams at least) will have a
graphical interface with Undo/Redo.  This (undo/redo support) seems to me
like the kind of thing that should be "almost free" providing you go about
things in the right way.  In other words, a program with it should be
pretty much equivalent to one without (in functionality, speed and time to
development).  All that should be necessary is the correct concepts and a
structure that reflects them.


Actions

The obvious (to me at least) structure is to introduce "actions" which are
objects that embody certain actions (that change the system state).  So
far, no different from any chunk of code.  The additional twist is that an
action also generates its inverse when invoked.  From that (and also more
generally, from the idea that these are abstractions) an actin has to be
isolated and somehow "run".

In Python the natural way to express "running" an object is via the
__call__() method (which gives you an object that looks like a function).

Some thought also needs to be given to how program state is managed.  What
do actions act on?  This could be completely unstructured, but then undo
actions would need to be very careful to preserve all the necessary
references so that they can do their work when invoked later.  That in
turn implies closures that might entail odd storage requirements (remember
that an undo can itself be undone, so you need to store "everything", and
Python doesn't have continuations - not that we would use them here,
because we are using a database as the model, but that comes later...).

So it seems prudent (I don't have a more convincing argument than the
above) to have an additional abstraction which is the interface to state
in the system.  I call this "context" because it provides the context for
invocation of the action (unfortunately I also call the thing associated
with "with statements" context, which leads to confusion in my code - I
need a better name for the with statement context).

It follows that actions look something like __call(context)__.  In that
case, they would return an undo.  In fact, it's more convenient to have
them return a value that will be useful in a more general sense (ie as
part of the usual business of programming stuff - see monads below).  So
instead, undo actions can be either appended to the context, or specified
separately.  I went with separate, so the interface is __call(context,
undo)__.

In the above, context provides methods that change the system state and
undo is something that accepts an action.  So a typical action looks like:

class MyAction(object):

  def __init__(self, args):
    self.args = args

  def __call__(self, context, undo):
    context.do_stuff(self.args)
    undo.append(Opposite(args))

So far so good.  Obviously, the application also has a method that these
are submitted to, and which calls the action with the context, manages
undo, etc (in my case, the application code does not manage undo - that is
handled by the separate GUI; in the GUI MVC context the application is the
model).

Thinking about what I just wrote, I guess it might be better to have the
application, then a wrapper that provides undo/redo, and then the GUI
around that.  That would remove the code I currently have that bounces
redo/undo back and forth between the application and the core.


Monads / Collections

Next we need to worry about how we write code in a natural way and what
the granularity of actions should be.  We will want to probably want to
write some basic actions which are quite "low level" and then have a way
of composing these into more complex actions.  And we would like this to
be possible in a nested way (of course).

The natural solution here is to have an action that is composed of smaller
actions.  When invoked it, in turn, invokes the actions it contains.  This
naturally allows nesting.

At the same time, we want to write code in a way that uses the results of
actions, even while they are being composed.  This is not as easy as it
first appears, because we do not have a result until the action is
evaluated, which occurs at a later time than the execution of the code
constructing the action (I am not sure how this changes depending on
whether the language is lazy or not, but Python is eager).

Because of this I adapted the "monad" syntax I described in an earlier
post.  Each action returns a single value (it may be a tuple or list, but
the initial binding syntax for the monad is single assignment - later
statements may unpack values).

So, for example, AddFoo() may be an action that creates a new Foo in the
database.  It might return the equivalent ORM instance, or the key
(instance is more useful externally, but the key is more useful internally
as it allows the inverse (undo) to be constructed with less assumptions
about what the ORM does with deleted objects - consider re-adding a
deleted value).  Then if UseFoo uses the instance we might have:

  m = ActionCollection()
  m.the_foo = AddFoo(foo details)
  m < UsefFoo(m.the_foo)

where it so happens that UseFoo returns no useful value (hence "<").


Irreversible Change

Not all actions will have an inverse.  For example, deleting a database. 
These are the "are you sure?" actions.  Such actions effectively delete
the existing undo stack, so the mechanism for accumulating undo actions
must be aware of these (for example, the undo value may be a special token
that the accumulator mechanism will detect).

This might suggest that such actions should themselves be responsible for
prompting the user, so that if they are "buried" in a composite action the
prompt still occurs, even if the GUI was "unaware" that a dangerous action
was being invoked.

However, there is a second consideration here - the user experience. 
While we as programmers may happily compose actions, the GUI must
associate a single undo action with a single GUI interaction.  At one
level this is feasible - a composite action creates a composite undo.  But
at another level it is not - what happens to the undos that are generated
*after* an irreversible action?  Either we present "undo half the action"
to the GUI layer, or we discard the undos.

Alternatively, we could prohibit irreversible actions from being grouped. 
This would force them to be submitted singly and so make them obvious to
the GUI layer (and the user) (it might still make sense to have a single
point for asking the user to confirm - this might be the same undo layer
posited earlier, between GUI and application core).

To enforce this, irreversible actions must look different.  In an untyped
language like Python this is not easy.  Perhaps the safest approach is to
also make such actions throw an exception if passed an undo accumulator. 
Again this makes most sense if the logic is handled at the intermediate
undo layer (note that the exception is thrown before the action occurs, so
any previous step can still be undone).  Or perhaps this is overkill?


Database

I mentioned above the idea that we can undo the already-completed part of
a composite action if we have to abort the action half-way through. 
However, is at least one case in which this is not necessary.

The application I am writing is, essentially, a front-end to a database. 
All the application actions are intended to modify the database (it's an
application to explicitly manage a database).  So there is an alternative
approach to undo, which is to use database transactions.

The reason I do not use this alone is that (as far as I know), they are
"single shot".  There is no way to have successive undos in a normal
database (there are databases that allow versioned histories - essentially
functional data structures - but I have to use MySQL (which isn't fit to
be called a database at times, but I digress...).  So I need some more
general mechanism for managing a whole series of undos, but for a single
composite action (ie implementing undo at the level of an action perceived
by the user via the GUI) it may be safer to use the database undo.

The trade-off is unclear (ie the correct choice is unclear).

Andrew

Extra Thoughts

Reading what I just posted, a couple of extra comments:

- I forgot to mention ORM.  The main issue is the degree of integration
between ORM and transactions.  I believe SQL Alchemy is OK in this regard
(I am very impressed with SQL Alchemy).

- It may seem odd that you can undo and then redo something which included
generated values:

  m = ActionCollection()
  m.the_foo = AddFoo(foo details)
  m < UsefFoo(m.the_foo)

That will only work in general if (1) IDs are consistent (so undoing
reverses the database counter) and (2) the ORM caches singletons
correctly.

(2) seems very unlikely to me, although I haven't investigated it.  (1)
seems like a safer bet, but you remember cannot rely on transactions -
undo must really undo!

It might be simplest to avoid such things completely and instead use the
natural keys that exist in the data.

Andrew

Yet More (Entropy?!)

An alternative approach that avoids some of the issues with undoing
composite actions may be avoided if the composite actions themselves
remain to be redone.  Then undo is only a localized issue (within a
particular composite context), while redo retains the original context
(reconstructed as before).

This implies that the collection of actions at the top level (which can be
stepped through, back and forth, with undo and redo, is not like lower
level collections.

In other words, composite actions effectively return themselves after
undoing twice (ie undo(undo(x)) is x).

This seems to imply an asymmetry between (re)do and undo (doing requires
links between actions implemented via the monad-scoped variables, which
implies a certain "long range" transmission of information not necessary
in undo).  I guess this reflects the natural construction of structure /
information, but it seems slightly odd to see such a physical effect in
these abstract surroundings.

Andrew

Clarification

The above may be clear to no-one except myself, and even then I have my
doubts.  The problem can be understood by working forwards, then backwards
then forwards again through the code I gave:

  m = ActionCollection()
  m.the_foo = AddFoo(foo details)
  m < UsefFoo(m.the_foo)

The first time through this code, "the_foo" is bound to something, that
probably depends on the database.

The Inverse for AddFoo is generated at this point, storing that
information.  Same for the inverse of UseFoo.

Running backwards (for undo), each action's inverse can run separately. 
There's no equivalent of the tying between two actions made by "the_foo"
because all that information in a sense "already exists".  It seems odd
that there is no need for something equivalent going backwards - hence my
comment about entropy.

OK, so now imagine going forwards again with a "redo".

The problem I was seeing is that if we treat each action in an isolated
way then there's no "the_foo" the second time round.  Instead there's
simply a AddFoo generated from its inverse (during the undo) and a UseFoo
generated from its inverse, but not structure to tie them together.  So I
was assuming that the inverse of the inverse of the UseFoo would have the
value of "the_foo" stored internally - a memory passed down the chain of
inverses.

Is that really any clearer?

And the solution is to instead save the container somehow.

So on undo the container runs each undo individually.

But on redo the container re-runs from scratch.  Then "the_foo" make take
on a logically equivalent value, but it may not be identical (if, say, the
undo doesn't reset the database autoincrement counters).

Andrew

And I am typing all this using a KeyTronics keyboard - UK layout - from
the 1990s.  It came with a good quality machine I bought way back.  I just
took it apart and cleaned it, and am using it again.  It's soooo much
better than anything I've had since (I always bought cheap
replacements...).  It's so clicky!  Unfortunately it's cream and rather
old-fashioned.  Perhaps so old-fashioned it's cool again?  And after
getting used to US (laptop) and Spanish (home server) keyboards, the UK
layout is annoying....  Still, I do have Ł signs (that's a pound - no idea
how it will display on the blog).

Not Monads!

I just wanted to note that the above really has very little to do with Monads
in any serious, well defined sense.

I considered deleting the article, but I am against such things on principle
and anyway, the general thoughts about deletion are something I may need in
the future.

Andrew

Comment on this post

Undo, Redo, Transactions, ORM, Monads, Python

Extra Thoughts

Yet More (Entropy?!)

Clarification

Not Monads!

C[omp]ute