Advanced Inversion of Control 1: Composite Registration with Microsoft Unity

I've been using Microsoft Unity for quite some time as a productivity booster, but only recently have I begun to really push it to its limits, to "put the pedal to the metal," as it were. In this blog post I'm going to demonstrate ways that you can create exotic composite configurations involving named registrations of types that implement multiple interfaces, facilitated by a new InjectionMember subclass I've created called InjectionRedirect, which you can download directly here.

So what is Microsoft Unity? Unity is an Inversion of Control container produced and supported by Microsoft. Unity obviously isn't the only IOC container out there but I've found it to be extremely versatile, which I why I use it. For a history of how Unity came about and how to use some of its advanced features, I suggest you read the free e-book put out by Microsoft called Dependency Injection with Unity.

What is Inversion of Control?

First things first: what do we mean by inversion of control? For beginner or mid-level software developers it can be difficult to make sense of all the jargon, so I'm going to define all of the common terms from the get-go to avoid any confusion.

Dependency Inversion Principle: One of the SOLID design principles (I would argue, the most important one) proposed by Robert C. Martin which states the following:

  1. High-level types do not depend upon low-level types; both depend upon abstractions.
  2. Abstractions do not depend upon details; details depend upon abstractions.

(Note the common phrase "depend upon abstractions." Now repeat it over and over and over again, like a mantra.)

Dependency Injection: The means by which the Dependency Inversion Principle is put into practice. In other words, how you will supply concrete implementations of abstractions to the classes which depend upon those abstractions. Dependency Injection comes in 3 forms:

  1. Constructor injection (the most common approach).
  2. Property injection (infrequently used).
  3. Method injection (rarely used).

Inversion of Control: Similar to the two principles above, but not quite the same thing. Inversion of Control expresses the notion that the classes you design will no longer be responsible for instantiating their dependencies, but rather will allow for some outside agency (hint: the IOC container) to both instantiate and provide concrete implementations of their dependencies, as well as manage the lifetimes of those dependencies. You no longer have creational code scattered throughout every far corner of your code base like a n00b programmer; the responsibility of object creation and lifetime management has been taken from all of your classes and placed into one centralized, maintainable location. Ergo, the control has been inverted.

So that brings us to our core question: what is an inversion of control container? In short, it is a tool that figures out how to assemble object graphs using rules or conventions that you have configured it for. Typically, you configure the container in one place, telling it what concrete implementations to provide for each dependency (which are usually abstractions—abstract classes or interfaces) and then you resolve the top level objects (composition root) near the beginning of your program. In a nutshell, that's it.

When explaining this to lay people I often turn to this analogy: if you have designed all your classes using the Dependency Inversion Principle then you have a bunch of components lying around that are conceptually like Lego blocks—versatile, reusable, cohesive. The IOC container is like a magic hat that you dump all of your Lego blocks into, utter some magical incantations, and then out of which pull fully constructed, complex objects like dragons, pirate ships, space shuttles, etc. You get the idea.

So, John, are you saying that an IOC container is necessary to achieve this? No, I am not. At my last job I encountered a lot of confusion concerning this topic while trying to introduce some junior developers to the Unity container for a project I was working on. In the greater scheme of things all that matters is that you abide by good coding practices (depend upon abstractions, not concretes) and then how you put all the pieces together is irrelevant; you could just as easily use "poor man's dependency injection" (assembling the pieces manually) for a simple project and you can implement an IOC container later if you need to scale out, or don't even bother. In fact, some experts like Danish developer Mark Seeman recommend avoiding an IOC container except for registration by convention scenarios. The point is this: an IOC container is just a tool—no more, no less.

Mark Seeman is obviously an authority on IOC and dependency injection (wrote a book on it, in fact), however in my opinion there are two other good reasons to use an IOC container for productivity gains besides registration by convention.

  1. When the sheer number of constituent pieces of a system and their corresponding abstractions are so overwhelming that it makes sense to explicitly register them in one spot using an easy, key/value pair syntax.
  2. When you have a need to produce complex, composite object graphs from some kind of a factory, knowing that only around 80% of those dependencies will be known at design time, with the rest provided at resolution time (run time).

It is the second scenario that I will be covering here. Buckle up!

Building Composites Using Inversion of Control

I'm going to use a somewhat contrived scenario here, so bear with me. I'll leave it as an exercise for the reader to think of more complex problems that might be solved in a similar fashion. Let's pretend that we need to build a system to do some simple human language processing on any arbitrary input text. The system will take the input text, run it through a series of filters or transformations, and then compute some statistics from the altered text. The pieces of this system should be succinct and compositional so that they can be easily swapped out and reconfigured as requirements change. We will assemble the text processing components together using a Chain of Responsibility style design.

This is the interface that our text processing components will implement:

public interface ITextProcessor
{
    string Process(string text);
}

You will notice that the interface only has a single method. This is an example of a Role Interface because it has a singular purpose and promotes implementations that abide by the Single Responsibility Principle. In fact, interfaces with only a single member are especially holy and sacrosanct because they are guaranteed to be free of semantic coupling between members of that interface in any given implementation (since there is only one member), and implementations are less likely to violate the Liskov Substitution principle (the L in SOLID). For more of the design philosophy behind this I recommend the Pluralsight course Encapsulation and SOLID (also produced by Mark S.). The opposite of a Role Interface is called a Header Interface because they resemble C++ header files and have a whole bunch members. I will not cover them too much here because they are generally a design smell and often violate the Interface Segregation Principle (the I in SOLID).

OK, moving along, let's also assume that we need a separate interface that provides statistical results to us from some kind of a text analyzer. That interface and accompanying stats class will look something like this:

public interface IStatisticsAggregator
{
    IDictionary<string, Statistics> Results { get; }
}
 
public sealed class Statistics
{
    public int Count { get; set; }
    public double Frequency { get; set; }
}

The statistics class exposes a count of the number of occurrences of a particular word in the source text and the frequency of that word. The interface will provide a dictionary of statistics keyed to each word found in the source text. Still pretty clear cut, right?

Well, there are some other nuances to take into consideration like casing, white space, etc so let's create a few preliminary text processors to standardize casing, collapse white space and remove unnecessary punctuation.

public sealed class CasingProcessor : ITextProcessor
{
    public string Process(string text)
    {
        return text.ToLowerInvariant();
    }
}
 
public sealed class WhiteSpaceProcessor : ITextProcessor
{
    private static readonly Regex wsRegex = new Regex(@"\s+", RegexOptions.Compiled);
 
    static WhiteSpaceProcessor() { }
 
    public string Process(string text)
    {
        return wsRegex.Replace(text, " ");
    }
}
 
public sealed class PunctuationProcessor : ITextProcessor
{
    private static readonly Regex puncRegex = new Regex(@"[^\w ]", RegexOptions.Compiled);
 
    static PunctuationProcessor() { }
 
    public string Process(string text)
    {
        return puncRegex.Replace(text, "");
    }
}

Finally, we will create our class that counts the words in the source text and aggregates statistical results.

public sealed class WordCountProcessor : ITextProcessor, IStatisticsAggregator
{
    private IDictionary<string, Statistics> results;
    public IDictionary<string, Statistics> Results
    {
        get
        {
            if (results == null)
            {
                results = new Dictionary<string, Statistics>();
            }
            return results;
        }
    }
 
    private string[] wordList;
    public WordCountProcessor(string[] wordList)
    {
        if (wordList == null)
        {
            throw new ArgumentNullException("wordList");
        }
        if (wordList.Length == 0)
        {
            throw new ArgumentException("wordList");
        }
        this.wordList = wordList;
    }
 
    public string Process(string text)
    {
        var count = 0;
        var tempResults = new ConcurrentDictionary<string, int>();
        foreach (var word in text.Split(' '))
        {
            if (wordList.Contains(word))
            {
                tempResults.AddOrUpdate(word, 0, (w, c) => c + 1);
            }
            count++;
        }
 
        if (count != 0)
        {
            results = (
                from kvp in tempResults
                select new
                {
                    Key = kvp.Key,
                    Value = new Statistics { Count = kvp.Value, Frequency = (double)kvp.Value / (double)count }
                }
            ).ToDictionary(anon => anon.Key, anon => anon.Value);
        }
        return text;
    }
}

Notice that this class implements both the ITextProcessor and IStatisticsAggregator interfaces. You might be wondering, doesn't this violate the Single Responsibility Principle? I would argue, no, and here's why: the class itself still has only one purpose (counting words and calculating their relative frequency in the text), however the class exposes two different facets or roles which allow it to be meaningfully used in the program—as a processor (analyzer) of text on a chain and as a provider of statistics, respectively. Rather than create a new abstraction and accompanying consumer code in the classes that depend on it, we are reusing an existing abstraction and therefore maximizing overall code reuse. In fact, I'd even frame such a scenario as a design principle, which I'm tentatively calling the Like Parts Principle and describe it as thus:

  • Functional classes in any given program/system should seek to be cross-compatible and interchangeable; abstractions should be reused wherever it makes sense as long as no unwanted side effects are introduced and no major design principles are violated. Thus, the building of compositional designs becomes easier.

This is somewhat similar to the Reused Abstractions Principle, though perhaps looking at it from the other side of the coin. If you're still skeptical I'd also like to remind you that this is a contrived example, and that more complex scenarios can and will present themselves in real-world systems.

Next we'll implement the Chain of Responsibility pattern as its own implementation of the ITextProcessor interface. The various text-processing implementations that we've created above can now be composed together by injecting them into this class via constructor injection. The purpose of this class is to merely call each processor on the chain in a linear fashion, passing the processed text along as it goes.

public sealed class CompositeProcessor : ITextProcessor
{
    private ITextProcessor[] processors;
 
    public CompositeProcessor(params ITextProcessor[] processors)
    {
        if (processors == null)
        {
            throw new ArgumentNullException("processors");
        }
        if (processors.Length == 0)
        {
            throw new ArgumentException("processors");
        }
        this.processors = processors;
    }
 
    public string Process(string text)
    {
        var workingText = text;
        foreach (var processor in processors)
        {
            workingText = processor.Process(workingText);
        }
        return workingText;
    }
}

Finally, the last piece needed is a factory which will put all the pieces together and spit them out as one usable object graph. So let's create an interface with a single (factory) method that receives a list of words to search for in the source text and returns a delegate that we can use to do the actual statistics aggregation.

public interface IAnalyzerFactory
{
    Func<string, IDictionary<string, Statistics>> GetAnalyzer(params string[] searchWords);
}

Implementations of this interface will build a custom object graph for each list of search words and handle the details of searching/aggregating. The delegate they pass back will search through one or more pieces of text and pass back the cumulative results. This requirement—needing to have a separate, state-bound analyzer for each set of search words—dictates that whatever is behind that interface should build a fresh object graph for each invocation of the factory method.

Starting out of the gate, we could simply do this using "poor man's dependency injection" as shown below:

public sealed class PoorMansAnalyzerFactory : IAnalyzerFactory
{
    private Tuple<ITextProcessor, IStatisticsAggregator> GetCompositionRoot(params string[] searchWords)
    {
        var wordCountProcessor = new WordCountProcessor(searchWords);
        return new Tuple<ITextProcessor, IStatisticsAggregator>(
            new CompositeProcessor(
                new CasingProcessor(),
                new WhiteSpaceProcessor(),
                new PunctuationProcessor(),
                wordCountProcessor),
            wordCountProcessor
        );
    }
 
    public Func<string, IDictionary<string, Statistics>> GetAnalyzer(params string[] searchWords)
    {
        var pair = GetCompositionRoot(searchWords);
        var processor = pair.Item1;
        var aggregator = pair.Item2;
 
        return (text) =>
        {
            processor.Process(text);
            return aggregator.Results;
        };
    }
}

Indeed, for this sample application the above implementation is more than adequate. However, real-world applications will likely be much, much more complex and may require the use of an IOC container to perform the registration and resolution of the object graph inside our factory.

So let's create another factory implementation that receives an IOC container as a dependency and then uses the container inside its factory method. Note the use of DependencyOverride to inject in dependencies that aren't known at registration time. This is an example of that second scenario that I was referring to above.

public sealed class IocAnalyzerFactory : IAnalyzerFactory
{
    private IUnityContainer container;
 
    public IocAnalyzerFactory(IUnityContainer container)
    {
        this.container = container;
    }
 
    public Func<string, IDictionary<string, Statistics>> GetAnalyzer(params string[] searchWords)
    {
        var pair = container.Resolve<Tuple<ITextProcessor, IStatisticsAggregator>>(new DependencyOverride<string[]>(searchWords));
        var processor = pair.Item1;
        var aggregator = pair.Item2;
 
        return (text) =>
            {
                processor.Process(text);
                return aggregator.Results;
            };
    }
}

Next, we'll create a bootstrapper class that sets up an IOC container to provide the same object graph. You'll notice that named registrations are used together with ResolvedParameter to provide the composite processor its array dependency. This is a fairly common scenario where you need to build up composites from pieces that are already registered in the container. What's slightly unusual is that the WordCountProcessor class has three separate registration instructions associated with it (the first one tells it what lifetime manager to use and the last two map the interfaces to the implementation). If you're familiar with Unity then you'll know that registering implementations to abstractions is only half the story; we also have to tell the container how to manage the lifetimes of the objects that get resolved. In this instance, since we have an implementation with two separate interfaces then we need to tell Unity to provide the same instance for each interface. However, we can't just create a singleton using either RegisterInstance or ContainerControlledLifetimeManager because we want a distinct object graph to come from the container every time we resolve. Quite a pickle, right? Well, we solve that problem by using the PerResolveLifetimeManager, IMO one of the more underappreciated lifetime managers that comes out of the box. This basically tells Unity "each time Resolve() is called, provide the same implementation of a given abstraction to anything that depends on it." The other registrations are fine using the default lifetime manager (TransientLifetimeManager) because each of them only gets injected once every time we resolve the object graph.

public sealed class ContainerBootstrapper
{
    public IUnityContainer RegisterTypes(IUnityContainer container)
    {
        return container
            .RegisterType<WordCountProcessor>(new PerResolveLifetimeManager())
            .RegisterType<ITextProcessor, CasingProcessor>("casing")
            .RegisterType<ITextProcessor, WhiteSpaceProcessor>("whiteSpace")
            .RegisterType<ITextProcessor, PunctuationProcessor>("punctuation")
            .RegisterType<ITextProcessor, WordCountProcessor>("wordCount")
            .RegisterType<ITextProcessor, CompositeProcessor>(
                new InjectionConstructor(
                    new ResolvedArrayParameter<ITextProcessor>(
                        new ResolvedParameter<ITextProcessor>("casing"),
                        new ResolvedParameter<ITextProcessor>("whiteSpace"),
                        new ResolvedParameter<ITextProcessor>("punctuation"),
                        new ResolvedParameter<ITextProcessor>("wordCount")
                        )))
            .RegisterType<IStatisticsAggregator, WordCountProcessor>()
            .RegisterType<Tuple<ITextProcessor, IStatisticsAggregator>>()
            .RegisterType<IAnalyzerFactory, IocAnalyzerFactory>()
            ;
    }
}

The main routine of our program looks something like this.

class Program
{
    private static void PrintResults(IDictionary<string, Statistics> results)
    {
        foreach (var kvp in results)
        {
            Console.WriteLine("{0,-7}  {1,5:g}  {2:p2}", kvp.Key, kvp.Value.Count, kvp.Value.Frequency);
        }
    }
 
    static void Main(string[] args)
    {
        var container = new ContainerBootstrapper().RegisterTypes(new UnityContainer());
 
        var factory = container.Resolve<IocAnalyzerFactory>();
 
        var inputText = File.ReadAllText("LoremIpsum.txt");
 
        var analyzer = factory.GetAnalyzer("lorem", "ipsum", "vitae");
 
        var results = analyzer(inputText);
 
        PrintResults(results);
 
        Console.WriteLine("Done.");
        Console.ReadKey();
    }
}

Let's run it and see what happens. The result?

Nothing. Absolutely nothing. So where did we go wrong?

The answer is inside the container. If you place a breakpoint in your code after the registration section you can look inside the Registrations property of the container and look for the problem. Let's take a look and see what we find.


Naive Registrations List

You'll notice right away that there is a different lifetime manager associated with the named registration called "wordCount". Rather than using the PerResolveLifetimeManager, as we expected, it is using the default TransientLifetimeManager, thus returning a different object instance at resolution time. Of course we weren't getting any results—the WordCountProcessor instance that's behind the IStatisticsAggregator interface is entirely different from the one that's behind the ITextProcessor interface. We can look at the object build plan by inspecting the container's policy list for more information on what's going on under the hood.


Naive Unity Container Policy List

What we're looking at is basically a list of strategies for building up an object graph. Each strategy represents some operation like "use this lifetime manager to manage this concrete type" or "map this interface to some concrete type". Also, take a close look at the properties that have names like ____BuildKey. This gives us a clue as to where we went wrong. At a fundamental level, Unity manages registrations using a key comprised of a type/string pair. The type component obviously refers to a given concrete/abstract .NET type and the string component is a name for the registration. If the string is null then that refers to the default registration. Both of those properties need to match in order for two keys to be semantically equivalent.

On the surface our problem is that the container is managing the named instance and the default instance under different lifetime managers. This is not what we wanted (one object instance, two interfaces) but it is exactly how the tool was always intended to work. If we registered the ITextProcessor interface for our word count processor implementation using the default (null) registration name then everything would work as planned and it would point to the same lifetime manager as the IStatisticsAggregator interface. Unfortunately we can't do that because the default registration for ITextProcessor is already referencing the CompositeProcessor.

So then the question becomes, how do we alter the policy list so that we go from this

MS Unity Two Lifetime Managers

to this?

MS Unity One Lifetime Manager

Well, one solution is to modify the build plan by updating the policy list. We can do that using a custom InjectionMember subclass.

If you have been using Unity for a while then you are already familiar with InjectionMember classes and what they do, which is change the way that registrations get resolved to concretes. For example, the InjectionConstructor class tells a specific registration to use a constructor in the concrete class that has a certain signature; the InjectionFactory class specifies that a factory method should supply the resolved reference, and so on. If we look at the Unity source code, we see that InjectionMember has the following description:

Base class for objects that can be used to configure what class members get injected by the container.

The class exposes an abstract method called AddPolicies with the following signature:

public abstract void AddPolicies(Type serviceType, Type implementationType, string name, IPolicyList policies);

This is what we need. When the AddPolicies method is invoked during build-up it will supply us with the name of the registration, the type that is being resolved (the target interface/abstract type) and the type of the implementation. All we need to do is supply a new BuildKeyMappingPolicy to the policy chain which instructs Unity to map a type from one named registration to another. If we can do that, then both will reference the same lifetime manager and, hence, resolve to the same object instance as long as we are using the PerResolveLifetimeManager. We can have our cake and eat it too. Here's what such a class might look like.

/// <summary>
/// Special injection member class that allows a registration to redirect to a registration with a different name.
/// For example, redirect a named registration to the default (null).
/// </summary>
public sealed class InjectionRedirect : InjectionMember
{
    private string redirectName;
 
    public InjectionRedirect(string redirectName = null)
    {
        this.redirectName = redirectName;
    }
 
    public override void AddPolicies(Type from, Type to, string name, IPolicyList policies)
    {
        var policy = new BuildKeyMappingPolicy(new NamedTypeBuildKey(to, redirectName));
        policies.Set<IBuildKeyMappingPolicy>(policy, new NamedTypeBuildKey(from, name));
    }
}

Our class is appropriately named InjectionRedirect because all that it does is redirect a given type mapping from one name to another. Fixing our broken container configuration code is as simple as adding a single instance of InjectionRedirect to the registration of the "wordCount" ITextProcessor, as shown below.

public sealed class ContainerBootstrapper
{
    public IUnityContainer RegisterTypes(IUnityContainer container)
    {
        return container
            .RegisterType<WordCountProcessor>(new PerResolveLifetimeManager())
            .RegisterType<ITextProcessor, CasingProcessor>("casing")
            .RegisterType<ITextProcessor, WhiteSpaceProcessor>("whiteSpace")
            .RegisterType<ITextProcessor, PunctuationProcessor>("punctuation")
            .RegisterType<ITextProcessor, WordCountProcessor>("wordCount", new InjectionRedirect())
            .RegisterType<ITextProcessor, CompositeProcessor>(
                new InjectionConstructor(
                    new ResolvedArrayParameter<ITextProcessor>(
                        new ResolvedParameter<ITextProcessor>("casing"),
                        new ResolvedParameter<ITextProcessor>("whiteSpace"),
                        new ResolvedParameter<ITextProcessor>("punctuation"),
                        new ResolvedParameter<ITextProcessor>("wordCount")
                        )))
            .RegisterType<IStatisticsAggregator, WordCountProcessor>()
            .RegisterType<Tuple<ITextProcessor, IStatisticsAggregator>>()
            .RegisterType<IAnalyzerFactory, IocAnalyzerFactory>()
            ;
    }
}

If we rerun our program against our fake lorem ipsum input text then we should actually see some results like this:

    lorem       30  0.63 %
    ipsum       46  0.97 %
    vitae       64  1.35 %
    Done.

Now it works! The "wordCount" ITextProcessor is resolving to the same reference as the IStatisticsAggregator.

Why don't we take a peek under the hood and see why this works.


MS Unity Registration List

Well, the registration list looks rather dubious. Going on this alone, it looks like the "wordCount" ITextProcessor would resolve to its own instance via a TransientLifetimeManager. What does the policy list show us?


MS Unity Policy List

That's much better. The build plan now has a BuildKeyMappingPolicy which is instructing Unity to map the "wordCount" ITextProcessor to the default WordCountProcessor. We've successfully redirected a named mapping to the default mapping for our chosen implementation. Pretty cool, huh?

Conclusion

An Inversion of Control container is a specialized tool that helps developers put the Dependency Inversion Principle into practice. An IOC container isn't necessary for this purpose, but it can act as a productivity booster, especially when using power features like registration by convention or dependency overrides. The Microsoft Unity framework is an IOC container that is generally very powerful and versatile, which is why I prefer it over some other IOC containers. In special circumstances, like when a system needs to resolve two different registrations—one of which is named and one which isn't—Unity can be extended in order to achieve the desired result. In this particular situation we created an InjectionMember subclass called InjectionRedirect, which allowed us to point a named registration to the default registration (or any other named registration), thus resolving to the same object instance.

You can download the full source for this example here.

How Functional Programming Found Me

I could say that the seeds were planted at a young age. Visiting EPCOT Center as a child, reading ample science fiction books, especially those by Isaac Asimov, having an interest in science and all things technological were enough to ignite my early interest in intelligent machines. As a teenager, I started reading books by Artificial Intelligence researcher Margaret Boden, which was how I first found out about LISP. In my early 20s I tinkered with ANSI Common LISP, but was disappointed in the seeming lack of a community, lack of a rich framework and toolbase, and poor interoperability with the leading frameworks of the day—Java and .NET. Moreover,

(all (of (the (parentheses (were (driving (me (batty)))))))).

So my brief foray into functional programming was halted prematurely while I increasingly absorbed myself in the dominant paradigm, object-oriented programming (for the remainder of this article whenever I refer to object-oriented programming I'm referring to the canonical, imperative style that is the norm when using an OOP language). And so I went on my way as a nice little C# developer, naively content in my myopic view of the world as being composed of objects while I indulged in polymorphism, design patterns, and the like. All of that changed in my late 20s, however, when one monumental .NET technology caused massive tectonic shifts in my software developer worldview—LINQ.

The first step in my transition to the functional world was when I realized that 60-80% of the data access code I was writing consisted of LINQ queries. Concomitant with that realization was a perspective I had developed in which I began to see the solutions to abstract problems as data streams, rather than things that set and modify values, then do stuff with those values.

The second step was when I noticed that I was increasingly using .NET delegates to implement what I quaintly dubbed "meta-methods," similar to that below:

bool InvokeSafe(Func<bool> action)
{
    try
    {
        return action();
    }
    catch (InvalidOperationException)
    {
        return false;
    }
}

At the time I naively thought I'd stumbled upon some powerful new dev technique, unaware that such patterns are the norm and a one of the pillars of functional programming, where they are idiomatically referred to as higher-order functions. The following (contrived) example shows what the equivalent code might look like in F#:

let invokeSafe func =
    try
        Some(func())
    with
    | :? InvalidOperationException -> None
    | _ -> reraise()

Indeed, as the C# language continues its transition into a hybrid OOP/functional language, such methods and extension methods have become commonplace in the .NET world.

Lastly, I had developed a renewed interest in Artificial Intelligence and various other abstract computational approaches. The functional programming style, by its very nature, lends itself readily to elegant, efficient, inherently parallelizable implementations of such algorithms.

The stage was set; I took the dive.

I chose to learn F# as my first "official" functional language because it is a Microsoft-sanctioned, first class .NET language that supports all the nifty frameworks and toolkits that I have come to know and love. Also, Don Syme and the rest of the F# crew put a great deal of effort into ensuring that F# plays nice with other .NET languages through its support of OOP and other idiomatic .NET features. More concisely, F# is a multi-paradigm language, just like C#, though it approaches that conceptual divide from the exact opposite direction. Not surprisingly, this allows applications, libraries, and components constructed using F# to dovetail nicely with those constructed using a classic OOP language like C#, paving the way for what I initially termed "hybrid applications," but should rightly be called multi-paradigm applications (more on this later).

And so as time flew by, and my skill and knowledge in the functional paradigm grew, I had a profound philosophical epiphany that transcended the realm of all things techy and geeky; veritably, it changed the way I view the world around me.

It's easy to view the world as constructed of things, which in turn move around and perform actions against other things—hence, the impetus for the creation of the first OOP languages to begin with. However, one may also view the world around oneself as constructed by doings; that is, what we perceive as reality is actually the product of long chains of interdependent quantum processes, going all the way back to some hypothetical First Cause.

From this vantage point, the world of object-orientation and its thing-centric bias toward abstraction rather resembles Georges Seurat's painting A Sunday Afternoon on the Island of La Grande Jatte—static, frozen, unmoving in its pointillist style.

Seurat - A Sunday Afternoon on the Island of La Grande Jatte

And the functional style in comparison? Perhaps more like post-surrealist modern art—colorful, dynamic, multidimensional. Now, this is not to say that I'm done with C# and all other OOP programming languages and techniques. Far from it. Rather, I now approach software development from a balanced perspective and with the understanding that OOP and FP are merely different problem-solving approaches, each more suited than the other for solving specific classes of problems. Like Yin and Yang, they both complement each other, and wise is the developer who knows not only where each is appropriate, but also how to use them together in a single application in order to solve challenging problems. In my humble opinion, such multi-paradigm applications, which combine both the imperative Yang of OOP with the declarative Yin of FP will truly represent the cutting edge, the realm of elites, in the years and decades to come.

Ying Yang

In closing, I now consider myself to be a functional software developer (while remaining a skilled object-oriented developer). While .NET is my current specialty, I do believe in staying open to new possibilities, which is why I have the likes of Scala, Clojure, Erlang, and Go on my radar. It's an exciting, dynamic world out there, and there's no way I'm going back!

 

Andrew Ng of Stanford Artificial Intelligence Laboratory on the Future of AI and Robotics

Andrew Ng, director of the Stanford Artificial Intelligence Laboratory (SAIL), on the future of robotics and AI. In this short lecture he talks about many of the problems facing AI researchers, yet gives hope for real progress in this field.

His sentiments in his closing remarks closely mirror my own:

So let me just close with a personal story. Ever since I was a kid I always wanted to work on AI and build smart robots and then I got older and got into college, and I started to learn about AI in college, and I learned how hard it was. It turns out that AI has given us tons of great stuff: AI has helped us build web search engines like Google and Bing, it has given us spam filters, it has given us tons of great stuff; but there has always been this bigger dream of not just building web search engines and spam filters but of getting machines that can see the world and think and understand the world and be intelligent the way that people are. For the longest time I gave up on that dream, and for many years as a professor I was even advising students to not think about that bigger AI dream... that's something I'm not that proud of now. It was only five years ago, when I learned about these ideas in neural science and machine learning, that the brain might be much simpler than we had thought and that it might be possible to replicate some of how the brain works in the computer and use that to build perception systems... that was the first time in my adult life when I felt like we might have a chance of making progress in this again... when I look at all of our lives I see all of us spending so much time in acts of mental drudgery, we spend so much time cleaning our houses, filling out silly paperwork, having to go shopping for trivial items. I think that if we make computers and robots smart enough to do some of these things for us, to free up our time for higher endeavors, what could be more exciting than that?

In future blog posts I'll likely be discussing this remarkable institution and some of the contributions its faculty have made to the fields of AI and computer science. Some heavy hitters like John McCarthy came out of SAIL, and I still think that original vision may be realized one day. One day...

Markov Chain Text Generator In F#

After spending a couple of months with my head down focusing on my day job and other life concerns I decided to get back to learning F#. So I dusted off the cobwebs and dove into a project that is somewhat trivial, yet fun and engaging enough to get me thinking in the Functional Style again—I decided to write a Markov Chain text generator.

In simple terms, a Markov chain is simply a string of probable states which are contingent upon the current state of a given system. For example, a Markov chain might be used to describe weather:

  • If it is sunny, then there is a 30% chance of rain tomorrow and a 70% chance it will be sunny again.
  • If it is rainy, then there is a 60% chance of rain tomorrow and a 40% chance it will be sunny.
  • And so on, and so forth...

Markov chains can also be useful for text analysis in that they can model what words are likely to follow any other given word in a text document. The program below does exactly that:

  1. open System
  2. open System.IO
  3. open System.Collections.Generic
  4. open System.Collections.Concurrent
  5. open System.Text.RegularExpressions
  6.  
  7. module Program =
  8. let fileName = @"..\..\magnacarta.txt"
  9. let numWordsToGenerate = 50
  10. let wordsRegex = new Regex(@"[A-z]+\'{0,1}[A-z]+", RegexOptions.Compiled)
  11. let rand = new Random()
  12.  
  13. let getLines (stream : Stream) =
  14. let sr = new StreamReader(stream)
  15. seq { while not <| sr.EndOfStream do yield sr.ReadLine() }
  16.  
  17. let getWords (line : string) =
  18. seq { for regexMatch in wordsRegex.Matches(line) do yield regexMatch.Value.ToLowerInvariant() }
  19.  
  20. let buildDict (stream : Stream) =
  21. let dict = new Dictionary<string, Dictionary<string, int>>()
  22. let addWord previous current =
  23. if not(dict.ContainsKey(previous)) then
  24. dict.Add(previous, new Dictionary<string, int>())
  25.  
  26. let dict2 = dict.[previous]
  27. if dict2.ContainsKey(current) then
  28. dict2.[current] <- dict2.[current] + 1
  29. else
  30. dict2.Add(current, 1)
  31. stream
  32. |> getLines
  33. |> Seq.map getWords
  34. |> Seq.concat
  35. |> Seq.pairwise
  36. |> Seq.iter (fun (previous, current) -> addWord previous current)
  37. dict
  38.  
  39. let buildMarkov (dict : Dictionary<string, Dictionary<string, int>>) =
  40. let markov = new Dictionary<string, (float * string) list>()
  41. for kvp in dict do
  42. let dict2 = kvp.Value
  43. let total = float (Seq.sum dict2.Values)
  44. let chain = [ for wordPair in dict2 do yield ((float wordPair.Value) / total, wordPair.Key) ]
  45. markov.Add(kvp.Key, chain)
  46. markov
  47.  
  48. let search (func : ('b -> 'a -> ('a option * 'b))) (initial : 'b) (items : seq<'a>) =
  49. let rec findIt (enum : IEnumerator<'a>) (acc : 'b) =
  50. if not(enum.MoveNext()) then
  51. None
  52. else
  53. let result = func acc enum.Current
  54. if Option.isSome <| fst result then
  55. Some(Option.get <| fst result)
  56. else
  57. findIt enum (snd result)
  58. findIt (items.GetEnumerator()) initial
  59.  
  60. let getRandWord (chain : (float * string) list) =
  61. let roll = rand.NextDouble()
  62. let result = search (fun (acc : float) (item : (float * string)) ->
  63. let myOption = if (roll <= acc + fst item) then Some(item) else None
  64. (myOption, acc + fst item))
  65. 0.0
  66. chain
  67. if Option.isNone result then failwith "Error getting random word." else snd <| Option.get result
  68.  
  69. [<EntryPoint>]
  70. let main _ =
  71. use fileStream = new FileStream(fileName, FileMode.Open)
  72. let markov = fileStream |> buildDict |> buildMarkov
  73. let firstWord = Seq.nth (rand.Next(markov.Count)) markov.Keys
  74. Seq.unfold (fun (word, count) -> if (count = numWordsToGenerate) then None else Some(word, (getRandWord markov.[word], count + 1))) (firstWord, 0)
  75. |> Seq.iter (printf "%s ")
  76.  
  77. Console.ReadLine() |> ignore
  78. 0

Let's examine this program in more detail.

Lines 13 - 37, the getLines, getWords and buildDict functions serve a single purpose, which is to dynamically read text from a stream, parse out the words, then keep a running count of which words follow each other word. Look at lines 31 - 36 in particular:

stream
    |> getLines
    |> Seq.map getWords
    |> Seq.concat
    |> Seq.pairwise
    |> Seq.iter (fun (previous, current) -> addWord previous current)

What this does, in a nutshell, is:

  1. Read each line from a stream.
  2. Break apart each line into a sequence of words.
  3. Smash together the sequence of sequences (Seq.concat) so that we have a single sequence of words—this is analogous to the SelectMany LINQ extension method you might have used in C#.
  4. Take each word and the one that follows it (Seq.pairwise).
  5. Add the word-combo to our dictionary.

The Seq.pairwise function is the hero of the day here. This underrated and rarely-used function fits perfectly in this application and keeps us working in the functional style.

It should be noted that for tallying up the count of the words I decided to use a dictionary of dictionaries (see line 21). While technically this is an imperative (hence, non-pure) style of programming, for performance reasons I felt it was a fine approach.

When all the counts have been acquired, we have a data structure that looks something like this:

Markov Chain

Each key in the main dictionary maps to another dictionary that contains a list of words and the count of each. From here it is easy to compute the probabilities for each word in each chain. That's where the buildMarkov function comes into play. All that this does is use Seq.sum to count up the total number of words in each chain, then divide each count by that total to come up with a probability value between 0.0 and 1.0. Now on to generating the words...

You'll notice that I implemented a special search higher-order function. As far as I can tell, there is no out-of-the-box function in F# that lets you search through a sequence while passing along an accumulator, yet this is precisely what we need. The first parameter to the search function is itself a function which:

  • Takes an accumulator value.
  • Takes a sequence item.
  • Returns Some(item) if the search criteria is met or None if it isn't, tupled to the next value of the accumulator.

The additional parameters are the initial value of the accumulator and the sequence to operate against.

The bulk of the work for this function is accomplished using the nested function called findIt. The astute reader will notice that this is a tail-recursive function—it consumes no stack space, hence can operate against a sequence of any size without running out of memory. To verify that this is the case, let's examine the body of the findIt function using Telerik's JustDecompile utility against the compiled executable. Here's what it looks like translated into C#:

while (@enum.MoveNext())
{
    Tuple<FSharpOption<a>, b> result = FSharpFunc<b, a>.InvokeFast<Tuple<FSharpOption<a>, b>>(this.func, acc, @enum.Current);
    if (OptionModule.IsSome<a>(Operators.Fst<FSharpOption<a>, b>(result)))
    {
        return FSharpOption<a>.Some(OptionModule.GetValue<a>(Operators.Fst<FSharpOption<a>, b>(result)));
    }
    acc = Operators.Snd<FSharpOption<a>, b>(result);
    @enum = @enum;
}
return null;

You'll notice that the F# compiler turned our "recursive" function into a while loop. Pretty cool!

Once we have the search function in our tool belt, the rest is easy. The getRandWord function uses search to pick a random word from a given Markov chain by accumulating the probabilities as it moves along. So if the first item in the chain has a probability of 0.25, the next item has a probability of 0.50, and the random number generator rolls a 0.76, then it will select (you guessed it) the third item.

The generation of the actual words is accomplished using my favorite F# function, Seq.unfold. Line 74 simply takes a count value and an initial word (state) to "unfold" the next word in the sequence, or return None if the max count has been reached.

The output of the program looks something like this when using the Magna Carta as input.

services and sworn knights cross as is responsible for god and by the owner of that it shall fail to bring with four barons shall have all evil tolls except those possessions or to be given or if any such thing be responsible to attach and the common counsel of

While it doesn't make a lot of sense grammatically, it does have some syntactic resemblance to natural English language. In fact, now you have an idea of how spammers try to fool spam detection systems. More noble uses would include word suggestion algorithms in search applications (e.g. Google).

So that's it for basic text analysis using Markov Chains in F#.

Happy coding!

Download F# Source

Are Design Patterns Really Anti-Patterns?

When I first read the Gang of Four's monumental book Design Patterns: Elements of Reusable Object-Oriented Software, I thought that I had discovered the Holy Grail of software development. I was amazed at the power and flexibility that design patterns afforded me in solving difficult problems, the seeming elegance bestowed upon the humble programmer who was constantly embroiled in battle against the demons of ever widening problem-space complexity.

As so often happens to those who seek continuous improvement, however, very large tectonic shifts in my worldview started occurring as I learned more and more about the theory behind software and started opening myself to different paradigms of programming.

Buzzword Bingo

As more and more recruiters identified Design Patterns as a "hot item" on my resume I got an increasingly uneasy feeling, not because it's a frivolous skill to have—design patterns are useful in a number of scenarios—but because people I talked to didn't understand why they were useful. Moreover, I find that a lot of programmers who should know better see them as a silver bullet instead of a set of tools that are appropriate in specific contexts.

Failure is Always an Option

Not only is failure always an option, it is necessary for growth. One of my big pet projects that I've worked on/off again the past few years is a stock market analysis engine called Continuum. My intent behind the last iteration was to create a genetic algorithm running behind a back testing engine. The genetic algorithm would iterate against a number of historical data sets and over time evolve an effective trading strategy consisting of technical and fundamental indicators. Simple, right? Nope.

Even with all my knowledge of loose coupling, abstraction, and other architectural best practices I found that the solution to this problem was still very hard for me to conceptualize. After playing with a bunch of reflection-based approaches and something I dubbed a "meta-interface," my project slammed into a brick wall. I put it on hold and pursued other endeavors. Little did I know at the time, there in fact is a tool which lends itself very well to this problem (partial function applications) but it is not available in the world of object-oriented programming.

OOP is Fundamentally Broken

After my setback with Continuum I started to wonder if I wasn't barking up the wrong tree entirely using an object-oriented approach. In addition, I witnessed a number of programmers in the "professional" workplace nonchalantly employing horrific OOP practices such as:

  • Using inheritance to extend the behavior of a class/component.
  • Creating "God" classes containing hundreds of properties and/or methods.
  • Neglecting the power of OOP entirely and just using C# to write really bad procedural code.

People smarter than I have pointed out that object-oriented languages likely weren't even implemented correctly in the first place! As it all sunk in, I came to realize that:

  1. There is a better way.
  2. It's conceivable that OOP design patterns, especially those of the behavioral variety, are hacks which attempt to compensate for fundamental shortcomings of the OOP paradigm.

Around this time I also realized that more than half the C# code I was writing consisted of LINQ query expressions and lambdas.

I was ready for the next step...

Functional Programming in the .NET World

I began teaching myself F#, Microsoft's "official" functional programming language for the .NET stack, and immediately fell in love.

The declarative style of the language jived well with my style of thinking and made it seem almost effortless for me to implement complex abstractions and algorithms.

Philosophically, I think it's fun to imagine that the universe around us is really built from processes instead of things. For instance, a person isn't a concrete object with properties and behaviors but is rather a process of life that changes and adapts over time. From this perspective, functional programming paradoxically lends a more accurate representation of the real world than OOP.

More pragmatically, functional programming languages are far better suited to representing complex algorithms because they facilitate behavioral composition as opposed to state composition (OOP).

The Proof is in the Pudding

In the next few blog entries I will set out to show how a functional programming language, F#, may be used to implement many of the classic Gang of Four design patterns in a functional, declarative, and (hopefully) much more elegant style. I will begin with some of the low-hanging fruit.

Let's see what the Chain of Responsibility pattern might look like in a functional style as opposed to a standard C#, object-oriented implementation...

Next up: A functional version of the Chain of Responsibility

Pages

Subscribe to