Turing Machine Simulation in C#

Introduction

Alan Turing’s idea of building a universal computing machine was truly revolutionary and it changed the face of the world. One extraordinarily simple machine capable of carrying out any computation seems impossible. This blog post is a laconic look at the history and operation of the Universal Turing Machine. The goal is to whet the appetite of the uninitiated and inspire them to seek out a deeper understanding of computation.

History

In 1936, Alan Turing published his famous “On Computable Numbers” paper. It was not his intention to invent a computer. In fact, the machine outlined in the paper was not initially meant to be implemented mechanically. The Automatic Computing Machine (now known as Universal Turing Machine), as he termed it, was nothing more than a mathematic concept. Turing did all of his computation with a fountain pen and paper.

Turing’s true ambition was to solve the famous “Entscheidungsproblem”. In a nutshell, he used the concept of an automatic computing machine to prove that there are some sequences of numbers that are impossible to compute. His proof is closely tied to the notorious Halting Problem.

In Turing’s time, the word computer had a very different meaning. Computer was a job description. Mathematicians painstakingly wrote out precise directions for computers. This way, a person with little background in arithmetic could perform computation without really understanding the overall implications of what they were doing. These instructions are what inspired Turing and they are reflected in the implementation of his automatic computing machine.

What’s most amazing about Turing’s contemplation of the automatic computing machine is that more than eighty years later, we’ve yet to come up with a more powerful computational model. We have more efficient means of computation, but none of them can solve any problems that the original machine could not. Extraordinary to say the least!

Universal Turing Machine

The Universal Turing Machine is elementary. If you’ve ever built a state machine, this will all start to look very familiar. The machine only has 4 components.

  1. Paper Tape
  2. Printer
  3. Scanner
  4. Transition Table

The paper tape is a theoretically infinite piece of paper sectioned off into squares. Each square is meant to hold a single character. The printer and scanner are mounted together on a head that move as a unit. The printer can print a single character to the tape and the scanner can read a single character from the tape. The head can only move one square of tape at a time. The real magic happens in the transition table, or “table of states of mind” as Turing called them (remember Turing’s idea of a computer was a human). The table is a list of instructions in the form of: If the machine is in state A and the scanner reads character B, print character C, move the head in D direction and place the machine in state E. ABCDE are all variables.

In order to perform a computation, information goes on the tape, the machine gets an initial state, the transition table is loaded, and it’s “off to the races” following the instructions in the transition table. Once the machine reaches its’ final state, the tape will hold the computed answer. That is all that is required to perform any computation. Such exquisite simplicity!

Programmability

Turing’s was not the first computation machine. In fact, many had come before him. However, his machine had something truly exceptional: programmability. A physical machine could conceivably contain a single physical transition table. Turing created a physical transition table that could read any number of logical transition tables from the tape. This was truly the “Hello World” of computer programming.

Turing used something he coined “Standard Description” to create an initial transition table capable of reading any other transition table from the tape. Many consider this to be the world’s first programming language. Concepts extracted from his work such as symbol tables and m-functions are still in use today.

The notion of a machine that can emulate any other machine is known as Turing Completeness. The ramifications of this are seemingly endless. The whole of the computer industry is built on this concept. The sheer power and simplicity are mind boggling.

Simulation

Now comes the fun part! Let’s build a Turing machine simulation in C#. Please take note that this is only a thought experiment to demonstrate the basic structure of a Turing machine. Some of the more convoluted details such as e-tape/f-tape, encoding, and reading instructions from the tape are left out for the sake of brevity. That being said, with an infinite amount of time it’s entirely possible to compute any possible computation using this simulation and a proper initial transition table.

I’m only giving a short synopsis of the code below. Everything is written in a somewhat functional style with no mutation. I’m sure this could be up for debate, but if you choose to debate it you’re missing the point of the post… If you have any questions or comments, feel free to comment or contact me directly. I’d love to speak with you about it. The full code is available on github: https://github.com/dalealleshouse/TuringMachine

First, we have a Head that consists of the tape, printer, and scanner. The tape is just an IEnumerable of characters that automatically grows as needed (fun fact: Turing was also instrumental in the idea of recursive enumeration). Each character in the IEnumerable represents a single square on the paper tape. The class has methods that read from the tape (scanner), write to the tape (printer), and move the head position. One special thing to note is the override of the ToString method which will return the data on the tape in a human readable form.

using System;
using System.Collections.Generic;
using System.Linq;

namespace TuringMachine
{
    public class Head
    {
        public const char Blank = '_';

        public Head(IEnumerable tape, int headPosition)
        {
            if (tape == null) throw new ArgumentNullException(nameof(tape));

            var safeData = tape as char[] ?? tape.ToArray();
            if (headPosition > safeData.Count() - 1 || headPosition < 0)
                throw new IndexOutOfRangeException("Invalid head position");

            Tape = safeData;
            HeadPosition = headPosition;
        }

        public IEnumerable Tape { get; }

        public int HeadPosition { get; }

        public Head Write(char head) => new Head(new List(Tape) { [HeadPosition] = head }, HeadPosition);

        public Head MoveLeft() => HeadPosition == 0
            ? new Head(new[] { Blank }.Concat(Tape), 0)
            : new Head(Tape, HeadPosition - 1);

        public Head MoveRight() => HeadPosition == Tape.Count() - 1
            ? new Head(Tape.Concat(new[] { Blank }), HeadPosition + 1)
            : new Head(Tape, HeadPosition + 1);

        public Head Move(HeadDirection direction)
        {
            switch (direction)
            {
                case HeadDirection.Left:
                    return MoveLeft();
                case HeadDirection.NoMove:
                    return this;
                case HeadDirection.Right:
                    return MoveRight();
                default:
                    throw new ArgumentOutOfRangeException(nameof(direction), direction, null);
            }
        }

        public char Read() => Tape.ElementAt(HeadPosition);

        public override string ToString() => $@"Tape: {Tape.Select(GetChar).Aggregate((agg, next) => agg + next)}";

        private string GetChar(char c, int index) => index == HeadPosition ? $"({c})" : c.ToString();
    }
}

Next, let’s turn our attention to the transition table. Below is a POCO to hold transition data. A transition table is an IEnumerable of transition objects. State is an integer value and HeadPostion is an Enum composed of Left, No Move, and Right.

namespace TuringMachine
{
    public class Transition
    {
        public Transition(int initialState, char read, char write, HeadDirection headDirection, int nextState)
        {
            InitialState = initialState;
            Read = read;
            Write = write;
            HeadDirection = headDirection;
            NextState = nextState;
        }

        public int InitialState { get; }

        public char Read { get; }

        public char Write { get; }

        public HeadDirection HeadDirection { get; }

        public int NextState { get; }
    }
}

The last piece of the puzzle is the machine itself. A machine is initialized with a state, a Head object, and a transition table. The interesting part of this class is the step method. For our purposes, I’ve defined any state less than 0 to denote a special stop state (error or halt). If the machine is in a stop state, it will no longer process transitions. If the machine is unable to find a suitable transition, it goes into an error state (fun fact: the fact that this machine can go into an error state makes it an undeterministic machine as opposed to a deterministic machine). If it finds a suitable transition, it applies the defined data and returns a reconfigured machine.

using System;
using System.Collections.Generic;
using System.Linq;

namespace TuringMachine
{
    public class Machine
    {
        public Machine(int state, Head head, IEnumerable transitionTable)
        {
            if (head == null) throw new ArgumentNullException(nameof(head));
            if (transitionTable == null) throw new ArgumentNullException(nameof(transitionTable));

            State = state;
            Head = head;
            TransitionTable = transitionTable;
        }

        public int State { get; }

        public Head Head { get; }

        public IEnumerable TransitionTable { get; }

        public Machine Step()
        {
            if (State < 0) return this;

            return
                TransitionTable
                    .Where(t => t.InitialState == State && t.Read == Head.Read())
                    .DefaultIfEmpty(new Transition(0, Head.Blank, Head.Read(), HeadDirection.NoMove,
                        TuringMachine.State.Error))
                    .Select(
                        t => new Machine(t.NextState, Head.Write(t.Write).Move(t.HeadDirection), TransitionTable))
                    .First();
        }

        public Machine Run()
        {
            var m = this;

            while (m.State >= 0)
                m = m.Step();

            return m;
        }
    }
}

That’s all we need! Let’s start off easy by declaring a transition table that will add two positive numbers. We’ll represent the numbers on the tape by a series of “1” characters separated by a blank. Our transition table is below.

using System.Collections.Generic;
using System.Resources;

namespace TuringMachine
{
    public static class TransitionTableGenerator
    {
        public static IEnumerable Addition() => new[]
        {
            new Transition(0, Tape.Blank, Tape.Blank, HeadDirection.Right, 0),
            new Transition(0, '1', '1', HeadDirection.Right, 1),
            new Transition(1, Tape.Blank, '1', HeadDirection.Right, 2),
            new Transition(1, '1', '1', HeadDirection.Right, 1),
            new Transition(2, Tape.Blank, Tape.Blank, HeadDirection.Left, 3),
            new Transition(2, '1', '1', HeadDirection.Right, 2),
            new Transition(3, Tape.Blank, Tape.Blank, HeadDirection.Left, 3),
            new Transition(3, '1', Tape.Blank, HeadDirection.Left, 4),
            new Transition(4, Tape.Blank, Tape.Blank, HeadDirection.NoMove, State.Halt),
            new Transition(4, '1', '1', HeadDirection.Left, 4)
        };
    }
}

The test below shows the machine in action adding 3 and 2. I highly recommend stepping through the code in order to really grok all of this. The answer is returned on the tape as a series of 5 “1” characters.

[TestMethod]
public void AddTwoNumbers()
{
    const string expected = "Head: (_)11111__";
    var sut = new TuringMachine.Machine(
        0,
        new TuringMachine.Head(new[] { '1', '1', '1', TuringMachine.Head.Blank, '1', '1' }, 0),
        TransitionTableGenerator.Addition());

    var result = sut.Run();
    Assert.AreEqual(expected, result.Head.ToString());
}

OK, that’s not exactly an impressive result. Let’s see if we can do something slightly more complicated. Using the same input, let’s multiply the two numbers. All we need is a different transition table.

using System.Collections.Generic;
using System.Resources;

namespace TuringMachine
{
    public static class TransitionTableGenerator
    {
        public static IEnumerable Multiplication() => new[]
        {
            new Transition(0, Tape.Blank, Tape.Blank, HeadDirection.Right, 1),
            new Transition(0, '1', Tape.Blank, HeadDirection.Right, 2),
            new Transition(1, Tape.Blank, Tape.Blank, HeadDirection.Right, 14),
            new Transition(1, '1', Tape.Blank, HeadDirection.Right, 2),
            new Transition(2, Tape.Blank, Tape.Blank, HeadDirection.Right, 3),
            new Transition(2, '1', '1', HeadDirection.Right, 2),
            new Transition(3, Tape.Blank, Tape.Blank, HeadDirection.Left, 15),
            new Transition(3, '1', Tape.Blank, HeadDirection.Right, 4),
            new Transition(4, Tape.Blank, Tape.Blank, HeadDirection.Right, 5),
            new Transition(4, '1', '1', HeadDirection.Right, 4),
            new Transition(5, Tape.Blank, '1', HeadDirection.Left, 6),
            new Transition(5, '1', '1', HeadDirection.Right, 5),
            new Transition(6, Tape.Blank, Tape.Blank, HeadDirection.Left, 7),
            new Transition(6, '1', '1', HeadDirection.Left, 6),
            new Transition(7, Tape.Blank, '1', HeadDirection.Left, 9),
            new Transition(7, '1', '1', HeadDirection.Left, 8),
            new Transition(8, Tape.Blank, '1', HeadDirection.Right, 3),
            new Transition(8, '1', '1', HeadDirection.Left, 8),
            new Transition(9, Tape.Blank, Tape.Blank, HeadDirection.Left, 10),
            new Transition(9, '1', '1', HeadDirection.Left, 9),
            new Transition(10, Tape.Blank, Tape.Blank, HeadDirection.Right, 12),
            new Transition(10, '1', '1', HeadDirection.Left, 11),
            new Transition(11, Tape.Blank, Tape.Blank, HeadDirection.Right, 0),
            new Transition(11, '1', '1', HeadDirection.Left, 11),
            new Transition(12, Tape.Blank, Tape.Blank, HeadDirection.Right, 12),
            new Transition(12, '1', Tape.Blank, HeadDirection.Right, 13),
            new Transition(13, Tape.Blank, Tape.Blank, HeadDirection.NoMove, State.Halt),
            new Transition(13, '1', Tape.Blank, HeadDirection.Right, 13),
            new Transition(14, Tape.Blank, Tape.Blank, HeadDirection.NoMove, State.Halt),
            new Transition(14, '1', Tape.Blank, HeadDirection.Right, 14),
            new Transition(15, Tape.Blank, Tape.Blank, HeadDirection.Left, 16),
            new Transition(15, '1', Tape.Blank, HeadDirection.Left, 15),
            new Transition(16, Tape.Blank, Tape.Blank, HeadDirection.NoMove, State.Halt),
            new Transition(16, '1', Tape.Blank, HeadDirection.Left, 16)

        };
    }
}

Below is the multiplication test. The answer is indicated by a string of 6 “1” characters on the tape.

[TestMethod]
public void MultiplyTwoNumbers()
{
    const string expected = "Head: ______(_)111111";
    var sut = new TuringMachine.Machine(
        0,
        new TuringMachine.Head(new[] { '1', '1', '1', TuringMachine.Head.Blank, '1', '1' }, 0),
        TransitionTableGenerator.Multiplication());

    var result = sut.Run();
    Assert.AreEqual(expected, result.Head.ToString());
}

Conclusion

I hope you enjoyed this whirlwind tour of Turing machines as much as I enjoyed writing it. There are much deeper concepts just under the surface and I hope I’ve piqued your interest enough to make you hungry for more. My ambition is that this post sends you on a journey into the exciting world of computability. Don’t be satisfied with merely knowing enough to write programs; keep digging until you master the domain. I’ll leave you with a couple book recommendations that I’m sure you’ll find invigorating.

  • Understanding Computation: From Simple Machines to Impossible Programs - Tom Stuart
  • Introduction to Automata Theory, Languages, and Computation - John E. Hopcroft , Rajeev Motwani, Jeffrey D. Ullman

If there is enough interest, I may do a follow up to this post on how to do pattern matching and some simple regular expression parsing using the Turing machine simulation.

As always, thanks for reading and I would love to hear from you.

Easy Immutable Objects in C#

Aristotle said, “Change in all things is sweet.” With all due respect to the great philosopher, he obviously never had to write software…

Head on over to Stack Overflow and search for “Immutable Object Patterns in C#” and you will see that this is a point of contention for many developers. Creating immutable objects in C# is cumbersome at best. What if I told you there is a practically effortless way to accomplish this with about one quarter of the code that is used in typical examples. I knew that would get your attention! Hang on tight while I walk you through an exciting demonstration!

As a side note, I’m not going to try to sell anyone on immutability in this post. There are countless other articles out there with that purpose. From here forward, I’m going to assume the reader understands why and when they need immutable objects.

The Problem

It’s a typical Friday night, when the phone rings. It’s NASA again (sigh…), and they need another brilliant celestial program in the key of C#. So much for relaxing, duty calls… After contemplating the specs, it’s obvious that an immutable planet class is a requirement. Let’s get started.

Typical C# Solution

In order to create the planet object in C#, you must create a constructor that accepts all property values and then sets those property values in the constructor body. This is a fairly recent addition to C#. In older versions you also had to create backing fields for each property. Additionally, it’s wise to override the equals method because by default C# uses reference equality. This could be a topic for debate and your mileage may vary; however, for the sake of argument let’s just assume we want value equality for planet objects. Another debatable topic may be whether to use a struct or a class. This example uses a class because C# will always create default parameterless constructors for structs. It doesn’t really make sense to have an instance of a planet that cannot change and is initialized without values. The result is the code below.

public class Planet { public Planet( string name, decimal massKg, decimal equatorialDiameterKm, decimal polarDiameterKm, decimal equatorialCircumferenceKm, decimal orbitalDistanceKm, decimal orbitPeriodEarthDays, decimal minSurfaceTemperatureCelsius, decimal maxSurfaceTemperatureCelsius) { this.Name = name; this.MassKg = massKg; this.EquatorialDiameterKm = equatorialDiameterKm; this.PolarDiameterKm = polarDiameterKm; this.EquatorialCircumferenceKm = equatorialCircumferenceKm; this.OrbitalDistanceKm = orbitalDistanceKm; this.OrbitPeriodEarthDays = orbitPeriodEarthDays; this.MinSurfaceTemperatureCelsius = minSurfaceTemperatureCelsius; this.MaxSurfaceTemperatureCelsius = maxSurfaceTemperatureCelsius; } public string Name { get; } public decimal MassKg { get; } public decimal EquatorialDiameterKm { get; } public decimal PolarDiameterKm { get; } public decimal EquatorialCircumferenceKm { get; } public decimal OrbitalDistanceKm { get; } public decimal OrbitPeriodEarthDays { get; } public decimal MinSurfaceTemperatureCelsius { get; } public decimal MaxSurfaceTemperatureCelsius { get; } public override bool Equals(object obj) { if (ReferenceEquals(null, obj)) { return false; } if (ReferenceEquals(this, obj)) { return true; } return obj.GetType() == this.GetType() && this.Equals((Planet)obj); } protected bool Equals(Planet other) => string.Equals(this.Name, other.Name) && this.MassKg == other.MassKg && this.EquatorialDiameterKm == other.EquatorialDiameterKm && this.PolarDiameterKm == other.PolarDiameterKm && this.EquatorialCircumferenceKm == other.EquatorialCircumferenceKm && this.OrbitalDistanceKm == other.OrbitalDistanceKm && this.OrbitPeriodEarthDays == other.OrbitPeriodEarthDays && this.MinSurfaceTemperatureCelsius == other.MinSurfaceTemperatureCelsius && this.MaxSurfaceTemperatureCelsius == other.MaxSurfaceTemperatureCelsius; public override int GetHashCode() { unchecked { var hashCode = (this.Name?.GetHashCode() ?? 0); hashCode = (hashCode * 397) ^ this.MassKg.GetHashCode(); hashCode = (hashCode * 397) ^ this.EquatorialDiameterKm.GetHashCode(); hashCode = (hashCode * 397) ^ this.PolarDiameterKm.GetHashCode(); hashCode = (hashCode * 397) ^ this.EquatorialCircumferenceKm.GetHashCode(); hashCode = (hashCode * 397) ^ this.OrbitalDistanceKm.GetHashCode(); hashCode = (hashCode * 397) ^ this.OrbitPeriodEarthDays.GetHashCode(); hashCode = (hashCode * 397) ^ this.MinSurfaceTemperatureCelsius.GetHashCode(); hashCode = (hashCode * 397) ^ this.MaxSurfaceTemperatureCelsius.GetHashCode(); return hashCode; } } }

Wow, that’s a lot of code. Looking ahead, let’s imagine what it will take to add a new property in the future. All the following changes are required:

  1. Constructor arguments
  2. Constructor body
  3. Properties
  4. Equals method
  5. GetHashCode method

That’s a ton of changes with several opportunities for error. All that typing! My fingers are sore!

A Better Way

Fortunately, there is a better way to create the planet class! The answer is, use F#. I know what you’re thinking, “Wait, hold the presses! Look at the title of this blog post!”. Hold on, allow me to elucidate. I’ll first put you at ease by telling you that you don’t even need to learn F# to use this solution. You just need to create a simple F# project and reference it from your C# project. Because F# is a dot net language, F# libraries are entirely accessible to C#.

F# has a construct known as a record type that mimics the behavior of the C# class shown above. The best part is that record types are effortless to define. Below is the code required to create a planet class that behaves identically to the C# class defined above.

type Planet = { Name: string; MassKg: decimal; EquatorialDiameterKm: decimal; PolarDiameterKm: decimal; EquatorialCircumferenceKm: decimal; OrbitalDistanceKm: decimal; OrbitPeriodEarthDays: decimal; MinSurfaceTemperatureCelsius: decimal; MaxSurfaceTemperatureCelsius: decimal }

You don’t get much more concise and maintainable than that! Adding new properties is a relative breeze.

What I like most about this solution is that it acts as a “gateway drug”. There are many situations where F# offers significant advantages. However, many developers are intimidated by taking a big leap into a new language. How do you sell it to your boss? Where do you begin? This is a very pain free way to get your F# “foot in door”.

Conclusion

Using an F# library for immutable objects reduces required code by an amazing amount. Additionally, it eradicates error prone maintenance. With this new weapon in our arsenal, we can knock out that program for NASA and be done in time to curl up on the couch with a cigar and scotch before bed. Yay for humanity!

If you need more concrete examples, I encourage you to go have a look at the accompanying github repository: https://github.com/dalealleshouse/ImmutableExample. Download the source code, and notice that there are 4 projects. A C# domain project, an F# domain project, a C# planet repository project, and a test project. Change the reference in the planet repository project back and forth from the C# and F# projects in order to demonstrate the solution.

I hope this solution saves you as much time and trouble as it has me. As always, thank you for reading and feel free to contact me with any questions.

Recursion – Good, Bad, or Indifferent?

For developers using imperative languages (C, C++, C#, Java, Python, etc…), recursion can seem arcane. It’s just not something encountered regularly. However, recursion is a staple of functional programming. Given the functional programming renaissance, it may be time to “bone up”. Even if you have no interest in learning a functional language, functional concepts have many benefits that can be applied to imperative programming (i.e. LINQ, yeah, who doesn’t LOVE that). This blog post is meant to give a very broad overview of recursion for developers who don’t use it much.

WTF is Recursion?

In order to understand recursion one must first understand recursion. Yeah, I know, that’s a really old joke. Moving on…

There are heaps of rather byzantine definitions floating around. However, for our purposes we are going to say that a recursive method is one that calls back to itself. This is best demonstrated via example. Consider the following function that calculates the greatest common divisor of 2 numbers.

private int GreatestCommonDivisor(int x, int y) { return y == 0 ? x : GreatestCommonDivisor(y, x % y); }

Make sure you fully grok that function before reading on. There is a lot happening in those few lines of code.

Most recursive functions can also be written iteratively. In other words, recursive functions can be rewritten using looping constructs (while, for, etc…). See the example below.

private int GreatestCommonDivisor(int x, int y) { while (true) { if (y == 0) break; var remainder = x % y; x = y; y = remainder; } return x; }

The two functions above are commensurate. So, why would one choose one over the other? Read on! More about this in the next section.

The Bad

In imperative programming languages, recursive functions should be avoided in most cases (please, no hate mail about how this isn’t true 100% of the time). Recursive functions are less efficient than their iterative counterparts. Additionally, they are subject to the perils of stack overflows. Why is this true? I’m glad you asked. Let’s consider a greatly simplified version of what happens when a function is invoked.

  1. function arguments, variables, and return address are pushed on the stack
  2. control jumps to the function
  3. function code runs
  4. function results are copied into the return value
  5. stack is rewound to it’s previous position (memory is reclaimed)
  6. control jumps back to the caller

Often times, all of the above consumes more resources than looping. Therefore, recursive method calls are less performant.

The bigger problem is that the call stack is allocated a relatively meager amount of memory (varies wildly depending on the platform). Exceeding this causes the dreaded stack overflow exception to rear it’s ugly head. Each function call eats up space on the stack like a donkey eating a waffle. That space isn’t reclaimed until the function returns. As a total SWAG, I wouldn’t trust a recursion depth of more than about a thousand. Of course, this number varies wildly depending on the platform and amount of stack space the function consumes.

Methods that employ iteration do not suffer from any of the problems outlined in this section. In spite of that, there are still some good reasons to use recursion. Read on my friend!

The Good

As demonstrated above, recursive functions are generally shorter and more elegant. In the words of the great Donald Knuth, “premature optimization is the root of all evil”. Unless your application is extremely performance critical, chances are you will never notice the few extra microseconds. The added benefit of terse and expressive code far outweighs the performance hit. Obviously, stack overflow exceptions aren’t going away. However, if the estimated recursion depth is modest there is no reason to avoid recursion. Put succinctly, if your use case is not performance critical and the estimated recursion depth is reasonable, it’s a good candidate for recursion.

Now wait a minute, I said that stack overflows aren’t going away but I also said that recursion is a staple for functional programming. How can both of these statements be true? Three words: tail call optimization. Many functional languages employ this witchery. In a nutshell, here’s what happens. If a function’s return expression is a result of a function call, the stack frame is reused instead of pushing a new one on the call stack. That’s all there is to it! Wouldn’t it be wondrous if imperative languages did this? Maybe, someday…

Wrap This Up Already

Recursion is a useful technique for making code terse and comprehensible. However, it is less performant and breeds stack overflow exceptions in non tail call optimized languages. Carefully scrutinize your use case when choosing between recursive and iterative functions.

Thanks for reading!

Constructing the SUT (System Under Test) – Eradicating Brittle Unit Tests

I’m not going to proselytize unit testing in this blog post, there are hoards of articles on the internet for that already. Let’s just agree, for arguments sake, that they do awesome things for any software project. In spite of this majesty, brittle unit tests can suck the life out of programmers. There are many reasons for test frailty (a topic for another time), but the main one I’m going after in this piece is adding dependencies. In short, adding a new dependency to any class makes the existing tests fail. Is there anyway of getting around this? Yes there is!

As a side note: In a perfect world, software would be architected so elegantly that adding dependencies would be unnecessary. Unfortunately, I don’t live in that world. If you know how to get there please send me directions! That being said, adding dependencies may be a sign that you aren’t adhering to the single responsibility principal. Just something to keep in mind… Regardless, the pattern laid out below has made my life easier.

The Developer and the Brittle Test

Once upon a time, in a land far far away, our hero, writes the following really interesting service.

public class ReallyInterstingService { private readonly IDoSomethingAwesome _doSomethingAwesome; public ReallyInterstingService(IDoSomethingAwesome doSomethingAwesome) { this._doSomethingAwesome = doSomethingAwesome; } public string InterstingMethod() { return this._doSomethingAwesome.ToString(); } }

This really interesting service needs tests. Our hero, being a true hero, used TDD so he wrote the tests below before ever writing the service. Problem solved!

[TestClass] public class ReallyInterstingServiceShould { [TestMethod] public void ReturnString() { var awesomeMock = new Mock<IDoSomethingAwesome>(); var sut = new ReallyInterstingService(awesomeMock.Object); var result = sut.InterstingMethod(); Assert.IsInstanceOfType(result, typeof(string)); } }

The tests are fantastic! Anyone can refractor without fear. Life is good! However, as with any great story, along comes the antagonist: the evil manager. Management demands our hero to befoul really interesting service with some inanity. After a long battle, our hero concedes and makes the modifications below.

public class ReallyInterstingService { private readonly IDoSomethingAwesome _doSomethingAwesome; private readonly IDeathToAwesome _deathToAwesome; public ReallyInterstingService(IDoSomethingAwesome doSomethingAwesome, IDeathToAwesome deathToAwesome) { this._doSomethingAwesome = doSomethingAwesome; this._deathToAwesome = deathToAwesome; } public string InterstingMethod() { return this._doSomethingAwesome.ToString(); } public string LoadOfTripe() { return this._deathToAwesome.ToString(); } }

As you can see, a new dependency was added and now all the beautiful tests have failed. Woe to the kingdom. Our hero is vexed! How could he have foreseen this tragedy? What can he do to protect the program against such calamity in the future?

After a long quest our hero stumbles upon the humble author’s DotNetTestHelper open source project. It’s an incredibly simple library still in it’s infancy, but it has something wonderful: SutBuilder! He refractors the test as follows.

[TestClass] public class ReallyInterstingServiceShould { [TestMethod] public void ReturnString() { var awesomeMock = new Mock<IDoSomethingAwesome>(); var sut = new SutBuilder<ReallyInterstingService>() .AddDependency(awesomeMock.Object) .Build(); var result = sut.InterstingMethod(); Assert.IsNotNull(result); Assert.IsInstanceOfType(result, typeof(string)); } }

What wizardry is this say you? The SUT was constructed without the added dependency! The test is also protected against added dependencies in the future. The kingdom is saved! They lived happily ever after.

The End

Ok Ok Ok, that was a bit absurd. Anyway…

SutBuilder is a utility I wrote as part of an open source project of dot net testing utilities. The full source code is available here. What it does is simple: it constructs an instance of the generic type parameter. See the code below.

// These two statements have identical results sut = new ReallyInterstingService( new Mock<IDoSomethingAwesome>().Object, new Mock<IDeathToAwesome>().Object); sut = new SutBuilder<ReallyInterstingService>().Build();

Note: I’m using Moq to create mocks. I really dig that framework! It’s free and easy to use.

SutBuilder finds the constructor with the most arguments and uses it for instantiation. For each constructor argument, SutBuilder determines if an object of the argument type was passed in via the AddDependency method. If it was, it will pass that object to the constructor, otherwise it will pass an empty Moq mock of that type. AddDependency returns an instance of SutBuilder to provide a nice fluent API. See the code below.

IDoSomethingAwesome somethingAwesome = new DoSomethingAwesome(); // These two statements have identical results sut = new ReallyInterstingService( somethingAwesome, new Mock<IDeathToAwesome>().Object); sut = new SutBuilder<ReallyInterstingService>().AddDependency(somethingAwesome).Build();

All the magic happens in the Build method where It returns the created instance. That’s all there is to it!

As mentioned above, DotNetTestHelper is in it’s infancy. I will entertain any and all pull requests!

Thank you for reading!

Two Common Misconceptions about Multithreading and Async

I’ve recently talked to several experienced developers that struggle with the async/await keywords introduced in .NET 4.5. There are literally hundred of good articles out there on the topic; however, they continue to struggle with two misconceptions. The first is that the async keyword is just another way to do multithreading. The other is that multithreading and asynchrony are meant to improve performance. This blog post will give some history and dispel these fallacies.

Multithreading improves performance FALSE

I may be dating myself here, but I remember working with 16 bit windows (when I was a young humpback freak). Back then, the OS would hand over the CPU to an application. The application completely controlled the CPU and would relinquish control once it ran to completion. The OS had no way of breaking into the application process. Therefore, fatal exceptions or infinite loops would cause the machine to become unresponsive and the only way to regain control was a reboot. In order to combat this problem, threads were introduced.

In a nutshell, a thread is a virtualization of the CPU. Threads are provisioned by the OS and scheduled to run for a quantum (slice of time). At the end of each quantum, the OS performs a context switch. A context switch consists of storing away the current state of the registers and restoring the registers for the next thread. Threads are scheduled by the OS in a round robin fashion. This is how OS can do more than one thing at a time. If an application gets caught in an infinite loop, the OS can kill it from a different thread.

The main take away concept here is that, although very efficient, new threads and context switches are not free. The more threads there are, the more context switches, and the less time each thread has on the CPU. When you introduce threading, the overall system performance goes DOWN. Threading was introduced to make the OS fault tolerant against application errors. Any time you can perform work in a single thread, that is preferred.

The most common use of multithreading is to keep an UI responsive. A UI thread needs to be available to respond to user input; therefore, work needs to be done in different threads.

Now, it’s time to make a seemingly contradictory statement: multithreading can make your programs run faster. Raw performance and overall application processing time are two different things. Today, many machines come equipped with multiple CPUs. If you have CPU bound work (see the next section), you can reduce application processing time by scheduling multiple CPUs to do work at the same time. This assumes that the OS does not have the CPUs busy doing other things…

Asynchronous means Multithreading FALSE

Although the two concepts are somewhat related (you can do multithreading with the async/await keywords), they are very different. Asynchronous calls do pretty much the opposite of multithreading; they make a single thread do more. This is accomplished by not holding a thread hostage waiting on I/O bound work. Before we continue, lets define I/O bound verses CPU bound work.

I/O bound work – The OS makes a request to a device driver (network card, printer, hard drive, etc…). The device performs some work and returns data back to the OS.

CPU bound work – Actual processor cycles (long loops, calculations, etc…)

In reality, there is very little CPU bound work. Yes, it does exist but the majority of time intensive tasks fall into the I/O bound category.

When your application makes a request to a device driver (via the OS), it does not return data immediately. The OS sends the request to the device and then forgets about it until the device sends an interrupt indicating that it’s done. If your application is not using an asynchronous method call, the thread will just hang doing nothing while the device is doing it’s thing. An asynchronous method call will return the thread back to the OS so it can do other work. Once the OS receives the “I'm done” interrupt, the OS will schedule the work to resume. In this way, the OS avoids the overhead of creating new threads.

The above is an greatly simplified version of things; however, I hope it gave you enough of a conceptual understanding to enable you to use async/await in the right way. There are plenty of computer science resources out there if you want a deeper dive…

Thank you for reading! As always, feel free to hit me up with any questions.