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:
- 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.
- 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:
public class CommandProcessorTest
{
private const int CAPACITY = 5;
private int testValue;
private CommandProcessor processor;
[SetUp]
public void SetUp()
{
testValue = 0;
processor = new CommandProcessor(CAPACITY);
}
[Test]
public void SingleUndo()
{
int originalValue = testValue;
processor.Do(delegate { testValue++; },
delegate { testValue = originalValue; });
processor.Undo();
Assert.AreEqual(originalValue, testValue);
}
}
...and the code to make it work:
public delegate void Action();
public class CommandProcessor
{
private CircularBuffer<Action> undoBuffer;
public CommandProcessor(int capacity)
{
undoBuffer = new CircularBuffer<Action>(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()
{
int originalValue = testValue;
processor.Do(delegate { testValue++; }, delegate { testValue = originalValue; });
int changedValue = testValue;
processor.Undo();
processor.Redo();
Assert.AreEqual(changedValue, testValue);
}
Conceptually, this should be fairly easy:
public void Undo()
{
PopAndDo(undoBuffer);
}
public void Redo()
{
PopAndDo(redoBuffer);
}
private void PopAndDo(CircularBuffer<Action> 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<Action> undoBuffer,
Action redoAction, CircularBuffer<Action> 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<Action> undoBuffer;
private CircularBuffer<Action> redoBuffer;
public CommandProcessor(int capacity)
{
undoBuffer = new CircularBuffer<Action>(capacity);
redoBuffer = new CircularBuffer<Action>(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<Action> undoBuffer,
Action redoAction, CircularBuffer<Action> 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<Action> 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);
}
}
Posted in .NET, Design Patterns, Functional Programming, TDD | no comments |
Using Higher Order Functions in Windows Forms Applications
My wife is in the middle of a research project comparing diet to the age of reproduction in African house snakes. She has to collect quite a bit of data, and when I finally looked at the spreadsheets she was maintaining, I was ashamed that I had not written something for her earlier.
This was really the first Windows Forms application that I’ve had the opportunity to do in years (my UI’s aren’t very inspiring). However, I have to maintain a couple at work that were primarily written by former colleagues, and I’ve always been a bit dismayed at the enormous amount of duplication that the standard event-driven application generates.
Despite the fact that the application I wrote for my wife was nothing more than a one-off application, one which you don’t expect to have to maintain, I focused on eliminating the duplication I see in the Windows applications at work. The result isn’t something that I would even begin to consider done for a corporate application, but I found the duplication removal techniques worth writing about. The code can be found here.
The biggest gains in removing duplication, and the ones most readers are likely to be least familiar with, are the use of higher order functions. My impression is that most C# developers aren’t very comfortable with higher order functions. Actually, I think that’s probably true for most developers working within mainstream commercially developed (Microsoft, Borland, Sun) languages. They’re simply not emphasized enough.
For example, all the forms had a ListView to display the data. All of them had to define the column header names and the data that goes in each row. It looked something like this:
protected override void AddHeaders()
{
AddHeader(“Weight”);
AddHeader(“Length”);
AddHeader(“HL”);
AddHeader(“HW”);
}
protected override void AddCells()
{
AddCell(Weight);
AddCell(Length);
AddCell(HeadLength);
AddCell(HeadWidth);
}
Having the subclass define the column header names and the data that goes in each row didn’t bother me. What did bother me was having to specify the order that the headers and data needed to be shown in two different place. However, while the header names were static, the data would be different for each invocation. The result was to specify the order only once, in an associative array (I used .NET 2.0’s generic Dictionary, which seemed to maintain the order I entered the items). The key would be the column name, and the value would be a function to retrieve the data value.
// The superclass for all Forms…
public class SnakeForm : Form
{
protected delegate object GetterDelegate(object value);
private IDictionary<string, GetterDelegate> associations;
protected virtual void AddListViewAssociations(IDictionary<string, GetterDelegate> associations)
{
throw new NotImplementedException(“Override…”);
}
protected virtual IEnumerable ListViewHeaders
{
get
{
foreach (string header in associations.Keys)
{
yield return header;
}
}
}
protected virtual IEnumerable ListViewValues(object value)
{
foreach (GetterDelegate getter in associations.Values)
{
yield return getter(value);
}
}
protected virtual void AddCells(object source)
{
foreach (object value in ListViewValues(source))
{
AddCell(value);
}
}
private void SnakeForm_Load(object sender, EventArgs e)
{
associations = new Dictionary<string, GetterDelegate>();
AddListViewAssociations(associations);
AddHeaders();
}
private void AddHeaders()
{
foreach (string header in ListViewHeaders)
{
AddHeader(header);
}
}
private void AddHeader(string name)
{
ColumnHeader header = new ColumnHeader();
header.Text = name;
lvData.Columns.Add(header);
}
The important things to note are that the subclass is passed, in a template method, a collecting parameter, associations, each entry of which represents a column name along with a way of retrieving the value for a row in that column. The delegate used to retrieve the value can be passed a single state parameter, which is needed by the report forms that need to pass in the source object for each row. Given that information, the superclass can manage most of the work. (AddListViewAssociations would have been abstract, except for the fact that Visual Studio’s designer doesn’t much care for abstract classes.)
For example, here is the information for the measurement form that was first given to show the problem:
protected override void AddListViewAssociations(IDictionary<string, GetterDelegate> associations)
{
associations.Add(“Weight”, delegate { return Snake; });
associations.Add(“Length”, delegate { return Length; });
associations.Add(“HL”, delegate { return HeadLength; });
associations.Add(“HW”, delegate { return HeadWidth; });
}
One of the benefits of removing the ordering duplication is that the column names now sit beside the functions for retrieving the values, making it easier to understand. Notice that the GetterDelegate definition actually accepts an object parameter. C#’s anonymous delegate syntax lets you ignore unused parameters, making for a somewhat more readable line.
One of the forms shows the information about feedings per snake, and needed that parameter. Below is the entire implementation of the form (aside from the designer-generated code).
// ReportForm is a subclass of SnakeForm
public partial class FeedingBySnakeReport : ReportForm
{
public FeedingBySnakeReport()
{
InitializeComponent();
}
protected override void AddListViewAssociations(IDictionary<string, GetterDelegate> associations)
{
associations.Add(“Snake”, delegate(object obj) { return ((FeedingReportDto)obj).Snake; });
associations.Add(“Diet”, delegate(object obj) { return ((FeedingReportDto)obj).Diet; });
associations.Add(“Date”, delegate(object obj) { return ((FeedingReportDto)obj).Date; });
associations.Add(“Weight”, delegate(object obj) { return ((FeedingReportDto)obj).Weight; });
associations.Add(“Food Weight”, delegate(object obj) { return ((FeedingReportDto)obj).FoodWeight; });
associations.Add(“Ate?”, delegate(object obj) { return ((FeedingReportDto)obj).Ate; });
associations.Add(“%BM”, delegate(object obj) { return ((FeedingReportDto)obj).PercentBodyMass; });
associations.Add(“Comments”, delegate(object obj) { return ((FeedingReportDto)obj).Comments; });
}
protected IEnumerable GetReportValues()
{
FeedRepository repository = new FeedRepository();
return repository.FeedingsBySnake(Snake);
}
}
In case you’re wondering what this form does, it allows you to select a snake, or all snakes, and see the feeding information in the ListView. It also lets you export all the data to a CSV file. Not bad for 30 lines of code.
Another thing that bothered me about all the event handlers was how similar they looked. The workflow was abstracted in the superclass into a HandleEvent method:
protected delegate void EventHandlerDelegate();
protected virtual void HandleEvent(EventHandlerDelegate handler)
{
Cursor = Cursors.WaitCursor;
try
{
handler();
}
catch (Exception ex)
{
ShowError(ex.Message);
}
finally
{
Cursor = Cursors.Default;
}
}
HandleEvent takes a function that handles the meat of the event handler and wraps it within the code that’s common to all event handlers. Here’s a couple examples:
// In DataEntryForm, an abstract superclass, and subclass of SnakeForm
private void btnSave_Click(object sender, EventArgs)
{
HandleEvent(delegate
{
if (!IsOkToSave())
return;
Save();
AddRow(null);
FinishListViewUpdate();
Reset();
});
}
// In ReportForm, an abstract superclass, and subclass of SnakeForm
private void btnShow_Click(object sender, EventArgs e)
{
HandleEvent(delegate
{
lvData.Items.Clear();
// GetReportValues() is a template method defined in the subclasses.
IEnumerable reportValues = GetReportValues();
foreach (object record in reportValues)
{
AddRow(record);
}
});
}
Managing the ListView proved to be fertile territory for removing duplication through higher order functions. For example, I used the first row’s data to set the column alignments automatically—if it looked like a number or date, right-align the data; otherwise left-align it.
private void SetAlignments(object record)
{
int i = 0;
// A bit hackish, but the report dtos currently provide strings only…
foreach (object value in ListViewValues(record))
{
if (IsNumber(value) || IsDate(value))
lvData.Columns[i].TextAlign = HorizontalAlignment.Right;
else
lvData.Columns[i].TextAlign = HorizontalAlignment.Left;
i += 1;
}
}
private bool IsNumber(object value)
{
try
{
double.Parse(value.ToString().Replace(”%”, ””));
return true;
}
catch
{
return false;
}
}
private bool IsDate(object value)
{
try
{
DateTime.Parse(value.ToString());
return true;
}
catch
{
return false;
}
}
Look how alike IsNumber and IsDate look. We can simplify:
private delegate void ParseDelegate(string text);
private bool IsNumber(object value)
{
return CanParse(value, delegate(string text) { double.Parse(text.Replace(”%”, ””)); });
}
private bool IsDate(object value)
{
return CanParse(value, delegate(string text) { DateTime.Parse(text); });
}
private bool CanParse(object value, ParseDelegate parser)
{
try
{
parser(value.ToString());
return true;
}
catch
{
return false;
}
}
I used a similar trick to auto-size the column widths in the ListView based on the width of the largest item. Here’s the refactored code:
private delegate string GetTextDelegate(int index);
private void AutoSizeListView()
{
int[] widths = new int[lvData.Columns.Count];
FillSizes(widths, delegate(int i) { return lvData.Columns[i].Text; });
foreach (ListViewItem item in lvData.Items)
{
FillSizes(widths, delegate(int i) { return item.SubItems[i].Text; });
}
for (int i = 0; i < lvData.Columns.Count; i++)
{
if (!IsHidden(lvData.Columns[i]))
{
lvData.Columns[i].Width = widths[i] + 12;
}
}
}
private void FillSizes(int[] widths, GetTextDelegate text)
{
using (Graphics graphics = CreateGraphics())
{
for (int i = 0; i < lvData.Columns.Count; i++)
{
SizeF size = graphics.MeasureString(text(i), lvData.Font);
if (size.Width > widths[i])
widths[i] = (int)size.Width;
}
}
}
private bool IsHidden(ColumnHeader header)
{
return header.Width == 0;
}
If this were a more long-lived application, I really should have bit the bullet and created my own ListView subclass. The methods above reek of Feature Envy.
Being able to treat functions as first-class objects is extremely useful. For some reason, it doesn’t get the attention it deserves in most development books. And it’s often somewhat obscured by intimidating sounding names like “lambda expressions” thanks to its roots in lambda calculus. However, much of what I was able to do in this application was possible only because I was able treat functions as data and pass them as parameters. And it was helped by the fact that I didn’t have to explicitly define each function as a method; I could create them anonymously like any other data object (although C#’s anonymous delegate syntax is somewhat obscured by the static typing).
Posted in .NET, Design, Functional Programming | no comments |
C# Execute Around Method
Kent Beck called one of the patterns in Smalltalk Best Practice Patterns “Execute Around Method.” It’s a useful pattern for removing duplication in code that requires boilerplate code to be run both before and after the code you really want to write. It’s a much lighter weight method than template methods (no subclassing), which can accomplish the same goal.
As an example, I’ve written the following boilerplate ADO.NET code countless times:
public DataTable GetTable(string query, IDictionary parameters)
{
using (SqlConnection connection = new SqlConnection(this.connectionString))
{
using (SqlCommand command = new SqlCommand(query, connection))
{
connection.Open();
foreach (DictionaryEntry parameter in parameters)
{
command.Parameters.AddWithValue(parameter.Key.ToString(), parameter.Value);
}
SqlDataAdapter adapter = new SqlDataAdapter(command);
using (DataSet dataset = new DataSet())
{
adapter.Fill(dataset);
return dataset.Tables0;
}
}
}
}
public void Exec(string query, IDictionary parameters)
{
using (SqlConnection connection = new SqlConnection(this.connectionString))
{
using (SqlCommand command = new SqlCommand(query, connection))
{
connection.Open();
foreach (DictionaryEntry parameter in parameters)
{
command.Parameters.AddWithValue(parameter.Key.ToString(), parameter.Value);
}
command.ExecuteNonQuery();
}
}
}
Notice that the connection and parameter management overwhelms the actual code that each method is trying to get to. And the duplication means I have multiple places to change when I decide to do something differently. However, since the using block encloses the relevant code, a simple Extract Method refactoring is not as easy to see.
Here’s the result of applying an Execute Around Method pattern to it.
private delegate object SqlCommandDelegate(SqlCommand command);
public DataTable GetTable(string query, IDictionary parameters)
{
return (DataTable)ExecSql(query, parameters, delegate(SqlCommand command)
{
SqlDataAdapter adapter = new SqlDataAdapter(command);
using (DataSet dataset = new DataSet())
{
adapter.Fill(dataset);
return dataset.Tables0;
}
});
}
public void Exec(string query, IDictionary parameters)
{
ExecSql(query, parameters, delegate(SqlCommand command)
{
return command.ExecuteNonQuery();
});
}
private object ExecSql(string query, IDictionary parameters, SqlCommandDelegate action)
{
using (SqlConnection connection = new SqlConnection(this.onnectionString))
{
using (SqlCommand command = new SqlCommand(query, connection))
{
connection.Open();
foreach (DictionaryEntry parameter in parameters)
{
command.Parameters.AddWithValue(parameter.Key.ToString(), parameter.Value);
}
return action(command);
}
}
}
Much nicer, no?
Posted in .NET | no comments |