| Andrew Cooke | Contents | Latest | RSS | Twitter | Previous | Next

C[omp]ute

Welcome to my blog, which was once a mailing list of the same name and is still generated by mail. Please reply via the "comment" links.

Always interested in offers/projects/new ideas. Eclectic experience in fields like: numerical computing; Python web; Java enterprise; functional languages; GPGPU; SQL databases; etc. Based in Santiago, Chile; telecommute worldwide. CV; email.

Personal Projects

Lepl parser for Python.

Colorless Green.

Photography around Santiago.

SVG experiment.

Professional Portfolio

Calibration of seismometers.

Data access via web services.

Cache rewrite.

Extending OpenSSH.

Last 100 entries

Hilary Mantel: The Assassination of Margaret Thatcher - August 6th 1983; NSA Interceptng Gmail During Delivery; General IIR Filters; What's happening with Scala?; Interesting (But Largely Illegible) Typeface; Retiring Essentialism; Poorest in UK, Poorest in N Europe; I Want To Be A Redneck!; Reverse Racism; The Lost Art Of Nomography; IBM Data Center (Photo); Interesting Account Of Gamma Hack; The Most Interesting Audiophile In The World; How did the first world war actually end?; Ky - Restaurant Santiago; The Black Dork Lives!; The UN Requires Unaninmous Decisions; LPIR - Steganography in Practice; How I Am 6; Clear Explanation of Verizon / Level 3 / Netflix; Teenage Girls; Formalising NSA Attacks; Switching Brakes (Tektro Hydraulic); Naim NAP 100 (Power Amp); AKG 550 First Impressions; Facebook manipulates emotions (no really); Map Reduce "No Longer Used" At Google; Removing RAID metadata; New Bike (Good Bike Shop, Santiago Chile); Removing APE Tags in Linux; Compiling Python 3.0 With GCC 4.8; Maven is Amazing; Generating Docs from a GitHub Wiki; Modular Shelves; Bash Best Practices; Good Emergency Gasfiter (Santiago, Chile); Readings in Recent Architecture; Roger Casement; Integrated Information Theory (Or Not); Possibly undefined macro AC_ENABLE_SHARED; Update on Charges; Sunburst Visualisation; Spectral Embeddings (Distances -> Coordinates); Introduction to Causality; Filtering To Help Colour-Blindness; ASUS 1015E-DS02 Too; Ready Player One; Writing Clear, Fast Julia Code; List of LatAm Novels; Running (for women); Building a Jenkins Plugin and a Jar (for Command Line use); Headphone Test Recordings; Causal Consistency; The Quest for Randomness; Chat Wars; Real-life Financial Co Without ACID Database...; Flexible Muscle-Based Locomotion for Bipedal Creatures; SQL Performance Explained; The Little Manual of API Design; Multiple Word Sizes; CRC - Next Steps; FizzBuzz; Update on CRCs; Decent Links / Discussion Community; Automated Reasoning About LLVM Optimizations and Undefined Behavior; A Painless Guide To CRC Error Detection Algorithms; Tests in Julia; Dave Eggers: what's so funny about peace, love and Starship?; Cello - High Level C Programming; autoreconf needs tar; Will Self Goes To Heathrow; Top 5 BioInformatics Papers; Vasovagal Response; Good Food in Vina; Chilean Drug Criminals Use Subsitution Cipher; Adrenaline; Stiglitz on the Impact of Technology; Why Not; How I Am 5; Lenovo X240 OpenSuse 13.1; NSA and GCHQ - Psychological Trolls; Finite Fields in Julia (Defining Your Own Number Type); Julian Assange; Starting Qemu on OpenSuse; Noisy GAs/TMs; Venezuela; Reinstalling GRUB with EFI; Instructions For Disabling KDE Indexing; Evolving Speakers; Changing Salt Size in Simple Crypt 3.0.0; Logarithmic Map (Moved); More Info; Words Found in Voynich Manuscript; An Inventory Of 3D Space-Filling Curves; Foxes Using Magnetic Fields To Hunt; 5 Rounds RC5 No Rotation; JP Morgan and Madoff; Ori - Secure, Distributed File System; Physical Unclonable Functions (PUFs); Prejudice on Reddit; Recursion OK

© 2006-2013 Andrew Cooke (site) / post authors (content).

Undo, Redo, Transactions, ORM, Monads, Python

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

Extra Thoughts

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

Date: Sat, 10 May 2008 15:07:47 -0400 (CLT)

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?!)

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

Date: Sat, 10 May 2008 16:12:30 -0400 (CLT)

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

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

Date: Sat, 10 May 2008 18:14:22 -0400 (CLT)

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!

From: andrew cooke <andrew@...>

Date: Fri, 19 Mar 2010 19:30:51 -0400

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