Oslo: Misconceptions and Fallacies

In the many conversations and debates I’ve had about Oslo recently–in person, on the phone, through email, on blogs, and in the Oslo forum–I’ve encountered a good amount of resistance to the goals of Oslo.  Some of this is due to misconception and general confusion, some is due to an attachment to one’s current methodology, and some I believe is simply due to a fear of anything new and unknown.  In the course of these conversations, I’ve run across a common set of thoughts or themes which I have attempted to represent faithfully here.

My first article, Why Oslo is Important, attempted to elucidate the high-level collection of concepts, technologies, and tools flying under the Oslo banner as it exists today and how I imagine it evolving in the future.  Though I’ve received a lot of interest and appreciation, it also managed to spark some feedback from those who were still confused or concerned, leading me to believe that I had failed to deliver a fully satisfying explanation.

Understandably, Oslo and its target domain are too large to explain or digest in a single article, even a long one.  It’s also too early in the development cycle to be very specific.  So it’s reasonable to suggest that one can’t be totally satisfied until substantial examples and reference applications are built using the Oslo tools.  Fair enough.

This article isn’t going to provide that reference application.  It has the more modest goal of trying to dispel some of the common misconceptions and fallacies that I’ve encountered, and my responses to them.  In future articles, as I design and develop my newest software system, I’ll be documenting and publishing the how and why of my use of Oslo tools and technologies to provide more specific evidence of its usefulness.  I’ll also be providing references to much of the good work that is being done to provide solutions to various problems.

As always, I encourage you to participate and provide feedback: to me, and especially to the Oslo team.  The more brain power we can bring to bear on this problem in the community, the better off the Oslo team will be, and the faster Oslo will evolve to become precisely the set of tools we need to improve our overall development experience, and developer productivity in particular.

“Oslo doesn’t solve any problems that can’t already be solved with existing tools or technologies.”

When the first steam-powered tractors were sold to farmers in the 1860’s, traditional ox and horse farmers might have said the same thing.  “This tractor won’t do anything that my ox-plowing method can’t already do.”  This is true, but it’s not an effective argument against the use of the new technology, which was a much faster and more cost-effective method of farming.  The same farmer could harvest much more of his crop in the same amount of time, and as the new technology matured and gas-powered engines became available (in the 1880’s), so did the benefit increase.  The same goes for any high level language above assembly language, the use of a relational database over a loose collection of files, display of text on a CRT instead of punched tape to communicate with a user, or any other great technological leap forward that “doesn’t accomplish anything new”.

Then again, it all depends what kind of problems you’re talking about.  If you get specific enough, I’m sure you’ll find plenty in Oslo that’s new, even so early in its development, such as a shared repository for interoperable models and the ability to define new parsers that provide tooling support such as keyword colorization.  Sometimes it’s these little details that act as the glue to pull components together and create substantial value through the synergy that results.  Visual Studio and Intellisense weren’t strictly needed (you can still use Notepad and cs.exe), but it can quickly answer dozens of questions a day without having to jump out of context and spend a lot of time looking through disconnected documentation.

“We don’t need to know about Oslo or model-driven development because the applications I build are small and specific, or otherwise don’t need to be so general and flexible.”

This may or may not be true for you, but saying that the industry doesn’t need to advance because you don’t perceive a direct benefit to your own development isn’t valid.  The reason your applications are able to be so simple is because of the wealth of tools, languages, platforms, frameworks, and libraries that your applications leverage.  Standing on the shoulder of giants, you might say.

Many of these systems and components can benefit tremendously from a model-driven approach, and if it improves productivity for Microsoft and other third-party developers, that means they’ll be able to spend less time on plumbing and more time building the framework features you care about.  It’s also likely to make all of those APIs cleaner and more consistent, resulting in easier discoverability and fewer headaches for you, the API consumer.  As the .NET Framework and other frameworks and libraries grow ever larger, this will be critical to keeping things organized and under control.

“Oslo is going to force me to model all kinds of things that really aren’t needed in my software.”

The existence of Oslo will not force you to model any characteristics that you aren’t already modeling through other means.  What it will do is provide more options and tools for modeling your software more effectively and more productively.  It will also significantly ease the burden of creating more heavily model-driven software if you decide that’s right for your application or service.

For more information and a clearer definition of what a model is, see this article on the MSDN Oslo Development Center.

“Oslo will impose a workflow on me that doesn’t make sense for my methodology or business.”

Where Oslo fits into your specific workflow will be ultimately determined by you.  This isn’t any different from Entity Framework.  In v1 of EF, the tooling supports the reading of database structure and the generation of entity classes, but there is work being done to support a workflow going in the other direction: that of starting with classes and generating the database.  The Entity Framework itself doesn’t actually care in which direction you want to work; the issue is primarily one of tool support.  Other initiatives such as adding support for POCO indicate that the EF team is listening to feedback from the community and making the necessary changes to achieve broad support of their framework.  I would expect the same from the Oslo team.

Early releases of Oslo will have similar limitations; currently it seems that M can only be used to generate a database structure from MSchema, and that database structure can be read by Entity Framework to generate your entity classes.  Because Microsoft has such a broad audience to satisfy, other workflows will have to be accommodated, such as starting with class files and generating M files and database schemas.  In fact, I’ve submitted feedback to Microsoft’s Connect site to ensure this kind of multi-master synchronization of model representations is considered.

“Putting everything in a database is overkill for my application, so Oslo isn’t relevant to me.”

While the Repository is an important aspect of Oslo, it isn’t required.  Command line tools exist to transform textual input (specified as MGraph, or in your own custom-defined format using a Domain Specific Language) into MGraph output.  There is a separate step to convert this into SQL, or to optionally inject this data directly into the Oslo Repository.

If you don’t want to use the Repository, there are already multiple methods available for instantiating objects directly from this text data, whether it’s read from a file, embedded as a resource, or sent as data over a network.  Josh Williams (SpankyJ) has published an example showing how to convert DSL text into XAML, and instantiate the object graph using an MGraphXamlReader, and Torkel Ödegaard of Coding Instinct wrote an article demonstrating how to write a generic deserializer without using XAML.

Model formats such as CSDL, MSL, and SSDL for EF, or configuration data currently specified for WCF and WF, will all very likely be expressed in some DSL specified with M (there has been talk about these efforts already).  Since applications without database access will need these technologies, it will be impossible to force developers to read this model data from a SQL Server database.

“We already have XML, XSD, and XSLT, so there’s no benefit to having yet another language to specify the same things.”

XSD is used to define formats and languages (such as XAML), and XML is used as a poor man’s one-size-fits-all meta-format for specifying hierarchical data.  While XML is friendly enough to open in text editors, it’s designed more for tools than for human eyes.

Having different languages and formats to represent different kinds of data actually eases human comprehension and authoring ability.  As Chris Anderson said in his Oslo session at PDC, when you’re looking at XML in an editor, what stands out are not what’s important to your domain, but rather what’s important to XML: elements and attributes.

People are using XML to define their DSLs and formats, not because XML is the best representation, but because writing parsers for new formats and languages is just too hard.  Customers had been asking Microsoft for the ability to write these DSLs easily, so it was out of conversations and customer feedback that Microsoft decided to expose these services.

So it’s not a matter of absolutely needing M and the ability to define new languages because of some inability to get work done without them.  Rather, it’s about reducing the amount of mental work required to author our models and increasing our productivity as a result.  It’s also about having powerful transformational tools available to convert all formats and languages into a common representation so that the models can all interoperate despite their differences, in the same way that .NET languages all compile to a common CIL/MSIL language so that many different programming languages can interoperate.  Without this ability, we’d have a different community of developers for each language instead of one broad group of “.NET developers” who can all share and benefit from each other’s knowledge and libraries.  This has been recognized as such an important advantage that there are efforts underway to compile languages other than Java to JVM byte cote.

The larger the community, the larger our collective pool of knowledge, and the greater reuse we actually achieve.

“Oslo is too general and abstract to be useful to real developers building real systems.”

The idea that generalization can get out of control for a specific problem is valid, in the same way that a problem can be over-analyzed.  But that doesn’t mean that we should stigmatize all general-purpose software, or that we should ignore the growing trend for enterprise software systems to require greater flexibility, user customization support, extensibility, and so on.

The fact is that life on Earth evolves towards greater complexity, and as supporting hardware resources increase and business demands grow, so does software.  Taming that complexity will require rethinking how we approach every aspect of software design and development, including how to model it.

The software development industry is stratified into many layers, from platform development to one-off, command-line utilities.  Some organizations write software to support millions of users, while others deploy specialized applications in-house, but most of us fall somewhere in between.  Oslo seems to be most applicable to enterprise software offered to many customers, including cloud services, but there are subsets of Oslo that will have an impact on a great majority of .NET developers sooner or later.

There’s a lot of thought and work that goes on in our world (and billions of dollars spent) on “pure research” in the sciences (including computer science) that isn’t directly applicable to every John Doe, but without which we wouldn’t have things like nuclear power plants, microwaves, radio, television, satellite communication, or many pharmaceuticals.  The Nobel laureates of the world who have spent their lives studying something so abstract and remote from every day life have contributed massively to the technological progress of our world, and quite often contribute to a better, more sanitary, healthy, and productive society.  Despite the risks and dangers each technology enables, we somehow still make steady progress in terms of reducing chaos and violence.

Without abstract and general technology like general purpose language compilers, which can specify any logic we dream up for any type of application we care to build, we’d be back in the stone age.  The Internet itself is based on communication standards that are so general, they are applicable to any application protocol or service traffic we can devise.

So before dismissing software (or any technology) due to its abstract or general nature, think about where we’d be without them.  Someone has to approach the colossal, abstract, general problems with enough foresight to deliver solutions before they’re too desperately needed; and who better than a huge organization like Microsoft with deep pockets?

Ironically, our ability to define Domain Specific Languages with Oslo give us the converse power: the ability to define languages and formats that are extremely specific to our purposes and problem domains, and therefore enable us to write our specifications with less ceremony and noise that accompanies a general purpose language.  This allows us to specify our intentions more easily by saying only what we need to say to get the point across.  So the only reason Oslo must be so general is to provide that interoperability and translation layer across a set of specific formats that we define… without us having to work so hard for it.

For different reasons, it reminds me of generics, another general and abstract tool: it’s a complicated feature to implement in a language, but it provides great expressive power.  Generics also don’t provide anything we couldn’t manage to do before in other ways, but I certainly wouldn’t want to go back to programming without them!  In fact, you might say it’s an effective modeling tool.

Why Oslo is Important

Contrary to common misunderstanding and speculation, the point of Oslo is not to put programming in the hands of business analysts who want to write their own business rules.  Do I think some of that will happen?  Architects and engineers will try everything they can imagine.  Some of them will succeed in specific niches or scenarios, but it won’t replace application or system design, and it will probably be very limited for the forseeable future.  Oslo is more about dramatically improving the productivity of designers and developers by generalizing common solution patterns and generating more adaptable tools.

Much of the confusion around Oslo occurs for two reasons:

1. Oslo is designed at a higher level of abstraction than most systems today, so its scope is broad and it will have an impact on virtually every product, solution and service across Microsoft.  It’s difficult to get your head around something that big.
2. Because of its abstract nature, core concepts are defined in terms that are heavily overloaded, like "Model", "Repository", and "Language".  Once you’ve picked up the lingo and can translate Oslo terminology into language you’re already familiar with, both the concept and magnitude of it will become obvious.

Oslo isn’t something completely new; in fact, Oslo borrows from a lot of previous research and even existing model-driven development tools.  Oslo focuses existing technologies and techniques into a coherent and mature vision of development, combining all parts into a more powerful whole, and promises to deliver a supremely adaptable and efficient platform to develop on.

What Is Oslo?

Oslo is a software factory for generating first-class, tool-supported languages out of your declarative specifications.

A factory is a highly organized production facility
that produces members of a product line
using standardized parts, tools and production processes.

-from a review of Software Factories

The product line is analogous to Oslo’s parsers, transform tools, and IDE plugins for new data models and languages (both textual and visual) that you define.  The standardized parts are Oslo’s library components; the tools are the M languages and the Quadrant/Intellipad application; and the processes are shaped by the flow of data through the Oslo tool chain (see the diagram near the end of this article).

With Oslo, you build the custom tools you need to rapidly build or generate software systems.  It’s all about using the right tool for the job, and having a say in how those tools are shaped to obtain the greatest leverage.

As stated at the home page of softwarefactories.com:

We see a capacity crisis looming. The industry continues to hand-stitch applications distributed over multiple platforms housed by multiple businesses located around the planet, automating business processes like health insurance claim processing and international currency arbitrage, using strings, integers and line by line conditional logic. Most developers build every application as though it is the first of its kind anywhere.

In other words, there’s already a huge shortage of experienced, highly-qualified professionals capable of ensuring the success of these increasingly complex systems, and with the need (and complexity) growing exponentially, our current development practices increasingly fall short of the total demand.

Books like Greenfield’s Software Factories have been advocating building at a higher level of abstraction for years, and my initial reaction was to see it as a natural, evolutionary milestone for a highly mature software system.  However, it’s an awful lot of focused development effort to attain such a level of maturity, and not many organizations are able to pull it off given the state of our current development platforms.

It’s therefore fortuitous that Microsoft teams have taken up the challenge of building these abilities into their .NET platform.  After all, that’s where it really belongs: in the framework.

Unexpected Awesomeness

Oslo of course contains a lot of expected awesomeness, but where it will probably have the most impact in terms of developer productivity is with new first-class languages and language tools.  Why?  It first helps to understand the world of data formats and languages.

We’ve had an explosion of data formats–these mini Domain Specific Languages, if you will (especially in the form of complex configuration files).  As systems evolve and scale, and the ways we can configure and compose our application’s behavior continues to grow, at what point do we perceive that configuration graph as the rich language that it becomes?  Or when our user interfaces evolve from Monolithic to Modular to Composite to Granular Composite (or User Composable), at what point does that persistent object graph become our UX DSL (as with XAML in WPF).

Sometimes we set our standards too low, or are slow to raise them when the time has come to do so.  With XML we get extensibility in defining languages and we think, "If we can parse it, then we can build a tool over it."  I don’t know about you, but I’d much rather work with rich client software–some kind of designer–over a textual data format any day.

But you know how things go: some company like Microsoft builds a whole bunch of cool stuff, driven off some XML configuration, or they unleash something like XAML on which WPF, WF, and more are built.  XAML is great for tools to read and write, and although XML and XAML are textual and not binary and therefore human readable in a text editor (the original intention behind that term), it’s simply not as easy to read as C# or VB.NET.  That’s why we aren’t all rushing to program everything in XAML.

Companies like Microsoft, building from the bottom up, release their platforms well in advance of the thick client user experiences that make them enjoyable to use and which encourages mass adoption.  Their models, frameworks, and applications are so large now that they’re released in massively differentiated stages, producing a technology adoption gap.

By giving that language a syntax other than XML, however, we can approach it in the same way we approach our program logic: in the most human readable and aesthetically-pleasant way we can devise, resembling our programming languages of choice.

Sometimes, the density of data and its structure in our model is such that a visual editor fails to represent that model well.  Source code is a case in point.  You could create a visual designer to visualize flow control, branching logic, and even complex expression building (like the iTunes Smart Playlist), but code in text format is more appropriate in this kind of scenario, and ends up being more efficient with the existing tooling available.  Especially with an IDE like Visual Studio, we’re working with human-millenia of effort that have gone into the great code editing tools we use today.  Oslo respects this need for choice by offering support for building both visual and textual DSLs, and recognizes the fluent definition of new formats and languages as the bridge to the next quantum leap in productivity.

If we had an easy way of defining languages in formats that we developers felt comfortable working with–as we’re comfortable with our general purpose languages and their rich tool support–then we’d be much more productive in the transition between a technology first being released and later having rich tool support over it.  WPF has taken quite a while to be adopted as much as it has, partly due to tool availability and maturity.  Before Expression Blend or Cider designers were released and hand-coding XAML was the only way, those who braved the angle brackets struggled with it.  As I play with Silverlight, I realize how much must still be done in XAML, and how we still struggle.  It’s simply not as nice to work with as my C# code.  Not as rich, and not as strongly tool-supported.

That’s one place Oslo provides value.  With the ability to define new textual and visual DSLs, rigorous verification and validation in a rich set of tools, the promise of Intellisense, colorization of keywords, operators, constants, and more, the Oslo architects recognize the ability to enhance our development experience in a language-agnostic way, raising the level of abstraction because, as they say, the way to solve any technical problem is to approach it at one higher level of indirection.  Unfortunately, this makes Oslo so generalized and abstract that it’s difficult to grasp and therefore to appreciate its immensity.  Once you can take a step back and see how it fits in holistically, you’ll see that it has the potential to dramatically transform the landscape of software development.

Currently, it’s a lot of work to implement all the language services in Visual Studio to give them as rich an experience as we’ve come to expect with C#, VB.NET, and others.  This is a serious impediment to doing this kind of work, so solving the problem at the level of Oslo drastically lowers the barrier to entry for implementing tool-supported languages.  The Oslo bits I’ve seen and played with are very early in the lifecycle for this massive scope of technology, but the more I think about its potential, the more impressed I am with the fundamental concept.  As Chris Anderson explained in his PDC session on MGrammar, MGrammar was an implementation detail, but sometime around June 2007, that feature team realized just how much customers wanted direct access to it and decided to release MGrammar to the world.

Modeling & The Repository

That’s all well and good for DSLs and language enthusiasts/geeks, but primarily perhaps, Oslo is about the creation, exploration, relation, and execution of models in an interoperable way.  In other words, all of the models that are currently used to describe a software system, or an entire IT environment, are either not encoded formally enough to verify or execute, or they’re encoded or stored in proprietary ways that don’t allow interoperability with other models.  A diagram in Visio or PowerPoint documenting network topology, for example, knows nothing about the component architecture or deployment model of the software systems installed and running on that network.

When people usually talk about models, they imagine high-level architecture documents, overviews used to visually summarize work that is much more granular in nature.  These models aren’t detailed, and they normally aren’t kept up to date and in sync with the current design as changes are made.  But modeling in Oslo is not an attempt to make these visual models contain all of the necessary detail, or to develop software with visual tools exclusively.  Oslo simply provides the tools, both graphical and textual, to define and relate many models.  It will be up to the development community to decide how all these tools are ultimately used, which parts of our systems will be specified in a mix of general purpose, domain specific, and visual languages.  Ultimately, Oslo will provide the material and glue to fill the gaps between the high and low level specifications, and unite them into a common, connected, and much more useful set of data.

To grasp what Oslo modeling is really all about requires that we expand our definition of "model", to see the models expressed in our configuration and XAML files, in our applications’ database schemas, in our entity classes, and so on.  As software grows in complexity and becomes more composable, we can use various languages to model its behavior, store that in the repository for runtime execution, inspection, or reuse by other systems.

This funny and clever Oslo video (reminiscent of The Hitchhiker’s Guide to the Galaxy) explains modeling in the broader sense alluded to here.

If we had some universal container for the storage of all different kinds of models, and a standardized way of relating entities across models, we’d be able to do things like impact analysis, where we could see the effect on software systems if someone were to alter the network it was running on; or powerful data mining on the IT execution environment of a business.

Many different tools, with different audiences, will be able to connect into this repository to manipulate aspects of the models that they understand and have access to.  This is just the tip of the iceberg.  We already model so much of what we do in the IT and software worlds, and as we begin adopting business process middleware and orchestration software like BizTalk, there’s a huge amount of value in those models converging and connecting.  That’s where the Oslo Repository comes in.

Oslo provides interoperability among models in the same way that SOA provides interoperability among services.  Not unlike the interoperability we have now among many different languages all sharing the same CLR specification.

Bridging data models across repositories or in shared repository is a major step forward.  With Windows Azure and Microsoft’s commitment to their online services platform (and considering the momentum of the SaaS movement with Amazon, Google, and others), shared storage and data sets are the future.  (Check out SQL Data Services if you haven’t already, and watch for some exciting announcements coming later this year!)

The Dichotomy of Data vs. Metadata

Jeff Pinkston from the Oslo team aptly reflects the attitude of the group when he scoffs at the categorical difference between data and metadata.  In terms of storing and querying it, serializing and communicating it, and everything else that matters in enterprise software, data is data and there’s no reason not to treat it the same when it comes to architecting a system.  We have our primary models and our secondary models, our shared models and our protected models, but they’re still just models that shape our software’s behavior, and they share all of the same characteristics when it comes to manipulation and access.  It’s their ultimate effect that differs.

It’s worth noting, I think, the line that’s been drawn between code and data in some programming languages and not in others (C# vs. LISP).  A division has been made for the sake of security rather than necessity.  Machine instruction codes are represented in the same sort of binary data and realized in the same digital circuitry as traditional user data.  It’s tempting to keep things locked down and divided, but as languages evolve to become more late bound and dynamic (and as the tools evolve to make this feasible), there will be more need for the manipulation of expression trees and ASTs.  I strongly suspect the lines will blur until they disappear.

Schema and Object Instance Languages

In order to define models, we need a tool.  In Oslo, this is a textual language called MShema and an editor called Intellipad.  I personally think it’s odd to talk people’s ears off about "model, model, model", and then to use the synonym "schema" to name the language, but all of these names could change before they’re shipped for all we know.

This is a simple example of an MSchema document:

module MyModel
{
    type Person
    {
        LastName : Text;
        FirstName : Text;
    }

    People : Person*;
}

By running this through the "M Compiler", a SQL script is generated that will create the appropriate database objects.  Intellipad is able to verify the correctness of your schema, and what’s really nice is that you don’t even have to specify data types when you start sketching out your model.  Defaults are assumed, and you can get more specific as your model evolves.

MGraph is a language for defining instances of objects, constrained by an MSchema and similar in format.  So MSchema is to MGraph what XSD is to XML.

In this article, Lars Corneliussen explains Microsoft’s vision to make MGraph as common as XML is today.  Take a look at his article to see a side-by-side comparison of the same object represented as XML (POX), JSON, and MGraph, and decide for yourself which you like best (or see below).

MSchema and MGraph are easier and more efficient to read and write than XML.  Their message format resembles typical structured programming languages, and developers are already familiar with these formats.  XML is a fine format for a tool; it’s human readable but not human-friendly.  A C-style language, on the other hand, is much more human-friendly than all of the angle brackets and the redundancy (and verbosity) of tag text.  That narrows down our choice to JSON and MGraph.

In JSON, the property/field/attribute names are delimited by quotation marks, suggesting that the whole structure is a dumb property bag.

{
    "LastName" : "Vanderboom",
    "FirstName" : "Dan"
}

MGraph has a very similar syntax, but its attribute property names are recognized and validated by the parser generated from MSchema, so the quotation marks are unnecessary.  It ends up looking more natural, and a little more concise.

{
    LastName : "Vanderboom",
    FirstName : "Dan"
}

Because MGraph is just a message format, and Microsoft’s service offerings already support multiple message formats (SOAP/POX/JSON/etc.), it wouldn’t disrupt any of their architecture to add an MGraph adapter, and I’ll be shocked if I don’t hear about one in their next release.

Meta-Languages and MGrammar

In the same way that Oslo includes a meta-model because it allows us to define models, it also includes a meta-language because it allows us to define languages (as YACC and ANTLR have done).  However, just as Pinkston doesn’t think data and metadata should be treated different, it makes sense to think of a language that defines languages as just another language.  There is something Zen about that, where the tools somehow seem to bend back upon themselves like one of Escher‘s drawings.

Here is an example language defined by MGrammar in a great article on MSDN called MGrammar in a Nutshell:

module SongSample
{
    language Song
    {
        // Notes
        token Rest = "-";
        token Note = "A".."G";
        token Sharp = "#";
        token Flat = "b";
        token RestOrNote = Rest | Note (Sharp | Flat)?;

        syntax Bar = RestOrNote RestOrNote RestOrNote RestOrNote;
        syntax List(element)
          = e:element => [e]
          | es:List(element) e:element => [valuesof(es), e];

        // One or more bars (recursive technique)
        syntax Bars = bs:List(Bar) => Bars[valuesof(bs)];
        syntax ASong = Music bs:Bars => Song[Bars[valuesof(bs)]];
        syntax Songs = ss:List(ASong) => Songs[valuesof(ss)];

        // Main rule
        syntax Main = Album ss:Songs => Album[ss];

        // Keywords
        syntax Music = "Music";
        syntax Album = "Album";

        // Ignore whitespace
        syntax LF = "\u000A";
        syntax CR = "\u000D";
        syntax Space = "\u0020";

        interleave Whitespace = LF | CR | Space;
    }
}

This is a pretty straight forward way to define a language and generate a parser.  Aside from the obvious keywords to define syntax rules and token patterns (with an alternative and more readable format for regular expressions), the => projection operator allows you to shape the MGraph output according to your needs.

I created two simple languages with MGrammar on the plane trip back to Milwaukee from the PDC in November.  The majority of my time was spent fussing with the editor, Intellipad, and for the last half hour I found it very easy to create a language on the fly, extending and changing it through experimentation quickly and easily.  Projections, which are functional expressions in MGrammar used to shape MGraph output, are the most challenging part.  There are a number of techniques that shape the output graph, so it will be good to see how this is approached in future reference examples.

Surreptitiously announced just before I wrote this, Mike Weinhardt at Microsoft indicated that a gallery of example grammars for MGrammar is being put together, to point to the sample grammars for various languages in addition to grammars that the community develops, and it should be available by the end of this month.  These examples demonstrating how to define languages and write sensible projections, coming from the developers who are putting MGrammar together, will be an invaluable tool for teaching you how to use common patterns (just as 101 LINQ Samples did for LINQ).

As Doug Purdy explained on .NET Rocks: "People who are building a domain specific language, and they don’t want to understand how to build a parser, or they’re not language designers.  Actually, they are language designers.  They design a language, but they actually don’t do the whole thing.  They don’t build a parser.  What they do, they just leverage the XML parser.  And what we’re trying to do is provide a toolset for folks where they don’t have to resort to XML in order to do DSLs."

From the same episode, Don Box said of the DSL session at PDC: "I’ve never seen a session with more geek porn in it."

Don: "It’s like crack for developers.  It’s kind of addictive; it takes over your life."

Doug: "If you want the power of Anders in your hand…"

The Tool Chain

Now that we have a better sense of what’s included in Oslo in terms of languages, editors, and the shared repository, we can look at the relationship among the other pieces, which are manifested in the CTP as a set of command-line tools.  In the future, these will integrate into an IDE, most likely Visual Studio.  (I’d expect Intellipad and Quadrant to merge with Visual Studio, but there’s no guaranty this will happen.)

When you create your model with MSchema, you’ll use m to validate that model and generate a SQL script to create a SQL Server 2008 database schema (yes, it only works right now with SQL Server 2008).  You’ll also use the m command to validate your object graph (written in MGraph) against your schema, and translate that into a set of SQL commands to perform inserts and updates against tables.

With enough models, there’ll be huge value in adding yours to the repository.  If you don’t mind writing MGraph or you generate it automatically with something like an MGraphSerializer class in your code, this may be all you need.

If, on the other hand, you decide you could really benefit by defining your own textual language to use instead of MGraph, you can use MGrammar to define a new language.  This language gets compiled by the mg compiler to create your parser, and the mgx command translates code in your new language into an MGraph, which can then be pulled into your database using m.

This diagram depicts the process:

Other than these command-line tools, Quadrant is the highly extensible visual tool for exploring models graphically, and Intellipad is a different face on the same shell for defining DSLs with MGrammar and writing DSL code, as well as writing and verifying MSchema and MGraph code.

We should see fairly soon the convergence of these three languages (MGraph, MSchema, and MGrammar) into a single M language.  This makes sense, since what you want to project in your DSL should be something within your model, verified by your schema.  This may ultimately make these projections much easier to write.

We’ll also see this tool chain absorbed into multiple development environments, eventually with rich binding across multiple representations of our model, although this will take longer in Visual Studio.

Languages and Nested Languages

I looked at some MService examples, and I can understand Damon’s concern that although it’s nice to have "operation" as a keyword in a service-oriented language, with more keywords giving you the ability to specify aspects of each endpoint and the communications patterns required, that enclosing the business logic within that service language is probably not a good idea.  I took this from Dennis van der Stelt’s blog:

service Service
{
  operation PhotoUpload(stream : Stream) : Text
  {
    .PostUriTemplate = "upload";

    index : Text = invoke DateTime.Now.Ticks.ToString();
    filename : Text = "d:\\demo\\photo\\" + index + ".jpg";
    invoke MService.ServiceHelper.StoreInFile(stream, filename);

    return index;
  }
}

Why not?  You’re defining a general purpose language within the curley braces, one capable of defining variables, assigning values, referencing .NET objects, and calling methods.  But why do you want to learn a new language to write services when the language you’re using right now is already supremely capable of that?  Don’t you already know a good syntax for invoking methods (other than "invoke %mehthod%")?  If instead you simply referenced an assembly, type, and method from an MService script, you could externally turn any .NET method with serializable parameters and return value into a service operation by feeding it this kind of file, without having to recompile, and without having to reinvent the wheel.

The possible exception would be if MGrammar adds the ability (as discussed by speakers at the PDC) of supporting multiple layers of enclosing languages within other languages.  In other words, you could use MService to define operations and their attributes using its own syntax, and within the curly braces that follow, use the C# or VB.NET parsers to process the logic with the comprehension of a separate language.  There are some neat possibilities here, but I expect the development community to be conservative and hesitent about mixing layers of semantics, as there is an awful lot of room for confusion and complexity.  It may be better to leave different language blocks in separate files or containers, and to allow them to reference each other as .NET assemblies and XML files reference each other today.

However, I wouldn’t get too hung up on the early versions of these new languages, or any one language specifically.  The useful, sensible ones that take real developer needs into account and provide the most value will be adopted, and many more will quickly fall into disuse.  But the overall pattern will be for the emergence of an amazing amount of leverage in terms of improving human comprehension and taking advantage of our ability to manipulate structured, symbolic object graphs to build and verify software systems.

Resources

After a few months of research and many hours of writing, I don’t feel like I’ve even scratched the surface.  But instead of giving you an absolutely comprehensive picture, I’m going to stop here and continue in future articles.  In the meantime, check out the following resources.

For an overview of the development paradigm, look for information on language-oriented programming, including an article I wrote that alludes to how "we will have to raise the level of abstraction to a point that may be hard for us to imagine with our existing tools and languages" due to the "precipitious growth of software complexity".  The "community of abstractions" is the model in Oslo-speak.

For Microsoft specific content: there were some great sessions at the PDC (watch the recorded videos).  It was covered (with much confusion) on the .NET Rocks! podcast (here and here) as well as on Software Engineering Radio; and there are lots of bloggers talking about their initial experiences with it, such as Shawn Wildermuth, Lars Corneliussen, and of course Chris Sells and Jeff Pinkston.  The most clear and coherent explanation I’ve heard was from an interview with Ron Jacobs and David Chappell (Ron gave the keynote at MSDN Dev Con, hosted the ARCast podcast for years).  MSDN has at least 29 videos on the Oslo Developer Center, where there’s a good amount of information. including a FAQ.  There’s also the online guide for MGrammar, MGrammar in a Nutshell, and the Oslo team blog.

If you’re interested in creating DSLs, make sure to keep a look out for details about the upcoming DSL Developers Conference, which is tentatively planned for April 16-17, immediately following the Lang.NET conference (on general purpose languages) on April 14-16.  I’m hoping to be at both this year.  And in case you haven’t heard, Microsoft is planning another PDC Conference for 2009, the first time ever these conferences have run for two consecutive years!  There will no doubt be much more Oslo news and conference material to cover it at the PDC in November.

Pluralsight, an instructor-led training company, now teaches a two-day "Oslo" Fundamentals course (and Don Box’s blog is hosted there).

The best way to learn about Oslo, however, is to dive in and use it.  That’s what I’m doing with my newest system, which needs to be modeled from scratch.  So if you haven’t done so already, download the Oslo SDK (link updated to January 2009 SDK) and introduce yourself to the future of modeling and development!

[Click here for the next article in this Oslo series, on common misconceptions and fallacies about Oslo.]

Functional Programming as Intensity of Expression

On my long drive home last night, I was thinking about the .NET Rocks episode with Ted Neward and Amanda Laucher on F# and functional programming.  Though they’re writing a book on F# together, it seems even they have a hard time clearly articulating what functional programming is all about, and where it’s all headed in terms of mainstream commercial use… aside from scientific and data transformation algorithms, that is (as with the canonical logging example when people explain AOP).

I think the basic error is in thinking that Functional is a Style of programming.  Yet, to say that so-called Imperative-based languages are non-functional is ridiculous.  Not in the sense that they “don’t work”, but that they’re based on Objects “instead of” Functions.

This isn’t much different from the chicken-and-egg problem.  Though the chicken-and-egg conundrum has a simple (but unobvious) answer, it doesn’t really matter whether the root of program logic is a type or a function.  If I write a C# program with a Program class, the Main static function gets called.  Some action is the beginning of a program, so one might argue that functions should be the root-most logical construct.  However, you’d then have to deal with functions containing types as well as types containing functions, and as types can get very large (especially with deep inheritance relationships), you’d have to account for functions being huge, spanning multiple code files, and so on.  There’s also the issue of types being organizational containers for functions (and other members).  Just as we use namespaces to organize our types, so we use types to organize functions.  This doesn’t prevent us from starting execution with a function or thinking of the program’s purpose functionally; it just means that we organize it inside a logical container that we think of as a “thing”.

Does this limit us from thinking of business processes as functional units?  Ted Neward suggests that we’ve been trained to look for the objects in a system, and base our whole design process on that. But this isn’t our only option for how to think about design, even in our so-called imperative languages.  If we’re thinking about it wrong, we can and should change the process; we don’t need to blame our design deficiencies on the trivial fact of which programming construct is the root one.  In fact, there’s no reason we should use any one design principle to the exclusion of others.  Looking for the things in the system is and will remain a valuable approach for discovering and defining database schemas and object models.  The very fact that “functional languages” aren’t perceived as especially useful for stateful components isn’t a fault of a style of programming, but is rather a natural consequence of functions being an incomplete aspect of a general purpose programming language.  Functional is a subset of expressive capability.

Where “functional languages” have demonstrated real value is not in considering functions as root-level constructs (this may ultimately be a mistake), but rather in increasing the flexibility of a language to be much more expressive when defining functions.  Making functions first-class citizens that can be passed as parameters, returned as function values, and stitched together with metaprogramming techniques, is a huge step in the right direction.  The use of simple constructs such as operators to match patterns, reverse the evaluation of functions and the flow of values with piping, and perform complex set- and list-based operations, all increase the expressive intensity and density of the functions in a language.  This can only add to the richness of our existing object models.

Sticking objects together in extensible and arbitrarily complex structures is routine for us, but now we’re seeing a trend toward the same kind of composability in functions.  Of course, even this isn’t new, per se; the environmental forces that demand this power just haven’t become significant enough to require that level of power in mainstream languages, because technology evolution (like evolution in general) tends to work by adapting solutions that are “good enough”.

It’s common to hear how F# is successfully incorporating “both functional and imperative” styles into one language, and this is important because what we need is not so much the transition to a functional style, as I’ve mentioned already, but a growth of greater functional expressiveness and power in existing, successful, object-oriented languages.

So let our best and favorite languages grow, and add greater expressive powers to them, not only for defining functions, but also in declaring data structures, compile-time constraints and guarantees, and anything else that will help to raise the level of abstraction and therefore the productivity with which we can naturally express and fulfill our business needs.

Ultimately, “functional programming” is not a revolutionary idea, but rather an evolutionary step forward.  Even though it’s impact is great, there’s no need to start from scratch, to throw out our old models.  Incompatibility between functional and imperative is an illusion perpetuated by an unclear understanding of their relationship and each aspect’s purpose.

Observations on the Evolution of Software Development

Neoteny in the Growth of Software Flexibility and Power

Neoteny is a biological phenomenon of an organism’s development observed across multiple generations of a species.  According to Wikipedia, neoteny is “the retention, by adults in a species, of traits previously seen only in juveniles”, and accounts for many evolutionary shifts, including the human brain’s ability to remain elastic and malleable later in life than those of our distant ancestors.

So how does this relate to software?  Software is a great deal like an organic species.  The species emerged (not long ago), incubated in a more or less fragile state for a number of decades, and continues to evolve today.  Each software application or system built is a new member of the species, and over the generations they have become more robust, intelligent, and useful.  We’ve even formed a symbiotic relationship with software.

Consider the fact that software running on computers was at one time compiled to machine language code for a specific processor.  With the invention of platform-independent instruction sets and their associated runtimes performing just-in-time compilation (Java’s JVM and .NET Framework’s CLR), we’ve delayed the actual production of machine language code until it’s actually needed on the target machine.  The compiler produces a slightly more abstract representation of the program logic, and an extra translation step at installation or runtime is needed to complete the process to make the software usable.

With the growing popularity of dynamic languages such as Lisp, Python, and the .NET Framework’s upcoming release of its Dynamic Language Runtime (DLR), we’re taking another step of neoteny.  Instead of a compiler generating instruction byte codes, a “compiler for any dynamic language implemented on top of the DLR has to generate DLR abstract trees, and hand it over to the DLR libraries” (per Wikipedia).  These abstract syntax trees (AST), normally an intermediate artifact created deep within the bowels of a traditional compiler (and eventually discarded), are now persisted as compiler output.

Traits previously seen only in juveniles… now retained by adults.  Not too much of a metaphorical stretch!  The question is: how far can we go?  And I think the answer depends on the ability of hardware to support the additional “just in time” processing that needs to occur, executing more of the compiler’s tail-end tasks within the execution runtime itself, providing programming languages with greater flexibility and power until the compilation stages we currently execute at design-time almost entirely disappear (to be replaced, perhaps, by new pre-processing tasks.)

I remember my Turbo Pascal compiler running on a 33 MHz processor with 1 MB of RAM, and now my cell phone runs at 620 MHz (with a graphics accelerator) and has gigabytes of memory and storage.  And yet with the state of things today, the inclusion of language-specific compilers within the runtime is still quite infeasible.  In the .NET Framework, there are too many potential languages that people might attempt to include in such a runtime: C#, F#, VB, Boo, IronPython, etc.  Trying to cram all of those compilers into a universal runtime that would fit (and perform well) on a cell phone or other mobile device isn’t yet feasible, which is why we have technologies with approaches like System.Reflection.Emit (on the full .NET Framework), and Mono.Cecil (which works on Compact Framework as well).  These work at the platform-independent CIL level, and so can interpret and generate programs generically, interact with each others’ components, and so on.  One metaprogramming mechanism can therefore be reused across all .NET languages, and this metalinguistic programming trend is being discussed on the C# and other language design teams.

I’ve just started using Mono.Cecil, chosen because it is cross-platform friendly (and open source).  The API isn’t very intuitive, but because the source is available, and because extension methods can go a long way to making it more accessible, it’s a great option.  The documentation is sparse, and assembly generation has some performance issues, but it’s a work-in-progress with tremendous potential.  If you’re doing any kind of static analysis or have any need to dynamically generate and consume types and assemblies (to get around language limitations, for example), I’d encourage you to check it out.  A comparison of Mono.Cecil to System.Reflection can be found here.  Another library called LinFu, which performs lots of mind-bending magic and actually uses Mono.Cecil, is also worth exploring.

VB10 will supposedly be moving to the DLR to become a truly dynamic language, which considering their history of support for late binding, makes a lot of sense.  With a dynamic language person on the C# 4.0 team (Jim Hugunin from IronPython), one wonders if C# won’t eventually go the same route, while keeping its strongly-typed feel and IDE feedback mechanisms.  You might laugh at the idea of C# supporting late binding (dynamic lookup), but this is being planned regardless of the language being static or dynamic.

As the DLR evolves, performance optimizations are being discovered and implemented that may close the gap between pre-compiled and dynamically interpreted languages.  Combine this with manageable concurrent execution, and the advantages we normally attribute to static languages may soon disappear altogether.

The Precipitous Growth of Software System Complexity

We’re truly on the cusp of a precipitous period of growth for software complexity, as an exploding array of devices and diverse platforms around the world connect in an ever-more immersive Internet.  Taking full advantage of parallel and distributed computing environments by solving the challenges of concurrency and coordination, as well as following the trend toward increased integration among software components, is pushing software complexity into new orders of magnitude.  The strategies we come up with for organizing these systems will have to take several key factors into consideration, and we will have to raise the level of abstraction to a point that may be hard for us to imagine with our existing tools and languages.

One aspect that’s clear is the rise of declarative or intention-based syntax, whether represented as XML, Domain Specific Langauges (DSL), attribute decoration, or a suite of new visual modeling editors.  This is in part a consequence of raising the abstraction level, as lower-level libraries are entrusted to solve common problems and take advantage of common opportunities.

Another is the use of Inversion of Control (IoC) containers and dependency injection in component based architectures, thereby standardizing the lifecycle of the application and its components, and providing a common environment or ecosystem for all of its components, as well as introducing a common protocol for component location, creation, access, and disposal.  This level of consistency is valuable for sharing a common understanding of how to troubleshoot software components.  The more predictable a component’s interaction with the rest of the system, the easier it is to debug and modify; conversely, the more unique it and its communication system is, the more disparity there is among components, and the more difficult to understand and modify without introducing errors.  If software is a species and applications are individuals, then components are the cells of a system.

Even the introduction of functional programming languages into the mainstream over the past couple years is due, in part, to the ability of those languages to provide more declarative support, more syntactic flexibility, and new ways of dealing with concurrency and coordination issues (such as immutable values) and light-weight, ad hoc data structures (tuples).

Balancing the Forces of Coupling, Cohesion, and Modularity

On a fundamental level, the more that components are independent, the less coupled and the more modular and flexible they are.  But the more they can communicate with and are allowed to benefit from each other, the more interdependent they become.  This adds to cohesiveness and synergy, but also stronger coupling to a community of abstractions.

A composition of services has layers and segments of interdependence, and while there are dependencies, these should be dependencies on abstractions (interfaces and not implementations).  Since there will be at least one implementation of each service, and the extensibility exists to build others as needed, dependency is only a liability when the means for fulfilling it are not extensible.  Both sides of a contract need to be fulfilled regardless; service-oriented or component-based designs merely provide a mechanism for each side to implement and fulfill its part of the contract, and ideally the system also provides a discovery mechanism for the service provider to publish its availability for other components to discover and consume it.

If you think about software components as a hierarchy or tree of services, with services of one layer depending on more root services, it’s easy to see how this simplifies the perpetual task of adding new and revising existing functionality.  You’re essentially editing an outline, and you have opportunities to move services around, reorganize dependencies easily, and have many of the details of the software’s complexity absorbed into this easy-to-use outline structure (and its supporting infrastructure).  Systems of arbitrary complexity become feasible, and then relatively routine.  There’s a somewhat steep learning curve to get to this point, but once you’ve crossed it, your opportunities extend endlessly for no additional mental cost.  At least not in terms of how to compose your system out of individual parts.

Absorbing Complexity into Frameworks

The final thing I want to mention is that a rise in overall complexity doesn’t mean that the job of software developers necessarily has to become more difficult than it is currently.  With the proper design of components that abstract away the complexity into reusable frameworks with intuitive interfaces, developers at the business logic level don’t need to be aware of the inner complexity, in the same way that software developers are largely absolved of the responsibility of thinking about the processor’s inner workings.  As we build our technology stack higher and higher, like the famed Tower of Babel, we must make sure that it’s organized and structured in a way to support that upward growth and the load imposed upon it… so it doesn’t come crashing down.

The requirements for building components tomorrow will not be the same as they were yesterday.  As illustrated in this account of the effort involved in a feature change at Microsoft, in the future, we will also want to consider issues such as tool-assisted refactorability (and patterns that frustrate this, such as “magic strings”), and due to an explosion of component libraries, discoverability of types, members, and their use.

A processor can handle any complexity of instruction and data flow.  The trick is in organizing all of this in a way that other developers can understand and work with.

Using Extension Methods to Manipulate Control Bitmaps in Compact Framework

I’m loving extension methods.  All of the methods that I wish BCL classes had, I can now add.  While I consider it highly unfortunate that we can’t yet add extension properties, events, or static members of any kind, still it’s a great amount of power in terms of making functionality discoverable in ways not possible before.

During the implementation of my Compact Framework application’s MVC framework, I wanted to support displaying views modally.  However, using a screen stack of UserControls that are all hosted in a single master Form object, I lose out on this built-in functionality and so found myself in need of creating this behavior myself.  One of the difficulties in doing this is displaying a view that may not cover every portion of other views beneath it; if the user clicks on one of the views “underneath”, that control gets activated, and if pressed on a control, that control will handle the event (such as Button.Click).

My solution to the problem is simple.  Take a snapshot of the master form and everything on it, create a PictureBox control that covers the whole form and bring it to front, and set its image to the snapshot bitmap.  Doing this provides the illusion that the user is still looking at the same form full of controls, and yet if they touch any part of the screen, they’ll be touching a PictureBox that just ignores them.  The application is then free to open a new view UserControl on top of that.  When the window is finally closed, the MVC infrastructure code tears down the PictureBox, and the real interface once again becomes available for interaction.

In addition, I wanted the ability to emphasize the modal view, so you can see from the picture above that I decided to accomplish this by de-emphasizing the background bitmap.  By darkening the snapshot, the pop-up modal view really does seem to pop out.  The only problem with bitmap manipulation using the Compact Framework library is that it’s extremely slow, but I get around this by using some unsafe code to manipulate the memory region where the bitmap image gets mapped.  (If you’re unfamiliar with the unsafe keyword, don’t worry: this code actually is safe to use.)

Here is the full source code for taking a snapshot of a form (or any control), as well as adjusting the brightness.

using System;
using System.Linq;
using System.Collections.Generic;
using System.Text;
using System.Drawing;
using System.Drawing.Imaging;
using System.Windows.Forms;
using System.Runtime.InteropServices;

public static class ControlBitmapExtensions
{
    [DllImport("coredll.dll")]
    private static extern bool BitBlt(IntPtr hdc, int nXDest, int nYDest, int nWidth, int nHeight,
        IntPtr hdcSrc, int nXSrc, int nYSrc, int dwRop);

    public struct PixelData
    {
        public byte Blue;
        public byte Green;
        public byte Red;
    }

    public static Bitmap GetSnapshot(this Control Control)
    {
        Rectangle rect = new Rectangle(0, 0, Control.Width, Control.Height - 1);
        Graphics g = Control.CreateGraphics();
        Bitmap Snapshot = new Bitmap(rect.Width, rect.Height);
        Graphics gShapshot = Graphics.FromImage(Snapshot);
        BitBlt(gShapshot.GetHdc(), 0, 0, rect.Width, rect.Height, g.GetHdc(), rect.Left, rect.Top, 0xCC0020);
        gShapshot.Dispose();

        return Snapshot;
    }

    public static unsafe Bitmap AdjustBrightness(this Bitmap Bitmap, decimal Percent)
    {
        Percent /= 100;
        Bitmap Snapshot = (Bitmap)Bitmap.Clone();
        Rectangle rect = new Rectangle(0, 0, Bitmap.Width, Bitmap.Height);

        BitmapData BitmapBase = Snapshot.LockBits(rect, ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);
        byte* BitmapBaseByte = (byte*)BitmapBase.Scan0.ToPointer();

        // the number of bytes in each row of a bitmap is allocated (internally) to be equally divisible by 4
        int RowByteWidth = rect.Width * 3;
        if (RowByteWidth % 4 != 0)
        {
            RowByteWidth += (4 - (RowByteWidth % 4));
        }

        for (int i = 0; i < RowByteWidth * rect.Height; i += 3)
        {
            PixelData* p = (PixelData*)(BitmapBaseByte + i);

            p->Red = (byte)Math.Round(Math.Min(p->Red * Percent, (decimal)255));
            p->Green = (byte)Math.Round(Math.Min(p->Green * Percent, (decimal)255));
            p->Blue = (byte)Math.Round(Math.Min(p->Blue * Percent, (decimal)255));
        }

        Snapshot.UnlockBits(BitmapBase);
        return Snapshot;
    }

    public static Bitmap Brighten(this Bitmap Bitmap, decimal PercentChange)
    {
        return AdjustBrightness(Bitmap, 100 + PercentChange);
    }

    public static Bitmap Darken(this Bitmap Bitmap, decimal PercentChange)
    {
        return AdjustBrightness(Bitmap, 100 - PercentChange);
    }
}

 

Because Control is extended by GetSnapshot, and Bitmap is extended by AdjustBrightness, Brighten, and Darken, I can write very clear and simple code like this on the consuming side:

Bitmap bitmap = MyForm.GetSnapshot().Darken(40);

…and voila!  I have a snapshot.  Note that because Darken extends Bitmap, it can now be used with any Bitmap.  As we read from this code from left to right, we’re observing a pipeline of transformations.  MyForm is the source data, GetSnapshot is the first step, Darken is the next change, and with more extension methods on Bitmap we could continue to process this in a way that is very natural to think about and construct.

I do have to admit that I cheated a little, though.  Even with the direct memory manipulation with pointers, it still didn’t perform very well on the Symbol and DAP devices I tested on.  So instead of adjusting the brightness on every pixel, I only darken every third pixel.  They’re close enough together that you can’t really tell the difference; however, the closer to 100 percent you darken or brighten an image, the more apparent the illusion will be, since two thirds of the pixels won’t be participating.  So it’s good for subtle effects, but I wouldn’t count on it for all scenarios.

This every-third-pixel dirty trick happens in the for loop, where you see i += 3, so go ahead and experiment with it.  Just be careful not to set it to large even numbers or you’ll end up with stripes!

The Visitor Design Pattern in C# 3.0

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.

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.

Tree Data Structure Source Code Posted

[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.

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

[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.

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.

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.

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.

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.

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.]

Tags: Data+Structures, Trees, Algorithms, Hierarchy, Object+Oriented+Design, Problem+Modeling, Software+Architecture, Refactoring, Design

Important Professional Skills for Software Architects

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.

Tags: Risk+Identification, Risk+Management, Critical+Thinking, Analysis, Strategy, Long+Term+Planning, Continuous+Research, Ethics, Customer+Advocacy, Communication+Skills, Professional+Skills, Conflict+Resolution, Negotiation, Problem+Modeling

The Architecture Journal: Mobile Architecture

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.

Tags: Compact+Framework, Mobile+Architecture, Windows+Mobile, Windows+CE, Software+Architecture, The+Architecture+Journal