C[omp]ute

From: "andrew cooke" <andrew@...>

Date: Sat, 10 May 2008 15:00:32 -0400 (CLT)

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