Breaking Up with IoC Containers

Straight Up
 
I've stopped using or caring about IoC containers. I used to use them because they were so quick and easy and they kept my code looking pristine and beautiful. Now I do manual dependency injection and the results on non-trivial systems are very interesting and look even more beautiful. At the end of the post we'll examine a little bit more of why I left them behind. In the meantime, I've probably left you wondering what the heck I do to keep things from getting out of hand. "What about the times when you have to inject a dependency through five other objects before it gets to where you need it??" Yeah, we'll get to that.
 

Focusing the Discussion
 
The statements I make in this article assume the following:
  1. You know what an IoC container is.
  2. You only use an IoC container to clean up your dependency injection.
  3. You aren't writing prototypical, throw away code.
  4. The system under question is not an ideal of perfection. It's just a realistic system where I can concretely show the product of applying this abstract idea.
Now, the problem domain: The code in this post was for a Twitter/IM client I was building for a while. Its point was to unify all of your messaging clients into one in a way that made the different clients a non-concern to the user. It was about unifying and simplifying. It has been about a year since I've touched this code so when I first came back and looked at the IoC declaration to re-figure out the lay of the land, I was underwhelmed.
 

Here's my original IoC container declaration:

 
The problem I have that needs solving is how to make my code into living documentation that describes itself long after I've forgotten about it.
 
The Hot New Thang I Replaced IoC With
 
That code really doesn't tell me anything useful about my system. "Wha- HUH?!" you say. Seriously, I get an idea of what the objects are in my system and how they correlate with my interfaces, but what about how the objects are used by one another? The power of OOP lies in graphs of objects. A graph is nothing if not a precise way of storing the interrelationships between individual elements. 
 
So what's the alternative? Ditching IoC and wiring everything together by hand. Ok, ok. I know. It sounds extreme and it sounds painful. Let's address some of what may seem to be pain. Here we can answer the earlier question of what do you do when you need to inject an object through several layers... you won't need to. The reason you've had to do this in the past is because you instantiated objects within other objects. By giving just one class this responsibility, you prevent that from ever happening again. Just pulling all of the dependencies up to the top most level isn't what this is all about though. There's still pain and, as you can see from this example, it does very little to add to the clarity:
 
So after looking at the entire system's wire up and revisiting the different classes I came up with some more appropriate naming:
 
That's the new hawtness. Sitting down, thinking of the code and how the different objects work together and naming them in a way that binds them into a cohesive overarching vision.
 
One of the key principles of OO design is cohesion afterall. Prior to getting all of these objects together and seeing how they were interconnected I didn't really see that they weren't cohesive. The various objects weren't named in a way that illustrated their cohesion with the rest of the system and I didn't have an easy way of seeing them all related to each other. 
 
A key concept that comes out of this is that code is a form of literature. Donald Knuth says,
 
"I believe that the time is ripe for significantly better documentation of programs, and that we can best achieve this by considering programs to be works of literature...

Let us change our traditional attitude to the construction of programs: Instead of imagining that our main task is to instruct a computer what to do, let us concentrate rather on explaining to human beings what we want a computer to do.

The practitioner of literate programming can be regarded as an essayist, whose main concern is with exposition and excellence of style. Such an author, with thesaurus in hand, chooses the names of variables carefully and explains what each variable means. He or she strives for a program that is comprehensible because its concepts have been introduced in an order that is best for human understanding, using a mixture of formal and informal methods that reinforce each other."

 Donald Knuth. "Literate Programming (1984)" in Literate Programming. CSLI, 1992, pg. 99
 
By declaring my object graph in a single spot a human can read it, can see how the different objects depend on and relate to one another, I have a great spot to introduce a new programmer into my system. It isn't necessarily easy, but it will be a more thorough and thoughtful treatment on the system than the original IoC declaration. If I had a better job of adhering to DDD principles in this system, I'd like to think this wire up would be even more valuable.
 
Before you go too long thinking that if I would have just taken the same amount of time with my IoC container I could've fixed the issues with it here's a sample of what it looks like AFTER renaming the classes:
 
On top of that, even if it did read exactly the same, if I am only using it for dependency injection and you don't believe it will add more value to the system's understanding (and I can't believe that you would argue with that) then it's adding superfluous complexity to my project.
 
Having a Conversation with Your Code
 
There may come a time when you try to employ these ideas on a system you're building and it may seem too difficult to get this working. Like writing a book, technical manual, blog post, etc. this technique is an art. The technique itself is not the problem, except of course when it is. To know for sure you need to have a dialog with yourself. Look for the root cause of your difficulties, they'll usually align with places where you've bucked the corner stone OO principles (encapsulation, cohesion, and polymorphism). If, in reading this article, you wonder what about those times when you have an object with 12 parameters that is instantiated inside some other object... ask yourself why you're doing this first, and don't just answer with "Because it was the simplest, easiest thing to do." Simple is not equivalent to the least amount of work. Think towards root cause analysis and solve, or at least move towards solving, the root cause.
 
In this case, IoC containers never solved the root cause of why my objects were so difficult to instantiate and use. IoC containers never helped me to make a system that better communicated my intent. IoC containers did however help me create a composite application. So I will continue using them to that aim and cease using them for most others.
 
Good luck with this! Tell me your thoughts and if you think I'm stark raving mad by leaving a comment or shooting me an email. Thanks!

Message Oriented Object Design and James Shore's Challenge

James Shore posted an architectural challenge this week on his blog and personally threw his gauntlet in my face to answer the challenge using this message oriented design stuff I've been ranting and raving about. Of course when I say "threw his gauntlet in my face" I really mean he said it might be interesting to see... BUT STILL! A man can't back down from that! ;)

 

You can read about his challenge in detail here: http://jamesshore.com/Blog/Architectural-Design-Challenge.html
 
To sum it up, the idea is to build a ROT13 file encoder, TDD'd and beautiful. There were two parts to his challenge. The first was just to get everything done by reading the whole file into memory. Then he wanted us to refine our design around this idea. Once that was done we could move onto to part two of the challenge which required us to process the file as we load it off of disk and save it back to disk incrementally.
 
What did I learn from this experience? I'm extremely happy with the flexibility and robustness of the designs I get when I approach things from a message oriented point of view. There are times where it's too much (there are no absolutes laws right?) but for any system I work on of any actual complexity, it is a great guiding hand for me.
 
 
To get a general idea of what I did I've provided the way I connected my objects together below:
 
First my mistakes:
 
1) This part is confusing. I'm basically just creating an object that will forward every message it receives to both other objects but it isn't executed well:
 
2) Instead of having a separate configuration command, the things I wanted configured, should have just been configured on the fly. Setting them to be configured and then calling for configuration to occur seems way too meh.
 
3) The line where I call out fileReader.Read(); is where the whole system comes to life but I fear that's not obvious.
 
Now what I like:
 
1) Whenever I create a message oriented design, I can discuss the whole system by pointing to the place where I configure my dependencies. The overall system flow may not be perfectly digestable but if one were to try to create a flow chart from this configuration they would find it very easy (I have and it lends itself well to presentations ;)  ). Another thing is, instead of needing a call graph that shows how objects talk to one another, the same ideas fall out of the view of how the objects are dependent on one another in my experience.
 
2) Whenever I run into too much pain with this approach it's a smell I did something wrong. Case in point: While working on part I of the challenge, I had begun to write and test a class that was essentially going to orchestrate all of the other classes together on top of the class which configures which objects talk to one another. Essentially I was building a router. The pain for me was that I was creating WAY too many fakes and needing to care WAY too much about what they were doing. So I took a step back and drew my objects on a piece of paper and then reconnected them per the new design I drew. There were hardly any code changes necessary and it was pretty short work.
 
3) I tend to write tiny objects. Some people hate having too many objects or objects that don't do much so your tastes may vary. I've found that smaller more focused classes help me however. When they encompass literally only a single responsibility I find them to be easier to replace/modify when they no longer fit my needs and I only need to mock when I absolutely need to.
 
If you haven't been talking with me or reading what I've been writing about Message Oriented Object Design here's a brief quick summary:
 
Message Oriented Object Design is an object oriented design philosophy wherein we view objects as sending immutable messages/publishing events on channels. MOOD systems also rely on the configuration of object networks to enable collaboration between them. A core tenet is the lack of inter-object getters (be it method or property calls).
 
4) I like how little code there is in my console application.
 
That's it! Leave me a comment if you want to lend your own critique of what I've done. I also encourage you to head over to James' site and throw your own hat in the ring and critique other people's designs (be harder on the other designs though of course!).
 
Till next time.

Message Oriented Object Design and Machine Learning in Javascript

This article will show how to use Message Oriented Object Design (not unlike Message Oriented Programming aka MOP or Actor Model) to model your user interface as an actor and handle some more complex processing while updating the user interface. Specifically, the sample code implements a simple machine learning exercise wherein you enter any character on your keyboard and the program attempts to guess what you chose (without cheating ;).
 
First what is Message Oriented Object Design (henceforth referred to as MOOD)? Message Oriented Object Design is an object oriented design philosophy wherein we view objects as sending immutable messages/publishing events on channels. MOOD systems also rely on the configuration of object networks to enable collaboration between them. A core tenet is the lack of inter-object getters (be it method or property calls). Since I wrote this example in Javascript and it has no inherent support for this concept all of the ideals of MOOD will need to be enforced by convention. Message Oriented Object Design is a term I made up. I'm not sure that it's sufficiently different from Message Oriented Programming or Message Based Programming to warrant existence but I also don't want to sully those terms with my own ideas if there are important subtleties I'm missing.
 
I'm in the process of writing a very in depth article on Message Oriented Object Design so if you want to know more just let me know and I'll contact you when it's available. For now, suffice it to say that the words object and actor are interchangeable as are the words message, method, or event.
 
The problem we're going to solve is this: Given a text box where a user can enter in any character literal we will create a system that will use that information to predict what the user's next entry to be and also update the web page with our stats on how we're doing. Because we're using the MOOD philosophy, there will be no getters between objects (using them on private methods is perfectly acceptable though).
 
To get started I wrote the following very simple javascript object to represent the user interface:
 
 
One of the key ideas that makes MOOD so powerful is that it views your user interface as just another MOOD object (basically an as an actor). This means that all of the UI eventing that can be so troublesome finds a home here. The idea of asynchronous actions will be built into all of our objects so even as we switch contexts to work on the machine learning portion of the system, the overall object design will look very familiar.
 
Here you can also see the concept of a channel in my objects. In MOOD (and Message Oriented Programming) we always assume that we're using a channel which well pass along our message to the correct object. So while we will end up passing an object reference as the channel, this assumption forces us to view our code as though it is an isolated object unaware of how its method calls will affect others. This will enable us to ensure an extremely clean separation of concerns (SRP) and it will make it easier on us to verify when we violate SRP. How? Look at the semantic meaning of the code in the object. Does any of it seem out of place for an object that's managing the type of UI we are? Why isn't there any knowledge of the learning that this program will be doing? Think about this as we continue.
 
Once I had this code written, I wrote some quick test code just to make sure it was outputting the correct values to the correct spots in the HTML. I'll leave writing that code as an exercise to the reader as it is fairly trivial.
 
Next up, I iterated on the actor that managed the learning task. While the latest code is utilizing a markov chain to learn the users' patterns, I started it incrementally by just having it guess "yesterday's weather" (ie. use the current input as our prediction of the next input). This is the completed implementation:
 
 
As a refresher, the Markov Chain as I've implemented it tells us which value is most likely to be entered next given the previous value. I won't go into the implementation details but the code is fairly concise and is hopefully legible enough to be decrypted. 
 
The learning actor has just a couple of main parts to it.
  • The next(value) message that is passed the value that the user entered.
  • The _learn_from_new_information(previous_value, current_value) method that trains our markov chain.
  • The _make_best_guess(value) method that utilizes our trained markov chain to make an educated guess about the user's next entry.
  • Last but not least, a simple set_guess_channel_to(channel) message that we can use to publish what we guessed and what the right guess actually was.
Initially, I had actually written the code that is now in the scoreboard actor as a part of the learning actor. Here's that code:
 
 
You can see it's fairly simple and likewise I was hesitant to move it to a new class. As you get started with this style, you will feel this quite often. I recommend fighting through the pain until you come upon the first "major" refactoring you need to do. The ease in which you'll be able to make that change I guarantee will astound you and you'll be hooked. Another reason I hesitated to move this out of my learning actor is that I assumed I would be duplicating the concept of "the previous value must equal the last". Since MOOD doesn't allow for getters I knew that the only way I could have shared that logic would be copy 'n' paste reuse (read: ewww). Look at the algorithm left over in the learning actor though. It never cares whether or not we guessed right. It only tracks the guesses and makes a hypothesis regarding them. So if guess checking wasn't a concern of the learning algorithm why did I have it there to begin with? I simply wanted to display a scoreboard. Hence the creation of my scoreboard actor.
 
We've got all of these objects but what to do with them? The configuration of our objects is referred to as the network configuration. This is essentially just a different flavor of dependency injection. The difference here being that your configuration will be able to be factored away from the rest of your code and isolated if you so choose. Here's the object network configuration for this code:
 
 
The first thing that should stand out to you is that we are making no attempt to make our objects immutable. In MOOD, just like in Actor Model, we are guaranteed that an actor will only ever be used from the context of a single thread throughout its lifetime. This might seem to be a poor constraint here is why it's not: Imagine the learning actor gets some VERY complex logic. That isn't a stretch depending on how accurate you want the guesses to be. So, if you had written this code without using this style and didn't explicitly design for asynchronicity what might happen? The first time that learning actor needs to really think, your UI will freeze up. Because we wrote this using Message Oriented Object Design however, we can throw that logic _anywhere_ and it won't block our UI. What do I mean by anywhere? I mean we could literally host it on a web service and instead of implementing our actor on the HTML we could have an actor that was responsible for interacting with the web service. Someday, if Javascript gets threads we could even throw the extra work onto a thread and create a channel object to manage the threading context on the passed messages. The rest of our code wouldn't change for either case. If you need an actual example leave me a comment to that effect because for now this seems as though it's easy to see especially once someone has pointed it out. In the meantime, if you've been thinking that Message Oriented Object Design is a lot of extra work for pedantic self-indulgent programmers think about whether or not your code could do that.
 
Oh yeah. Also, notice that there is only one VERY thin object in all of that code that has anything to do with the DOM. The rest is trivially unit testable. And not just testable in a small way, but testable as in only the object under test will be exercised. I didn't TDD this code. That's just the way the MOOD pulls me.
 
Also, I apologize in advance for my horrible naming of methods and objects. Hopefully it still gets the point across.
 
That's it! Go ahead and try it, it's pretty neat. Just "randomly" pressing keys on the keyboard the way I do the code was able to guess correctly 40% of the time or so. Not bad at all! Also, regular patterns like "abcabcabc" it will get pretty quick and you'll see the code try to follow you if you do something like "aaaabababaaaababababab". Of course, like all learning agents, the more random the string you enter, the worse the agent will perform.
 
The full HTML source code is here for you to download and try. It does require you to include jquery for it to work. Leave a comment if you have any questions! :)
 

Katas for Practicing Refactoring

Problem

I've tried to do the various TDD katas found laying around on the web (not dissimilar to those found here: http://codekata.pragprog.com/) and found I have a couple issues with most of them. First it has to do with what I perceive a kata to be.

A kata is a choreographed set of movements that are practiced ad-tedium so that they come almost instinctively, one after another. They are very narrow and focused. There is no real problem solving to be found in them.

In completing some of the various katas I've found on the net, I've noticed they are more complex than I'd like, but also, in the end, I don't really know that I've done it right. It's extremely easy for me to get off track. I also never know why I'm doing it. What am I learning? Am I learning?

It's important to note that I'm not saying the TDD katas out there are broken, if they work for you then I don't recommend you stop them although you may still want to give these a try. I'm really just saying that they are broken to me.

Solution

In response to my experiences I came up with the idea of practicing kata forms based on Martin Fowler's book, Refactoring. Almost all of the refactorings in this book are extremely simple and the kata itself implies the "solution" you should arrive at at the end. We do refactorings numerous times daily. A lot of times it's with the help of tools, but there are plenty the tools don't cover. Simultaneously, there are times when your favorite tool is broken (COUGH Resharper 5 Beta COUGH) and you may need to whip one out by hand. Also, there is no need to ponder how to model the domain of the kata. The sample has been TDD'd and all that's left is to refactor the tests and the sample code together into the direction described by Fowler's book. I have decided to keep my samples as close to Fowler's as possible (sometimes steering a little away to maintain my personal coding standards).

That gives us a bonus for free. The refactoring katas also serve as an excellent introduction into what makes TDD addicting, the safety net. When the kata is being refactored, the tests may require refactoring but they shouldn't require massive changes. Everything a practicer might do, should already be covered. This means that if they make a misstep, the tests will usually catch them and guide them back onto the correct path. 

Follow Along

I recommend using Refactoring as a guide to follow along with the refactorings and practicing them until they are a muscle reflex. This is the book to buy in case you're too lazy to Google it: http://rcm.amazon.com/e/cm?lt1=_blank&bc1=000000&IS2=1&bg1=FFFFFF&fc1=000000&lc1=0000FF&t=justibozon-20&o=1&p=8&l=as1&m=amazon&f=ifr&md=10FE9736YVPPT7A0FBG2&asins=0201485672

Contribute!

I have completed one refactoring and have half of another larger one posted to my GitHub account.There are a lot of refactorings to cover and I could really use some help. I've done the hard part and gotten the project started and added a couple of my favorite refactorings. If you like this whole concept do the same. :)

Where are they Hosted?

TDD-ing Concurrent Code

A Method for Modelling Concurrency
 

I'm prepping code for Code Camp Boise and Seattle and I thought I'd share some of the simple stuff I'm writing as I'm writing it to act as an introduction of sorts to the concepts.

 
I hear a lot of people say things like "Well we made this process concurrent so now we can't test it." That just always felt wrong to me. Over the past year or two, as I've been reading about threading though I've kept this in mind. Like any concern, it's difficult to test without taking it into account if the concern isn't abstracted away from the code under test.
 

Testing concurrent software can be extremely difficult. While debugging, breakpoints can be seemingly randomly tripped by other threads that you don't care about, your data can change right under your nose whether or not you're paused, etc.
 
Another issue I hear is that synchronizing across threads is a pain. What happens if after verifying the object you want to use is in the appropriate state, some other thread changes it and then when you use it it throws an exception? In this way, race conditions can be extremely difficult to manage.
 
One way to handle this is to use a message based data flow oriented model. Why? Well first and foremost because this allows you to model your data dependencies and allow the abstraction to suss out the details. By just declaring a network of processes (which are essentially objects) as a directed graph you gain the ability to do this. Now you've explicitly declared how these different processes will interact with one another and since data flow programming uses immutable objects you won't have to worry about any processes interfering with each other.
 
Yet another great thing about developing a data flow network is that you can test each process in isolation without it even having any knowledge of threading. That's what I will be talking about for the remainder of this post.
 
Some Context
 
A friend of mine needed a computer program that would go through a text file of over 10,000 lines of text (sometimes more) and find all of the valid email addresses. First and foremost I came up with a quick description and overview of the process I could see going through:
 
FileReadingAgent
reads in lines from file line by line and passes them along to the ObviousEmailExtractionAgent while skipping the blank lines.

ObviousEmailExtractionAgent
extracts obviously good email addresses from each line and passes them on to the GoodEmailCollectionAgent. 
Lines without obviously good email addresses (or with none at all) are passed to the NonObviousEmailExtractionAgent for further processing.

NonObviousEmailExtractionAgent
Uses more intelligent email extraction rules to find less obvious email addresses
Passes any found email addresses on to the GoodEmailCollectionAgent.

GoodEmailCollectionAgent
Aggregates known good email addresses.
 
So to reiterate, all of these agents should be assumed to be running in their own threads. Also, they only communicate to one another via immutable messages. 
 
The FileReadingAgent would have a connection to the ObviousEmailExtractionAgent. The ObviousEmailExtractionAgent would have *two* connections. One to the GoodEmailCollectionAgent and another to the NonObviousEmailExtractionAgent.
 
In this post I'd like to share the tests that went into creating the FileReadingAgent. 
 
TDD-ing a Process
 
The first context I worked on assumed there was only one line of text in a file. This is a basic context that just helps to ensure that the basic plumbing for my agent is all hooked up. This is how I tested this context:
 
 
The next context I worked on contained blank text lines. I wanted to ensure that those lines of text didn't get passed on to my email finding agents.
 
 
The final context has lines of text with whitespace characters and one line of text that is an email address. I wanted to ensure that only lines with any kind of text moved on to the agents that would actually try to parse out email addresses. In hindsight, this probably should have gone in the ObviousEmailExtractionAgent. It seems like the FileReading agent shouldn't really be concerned with this. I could probably just change the name of my FileReadingAgent to NonBlankLineReadingAgent and get by that way. ;)
 
 
My "final" code doesn't handle disposal or anything and it definitely should! That's an oversight on my part. Aside from that this code should be pretty much complete:
 
 
Notice the use of the IObserver interface? I'm stealing a bit from the new .NET Reactive framework (an idea that I got from Robert Ream). By using the OnNext method I can make my network of agents push oriented rather than pull oriented. The benefits of this can be enumerated in another blog post. :)
 
How could I connect these to run synchronously? Super easy. This is how I could link the LineByLineFileReader to the ObviousGoodEmailExtractionAgent:
 
lineByLineFileReader.ShouldSendLinesOfTextTo(obviousGoodEmailExtractionAgent);
 
Then to start I'd send the filepath I wanted to be processed to the lineByLineFileReader like so: 
 
lineByLineFileReader.OnNext("c:/myfile.txt");
 
Next time I'll show an overview of the whole application and how it works concurrently with a WPF UI. 

A TDD Practitioner's Pragmatic Argument Against 100% TDD

Not writing unit tests can drive more value than writing them if one
makes a good gamble. More often than not TDD pundits argue that if you
don't have tests you can't easily and rapidly discern a buggy system
from a solid one. They claim you can't effectively explore your code
base by utilizing the tests for hypothesis testing. They claim that
it's risky and wasteful.

They're half right.

It's all just economics. Pure test driven development provides us with
a solid risk mitigation technique, that if followed to the T can
ensure your code will only increase in quality and robustness. Most
self-respecting developers accept that. The controversy which
surrounds this subject usually revolves around whether or not the time
invested can be rationalized as driving a sufficient amount of value
to make it worthwhile. Most controversial is the idea that everything
you program must have a test rather than just most of what you
program. Not having a test to cover a change to the program means
there's more of a risk that a bug could creep in.

How do we leverage that risk though? The case can be made that unit
testing code can take longer than just programming what you want.
Those of us who feel very strongly about TDD would say that might
happen but you'd have to be lucky to get code without many bugs.
Others would argue against that but I say ok sure! Let us assume that
you'll only get that code done correctly, faster if you're lucky
but... How lucky? How much do you stand to gain if you win? Do you see
where I'm going here?

Risk can drive an exponential increase in a return on your investment.
That's an economic fact. If you accept that as well as the idea that
not unit testing is risky (as opposed to impossible) then you
hopefully agree with me on this.

I don't care what your stance is on this subject, this is a rational
argument for strategically not testing aspects of your code.

Now if we wish to argue this subject in the future we need to argue
the specific contextual situation of each developer. For some it is a
potentially profitable venture and for others it would be enormously
expensive. Now we can frame the whole debate as being so hard to
definitively settle due to the unique data that we'd need to
rationalize it at every company. This is nothing new as many of us
who've been arguing for unit testing have given up arguing with some
people. Both sides huffing while the TDD person says you really just
need to try it for yourself. What they're really saying is you'll need
to run your own study at your own company to see if the practice is
right for you.

Some of you will say that's fine but the developers who do this will
be accruing a hellish technical debt over time that they'll eventually
have to pay off.

Technical debt is really the wrong model for what we're discussing.
Why do we have to pay it back? I'll wait for the laughing to stop but
once you've caught your breath please really think about this. If not
"improving" that code is driving a hefty increase in value then we
don't really have to because what we're actually doing is leveraging
risk. That's actually why the whole debt analogy really works in the
first place, because debts are assumed risk, the difference being that
the investor needs to be paid back. Instead, if we view them as
gambles, we understand that it's possible to get Black Jack, or a
royal flush, or hit the jackpot.

Remember every decision we make every day is a multivariate
optimization problem. "Experts" give us their recommendations based on
their own personal experience, but every company is different. If you
don't have the data you need to support the cases you wish to make
start collecting it now.

The Best Way to Learn the Art of DO...?

Can't make any forward movement standing still... sometimes I find myself forcing me to move forward even if it's to some place I don't want to go, simply because it's the best place to go for right now. My fixation is on moving, expending energy even when it isn't economical to do so. My entrepreneurship class is one such example.

Is it a sunken cost? Should I just drop it and focus on my business without that class as a worry? It doesn't apply to my degree.

So now I'm thinking very hard on this problem. Given that the only possible value I can derive from the class is that which I can derive from the professor directly, I am really deciding upon the value of my professor. Over the last few weeks, what have I learned from him? Nothing. His own business drives limited profit (by his own admission) and consists of him consulting on how to start/run a business.

Rather than take a class to learn about business, maybe my friends have been right in that I need to just start a business. Even if I fail a few times (or a thousand), the lessons I learn would, without a doubt, be of a far higher value than anything I've learned thus far in this class.

I'm giving myself until tomorrow to think on it.

Using Graphs to Build Your Own Ruby Pattern Matcher

There's More Than One Way To Skin a Rat!

A while back I posted an article on using dynamic programming to implement a string matching algorithm I cobbled together. That article is here: http://justinbozonier.posterous.com/string-pattern-matching-welcome-to-dynamic-pr

Tonight, I'm writing about solving that same problem but by using a graph. It was a solution suggested by a few people and then finally a couple of days ago my boss (Kelly Leahy) brought up the problem once more as I was asking for suggestions of CS concepts he thinks I should tackle and we got back on the subject of that pattern matcher. If it was mentioned so much in the past why did I jump on it now? Quite simply, I've been learning Ruby lately at the insistence of James Thigpen. He's been ranting and raving (on top of many others) so I thought this would be a great first project.

Tools and Techniques Used

I tried my best to stick to pure TDD and unit testing with a context/spec naming style and test structure using RSpec. For my IDE I tried using RadRails, RubyMine, and NetBeans. Ultimately I chose NetBeans. For some reason it turned out to be the easiest for me. **shrug**

This is my very first Ruby project ever and I typically do C# development so if you see some ugly .NET-isms... please flame away so I might learn ;D

Stating the Problem

The problem to solve is given a pattern such as "a.c*z" we need a way to determine if a string like "abcdefghijklmnopqrstuvwxyz" matches it (it does) and that a string like "afdgkjbdkfdstg" does not. Our pattern matching grammar will have only three basic elements. A literal element that matches a character in a string exactly (ex. a, b, c, ..., x, y, z, 0-9, etc), a match any element which matches any single character (a period ie. "."), and a match all element (an asterisk "*") which matches zero or more occurences of any character or combination thereof.

It's like a REALLY simple regex evaluator.

And I know some people are going to ask, why not just use a regular expression? They're super sexy and simple to use in Ruby. Why reinvent the wheel?

I have this crazy idea that even though frameworks are pretty awesome at abstracting the difficult detais away from our view, living in ignorance of the basic data structures and algorithms that these frameworks are constructed of, that just leaves us using these things not because they save us time, but because we are dependent on them to get the job done. I'm all for frameworks, but I want to use them because I understand why I should use them, not because I can't understand how to live without them.

What Makes Solving This Difficult?

One of the key things that makes this a somewhat difficult problem to solve if you've never encountered it before is probably best shown as an example.

Imagine you have the following test string:
"*a*a*a"

now imagine how you would test that the following string matches it:
"aaaaababaaaaaaaaa"

See the problem is the * matches everything including the a so how do you know whether to treat the a as a part of the asterisk or as a literal? The answer that Kelly helped me to formulate is that you treat it as both. Basically you allow your solution to branch and when you come to the end of the string you're testing, you look to see if any of the branched paths finally completed the pattern.

I designed the program so that every character in the test pattern represents a given transition from one state to another. There are also three different types of states. A starting state where every match algorithm begins life, a terminal state which is where all matches will end life, and a standard state that represents an interim step from character to character.

So given our string pattern above, the program I wrote would generate the following graph:
  • Start State
    • Transitions to itself on any character (the asterisk)
    • Also, transitions to the next standard state via a literal transition edge that matches on the letter "a"
  • Literal Transition State
    • Transitions to itself on any character (the asterisk)
    • Also, transitions to the next standard state via a literal transition edge that matches on the letter "a"
  • Literal Transition State
    • Transitions to itself on any character (the asterisk)
    • Also, transitions to the next standard state via a literal transition edge that matches on the letter "a"
  • Literal Transition State
    • transitions to the terminal state via an always transition edge.
  • Terminal State
Getting Down to Brass Tacks

Let's look at the transitions and states in code to try to make some sense out of what has been a fairly abstract read up until now. First the graph states:

As you can see the states really do nothing aside from managing their transitions. I do a poor job of encapsulating these from the rest of my string matching world (ie. the objects that use this array could technically add to it directly) and that should be marked for refactoring later (whether or not it is is my lil secret! ;)

And then the transitions:

These are even simpler! The only bit of logic to a transition is it's test to determine whether or not the provided character can be transitioned on. 

Hopefully from just seeing this code you can get a pretty good feeling for how these things might fit together.

What gets more complicated is the building of the graph. I like to imagine that specs can help to explain the code they test somewhat so let me share some of those first:

My tests are awkwardly named so I could use some naming help if you care to leave a comment! :)

This is the class they test:

Here's a quick high level explanation:
  • First, create the root of the whole graph. This is ALWAYS a start state.
  • Store that as the state we're currently adding transitions to. (line 9)
  • Next, for each character in the test string we are matching against the string pattern create the appropriate transition.
  • Add the newly created transition to the current state
  • Set the current state to point to the destination of the new state provided by our new transition.
  • Rinse, lather, repeat...
  • Once that's done ALWAYS create a terminal state as the last state.
  • Attach it to our current state by adding a transition always transition to the current state that points at the final state.
Now about this transition always transition. It feels dirty and like needing to know the start and end state should be unecessary. Even in the current state needing to know the start state is probably unecessary, but the final state... I'm not sure how to handle that generically like the other states. Thoughts?

Also, notice the code block on line 11! That was my first sampling of Ruby awesomeness. I should totally have been able to avoid writing my own string reader by using ruby's string.each_char |c| {} code block but I learned about that after wrapping up and I didn't care to do more refactoring at the time. :)

Notice how I lied about the difference between a "." and a "*"? They're both the same transitions but they have different destination states. Here it is again:

The "*" transition acts as more of a loop back into the same state it left. The "." moves us forward to the next state.

Meat and Potatoes Time!!

Now all of that was built with the ultimate focus on getting the construction of the actual matcher to be as easy as possible. Here are the tests for how the matcher is ultimately used:

God it's painful showing off code that I'm sure could've been written more elegantly! I always convince myself it's for the best to not go back over it an edit it so that way it gives a more honest view of my coding process and doesn't turn into Justin just trying to look pretty.

So without further ado this is the entire implementation of the code that actually utilizes the graph to match a string against a given pattern:

Here's a general overview of the steps involved so that you can hopefully glean as much from my code as possible:
  • First "compile" the test pattern provided by the user into a graph representation.
  • Next make that graph the first state to be evaluated (a graph is really just represented by a start node that acts as the root.
  • Next we read the next character from the test string provided by the user.
  • We every transition of every state that has been queued for evaluation.
  • For each transition that tests true on its can_do method grab that transition's destination state and place that into our next states list/array.
  • Once we've done that for every state and transition until we've ran out of test string to process there should be at least one state in our next states queue that is ready to transition to the terminal state (assuming there is a match).
  • If there is then return true! We have a winner!
  • Else it's false and these strings don't match according to the given pattern.
Was It Good For You?

I try to share these kinds of learning experiences because so many times in the past I've been so thankful when someone else did. Maybe you're like me and don't have a CS background/degree and are trying to find ways to make data structures and algorithms more practical/applicable. It can be hard to take theory and find a way to apply it. Well anyway, hopefully it helps somebody.

Also, Ruby is a pretty nice language. I might even enjoy it more than Python (I like having an end keyword instead of ambiguous white space ;).

If the mood strikes you, you can find the whole project on my github account here: http://github.com/jcbozonier/DfaStringMatcher

Also, I know I call this a DFA in the github title but it isn't. A deterministic finite automata would have no cycles, whereas my graph does.

So that's that. If this was the least bit helpful let me know by leaving a comment and if you feel like I got something wrong or left something else out entirely leave a comment to that effect as well. Thanks for reading!

Mocking Frameworks, How'd They Do That?!

Writing Your Own Stubber, A How To Guide

The largest mystery when trying to understand how a mocking framework works has always been just understanding where this object it creates comes from. I mean I give the mocking framework an interface and it comes back with an object that implements everything (at least in the case of a stub). The point of this post is to show that they aren't magical and to hopefully extend what you think is possible in your own problem solving with C#. I'll be assuming you're familiar with mock objects and how/why they're used.

I developed a very small stub generating utility using TDD in order to explore the concepts that go into the big names such as Rhino.Mocks. This is the first test I wrote:

Hopefully that gives you an idea of how it is used. All of the tests you will see are centered around this single method call 

MockedObject = Mockery.Mock<IFoo>();

No matter what interface I'm stubbing out the call to my library will be the exact same. Here's a more complicated set of examples:

You already get the mocking frameworks I'm sure so let's cut to the meat and potatoes here:

The "magic" of the stubbing is handled through reflection and by emitting IL code. Here's an English translation of that code:
  • First we need to build our new type that will be implementing the interface we were given by the person using our code. We define this type as being public and as being a class. The null at line 25 tells the TypeBuilder that this class has no parent and line 26 tells the TypeBuilder that we're implementing the interface provided to us by the user.
  • Next we need to get a list of all of the methods that we need to implement on our new type. To do this I needed to reflect into the interface type provided and grab all of the methods it declares. I do this on lines 28 and 29.
  • If there aren't any methods we're done! Create that type and create a new instance of it! (lines 49 and 50).
  • If there are methods things get trickier.
    • First, if the method takes in parameters we need to generate a list of the types of those parameters so that we can write the corresponding IL. (Line 35)
    • Each method needs to be built up according to whether or not it has a return value. 
  • Then just create our instance.
Now the hardest part to figure out was how to create a method body for this new class. Let's look at the simplest example first:

IL is Sexy Black Magic

So what's happening here? 
  • First, I'm defining my method. I tell the TypeBuilder to define a method with the following properties:
    • same name as the one on my interface
    • that the method should be public and virtual, 
    • that the return type is void
    • that it will take in the provided set of types as parameters.
  • Then we're going to generate IL that does absolutely nothing with any of this. :)
  • We just generate a single IL instruction that just returns.
One thing that might seem magical is knowing what IL OpCodes to emit to get the desired effect. For that magic I just wrote an method in C#, compiled it, and opened it up as IL inside Reflector. The code it gave was a little verbose though so I tweaked it a bit to minimize things. 

Now let's take a look at the slightly more complicated example where I actually need to return a value:

The only differences here are at lines 16 and 17. At line 16 I emit an instruction to declare a local variable for the value that will be returned. At line 17 I push this value onto the stack and then immediately afterwards I return it. There is a property on the IL Generator to have the system automatically initialize your local variables to their default values. This is great for my stubber because that's all I want it to do! w00t!

Other than that knowing what the hell to call and how to get these different type and method builders just took a lot of googling.

<tdd_rant>

One of the benefits of using TDD in this process is that I could easily try out a chunk of code just to get things working (a spike) and then i could slowly strip portions of it away that I suspected added no value (especially handing for minimizing the IL instructions).  There are currently 12 tests or observations going on here. Because I know that all of my cases I tried to build have all been driven by those observations I can try making changes and I quickly tell how many of my expectations will fail.

For example, on line 67 I defined a single line method to detect if a method has parameters:

If I change that to this:

I get a failing unit test. The bonus is that I know exactly the use case that will fail (because it did ;).

When_executing_a_mocked_method_that_has_a_return_value_of_null_and_parameters (1 test), 1 test failed
   It_should_return_the_default_value, Failed:

This is a full list of test cases for my code:
<TestProject> (12 tests), Success
  TestProject (12 tests), Success
    When_executing_a_method_on_an_interface_with_several_methods_with_no_return_values (1 test), Success
      It_should_execute, Success

    When_executing_a_method_that_returns_an_int_on_a_mocked_object_with_mutliple_methods (1 test), Success
      It_should_return_the_default_value, Success

    When_executing_a_method_that_returns_an_obj_on_a_mocked_object_with_mutliple_methods (1 test), Success
      It_should_return_the_default_value, Success

    When_executing_a_mocked_method_that_has_a_return_value_of_null (1 test), Success
      It_should_return_the_default_value, Success

    When_executing_a_mocked_method_that_has_a_return_value_of_null_and_multiple_parameters (1 test), Success
      It_should_return_the_default_value, Success

    When_executing_a_mocked_method_that_has_a_return_value_of_null_and_parameters (1 test), Success
      It_should_return_the_default_value, Success

    When_executing_a_mocked_method_that_has_a_return_value_of_type_bool (1 test), Success
      It_should_return_the_default_value, Success

    When_executing_a_mocked_method_that_has_a_return_value_of_type_int (1 test), Success
      It_should_return_the_default_value, Success

    When_executing_a_mocked_method_that_has_no_return_or _parameters (1 test), Success
      It_should_be_callable, Success

    When_executing_a_mocked_method_that_has_NO_return_value_and_multiple_parameters (1 test), Success
      It_should_execute_with_no_error, Success

    When_instantiating_an_empty_interface (1 test), Success
      It_should_return_an_object_of_the_same_type, Success

    When_instantiating_an_interface_with_a_single_parameterless_method (1 test), Success
      It_should_return_an_object_of_the_same_type, Success