A Day In The Lyf

…the lyf so short, the craft so longe to lerne

Archive for November 2007

Using Closures to Implement Undo

While it seems to be fairly common knowledge in the functional programming world, I don’t think most object-oriented developers realize that closures and objects can be used to implement each other. Ken Dickey showed how it can be done rather easily in Scheme, complete with multiple inheritance and dynamic dispatch.

That’s not to say, of course, that all OO programmers should drop their object hats and run over to the world of functional programming. There is room for multiple paradigms.

Take the well-known Command pattern, often advertised as having two advantages over a more traditional API:

  1. Commands can be easily decorated, giving you some measure of aspect-oriented programming. CruiseControl.NET uses a Command-pattern dispatch for the web interface, and decorates each command with error-handling, etc, providing a nice separation of concerns.
  2. Commands can give you easy undo functionality. Rails migrations are a good example.

Recently, I had to retrofit Undo onto an existing legacy (and ugly) codebase, and I was able to do it quite elegantly with closures instead of commands.

What are closures?

Briefly (since better descriptions lie elsewhere), a closure is a procedure that “remembers” its bindings to free variables, where free variables are those variables that lie outside the procedure itself. The name come from LISP, where the procedure (or “lambda”, as LISPers call them) was said to “close over” its lexical environment. In C# terms, a closure is simply an anonymous delegate with a reference to a free variable, as in:

string mark = “i wuz here”;
DoSomething(delegate { Console.WriteLine(mark); });

Notice that the anonymous delegate references the variable mark. When the delegate is actually called, it will be within a lexical scope that does not include mark. To make that work, the compiler wraps the closure in a class that remembers both the code to execute and any variable bindings (remember – objects and closures can be interchanged).

As always, Wikipedia has a nice write-up. A C#-specific description can be found here.

What does a closure-based Undo look like?

The legacy code I needed to update maintained the entire object state serialized in XML. This was terrible for a number of reasons, but it did have the advantage of making undo easy in principle; just swap out the new XML with the XML before making the previous API call. I wanted something like this:

public delegate void Action();

public void AddItem(OrderItemStruct itemInfo)
{
    string originalXml = orderXml;
    Action todo = delegate
    {
        OrderApi.AddOrderItem(currentSession, ref itemInfo,
            ref orderXml, out errorCode, out errorMessage);
    };
    Action undo = delegate { orderXml = originalXml; };
    processor.Do(todo, undo);
}

In actual practice, the undo part of that could be wrapped up in some boilerplate code:

public void AddItem(OrderItemStruct itemInfo)
{
    CallApiMethod(delegate
    {
        OrderApi.AddOrderItem(currentSession, ref itemInfo,
            ref orderXml, out errorCode, out errorMessage);
    });
}

private void CallApiMethod(Action method)
{
    string originalXml = orderXml;
    processor.Do(method, delegate { orderXml = originalXml; });
    // error handling, etc…
}

Notice that the undo procedure is referencing originalXml. That variable will be saved with the closure, making for a rather lightweight syntax, even with the static typing.

Getting Started

Implementing a single undo is really quite easy. Here’s a simple test fixture for it:

[Test]
public void SingleUndo()
{
    CommandProcessor processor = new CommandProcessor(5);
    int testValue = 0;
    processor.Do(delegate { testValue++; },
        delegate { testValue--; });

    processor.Undo();

    Assert.AreEqual(0, testValue);
}

…and the code to make it work:

public delegate void Action();

public class CommandProcessor
{
    private CircularBuffer undoBuffer;

    public CommandProcessor(int capacity)
    {
        undoBuffer = new CircularBuffer(capacity);
    }

    public void Do(Action doAction, Action undoAction)
    {
        doAction();
        undoBuffer.Add(undoAction);
    }

    public void Undo()
    {
        if (!undoBuffer.IsEmpty)
        {
            Action action = undoBuffer.Pop();
            action();
        }
    }
}

I won’t go into how CircularBuffer works, but it’s such a simple data structure that you can figure it out.

Naturally, with undo, we’ll want redo:

[Test]
public void SingleRedo()
{
    CommandProcessor processor = new CommandProcessor(5);
    int testValue = 0;
    processor.Do(delegate { testValue++; }, delegate { testValue--; });
    processor.Undo();

    processor.Redo();

    Assert.AreEqual(1, testValue);
}

Conceptually, this should be fairly easy:

public void Undo()
{
    PopAndDo(undoBuffer);
}

public void Redo()
{
    PopAndDo(redoBuffer);
}

private void PopAndDo(CircularBuffer buffer)
{
    if (!buffer.IsEmpty)
    {
        Action action = buffer.Pop();
        action();
    }
}

However, we’re not actually adding anything to the redo buffer yet. What we need to do is rather interesting—we don’t want to add to the redo buffer until Undo is called. Closures to the rescue:

public void  Do(Action doAction, Action undoAction)
{
    doAction();
    undoBuffer.Add(delegate
    {
        undoAction();
        redoBuffer.Add(doAction);
    });
}

But let’s say I undo, redo, and then want to undo and redo again. That won’t work as written, and making it work is starting to get pretty ugly:

public void Do(Action doAction, Action undoAction)
{
    doAction();
    undoBuffer.Add(delegate
    {
        undoAction();
        redoBuffer.Add(delegate
        {
            doAction();
            undoBuffer.Add(delegate
            {
                undoAction();
                redoBuffer.Add(doAction);
            });
        });
    });
}

It’s becoming apparent that what we really want is infinite recursion, lazily-evaluated. How ‘bout a closure?

public void  Do(Action doAction, Action undoAction)
{
    doAction();
    undoBuffer.Add(DecoratedAction(undoAction, undoBuffer, doAction, redoBuffer));
}

private Action DecoratedAction(Action undoAction, CircularBuffer undoBuffer,
        Action redoAction, CircularBuffer redoBuffer)
{
    return delegate
    {
        undoAction();
        redoBuffer.Add(DecoratedAction(
            redoAction, redoBuffer, undoAction, undoBuffer));
    };
}

Now we see how easy it is to decorate closures—remember that the ability to decorate commands is an oft-quoted advantage of them. However, closures provide a more lightweight approach to programming than commands.

The elegance of this approach is hard to deny. All it takes is getting over the conceptual hump that functions are just data. Think about it—we just added a function that took two functions as arguments and returned another function.

What also was apparent to me is how much TDD helped me get to this point. It may not be obvious from the few snippets I’ve shown here, but building up to the DecoratedAction abstraction was a very satisfying experience.

For reference, here’s the full CommandProcessor class. The bit I haven’t shown, CanUndo and CanRedo, along with an event that fires when either one change, is there so that we know when to enable or disable a menu option in a UI.

public class CommandProcessor
{
    public event EventHandler UndoAbilityChanged;

    private CircularBuffer undoBuffer;
    private CircularBuffer redoBuffer;

    public CommandProcessor(int capacity)
    {
        undoBuffer = new CircularBuffer(capacity);
        redoBuffer = new CircularBuffer(capacity);
    }

    public void Do(Action doAction, Action undoAction)
    {
        FireEventIfChanged(delegate
        {
            doAction();

            // Redo only makes sense if we’re redoing a clean undo stack.
            // Once they do something else, redo would corrupt the state.
            redoBuffer.Clear();

            undoBuffer.Add(DecoratedAction(
                undoAction, undoBuffer, doAction, redoBuffer));
        });
    }

    private Action DecoratedAction(Action undoAction, CircularBuffer undoBuffer,
        Action redoAction, CircularBuffer redoBuffer)
    {
        return delegate
        {
            undoAction();
            redoBuffer.Add(DecoratedAction(
                redoAction, redoBuffer, undoAction, undoBuffer));
        };
    }

    public void Undo()
    {
        FireEventIfChanged(delegate { PopAndDo(undoBuffer); });
    }

    public void Redo()
    {
        FireEventIfChanged(delegate { PopAndDo(redoBuffer); });
    }

    public void Clear()
    {
        undoBuffer.Clear();
        redoBuffer.Clear();
    }

    public bool CanUndo
    {
        get { return !undoBuffer.IsEmpty; }
    }

    public bool CanRedo
    {
        get { return !redoBuffer.IsEmpty; }
    }

    private void PopAndDo(CircularBuffer buffer)
    {
        if (!buffer.IsEmpty)
        {
            Action action = buffer.Pop();
            action();
        }
    }

    private void FireEventIfChanged(Action action)
    {
        bool originalCanUndo = CanUndo;
        bool originalCanRedo = CanRedo;

        action();

        if (originalCanUndo != CanUndo || originalCanRedo != CanRedo)
            OnUndoAbilityChanged(EventArgs.Empty);
    }

    protected void OnUndoAbilityChanged(EventArgs e)
    {
        EventUtils.FireEvent(this, e, UndoAbilityChanged);
    }
}

Written by Brandon Byars

November 5, 2007 at 11:26 pm

Posted in .NET, Design Patterns, TDD

Tagged with

Follow

Get every new post delivered to your Inbox.