Critical Development

Language design, framework development, UI design, robotics and more.

Archive for the ‘Software Architecture’ Category

.NET Micro Framework vs. Microsoft Robotics Studio

Posted by Dan Vanderboom on April 12, 2008

The .NET Micro Framework is a compatible subset of the full .NET Framework, similar to how the Compact Framework is a subset.  But the Micro Framework can act as its own real time operating system (RTOS) instead of loading the tiny CLR in a host operating system, and works with a variety of hardware devices, including those that don’t have their own memory management unit (MMU).  The gist is that embedded applications as well as low-level drivers can now be written in managed code (a huge leap forward), and take advantage of garbage collection, strong-typing, and other nice features that are typically absent in embedded systems programming.  This supposedly reduces errors, boosts productivity, and reduces development costs.

I’ve been watching videos like this, reading about the Micro Framework for the past few months, have pre-ordered this book from Amazon, and have been itching to get my hands on a hardware development kit to start experimenting.  The only problem is that the interfaces for these embedded devices are so foreign to me (I2C, GPIO, etc.), and I’m not exactly sure what my options are for assembling components.  What kinds of sensors are available?  Do I have to solder these pieces together or is there a nice modular plug system similar to the SATA, IDE, and PCI connectors on modern computers (but on a smaller scale)?  Do I have to write my own device drivers for anything I plug in, or is there some abstraction layer for certain classes of inputs and outputs?

The other issue that makes me hesitate is the thought of programming without language conveniences like generics on a more resource-constrained device than the Windows Mobile devices I’m already frustrated with (and have been for the past four years).

I’m not saying that I’m not excited about managed code on tiny embedded devices, and I’m not saying I won’t start playing with (and blogging about) this important technology sometime in the next few months, but I’ve discovered another platform for embedded device development with the ability to interact directly with the physical world that offers a much lower technical barrier for entry, so that’s where I’m starting.

What I’m referring to is Microsoft Robotics Studio, which is by all accounts a phenomenal platform for more than just robotics, and seems to overlap somewhat with the Micro Framework’s reach (at the intersection of the computer-digital and physical-analog worlds).  The two critical components of this architecture are the Decentralized Software Services Protocol (DSSP, originally named WSAP) and the Concurrency & Coordination Runtime (CCR).  Make sure you watch this video on the CCR, and note how George emphasizes that “it’s not about concurrency, it’s about coordination”, which I found especially enlightening.  These are highly robust and general purpose libraries, and both of them will run on Compact Framework!  (I was very impressed when I read this.)

Without having studied them both in depth yet, the CCR seems to cannibalize on the Task Parallel Library (TPL), at least conceptually, offering a much more complete system of thread manipulation and synchronization than the original System.Threading types, all for a vertical industry that has much greater demands of a concurrency framework that must, for example, deliver massive concurrency and complex coordination rules in a highly-distributed system, all the while handling full and partial failures gracefully.  Some of the patterns and idioms for making concurrency and synchronization operations easy to write and understand are masterfully designed by Henrik Nielsen and George Chrysanthakopoulos (and I thought Vanderboom was a long name!).

The fact that the CCR and DSSP were developed together is significant.  Tasks running in parallel need to be manipulated, coordinated, and tracked regardless of whether they’re running on four processors in one computer or on 256 processors spread across a hundred devices, and distributed services need a dependable way of parallelizing their efforts on individual machines.  This is a synergistic relationship, each subsystem enhancing the elegance and usefulness of the other.  So why not use the CCR in every application instead of developing the TPL?  Are these two teams actively collaborating, or have they been building the two frameworks in isolation?

I also have to make special mention of the decentralized software services, which as a protocol sits on top of HTTP in a RESTful implementation.  It supports composition of services by creating partnerships with other services, defining securely which partnerships are allowed, offering identification and discovery of services, and much more.  In this assembly then, we have a robust library for building distributed, composable, decentralized services-oriented systems with event publication and subscription, with services that can be hosted on desktop and mobile computers alike.  Wow, call me a geek, but that’s really frickin’ cool!  Some of the ideas I have for future projects require this kind of architectural platform, and I’ve been casually designing bits and pieces of such a system (and got so far as getting the communication subsystem working in CF).  Now, however, I might be turning my attention to seeing if I can’t use the Robotics Studio APIs instead.

One thing to be clear about is that Robotics Studio doesn’t support Micro Framework, at least not yet.  I wonder exactly how much value there would be to adding this support.  With hardware options such as this 2.6″ x 2.3″ motherboard with a 1.6 GHz Intel Atom processor, video support, and up to 1 GB of RAM, capable of running Windows XP or XP Embedded, and priced at $95 (or a 1.1 GHz version for $45), we’re already at a small enough form factor and scale for virtually any autonomous or semi-autonomous robotics (or general embedded) applications.  There’s also the possibility for one or more Micro Framework devices to exchange messages with a hardware module that is supported in Robotics Studio, such as the tiny board just mentioned.

Where do we go next?  For me, I just couldn’t resist jumping in with both feet, so I ordered about $500 in robotics gear from Phidgets: USB interface boards, light and tempature sensors, a 3-axis accelerometer (think Wii controller), motors and servos, an RFID reader with tags, LEDs, buttons, knobs, sliders, switches, and more.  I plan to use some of this for projects at CarSpot, and the rest simply to be creative with and have fun.  I also pre-ordered this book, but the publication date is set for June 10th, so by the time I get it, I may have already figured most of it out.

Advertisements

Posted in Compact Framework, Concurrency, Distributed Architecture, Micro Framework, Microsoft Robotics Studio, Service Oriented Architecture, Software Architecture | 2 Comments »

The Visitor Design Pattern in C# 3.0

Posted by Dan Vanderboom on April 9, 2008

I use many common design patterns on a regular basis–composite, MVC/MVP, adapter, strategy, factory, chain of command, etc.–but I’ve never come across a situation where I felt Visitor in the classic definition (GoF) made sense.  I had read about it, but the necessity of defining the interfaces for not only the Visitor classes (that’s not so bad) but also the elements being visited, makes it seem overly complex and therefore tainted for me.  What if you don’t own the source code to the elements, and don’t want to inherit from existing types (if they’re not sealed) just to implement an IVisitedElement interface?

I wanted a less intrusive way of visiting any set of objects, without making any special demands on or assumptions about their types, and I suspected that new features in C# 3.0 would provide a way to make it elegant and terse.  What’s needed in essence is to visit each object in a collection with a common function or object, and to perform some action, transform the object in some way, and/or calculate some end result (usually an aggregation).  Can we do that without having to implement special interfaces or disrupting the code model in place?

For the sake of completeness and to serve as a baseline for other implementations, I’ll show you what the classic Visitor pattern looks like.

UML for Visitor Design Pattern

Here is the code that corresponds to this diagram.

interface IEmployeeVisitor
{
    void Visit(Employee employee);
    void Visit(Manager manager);
}

interface IVisitorElement
{
    void Accept(IEmployeeVisitor Visitor);
}

class EmployeeCollection : List<Employee>
{
    public void Accept(IEmployeeVisitor Visitor)
    {
        foreach (Employee employee in this)
        {
            employee.Accept(Visitor);
        }
    }
}

class Employee : IVisitorElement
{
    public decimal Income;
    public Employee(decimal income) { Income = income; }

    public virtual void Accept(IEmployeeVisitor Visitor)
    {
        Visitor.Visit(this);
    }
}

class Manager : Employee, IVisitorElement
{
    public decimal Bonus;
    public Manager(decimal income, decimal bonus) : base(income) { Bonus = bonus; }

    public override void Accept(IEmployeeVisitor Visitor)
    {
        Visitor.Visit(this);
    }
}

class SumIncomeVisitor : IEmployeeVisitor
{
    public decimal TotalIncome = 0;
    public void Visit(Employee employee) { TotalIncome += employee.Income; }
    public void Visit(Manager manager) { TotalIncome += manager.Income + manager.Bonus; }
}

class Program
{
    static void Main()
    {
        EmployeeCollection employees = new EmployeeCollection();
        employees.Add(new Employee(100000));
        employees.Add(new Employee(125000));
        employees.Add(new Manager(210000, 35000));

        SumIncomeVisitor visitor = new SumIncomeVisitor();
        employees.Accept(visitor);
        decimal result = visitor.TotalIncome;

        Console.WriteLine(result);
        Console.ReadLine();
    }
}

 
The first major disadvantage is the amount of plumbing that must be in place, and the two-way dependencies created, between visitors and the objects to be visited.  Though specific types aren’t hard-coded, a conceptual two-way dependency implied by the interfaces’ knowledge of each other requires forethought and special accomodations on both sides from the beginning.  Management of dependencies is always important; how well we do so determines how applications become more complex as they grow.  So whenever possible I ensure that dependencies run in one direction.  This creates natural segmentation and layering, and ensures that components can be pulled apart from each other rather than congealing into something like a tangled ball of christmas tree lights.

Instead of passing a collection of Employee objects to some calculating Visitor, we tell the Employee to accept a Visitor object, which then just turns around and calls the Visitor.  That by itself seems rather indirect and convoluted.  Visiting a single element isn’t very exciting.  Nothing very interesting happens until you have a whole bunch of things to work with.  So in order to visit a collection, a custom collection type is defined with an Accept method that in turn calls Accept on each Employee.  This custom collection is yet another type we’re required to write when otherwise a List<Customer> or something similar would suffice.  And what happens when your data structure is something other than a basic list?  What if you have a tree of objects you’d like to visit?  Would you then have to implement a tree data structure that is visitor friendly?  How many aggregation types do you want to reinvent with visitation specifically in mind?

The rest of it isn’t so bad.  The SumIncomeVisitor class contains both the processing logic and state for any calculations needed by that Visitor.  One of these is instantiated (another extra step), passed to the collection’s Accept method, and therefore executed against all employees in the collection.  After all objects are visited, the SumIncomeVisitor object contains the final result.  This all works, but seems pretty klunky.  Perhaps the pattern is more interesting if IVisitorElement classes provide more sophisticated Accept implementations.  I can’t think of any examples off-hand but I’ll be thinking about and looking for these.

The code above is just shy of 80 lines long.  Can we accomplish exactly the same goal with less code, more simply and clearly?

class Employee
{
    public decimal Income;
    public Employee(decimal income) { Income = income; }
}

class Manager : Employee
{
    public decimal Bonus;
    public Manager(decimal income, decimal bonus) : base(income) { Bonus = bonus; }
}

class Program
{
    static void Main()
    {
        List<Employee> employees = new List<Employee>();
        employees.Add(new Employee(100000));
        employees.Add(new Employee(125000));
        employees.Add(new Manager(210000, 35000));

        decimal TotalIncome = 0;
        employees.ForEach(e => SumEmployeeIncome(e, ref TotalIncome));

        Console.WriteLine(TotalIncome);
        Console.ReadLine();
    }

    static void SumEmployeeIncome(Employee employee, ref decimal TotalIncome)
    {
        TotalIncome += employee.Income;

        if (employee is Manager)
            TotalIncome += (employee as Manager).Bonus;
    }
}

 
In this code, you’ll notice a few simplifications:
  1. There are no IVisitorElement or IEmployeeVisitor interfaces.
  2. Employee and Manager types exist without any knowledge of or explicit support for being visited.
  3. No custom collection is required, so a basic List<Employee> is used.

In order to make this work, we need the same basic things that we needed before: visiting/processing logic, and a place to store state for that processing.  In the second approach, the state is stored in the TotalIncome variable within the Main method, where the calculation is being requested, and the processing logic kept in another method of the same class.  I could have declared TotalIncome as a class variable, but I’d really like to restrict any “scratch pad” data used in a calculation to have as restricted a scope as possible.  In the classic Visitor pattern, the data is encapsulated with the processing logic.  By calling a method with a secondary ref parameter, I can declare TotalIncome within the Main method and avoid cluttering the class definition with data that’s only relevant to one method’s logic.  This is a lighter-weight, more in-line approach than defining separate types and having to instantiate a Visitor object (Visitor Object vs. Visitor Method).

The actual mechanism for visiting every object is the ForEach method.  The List<T> class includes a very useful ForEach method that allows you to pass in an Action<T> delegate to execute a method for each element.  ForEach can’t take a method with our second ref parameter; it can only accept an Action<T> delegate.  The lambda expression e => SumEmployeeIncome(e, ref TotalIncome) creates an anonymous method that does in fact match Action<T>.  The parameter e is of type Employee because the employees collection is List<Employee>, which means the Employee type is inferred for Action<Employee>.  The anonymous method represented by the lambda then calls SumEmployeeIncome, passing the Employee e object through as well as the TotalIncome state to be transformed on successive calls for each Employee.

Finally, SumEmployeeIncome acts as the Visitor.  Different logic can be performed for different types where inheritance is involved, as it is with this sample, by testing for types using the is operator.  This is in contrast to the dual Visit methods taking Employee and Manager types respectively.  Actually, the classic Visitor pattern could have used the same approach in this regard.
 
Where more complex state is needed for processing, a new Visitor-state type could be created to support the processing, and by using an object for this purpose, it wouldn’t be necessary to declare or pass the parameter by reference.  Another option would simply be to declare multiple ref parameters.
 

The List.ForEach method is awfully nice, but what if you’re working with another data structure, such as an array, an ArrayList, a LinkedList<T>, or even a Tree<T>?  Defining a simple extension method can provide this tool regardless of what kind of collection you’re working with.

public static void ForEach<T>(this IEnumerable<T> collection, Action<T> action)
{
    foreach (T item in collection)
    {
        if (action != null)
            action(item);
    }
}

That’s better.  Now if only that extension method had been defined in the first place, the specific one in the List<T> class wouldn’t be necessary.

There’s an even more succinct way to accomplish the specific example above, using the Sum extension method on IEnumerable<T>.

TotalIncome = employees.Sum(e => (e is Manager) ? (e as Manager).Bonus + e.Income : e.Income);

I don’t mind writing or reading code like this, and as more functional programming constructs are merged into C#, I think it’s important to flex these mental muscles and become familiar with the syntax, but one might argue that this is a little more cryptic than the preceding example.  If the calculation was any more complicated, it would make sense to use a statement lambda with curly braces instead of the shorter expression lambda shown above.  Here’s one way it could be written as a statement lambda:

TotalIncome = employees.Sum(e =>
    {
        decimal result = e.Income;

        if (e is Manager)
            result += (e as Manager).Bonus;

        return result;
    });

You can see that there is more opportunity here to perform other actions and participate in more complex calculations.  This approach is even lighter-weight than the second approach suggested above using a separate named method and external state passed by reference.  The approach you take should depend on the needs and constraints of the situation.  Lighter-weight approaches are good for ad-hoc processing, whereas the heavier approaches make more sense if the visiting logic needs to be reused in other places.

If we don’t need to share state across visitations of objects in a collection, we could simply use extension methods, which is the simplest option of all.  After all, the original intent of the Visitor pattern was to allow us to add functionality to a class without modifying the original element’s type.  According to dofactory.com:

Represent an operation to be performed on the elements of an object structure. Visitor lets you define a new operation without changing the classes of the elements on which it operates.

Extension methods “add” functionality to existing classes, or at least create a compelling illusion that they do.  Just reference an assembly and import the right namespace to add the operations.  It is possible to share state, but only by doing something like passing in some shared state object to each call.

If C# had the ability to define a variable that would be static to a defined closure in a method (which it doesn’t), we could use extension methods all the time without any drawbacks.  (I miss the static local variable feature of Turbo Pascal.)

Conclusion

With the use of lambda expressions and extension methods, we’ve been able to cut the amount of code for the Visitor pattern by more than half and found that there was no need to specially prepare the data model classes to support visitation.  While the classic Visitor pattern may have more potential in complex and custom Accept scenarios, in general the need to visit elements of a collection can be better accomplished with the judicious use of available language features in C# than by blindly following classic design patterns without consideration for how relevant they really are.

While I certainly encourage developers to become familiar with common patterns, I also encourage them to think carefully about the code they’re writing, and to ask themselves if it’s as clear and simple as it can be.  As software systems grow in size–sometimes becoming victims of their own success–small inefficiencies and muddied designs can snowball into unmanageability.  Apply a simple solution first, and then add complexity only when necessary.

Doubt and ask why constantly.  Be educated and familiar with the literature, but don’t dogmatically accept everything you read: think for yourself and hone your skills at every opportunity.  While the goals and forces in software tend to remain constant over time, the forms that made sense years ago may become unnecessary with today’s tools.

Posted in Algorithms, Data Structures, Design Patterns, Object Oriented Design, Problem Modeling, Software Architecture | 10 Comments »

Tree Data Structure Source Code Posted

Posted by Dan Vanderboom on April 3, 2008

[Updated 8/14/2014] The source code for this library can be found here at GitHub. Also check out my blog post announcing it.

For those of you who have been waiting for the source code to the Tree<T> article I wrote, I’m happy to announce that it’s finally available.  I had originally intended to supply some non-trivial examples of its use, but with my super busy schedule at work and otherwise, I’ve had to reduce the scope just to get it out there.  One of my examples is large enough to warrant one or more large articles, so I also didn’t want to just toss them in there without sufficient explanation as to how it all works.

While I work on getting those ready, check out Damon Payne’s article on using a non-binary tree for modeling dependencies among concurrently-running tasks with the Task Parallel Library.  This is a great use of the tree data structure.  It would be interesting to see how that would work for tasks with cross-branch dependencies.  Does the tree become a graph?  Would iteration become a garbage-collection-like traversal?  How would it need to respond to insertion of tasks or modification or dependencies during execution?

My non-binary tree article, which has been updated with a short section just before the conclusion, can be found here.  At the very top of the article is a link to the source code in the form of a Visual Studio 2008 solution.  For those of you with VS2005, you should be able to easily extract the code and create a VS2005 project out of it.  I specifically targeted .NET 2.0 instead of 3.5, and originally tested it against Compact Framework.

I’ll also be doing further development of this library, so if you have any cool feature requests, let me know.

Posted in Algorithms, Concurrency, Data Structures, My Software, Object Oriented Design, Problem Modeling, Software Architecture | 6 Comments »

Tree<T>: Implementing a Non-Binary Tree in C#

Posted by Dan Vanderboom on March 15, 2008

[Updated 8/14/2014] The source code for this library can be found here at GitHub. Also check out my blog post announcing it.

[This is the first article in a series of intelligent data structures, which is continued here with KeyedList.]

I’ve always thought it was odd that the .NET Framework never shipped with a Tree or Tree class in its collection namespaces.  Most of the other classic data structures are there: List, Dictionary, Stack, Queue, and so on.  Where then is Tree?  I have no idea, but finding myself in need of one, I decided to build one, and in doing so realized that it was a little trickier than I first imagined it would be.  Certainly it isn’t difficult to get some kind of tree working, even without support for generics, but building one that is truly intuitive to use was a real challenge.  In this article I will share what I came up with, and will illustrate the thought process behind each of the design decisions that I made as a study in object-oriented design and the use of some cool C# language features like generics constraints.

First, what is a tree data structure and what is it used for?  A tree is, in layman’s terms, a collection of nodes (items) that are connected to each other in such a way that no cycles (circular relationships) are allowed.  Examples abound in organization charts, family trees, biological taxonomies, and so forth.  Trees are incredibly useful structures because they allow us to represent hierarchies and to compose complex structures out of basic parts and simple relationships.  In the world of programming specifically, this provides a mechanism for extensibility across many domains, and a container to assist us in searching, sorting, compressing, and otherwise processing data in efficient and sophisticated ways.  Trees are also a natural fit for use in the composite design pattern, where a group of objects can be treated (or processed) like a single object.

Just as it’s possible to implement recursive algorithms non-recursively, it’s also possible to create non-hierarchical data structures to store data that would more logically be stored in a tree.  In these cases, your code is typically much more clear when organized in a tree, leading to greater maintainability and refactorability.  Recursion itself, while not exceptionally common in every day programming tasks, plays a more important role in some interesting ways with trees and traversal patterns.  Traversal is the term used to describe how nodes in a tree are visited.  Later I’ll demonstrate some tree traversal techniques that you can use.

Binary vs. Non-Binary Trees

What are binary trees, and why the focus on non-binary trees?  Binary trees are a special kind of tree in which each node can only have two children, often referred to as left and right child nodes.  These special trees are very useful for sophisticated searching, sorting, and other algorithms.  However, trees that allow any number of children seem to abound in more general, every-day programming scenarios, as you’ll see from examples below.  In a follow-up article, I’ll demonstrate how you can create a BinaryTree class that inherits from Tree and applies the necessary restrictions and some useful abstractions.  Below (figure 1) is a binary tree, which I present here to contrast with the non-binary trees that we’ll be covering in detail.

BinaryTree

Figure 1. A generic binary tree.

For more information on implementing and using binary trees, see this article which is part of a larger series on data structures.

Examples of Non-Binary Trees

A simple example of a non-binary tree is the file system in any modern operating system.  The diagram below (figure 2) illustrates a small part of the structure of the Windows file system.  Folders can be nested inside other folders as deeply as needed, providing the ability to compose a complex organizational structure for storing files.  The traversal path—from the root to some other node—can be represented by a canonical resource descriptor such as C:\Windows\system32.

FileSystemTree

Figure 2. The file system is a tree structure of folders containing other folders.

This hierarchical structure can be represented and visualized in different ways, though the underlying relationships are the same.  The screenshot below (figure 3) is of Windows Explorer on my development computer.  The control is the common TreeView, which supplies a way in this case for users to explore and interact with the tree data structure of the file system.

FileSystemTreeView

Figure 3. A tree view control in Windows Explorer provides access to a hierarchy of nested folders.

Another example is the organization of controls in a form (for Windows Forms) or in a window (for WPF).  The next diagram (figure 4) depicts the relationship of controls containing child controls, which may in turn contain their own children, and so on.

AppWindowTree2

Figure 4. A user interface is composed of a tree of controls that contain other controls.

This is also manifested through a user interface with the Document Outline window in Visual Studio, which is very useful for selecting deeply nested controls, or container controls that are otherwise difficult to select in the forms designer itself.  This is shown in figure 5, where you can clearly see the different levels of all controls.

DocumentOutline

Figure 5. The document outline window in Visual Studio for a Windows Forms screen.

Defining the Basic Components

There is a lot of formal terminology in graph theory to contend with, but for our purposes, we only really need to be concerned with a few basic terms.

  • Tree – This refers to a collection of nodes connected by parent-child relationships in a hierarchical structure.
  • Parent – A node one level up from the current node.
  • Child – A node one level down from the current node.
  • Node – One item in a tree with an optional parent and zero or more children.
  • Root Node – A special node with no parent.  A tree can have only one root node.
  • Subtree – A section of a larger tree including the non-root node of a larger tree, plus all of its children.

That’s not so bad, is it?  In designing a reusable tree data structure, it’s important to establish a consistent and sensible pattern for semantics.  In fact, coming up with good names for the components of our data structure may be the most difficult part.  With poor identifiers, even simple structures can be confusing to those using it.

Begin with the End in Mind

I began with a quasi-test-driven development approach.  I asked myself how I’d like the end result to look when consuming the new data structure.  I knew from the start that a tree data structure that didn’t use generics wasn’t going to be very useful.  Imagine this code:

Tree ObjectTree;

What is the type of each node in the tree?  If I’m going to use this in different scenarios, the only answer is to make it an object, so that I could store whatever I liked in my tree, but this would require a lot of casting and a lack of type checking at compile type.  So instead, using generics, I could define something like this:

Tree <string> StringTree;

This is much better, and leads to two more steps that we’ll need to take conceptually.  The first one is that I will definitely want a tree of nodes for custom types in my software’s problem domain, perhaps Customer or MobileDevice objects.  Like strings, these objects are (for our purposes here) simply dumb containers of data in the sense that they are unaware of the tree structure in which they reside.  If we take this one level further, and consider custom types that are aware of their place within the tree (and can therefore particpate in much richer ways to compose hierarchical algorithms), we’ll need to consider how to make that awareness happen.  I will explain this in more detail later in this article.

public class Tree : TreeNode

{

    public Tree() { }

    public Tree(T RootValue)

    {

        Value = RootValue;

    }

}

This definition of Tree is really a matter of semantics and syntax preference.  I’m creating an alias for the TreeNode type, claiming that a Tree is a node itself—the root node in a Tree, by convention.  I call this a synonym type.  Here’s a very simple example of its use:

Tree<string> root = new Tree<string>();

root.Value = “zero”;

int d0 = zero.Depth;

TreeNode<string> one = zero.Children.Add(“one”);

int d1 = one.Depth;

TreeNode<string> twoa = one.Children.Add(“two-a”);

TreeNode<string> twob = one.Children.Add(“two-b”);

TreeNode<string> twoc = one.Children.Add(“two-c”);

string twocstr = twoc.Value;

int

d2 = two.Depth;

You can tell a few things by looking at this code:

  • The root node is defined as a Tree, but is manipulated like the other TreeNodes because it inherits from TreeNode.
  • Each node’s value is stored in a property called Value, which has a type of T (using generics).
  • A Depth property indicates how deeply in the tree the node is nested (the root has a depth of 0).
  • The Add method in the Children TreeNode collection returns a TreeNode object, making it easier to create a new node and get a handle to it in the same statement.

Connecting Nodes to Their Parents & Children

The intelligence needed to make a Tree work resides in two classes: TreeNode and TreeNodeList.  I could have used a standard collection type for TreeNodeList, but each TreeNode links to both Parent and Children nodes, which are two fundamentally different relationships; and I wanted parent and child nodes to connect and disconnect automatically behind-the-scenes—if you add a child to X, that child’s Parent property should automatically be set to X, and vice versa.  That requires hooking into the Add method in a custom collection class to manage those relationships.  TreeNodeList therefore looks like this:

public class TreeNodeList : List<TreeNode>

{

    public TreeNode Parent;

    public TreeNodeList(TreeNode Parent)

    {

        this.Parent = Parent;

    }

    public new TreeNode Add(TreeNode Node)

    {

        base.Add(Node);

        Node.Parent = Parent;

        return Node;

    }

    public TreeNode Add(T Value)

    {

        return Add(new TreeNode(Value));

    }

    public override string ToString()

    {

        return “Count=” + Count.ToString();

    }

}

The ToString override is very important for making your debugging sessions more manageable.  Without this kind of assistance, especially when troubleshooting recursive, hierarchical algorithms, you may go crazy digging through the debugger’s own tree view control to find what you’re looking for.

The Tree Node

The TreeNode itself gets a little tricky.  If you update the Parent property because a node is going to be moved to another part of the tree, for example, you want to make sure that it gets removed from the Parent’s list of Children, and you also want to add it as a child to the new Parent.  If the Parent was null, or is being set to null, then only one of those operations (remove or add) is necessary.

Here are the primary structural and payload-containing portions of this early version of the TreeNode class:

public class TreeNode : IDisposable

{

    private TreeNode _Parent;

    public TreeNode Parent

    {

        get { return _Parent; }

        set

        {

            if (value == _Parent)

            {

                return;

            }

            if (_Parent != null)

            {

                _Parent.Children.Remove(this);

            }

            if (value != null && !value.Children.Contains(this))

            {

                value.Children.Add(this);

            }

            _Parent = value;

        }

    }

    public TreeNode Root

    {

        get

        {

            //return (Parent == null) ? this : Parent.Root;

            TreeNode node = this;

            while (node.Parent != null)

            {

                node = node.Parent;

            }

            return node;

        }

    }

    private TreeNodeList _Children;

    public TreeNodeList Children

    {

        get { return _Children; }

        private set { _Children = value; }

    }

    private T _Value;

    public T Value

    {

        get { return _Value; }

        set

        {

            _Value = value;

            if (_Value != null && _Value is ITreeNodeAware)

            {

                (_Value as ITreeNodeAware).Node = this;

            }

        }

    }

}

There are two ways we could find the Root node.  The commented line shows a succinct way to walk the tree (recursively) toward successive parents until Parent is null.  The actual implementation being used shows another way, using a simple while loop.  I prefer this because in the event of debugging, it’s easy to step through a loop, and a little more difficult to jump through the same property on multiple, perhaps many, different instances of TreeNode.  I follow the same pattern for the Depth property (below).

A tree structure isn’t very useful, however, unless it can carry some kind of payload.  You want to build a tree of something, and it’s handy that we can use generics to tell the compiler that we want a Tree of strings (Tree), for example.  That’s what the Value property is for, and why its type is the generic type parameter T.

To instantiate and initialize TreeNodes, you’ll need some constructors.  Here are two of them I defined:

public TreeNode(T Value)

{

    this.Value = Value;

    Parent = null;

    Children = new TreeNodeList(this);

}

 

public TreeNode(T Value, TreeNode Parent)

{

    this.Value = Value;

    this.Parent = Parent;

    Children = new TreeNodeList(this);

}

The Tree Node Payload’s Awareness of its Place in the Tree

You probably noticed in the last section that the Value object is checked to see if it implements the ITreeNodeAware interface.  This is an optional extensibility mechanism for custom classes that need to be aware of the tree so that payload objects can read or manipulate it in some way.  In developing a data binding framework for Windows Forms that allows you to bind control properties to paths (“PurchaseOrder.Customer.Name”) instead of specific objects (PurchaseOrder.Customer, “Name”), as ASP.NET and WPF data binding works, I needed this ability and came to the conclusion that this would be a useful feature in general.  Later in the article, I will magically transform the TreeNode and TreeNodeList classes in such a way that both this interface and the Value property become unnecessary.

Until then, here’s how the interface looks with an example class that uses it.

public interface ITreeNodeAware

{

    TreeNode Node { get; set; }

}

public class Task : ITreeNodeAware<Task>

{

    public bool Complete = false;

    private TreeNode<Task> _Node;

    public TreeNode<Task> Node

    {

        get { return _Node; }

        set

        {

            _Node = value;

            // do something when the Node changes

            // if non-null, maybe we can do some setup

        }

    }

    // recursive

    public void MarkComplete()

    {

        // mark all children, and their children, etc., complete

        foreach (TreeNode<Task> ChildTreeNode in Node.Children)

        {

            ChildTreeNode.Value.MarkComplete();

        }

        // now that all decendents are complete, mark this task complete

        Complete = true;

    }

}

Using the ITreeNodeAware interface means we have another step to make in our implementation, and adds some complexity to its use in terms of discoverability and implementation of the interface by consumers of the Tree structure in creating custom payload classes.  By doing this, however, our Task objects will get injected with a Node property value when added to a Tree of Tasks.  So the payload object will point to the node via the Node property, and the Node will point to payload object via its Value property.  This is a lot of logic for such a simple relationship, but as we’ll see later, there is an elegant way around all of this.

Including Structure Helper Members

There are some common measurements of aspects of the tree’s nodes, as well as operations that you will typically want to perform on a tree or subtree, such as initialization, systematic traversal, pruning and grafting, disposal, and determination of depth, some of which I will discuss here.

Here is a property to determine your current nesting depth, which can be useful while debugging:

public int Depth

{

    get

    {

        //return (Parent == null ? -1 : Parent.Depth) + 1;

        int depth = 0;

        TreeNode node = this;

        while (node.Parent != null)

        {

            node = node.Parent;

            depth++;

        }

        return depth;

    }

}

Because the payload objects (referenced by the Value property) may require disposing, the tree nodes (and therefore the tree as a whole) is IDisposable.  Different trees of objects may require being disposed in different orders, so I’ve created a TreeTraversalType, a DisposeTraversal property of this type to specify the order, and have implemented the Dispose method that takes this into consideration.

public enum TreeTraversalType

{

    TopDown,

    BottomUp

}

private TreeTraversalType _DisposeTraversal = TreeTraversalType.BottomUp;

public TreeTraversalType DisposeTraversal

{

    get { return _DisposeTraversal; }

    set { _DisposeTraversal = value; }

}

Here is one way to implement IDisposable that includes a property indicating whether a node has been disposed, invokes a Disposing event, and traverses the tree according to the value of DisposeTraversal.

private bool _IsDisposed;

public bool IsDisposed

{

    get { return _IsDisposed; }

}

public void Dispose()

{

    CheckDisposed();

    OnDisposing();

    // clean up contained objects (in Value property)

    if (Value is IDisposable)

    {

        if (DisposeTraversal == TreeTraversalType.BottomUp)

        {

            foreach (TreeNode node in Children)

            {

                node.Dispose();

            }

        }

        (Value as IDisposable).Dispose();

        if (DisposeTraversal == TreeTraversalType.TopDown)

        {

            foreach (TreeNode node in Children)

            {

                node.Dispose();

            }

        }

    }

    _IsDisposed = true;

}

public event EventHandler Disposing;

protected void OnDisposing()

{

    if (Disposing != null)

    {

        Disposing(this, EventArgs.Empty);

    }

}

public void CheckDisposed()

{

    if (IsDisposed)

    {

        throw new ObjectDisposedException(GetType().Name);

    }

}

I overrode ToString in the TreeNodeList class above to display the count of children.  I do the same thing for TreeNode, which as I mentioned earlier aids a great deal in debugging.

public override string ToString()

{

    string Description = string.Empty;

    if (Value != null)

    {

        Description = “[“ + Value.ToString() + “] “;

    }

    return Description + “Depth=” + Depth.ToString() + “, Children=”

      + Children.Count.ToString();

}

Notice how the Value property, if it’s set, gets included in the ToString value.  If you’re looking at a TreeNode in the watch window, you’ll appreciate that your Value object can be represented without having to drill into anything.  You can see at a glance what the payload is, how deep it is in the tree, and how many child nodes it has.

The Role of Generics in Representing Payloads

I have already supplied enough logic and sample code for a fully functioning tree data structure for use in the .NET Framework, which incidentally was developed in a Compact Framework project and will therefore work in any .NET environment.  That being said, there are some syntactical inconveniences with the approach mentioned so far.  Consider the Tree example above in a scenario where we want to access a parent node’s payload from a current node:

TreeNode<Task> CurrentTaskNode = /* get current task node */;

bool IsComplete = CurrentTaskNode.Parent.Value.Complete;

Note that Parent doesn’t return our object of type T, but instead gives us a TreeNode; and our CurrentTaskNode object is also a node object and not a task object.  When we think about trees in theory, especially visually in the form of diagrams, the parent of a node is another node, meaning that parent and child are the same type of thing.  In our simple implementation so far, however, the parent of a task is not another task, but rather a task-tree-node, which is not the same thing.

If we start from a Task object instead of a TreeNode, the syntax is worse:

Task CurrentTask = /* get current task */;

bool IsComplete = CurrentTask.Node.Parent.Value.Complete;

Notice how each time we access Node or Value, we’re weaving in and out between types.  So we must manipulate this data structure and its payload all the while with explicit deference to the type disparity and dualism, and a careful naming of variables is important to avoid confusion between types (CurrentTaskNode vs. CurrentTask).  When I first had this realization, it occurred to me why a Tree data type may have been missing from the original .NET Framework.  I doubt very much that all the brilliant developers working on the base class libraries didn’t think to include such a useful structure, but perhaps the obvious implementations that came to mind seemed confusing and problematic for real-world use.

Fortunately, we now have capabilities in the CLR as of 2.0—and corresponding language features—that enable us to solve this problem elegantly.  I’m referring to generics, and more specifically, to generic constraints.

The simplifying idea is that by creating a payload class that inherits from TreeNode, and applying a simple generic constraint to get around some casting problems that would normally prevent us from compiling, we can make our final syntax look like this:

Task MakeDinner = new Task();

Task PrepareIngredients = MakeDinner.Children.Add(new Task());

Task CookMeal = MakeDinner.Children.Add(new Task());

Task PreheatOven = CookMeal.Children.Add(new Task());

Task BakeAt350 = CookMeal.Children.Add(new Task());

Task Cleanup = MakeDinner.Children.Add(new Task());

bool IsAllDone = BakeAt350.Parent.Parent.Complete;

Notice that in the final statement, we don’t have to navigate from BakeAt350 to some different type object through a Node property, and that we can go directly from Parent to the Complete property.  This is because our Task class is defined like this now:

public class Task : TreeNode<Task>

{

    public bool Complete = false;

 

    // recursive

    public void MarkComplete()

    {

        // mark all children, and their children, etc., complete

        foreach (Task Child in Children)

        {

            Child.MarkComplete();

        }

 

        // now that all decendents are complete, mark this task complete

        Complete = true;

    }

}

It’s been compressed!  The Node property is no longer necessary (since the task is-a node, instead of being contained-by a node), and therefore the ITreeNodeAware interface can also be dispensed with.  The MarkComplete method is different, too: we simply write Child.MarkComplete instead of Child.Value.MarkComplete, and we can loop through a collection of Task objects with the Children property directly, instead of going through a set of TreeNode objects in some external Node object.

In our consuming code above, we didn’t even have to mention the Tree or TreeNode type, but if we did declare a variable that way (for the sake of clarity), it would simply be a synonym of Task.  It would look like this:

Tree<Task> MakeDinner = new Tree<Task>();

We could use TreeNode as well; it makes no difference.  Task = Tree = TreeNode.

To make all of this magic happen, we need to define TreeNode with a generics constraint.

public class TreeNode : IDisposable where T : TreeNode

This tells the compiler that T must inherit from TreeNode, and therefore variables of type T are safe to manipulate as tree nodes.  TreeNodeList requires the same constraint:

public class TreeNodeList : List<TreeNode> where T : TreeNode

This breaks us out of a restrictive pattern where normally a custom collection class is unable to richly manipulate the objects within it (unless the collection is instantiated directly from consumer code, which is not the case in this pattern).  But because the collection class knows that all of its items will derive from TreeNode, it can manipulate them as tree nodes with no problem.

There is a price to pay for this convenience, however, which is that the tree is restricted to types that inherit from TreeNode.  This means that a Tree is no longer possible.  You will have to decide how you will likely use trees in your development to determine whether to design something like this into it.  If you want this cleaner syntax but still need trees of primitive and other non-TreeNode-derived types, you can create a distinct SimpleTree for this purpose.  It may even be possible for Tree to inherit from SimpleTree, hiding the Value property (with a private shadow method shown below) and adding the generic constraint.

Cleaning Up

Now that the basic functionality is in place, I decided to split the Tree class into two.  SimpleTree represents a simple tree data structure that can contain as its Value any object; and ComplexTree, which uses the generic constraint described above and supports more complex hierarchical algorithms and tree-aware nodes.  I really like the simplicity of the Tree name, but along with the need to support both simple and complex scenarios, there are two more reasons for this name-change decision.

First, in the System.Windows.Forms namespace, there is already a TreeNode class that corresponds to the TreeView control.  If I had designed that control, I probably would have named it VisualTree and its node VisualTreeNode to distinguish it from a logical node, but as it is, dealing with two different TreeNode classes, even in different namespaces, could be confusing and messy.  Second, the new Task Parallel Library (TPL) contains an implementation of a binary tree called Tree, which is a rather short-sighted name considering that all useful trees are not binary trees, as I’ve demonstrated in this article; BinaryTree would have been a much more appropriate name.  Hopefully by the time TPL is released, this identifier will be updated to reflect this.

Conclusion

Elegant implementations of tree data structures in .NET Framework, though problematic in the past, are finally possible with the introduction of generics and generic constraints.  With some careful syntax planning for consuming code, as well as experimentation with different language constructs, I hope I have shed some light on how these kinds of problems can be approached and solved.

In future articles, I will be exploring some techniques and specific uses for hierarchical algorithms.  Some of the very problems that appear too difficult to solve without a background in mathmatics can be much more easily understood and mastered by using tree data structures and associated visualization techniques.

[This is the first article in a series of intelligent data structures, which is continued here with KeyedList.]

Posted in Algorithms, Data Structures, Object Oriented Design, Problem Modeling, Software Architecture | 119 Comments »

Important Professional Skills for Software Architects

Posted by Dan Vanderboom on February 2, 2008

I was recently asked which professional skills were most important for a software architect, and the answers I came up with, I believe, apply to professionals in general.  Some of the following descriptions are slanted toward the software architect, but can be applied quite easily to other professions.

Customer advocacy.  First and foremost, we have an ethical obligation to our clients to discover and represent their best interests.  There are unscrupulous consultants who will milk contracts for as long as they can for their own financial survival, and this is a serious problem because it creates mistrust in our industry and problems for those who are honest.  As this problem may be outside of our immediate sphere of influence, I would also point out that even with the best intentions, those who are honest may not be serving the customer’s real needs due to hyperfocus on the detail and technology, and unfamiliarity with the requirements or lack of focus on business needs.  Some of this can only come with experience, but I believe we can all learn what our limitations are and to admit when we aren’t seeing enough of the big picture to make a confident recommendation.  This is an important focus of systems architecture organizations such as IASA and WWISA.  Dan Appleman in a recent Hanselminutes podcast episode covers this responsibility of the Software Architect very well.  I had the opportunity to meet Dan briefly at DevConnections, and consider him to be a great role model.

Articulate and organized written and verbal communication skills.  Communication skills are the glue that hold teams together and allow a single coherent vision of a project or product to be shared.  The most important of these skills is listening, or observation in general, as decisions can only be as good as the information they’re based on.  Communication skills can be further broken down for more intense self-examination and improvement: the ability to compose meaningful and relevant messages; delivery of those messages via writing, impromptu speaking, and prepared presentations all require different skills; and observance of social protocol to appear responsive, considerate, etc.  When I hear people saying that someone has “poor communication skills”, they are most often referring to a failure to observe social protocol, not that the person isn’t capable of composing and articulating their thoughts well.

Negotiation and conflict resolution.  Everything that involves communication contains the potential for conflict.  Knowing how to negotiate can prevent daily micro-conflcits from escalating out of control.  When we understand that conflict is normal and comes from the interaction of different perspectives, requiring a dynamic, shifting dance of give and take, we can embrace and work with it, using that energy and the diverse perspectives involved to our advantage, fueling our creative processes instead of letting them degenerate into unhealthy ego battles.

Problem-space modeling and creative problem solving.  The effectiveness of the solutions we put in place depend primarily on the way we view the problem.  Modeling a problem (seeing) is a very creative process, and the ability to be flexible and think outside the box when looking at a situation can lead to much simpler and more effective solutions.  Too often, designers assume the first model they imagine “is” the problem, instead of one of many ways to view it, and build their systems with this limiting and often dangerous assumption.  A willingness to play and refactor ideas, coming up with alternatives through brainstorming, and synthesizing conflicting approaches, all add to one’s repertoire of visualization techniques, and therefore problem-solving skills.

Risk identification and management.  Software development (as with business in general) involves a great deal of risk, with pitfalls around every corner.  Incorporating new tools, processes, and team members, solving problems in unfamiliar domains, company acquisitions, etc., can make a project miss schedule and budget targets.  Identifying the risks involved requires project experience and good observation skills.  Managing them requires organization and a proactive, prioritized approach, as well as planning for several alternatives and mitigations.  We start with awareness, then we identify, and finally we can manage and plan around them.

Critical thinking and analysis.  Complex software systems are designed and developed too frequently with a casual, shoot-from-the-hip mentality that endangers projects.  By thinking through issues with a critical and analytical approach, we can reduce risk substantially and ensure success.  The greatest barrier to proper critical thinking is impatience, the urge to jump to conclusions to avoid thought.  As David Allen says in Getting Things Done, “You have to think about your things more than you realize, but not as much as you’re afraid you might.”

Strategic (long-term) and tactical (short-term) project planning.  Short-sighted design and development, and lack of planning, leads to systems that are incapable of growing with or adapting to changing business needs.  Keeping long-term goals in mind ensures longevity and relevance.  This depends, of course, upon the resources and leadership of the company you’re working for.  You may be working on a project with a short lifetime, or your boss may not be persuaded to invest in strategic moves now to save time and money later.  But for most projects, development costs are too great to be wasted on short-sighted expediency.  In any case, long-term and short-term priorities and forces must be balanced against one another along the way.  Every decision and trade-off will have consequences down the line.

Continuous research on trends and technologies.  Long-term strategic planning can’t be effective without knowing the future state of the industry or its many technologies.  This is all about “knowing the territory” as Sun-Tzu has described in The Art of War.  We must often plan the future state of our software systems to take advantage of technologies that aren’t yet available.  This requires keeping ourselves in the loop and on top of our game at all times.  This is difficult in a world that is expanding exponentially, and often requires that we find a niche specialization both to differentiate ourselves and to provide more focused value.

Whereas a developer is concerned with doing things right and being efficient, an architect must focus on doing the right thing from a larger point of view.  As Peter Drucker writes, “Efficiency is doing things right; effectiveness is doing the right things.”  An architect must be effective.

Or as paraphrased by the VisualSVN tag line (quite brilliantly): “Right thing.  Done right.”

Couldn’t have said it better myself.

Posted in Goal Setting, Problem Modeling, Software Architecture | 1 Comment »

Code Clarity, Commenting, and Documentation for a Specific Purpose

Posted by Dan Vanderboom on February 2, 2008

I am currently transitioning from one job to another.  As such, I find myself looking through three and a half years of source code, and analyzing it from a perspective of needing to make sure that it’s maintainable for those who follow me.  One trend that I observe is the gradual decline of comments I’ve written over the years.  Not because I feel they are less important now than in the past, and certainly not because of laziness (I am very consistent and meticulous about my code).  As I will explain, the slimming down of comments isn’t necessarily a bad thing, and the number of comments isn’t directly related to the clarity of code.

It has to do with the mind set and skill level of the developer.  When I started my current job, I had been doing VB.NET development for a few years (after a succession of other languages), and C#—other than what I’d experimented with in MSDN magazines, and despite my experience with C and C++—was basically new to me.  I found myself commenting anything that was different from past language experiences, such as delegates and events (different syntactical style in VB.NET versus C#), or new design patterns or idioms that I learned or created.

Over time, familiarity with the language, the patterns being used, and the framework caused many of those comments to seem superfluous and redundant.  Things that once seemed odd—delegates, reflection, use of nested dictionaries, exception-handling patterns—have become so second-nature that comments describing them decreased in perceived value dramatically.  Add to that the fact that comments themselves are assets that need to be updated along with the code they reference, and the creation of unessential comments becomes something of a small burden to add to a rapidly-growing pile.

Up until now, when deciding whether to add a comment to a section of code, I’ve asked myself this question: if I were going to look at this code several months or years from now, what about it would be confusing at first glance?  This has led me to write clearer code, breaking operations that could appear on one line into several, and naming variables in the clearest way possible to indicate their role in whatever algorithm they appear.  This, I find, precludes the need for some of the comments I may have otherwise felt the need to write.  If we can write code in a way that is self-describing—making the best use of identifiers to do their job and identify purpose—then comments will often seem redundant.  (The purpose of a good comment is to clarify code, not to instruct a beginner on “how to program 101”.)

Coming up with good, accurate identifiers is an art in itself, and comes only through a great deal of experience, learning to describe the entity’s purpose instead of the implementation details whenever possible, being very specific instead of defining ambiguous methods like Process or DoWork.  Naming things consistently according to a unifying metaphor (or set of metaphors) also helps to clarify how all of the pieces fit into a coherent whole.  Above all, one must be willing to refactor and rename whenever it will enhance code clarity.

Not all comments can be obviated in this way, however.  Sometimes, algorithms are just plain hard, or the entities you’re working with are so abstract (such as manifests full of collections of cached reflection metadata) that comments are critical.  The need for comments in situations like this may be an indication that there is still an opportunity to refactor and make the purpose more clear, but since unoptimal solutions will always exist, and our opportunities to refactor are often limited by time, resources, and therefore other priorities, comments in these situations do serve a very useful purpose.

So without being irresponsible and leaving those who follow us with an undecipherable mess, while at the same time minimizing redundancy and unnecessary work, how can we come up with a code documentation strategy that makes sense?

First, I would consider the level at which code is commented.  There are comments we place above or to the right of a single statement, comments that describe a following block of code, and comments that appear on larger entities (such as methods and classes).  Method comments, whether XML or not, are a good place for defining the purpose and describing the strategy used.  If you feel that comments for every few lines of code creates unnecessary clutter, this may be a good place to provide some guidance.  With a little bit of contextual information, it is much easier to figure out how each line participates in the method’s strategy, and class-level comments can describe how that class fits within a larger design pattern.

Second, if you find yourself continuously copying and pasting comments because you keep reusing the same pattern or idiom that would, perhaps, be unobvious to outsiders, then you have an opportunity to consolidate those comments into your software solution’s design documentation.  I have discovered and identified fourty- or fifty-some patterns that I’ve used consistently throughout my current software system; and this list, along with descriptions, should serve as good prerequisite reading and background information for future developers, along with several diagrams of complicated interactions and dependencies.  If we as object-oriented developers value code reuse, then we should embrace comment reuse as well, and consolidate this knowledge in a place outside of our code base.  Having and updating this list can also serve as a reminder of the strategic level of your coding patterns, and give your software a more tangible form of stylistic identity.

Third, identify the purpose of comments and your target audience.  If you’re developing a system in-house, working on a commercial software system, or building a development library that you deliver with source code (or XML comments supplied for Intellisense), you will have different sets of eyes and different perspectives to consider.  Is the project huge and convoluted, or small and simple?  Sometimes the simple question of “could I understand it later?” is too short-sighted.  Coming up with a set of principles to follow will make all of your individual documentation decisions much easier.  Just as comments are used to indicate the purpose of your code, identifying the purpose of your comments is the surest way to a sensible documentation strategy.

Posted in Documentation, Object Oriented Design, Software Architecture | 1 Comment »

The Architecture Journal: Mobile Architecture

Posted by Dan Vanderboom on January 14, 2008

One of my favorite journals is The Architecture Journal: Input for Better Outcomes, published by Microsoft.  I can usually count on it for in-depth, high-level articles about current technologies and design practices, and I was excited to see an issue devoted to one of my favorite topics: mobile architecture.  Although it now requires a Live ID registration, it’s free, and I highly recommend that you take advantage of it.  In fact, you should even go back and read the old issues.  (There’s a cool beta of a reader for this journal that you can download here.)

That being said, I have to admit I’m rather disappointed with this particular issue.  Though I understand that not all mobile solutions will run on Windows CE or Windows Mobile devices, that UMPCs and tablets are considered part of the same market, still… broad remarks are made that don’t even hint at current limitations in the technology—information that architects considering mobile projects would find useful to know.

For example, the first article advocates the use of Microsoft Synchronization Services (“which lets application developers easily add synchronization…”), but fails to mention that it doesn’t support Windows CE or Windows Mobile at all (and who knows when it ever will, or how crippled it will be when it is finally supported?).

The article on extending enterprise applications to mobile devices touched on most of the same issues that I’ve run into over the past several years, but is so narrowly focused on a singular strategy and implementation that I felt it failed to present a more useful, and more abstract, treatment of the issues that could be appreciated and applied in vastly different scenarios.  The long lists of best practices such as “use database stored procedures to write wrapper code for faster data access” represents, I believe, one philosophy of data management in general, and is not wholly relevant to the topic of mobility and its specific ramifications.  What of the update statement that gets executed only a dozen times daily: will 20 milliseconds of faster execution time be worth the accumulated hours of maintenance and updating of those extra database objects as the product evolves?  How many development assets do you want to manage, if you can use an ORM solution like LINQ without incurring that overhead?

Likewise, recommendations to include a history table for every regular table, where you do only inserts and never updates based on triggers, begs the question of “where the hell do you get all of this storage space on your mobile devices that you can be so wasteful?”  You’re really going to make a copy of records from multiple tables when a single row in one of the table is updated in any way?  Every time?

While the article on Test Driven Development and Continuous Integration for Mobile Applications was one of my favorites (the other being an article on automotive applications), the author mentions his open source project wMobinium.net which provides automated testing for mobile devices.  Is this solution necessary now that Visual Studio 2008 supports automated tests for mobile devices?  Isn’t this guy rather late in announcing this project?  (I don’t know, as I’ve only toyed with VS2008’s mobile testing a little and am not aware of its shortcomings.)  He also mentions his appreciation for the release of Compact Framework v2.0, so either this article was written a while back (and is now stale), or this guy doesn’t realize that v3.5 has been out for a couple months now, with betas and CTPs going further back.

When I read an architecture journal, I expect deep, insightful, relevant, up-to-date material by those who preferably have implemented more than one system, and have learned valuable lessons in different contexts that they want to distill into wisdom and share with the community.  Where I have been impressed with past issues, I believe this one has fallen short.  Maybe I’m extra-critical because of my familiarity with the subject.  You be the judge.

But I still look forward to the next issue.  And it encourages me to start jotting down some ideas for future articles of my own.  What are the real gotchas in mobile development?  If we had a map of these pitfalls, and the corresponding opportunities…

To be continued.

Posted in Compact Framework, Problem Modeling, Software Architecture, Windows Mobile | Leave a Comment »

Project: Code-Named “SQL Mobile Bridge”

Posted by Dan Vanderboom on December 26, 2007

SQLMobileBridge

This is not the final name.  But it will be a useful product.  With as much as I’ve been working with rapidly-evolving mobile database schemas lately, I expect to save from 30 minutes to an hour a day in my frequent build-deploy-test cycles.  The lack of a good tool for mobile device database queries causes me a lot of grief.  I know Visual Studio 2008 has something built-in to connect to mobile devices over ActiveSync, but let’s face it: ActiveSync has been a real pain in the arse, and more often fails than works (my next blog will detail some of those errors).  I can only connect to one device at a time, and I lose that connection frequently (meanwhile, SOTI Pocket Controller continues to work and communicate effectively).  Plus I have a window constantly bugging me to create an ActiveSync association.

I work on enteprise systems using sometimes hundreds of Windows Mobile devices on a network.  So I don’t want to create an association on each one of those, and getting ActiveSync to work over wireless requires an association, as far as I know.

Pocket Controller or other screen-sharing tools can be used to view the mobile device, and run Query Analyzer in QVGA from the desktop, but my queries get big and ugly, and even the normal-looking ones don’t fit very well on such as small screen.  Plus Query Analyzer on PDAs is very sparse, with few of the features that most of us have grown accustomed to in our tools.  Is Pocket Query Analyzer where you want to be doing some hardcore query building or troubleshooting?

So what would a convenient, time-saving, full-featured mobile database query tool look like?  How could it save us time?  First, all of the basics would have to be there.  Loading and saving query files, syntax color coding, executing queries, and displaying the response in a familiar “Query Analyzer”/”Management Studio” UI design.  I want to highlight a few lines of SQL and press F5 to run it, and I expect others have that instinct as well.  I also want to be able to view connected devices, and to use several tabs for queries, and to know exactly which device and database the active query window corresponds to.  No hunting and searching for this information.  It should also have the ability to easily write new providers for different database engines (or different versions of them).

Second, integration.  It should integrate into my development environments, Visual Studio 2005 & 2008.  It should also give an integrated list of databases, working with normal SQL Server databases as well as mobile servers.  If we have a nice extensible tool for querying our data, why limit it to Windows Mobile databases?

Sometimes it’s the little details, the micro-behaviors and features, the nuances of the API and data model, that defines the style and usefulness of a product.  I’ve been paying a lot of attention to these little gestures, features, and semantics, and I’m aiming for a very smooth experience.  I’m curious to know what happens when we remove all the unnecessary friction in our development workflows (when our brains are free to define solutions as fast as we can envision them).

Third, an appreciation for and focus on performance.  Instead of waiting for the entire result to return before marshalling the data back to the client, why not stream it across as it’s read? — several rows at a time.  Users could get nearly instantaneous feedback to their queries, even if the query takes a while to come fully across the wire.  Binary serialization should be used for best performance, and is on the roadmap, but that’s coming after v1.0, after I decide to build vs. buy that piece.

Finally, a highly-extensible architecture that creates the opportunity for additional functionality (and therefore product longevity).  The most exciting part of this project is probably not the query tool itself, but the Device Explorer window, the auto-discovering composite assets it visualizes, and the ability to remotely fetch asset objects and execute commands on them.

The Device identifies (broadcasts) itself and can be interrogated for its assets, which are hierarchically composed to represent what is visualized as an asset tree.  One Device might have some Database assets and some Folder and File assets.  The Database assets will contain a collection of Table assets, which will contain DatabaseRow and DatabaseColumn assets, etc.  In this way, the whole inventory of objects on the device that can be interrogated, discovered, and manipulated in a standard way that makes inherent sense to the human brain.  RegistryEntry, VideoCamera, whatever you want a handle to.

This involves writing “wrapper” classes (facades or proxies) for each kind of asset, along with the code to manipualte it locally.  Because the asset classes are proxies or pointers to the actual thing, and because they inherit from a base class that handles serialization, persistence, data binding, etc., they automatically support being remoted across the network, from any node to any other node.  Asset objects are retrieved in a lazy-load fashion: when a client interrogates the device, it actually interrogates the Device object.  From there it can request child assets, which may fetch them from the remote device at that time, or use its locally-cached copies.  If a client already knows about a remote asset, it can connect to and manipulate it directly (as long as the remote device is online).

With a remoting framework that makes shuffling objects around natural, much less message parsing and interpretation code needs to be written.  Normal validation and replication collision logic can be written in the same classes that define the persistent schema.

So what about services?  Where are the protocols defined?  Assets and Services have an orthagonal relationship, so I think that Services should still exist as Service classes, but each service could provide a set of extension methods to extend the Asset classes.  That way, if you add a reference to ServiceX, you will have the ability to access a member Asset.ServiceXMember (like Device.Databases, which would call a method in MobileQueryService).  If this works out the way I expect, this will be my first real use of extension methods.  (I have ideas to extend string and other simple classes for parsing, etc., of course, but not as an extension to something else I own the code for.)  In the linguistic way that I’m using to visualize this: Services = Verbs, Assets = Nouns.  Extension methods are the sticky tape between Nouns and Verbs.

public static AssetCollection<Database> Databases(this Device device) { }

With an ability to effortlessly and remotely drill into the assets in a mobile device (or any computer, for that matter), and the ability to manipulate them through a simple object model, I expect to be a significantly productive platform on which to build.  Commands executed against those assets could be scripted for automatic software updates, they could be queued for guaranteed delivery, or they could be supplemented with new commands in plug-in modules that aid in debugging, diagnostics, runtime statistics gathering, monitoring, synchronizing the device time with a server, capturing video or images, delivering software updates, etc.

And if the collection of assets can grow, so can UI components such as context menu items, document windows, and so on, extending and adding to the usefulness of the Device Explorer window.  By defining UI components as UserControls and defining my own Command invocation mechanism, they can be hosted in Visual Studio or used outside of that with just a few adjustments.

More details to come.

Posted in Compact Framework, Linguistics, My Software, Object Oriented Design, Problem Modeling, Software Architecture, SQL Server Compact, User Interface Design | Leave a Comment »

Extreme Development Efficiency

Posted by Dan Vanderboom on December 20, 2007

I feel this overwhelming need to be a highly productive and efficient developer through constant attention and continuous improvement to the processes, techniques, and tools that I use.  Whenever there are bottlenecks in the process, frustrations and annoyances with the tools, or intuitive discomfort with the techniques and patterns that I’m using, I seek to eliminate the largest obstacle in my path to approach perfect fluidity and rapid development.

It’s important to move the big boulders first before filling in with smaller rocks and pebbles.  The big boulders: defining the right goals, collecting the right requirements, solving the right problems, and using the right processes.  If you’re heading in the wrong direction, it doesn’t really matter how fast you’re going.  Misunderstand your customer’s needs, and your chosen programming language won’t mean diddly squat.  The medium-sized rocks: applying the right design patterns and using the right tools for the job.  You can accomplish more with the right 100 lines of code than you can with 2000 lines of a rushed, poorly planned mess that will require constant maintenance and an eventual rewrite.  The small pebbles get really specific.  They may involve using code snippets or IDE plug-ins to more rapidly configure or develop projects, altering your workflow to circumvent predictable social distractions, standardizing on naming conventions, and so on.

I’ve spent a great deal of time studying architecture, design, and agile processes, and I admit that I’m constantly learning new things in these areas.  These things fascinate and stimulate me.  But I’ve been writing code for 24 years (starting with Apple 2 Basic), and I’ve developed an intuitive feel for how to write code, formulate complex algorithms, and design components and their interactions.  Explaining these concepts and techniques to less experienced developers, even with the vocabulary that I’ve acquired over the past few years on these topics, proves to be a great challenge.

But the small pebbles, the little tweaks of efficiency that I make to shave 5 to 10 minutes off each day, are easier to explain, much like the end game is easier to teach a beginner of chess than the middle or beginning game.  It’s more tactical, and more tangible, because it’s easier to measure and demonstrate.

It also offers a less competitive market to produce tools for, as these optimizations tend to be very specific to the technologies and tools, as well as the developers who use them.

So I’ve spent a lot of effort recently reducing build times, optimizing data synchronization strategies, applying multithreading to minimize application startup times, and developing some tools to improve development speed and reduce risk and errors.  One purpose of these efforts is to attain greater performance in the applications and systems that I build.  The end users will appreciate this effort, but there’s a selfish aim here as well: if I can speed things up to the point where I’m saving 10 minutes a day here, 15 minutes a day there, and more or less in other areas, I can easily recoup an hour or two a day that I would normally spend waiting around for a build to complete, an application to start up, or a query to run.  Per developer.

Development time is very expensive.  If we can minimize the time spent waiting around for things to happen (which is boring anyways), and maximize our productivity (which is exciting and satisfying), everyone will be happier in the end.  Developers will crank out new features and products quicker and customers will get their needed functionality sooner.

On the other hand, I’ve made a number of decisions to trade application performance for developer productivity.  My priority is usually to create correctly functioning software first, not with complete disregard to performance, but with performance considerations not automatically being at the forefront.  If the code is 20% slower than it could be, but the development team can refactor and extend the solution 250% faster, sometimes that trade-off is worthwhile.  And I’ve programmed in assembly language, so I’m familiar with the attitude that we have to preserve every byte, and reduce every unnecessary processing cycle we can to get the most out of the hardware.  It’s just not sensible to think this way anymore (except for very specialized functions or embedded systems).

Just as our perspective of hardware and software systems has matured to include concepts like total cost of ownership (TCO) once the system has been deployed into production, so too must we consider all of the ramifications of software design and performance on developer productivity and the flexibility of product evolution, and therefore the total cost of development.  If it’s cheap to build, it might be expensive to support.  In the end, we’ll have to pay for it one way or another.  We need to think about more than what it will cost us now.  What design and process decisions will minimize the cost over the entire lifetime of our products?

Posted in Software Architecture | Leave a Comment »

Multithreaded Design: Dedicated Task Threads or Bucket Brigade Strategy?

Posted by Dan Vanderboom on December 17, 2007

A few days ago, I took a dive into building a new software product.  It’s aim is mobile developers, such as myself, whose applications access databases on those mobile devices.  After six weeks of development, v1.0 will be released (by the end of January, 2008).  More details on that product to come later.

One of my goals is that its user interface should be very responsive.  When commands take a while to complete, they’ll need to execute on some other thread.  It’s a .NET Framework application, and in that environment, only one thread can update the user interface, so it’s a rare resource that needs to be protected from doing too much work that doesn’t fit that primary purpose.

I’ve written a fair amount of multithreaded code in the past.  Working with RFID hardware before the “Gen 2” standard, on pre-release Symbol (now Motorola) devices, I figured out how to integrate with the RFID radio at a low level, and only by using several threads was I able to obtain acceptable performance.  After wrestling with the issues like race conditions, deadlocks, and other complexities, I have a healthy respect for the amount of planning that’s required to make it work correctly.

My new product consists of three major layers: a user interface layer, a service layer, and a network communication layer.  The Command pattern will be used to publish and service commands.  Actions in the user interface will enqueue command objects to the service layer, where they’ll either be processed immediately or passed to another node in the network for processing remotely.

A simplification of this scenario is illustrated in the sequence diagram below.  Each color represents a separate thread.

DataService multithreaded sequence

The red user interface thread does minimal work.  When it calls the DataServiceProxy to request data, a command object is enqueued and the thread is allowed to return immediately to the user interface.  The blue line represents one thread in a larger pool of worker threads that grows or shrinks depending on the command queue size, and is dedicated to processing these commands.  In this example, the DataServiceProxy makes a call to the TCPConnection object and returns back to the pool.  When a message does arrive, this happens on a thread owned by the TCPConnection object.  Because we don’t want this thread to “get lost” and therefore be unavailable to process more TCPConnection logic, we enqueue a response object and return control immediately.  Finally, the DataServiceProxy object, using one of its threads, fires a MessageReceived event, which in turn calls Invoke so that it can update the user interface on the only thread that is capable of doing so.

I like using Sequence diagrams like this to plan multithreaded work.  It clears up issues that you wouldn’t normally be able to visualize clearly.  The first (and worst) mistake would be to allow the UI thread to cross all the way through to the TCPConnection object, making some blocking call while the network connection times out, throws an exception, handles the exception, etc.  Meanwhile, the user is waiting until they can interact with the screen again, waiting for the hourglass to go away so they can get on with their work.  By assigning specific roles to threads, and creating mechanisms by which threads can be kept within specific boundaries, their behavior is easier to predict and manage.

I don’t know a lot about how ThreadPools behave, but I’m going to be looking into that in detail over the next few weeks, and if I come across anything particularly noteworthy, I’ll write about it.  My instinct is to continue to use this pattern of thread role assignment, especially for my new product, but there’s another pattern I’ve been thinking about that may also work well.  A friend of mine at Bucketworks mentioned to me a while back about the efficiency of bucket brigades, and about how intensely they’ve been studied and found to create self-organizing and automatically-optimizing lines of workers.

Each Thread Is A Worker

The way I’ve been modeling thread work, I treat each thread like a worker: the UI worker hands off a job description to a DataServiceProxy worker, who then does something with it and passes it off to a TCPConnection worker, who in turn does some work with it and hands it off (over a network in that case).  So what happens when the scenario becomes more complicated than the simple sequence diagram above?  What if I have four or five hand-offs?  Is the assignment of specific threads to specific roles really the best use of those threads?  The UI thread is stuck, but the rest of them could technically move around.  Perhaps they’re devoted to one task at a time, but when a task is completed with nothing in that queue, could the worker thread be moved to perform another task?  So I started thinking about how a bucket brigade strategy may help.

Threads aren’t exactly like people workers, so I have to be careful about the analogy.  It’s probably no big deal processing-wise for threads to be sleeping if they’re not used, but each thread does consume some memory, and there must be some kind of overhead to deallocate and reallocate their thread-local resources.  Would it be better to share a single thread pool among a connected linkage of worker objects, or for each service object to allocate its own thread pool?

Will this work?  Bucket brigades tend to work best when the density of work is high and the amount of time to complete a task is relatively small and constant.  If a task takes too long to complete, the line can more easily become unbalanced.  I’m going to be thinking more about this possibility, and come up with some objective measurements that I can use to compare the approaches and determine when this would be appropriate in a thread-management strategy (if at all).

Bucket Brigades In Business

If you want some background on bucket brigades and their use in manufacturing and assembly lines, check out this paper by John Bartholdi and Donald Eisenstein.  They explain how expensive time-motion studies are done to balance assembly lines in large organizations to maximize throughput, and how this needs to be adjusted or redone when the length or configuration of work changes, or when worker productivity varies.  With bucket brigades, however, there’s less need for planning because the strategy “spontaneously generates the optimal division of work”.  Pretty neat stuff.

The list of companies using bucket brigades is impressive: McGraw-Hill, Subway (yes, the sandwich company), Readers Digest, Ford Customer Service Division, The Gap, Walgreen’s, Radio Shack, etc.

If anyone’s using this kind of strategy to manage work in software systems, I’d love to hear about it.

Posted in My Software, Object Oriented Design, Problem Modeling, Software Architecture, SQL Server Compact, User Interface Design | 1 Comment »