The stupidest thing I ever saw a developer do

So this story comes up quite a lot – this is the stupidest thing I ever saw a developer do. I need to paraphrase a little because it’s been many years, but in a nutshell we’d had a new guy start as a junior developer and he was working through bug tickets, with instruction to run solutions past another developer prior to checking them in. He was dealing with an issue where the backtrace read something like this:

undefined method `capitalize' for nil:NilClass (NoMethodError)

Which is a relatively simple exception to explain and is probably, in my experience, the most common backtrace a developer will ever see. It usually means that someone has not coded defensively, or that something has been coupled to something else in a non-obvious way and someone didn’t realise. You can easily achieve the error yourself:

my_hash = {}
my_hash[:key].capitalize

Anyway, after working on it for a few hours our developer came to me with his solution. Here is what he had done:

class NilClass
  def method_missing(method_sym, *arguments, &block)
    return
  end
end

For non-rubyists, here is a translation of what that bit of code does:

Let’s change the meaning of nothing, so that whenever someone tries to do something to nothing, we just do nothing.

I am not entirely proud of my reaction at the time, which was basically to laugh at the guy, tell pretty much everyone in the office about what he’d done, and then continue to tell the story for many years to come. To his credit, this “fix” had actually, to the untrained eye, fixed the problem because the software was now behaving as expected.

Evidently, the developer in question had, upon seeing the backtrace, Googled it. He had found a stackoverflow entry where someone else was having the same issue and some helpful user had submitted the NilClass monkey patch as a joke answer to the question. Other helpful users had up-voted this answer, which lead to our guy not identifying it as a joke.

I tried in vain to track down a link to this stackoverflow entry (it was many years ago) but to no avail.

Like I said, I tell this story quite a lot – the most recent time was earlier on today in fact, and it got me thinking. I worked through  the steps that this particular developer had taken:

  • He googled the error
  • He found a “solution”
  • Without understanding it, he stuck it in the codebase

And it dawned upon me that maybe I had been a little harsh on the guy, because that little trio of bullet points right there is one I have followed a whole bunch of times myself, especially when I was first getting started as a dev.

I never had a mentor, and regularly found myself being completely out of my depth and being asked to do things which I had no idea how to do. It was scary, it was stressful, and whilst being pushed in the deep end does make you very good very quickly (provided you swim) it can lead to you becoming overly reliant on the internet for solutions. You become adept at “skimming over documentation”. It’s bad practice.

If this story feels kind of familiar to you, then know that you are not alone – almost every programmer I have ever worked with has at some point engaged in “stackoverflow driven development” . Nowadays I always try to be aware of what I do not know – Taking time to properly understand what a solution means is not wasted time.

And if the guy who I laughed at ever reads this, please consider this an apology.

Creating your own attr_accessor in Ruby

When going through Ruby 101, you won’t need to do much research before you come accross the use of the attr_accessor methods. There are several flavours of this;

attr_accessor gives you a getter and a setter
attr_reader just gives you a getter
attr_writer just gives you a setter

Here’s a code example of this functionality being used;

class Person
  attr_accessor :name, :age
end

#above class definition enables the following
p = Person.new
p.name = "Mikey"
p.age = 30
puts p.name

Magic. It’s almost like you’ve somehow managed to add two more methods to the person class without defining them. Well, it turns out that this is exactly what you have done! For anyone who is not used to dynamic programming languages (and I include myself in that list) this can be a really tricky point in the learning curve. This sort of functionality is used all the time in ruby, and not only within the context of attr_accessors – The Rails framework, for example, uses dynamic code to allow you to add very complex functionality to your ActiveRecord classes with a single line of code.

If you are anything like me, then you can’t just take the fact that it works for granted! I needed to know *exactly* how this sort of thing is possible! This post will clear up exactly how this attr_accessor magic works by showing you how to make your own version of the same functionality.

Dynamic code is created using a series of “eval” methods which the ruby language makes available to you. There are several flavours (eval, instance_eval, class_eval, module_eval) – the one we’ll be using here is class_eval, which you basically use to add code to a class. As we will be trying to create a method that will be accesible from all classes, we will need to add our code to the Class class (not a typo!). This is going to get a bit headswimmy, so I’ll just go ahead and show you the code itself then discuss it below.

class Class
  #firstly, the * decoration on the parameter variable
  #indicates that the parameters should come in as an array
  #of whatever was sent
  def mikeys_attr_accessor(*args)

    #We simply iterate through each passed in argument...
    args.each do |arg|
      
      #Here's the getter
      self.class_eval("def #{arg};@#{arg};end")
      
      #Here's the setter
      self.class_eval("def #{arg}=(val);@#{arg}=val;end")                      
                      
    end
  end
end

The above code allows a new class to be defined as follows;

class Person
  mikeys_attr_accessor :name, :age  
end

Which in turn allows you to write code like this;

person = Person.new
person.name = "Mikey"
person.age = 30
puts person.name
puts person.age

A lot was going on in the first code example, but the rest of it functions exactly as you would expect attr_accessor to function. The focus here will therefore be on the first bit of code. So it all starts off pretty basically, we are able in ruby to extend any class simply by using the class keyword. We then add the method “mikeys_attr_accessor” to it, using a bit of ruby syntactic sugar to allow this method to receive any number of arguments. It’s worth pointing out that we should really check that these arguments were symbols, but as this is a simple example I’ll skip that part.

Next we iterate through each argument and make two calls to the “class_eval” method. The message we send to this is basically just an interpolated string representing the code we want included in our object. Yes, I did say object – you might raise the question at this point as to why I’m using the word “object” when we are clearly adding a method to a class. You might also question the presence of the word “self” before the “class_eval” call, surely this would mean that we have somehow managed to create an “instance” of a class?!

This was pretty much the point, while learning Ruby, that I lost cabin pressure.

class Person
end

Person.class
=> Class

The capital letter at ths start of Person indicates that it is a constant. Person is constant instance of the Class class. As you’ve instantiated the Class class in your Person class, you need to use “self” on the class eval to make sure that the class_eval method is talking to the Person instantiation of the Class class. You may need to read the previous sentence a few times before it sinks in (if you feel your ears starting to bleed, contact your GP immediately).

A better question is that, if this is the case, why is class_eval used instead of instance_eval? the short answer to that is that it has to do with scope and context. If you are interested in learning a bit more about metaprogramming, i found the following question over on stack overflow to be incredibly useful. Lots of great links from the respondants.

http://stackoverflow.com/questions/788689/ruby-metaprogramming-online-tutorial

TDD and UnitTests in ruby

I’m relatively new to ruby, but one thing I noticed pretty much from the start is that the community surrounding this language are incredibly passionate – not only about the language itself but about coding practices and development techniques. One of the things they are particularly vocal about is Test Driven Development (TDD). I personally have never used TDD in any of the projects I’ve been involved with, but the philosophy absolutely fascinates me so I will definitely be checking it out on whatever my next venture happens to be.

For anyone who needs a quick primer: TDD basically centres around the belief that if we code up a bunch of tests stating how we expect our code to behave then all we need to do is to write our code such that those tests pass, making it easier to see when we’re done and providing a constant test-bed for the future. Two immediate practical uses of this immediately spring to mind;

  • It can act as a sort of class blueprint which you work towards.
  • Keeps a constant check that you haven’t mucked anything up!

Unit testing

There are many types of test (the ruby on rails framework, for example, even lets you test your views!) but here I’m going to focus on unit testing – the act of testing units of source code to make sure they do what they’re meant to.

Let’s do the classic example. We’re coding up a “person” class. We start by creating a class stub like so…

class Person
end

Then in a separate file, create the unit test.

require "test/unit"
require "person"

class TestPerson < Test::Unit::TestCase

  def test_person_methods
    #assertions go here
  end

  def test_person_functionality
    #assertions go here
  end

  #more tests...
end

As with most things in ruby (and helped greatly by its reflective nature) they’ve made unit testing incredibly easy. After requiring the “test/unit” library and inheriting from the Test::Unit::TestCase class, you simply make a bunch of methods prefixed with;

test_

Each of these will be treated as a seperate test. As with most Unit Testing frameworks, any assertions which fail within a test will result in that test failing. After you’ve set up all of this, you just run the file with the tests in to get the results of the test!

An Example

Here’s an example of a test that would be able to see if methods existed within a class. You could use this as a test to work towards as you first create a class, but also if you ever want to change a method name or add a new method later. Imagine you decided that the Person class needed a name, age, firstname and lastname;

  def test_methods_exist
    #create a new person
    person = Person.new

    #create a literal array of the methods we expect to see
    expected_methods = %w{ age name firstname lastname }

    #run an assertion on each method stating that the method exists
    expected_methods.each do
      |method|
      assert(person.respond_to?(method), "#{method} does not exist")
    end
  end

I call the “assert” method with two arguments: the first must evaluate to a boolean value – if this returns false then the second optional parameter (which all assertions can have, by the way) specifies a custom message to display should the test fail. Here I’ve used interpolation to display a meaningful message about the method not existing (rather than just the “computer says no” response you’d get otherwise). Other, more specific assertions come with pretty good messages anyway, but you’ll always want to specify a message when using a vanilla assertion.

When you run the code you get output like this;

Loaded suite person-tests
Started
F
Finished in 0.021184 seconds.

  1) Failure:
test_methods_exist(TestPerson)
    [person-tests.rb:16:in `test_methods_exist'
     person-tests.rb:14:in `each'
     person-tests.rb:14:in `test_methods_exist']:
age does not exist.
 is not true.

1 tests, 1 assertions, 1 failures, 0 errors

It’s failed because the age method does not exist, as can be clearly seen from the output. Once we go back and add in those methods, the test passes;

Loaded suite person-tests
Started
.
Finished in 0.001792 seconds.

1 tests, 4 assertions, 0 failures, 0 errors

Another Example

You could use the same technique but apply it to the functionality of the Person class. Hopefully it’ll be self explanatory, but i should point out that the following example does not follow best practices! TDD best practices is a whole other can of worms, all I’m trying to do here is demonstrate the core assertions that are possible. If you were to run the below without having implemented the various methods, for example, your test class itself would raise an exception. Anyway, here goes;

  def test_person_functionality
    #set up a person
    person = Person.new
    person.firstname = "Mikey"
    person.lastname = "Hogarth"
    person.age = 30

    #check that the correct class was created
    assert_instance_of(Person, person)

    #check that "name" will return the first and last names appended
    assert_equal("Mikey Hogarth", person.name)

    #check that the age range is limited 0...200
    assert_raises(RangeError) { person.age = -1 }
    assert_raises(RangeError) { person.age = 201 } 

  end

Pretty noddy example and probably driving TDD advocates potty with agitation, but hopefully it demonstrates the functionality.

That pretty much wraps it up – anyone interested in what the person class might have looked like in order to pass the tests, here it is;

class Person

  attr_accessor :firstname, :lastname
  attr_reader :age

  def name
    @firstname + " " + @lastname
  end

  def age=(val)
    raise RangeError if(val > 200)
    raise RangeError if(val < 0)
    @age = val
  end

end

Here’s something awesome to close with. I had previously mentioned that the ruby community is very passionate – it should also be pointed out that they are completely nuts, as the following demonstrates!

If you wanted to create a test stub that you were going to come and finish up later, you are encouraged to do so using the following method;

  def test_person_is_valid
    flunk
  end

This is, 100% genuine, part of the standard ruby library. That method causes you to flunk the test. I’ll close with the output 🙂

Started
..F
Finished in 0.004339 seconds.

  1) Failure:
test_person_is_valid(TestPerson) [person-tests.rb:40]:
Flunked.

3 tests, 9 assertions, 1 failures, 0 errors

Singleton pattern in .net and c#

I was talking to my brother earlier (also a developer, although specializing in game development) and he mentioned that he’s always had an issue implementing the singleton pattern under c#/.net, also citing that he finds it a bit tricky generally when using OO languages.

Well, here’s one way to do it. As he’s a game developer, let’s assume that we’re using the pattern to accomodate the current state of a video game.

    

class GameState
    {
        //The Single Instance
        private static GameState _singleton = new GameState();     

        //The constructor
        private GameState()
        {
            _score = 0;
        }

        //A "player score" property and member
        private int _score;
        public static int Score
        {
            get
            {
                return _singleton._score;
            }
            set
            {
                _singleton._score = value;
            }
        }
    }

Possible improvements to this would be to have a static “initializeGameState()” method and create the singleton instance in there instead. Either way, using the above method allows you to write code like this;

           
GameState.Score = GameState.Score+100;

I don’t find much use for the singleton pattern in my line of work (the web) but hopefully this’ll be of use to someone!

EDIT: Many good improvements have been suggested in the comments which can help to make this even lazier (in my example, the initialization of the singleton would happen the first time someone used any of the static methods in the code, rather than when the user perhaps intended to start)

Project Euler Problem 4

Have decided to try and get a few of these done every week just to keep the ol’ brain alive. Here’s my working for Project Euler problem 4 in C#.

class Program
 {
 static void Main(string[] args)
 {
 int biggest = 0;

 for (int i = 100; i < 999; i++)            
   for (int j = 100; j < 999; j++)
   {
      int product = i * j;
      if (IsPalindromic(product))                      
        if (product > biggest)
          biggest = product;
   }
 
   Console.WriteLine("Done!, biggest was " + biggest);
   Console.ReadKey();

   }
 }

Where “IsPalindromic” is as follows…

        public static bool IsPalindromic(int number)
        {
            string s = number.ToString();
            int frontCounter = 0;
            int backCounter = s.Length-1;

            while (frontCounter < backCounter)
            {
                if (s[frontCounter] == s[backCounter])
                {
                    frontCounter++; backCounter--;
                    continue;
                }

                return false;
            }
            return true;
        }

brute force… but for something this trivial I don’t care 😛

Ancient Egyptian Multiplication in C#

Clocks have gone back in the UK and I can’t sleep so decided to do a little light programming to try and send me off. I’ve basically coded up an ancient Egyptian multiplication algorithm in C# using a .net Dictionary object. If you want to read up on the algorithm itself, here’s the wikipedia article.

This algorithm is also known as Egyptian multiplication, Ethiopian multiplication, Russian multiplication, or Peasant Multiplication. I did also find an implementation of this over on Rosetta Code – the one they have there is much more streamlined than what I ended up doing (they even did a linq version that I’m very jelous of!) but this one’s more readable than the recursive version they give over there so thought it was at least worth posting.

Okay then here we go: Ancient Egyptian Multiplication in C#!

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

        public static int AncientEgyptianMultiplication(int multiplicand1, int multiplicand2)
        {
            Dictionary<int, int> pairs = new Dictionary<int, int>();            
            pairs.Add(multiplicand1, multiplicand2);
            return performMultiplicaiton(pairs);
        }

        private static int performMultiplicaiton(Dictionary<int, int> pairs)
        {
            if ((int)pairs.Last().Key == 1)
                return pairs.Last().Value;
            else
            {
                var latestPair = pairs.Last();
                pairs.Add(latestPair.Key / 2, latestPair.Value * 2);

                if (latestPair.Key % 2 != 0)
                    return (int)latestPair.Value + performMultiplicaiton(pairs);
                else
                    return performMultiplicaiton(pairs);
            }
        }

Recursion Simplified

Why write an article about recursion? Every developer already knows what it is and it’s taught in every single computer science course the world over. Still, it’s a technique that can have even the most experienced developers running to the hills. There is a good reason for this; in whatever aspect they choose to deploy their skills, most developers will have no cause to use recursion and in many will have a really good reason not to. Over time this lack of exposure leads to an unfamiliarity and, eventually, rabid and uncontrollable fear.

The reason I am writing about recursion (well, the boring reason anyway) is that I’m planning to do a few articles about search algorithms and those will use recursion fairly liberally, so I wanted a foundation article to refer back to should anyone be afflicted by this rabid and uncontrollable fear 🙂 However, it dawned on me that I may have some wisdom to impart in the process of doing so. Therefore the aims of this article are to answer the following questions;

  1. What is recursion?
  2. Why are people so freaked out by recursion?
  3. How can those people shed their freak-out-ed-ness?
  4. How do you use recursion?
  5. When should you use recursion?

I used to struggle a bit with the concept myself. I eventually was lucky enough to have a very logical approach explained to me by a man named Uday Reddy around ten years ago – suddenly everything was so clear. Hopefully I’ll be able to do the same for you guys. Examples will be in C#

What is recursion?

Well, lets start off with a silly example; Go ahead and type “recursion” into google. You’ll find yourself presented with your search results along with a familiar message asking you;

Did you mean recursion?

Of course I did! A quick click on google’s advice leads me to the same page, with the same question. Aaaaah. I see what they did there…

Wikipedia, at time of writing, cites the example of two mirrors positioned exactly parallell to one another as an demonstration of real-world recursion. Already then, we’re associating the concept of recursion with the concept of infinity. Keep that in mind while we head straight into another silly example…

One of the available alternatives to XML is YAML (used for configuration files under the Ruby on Rails framework, for example). YAML syntax is significantly different to XML syntax in a number of ways; of particular note are the importance of whitespace and the complete absence of <braces>. In fact, it has almost nothing in common with any markup language so how very dare it acronymically declare itself “ML”? Well, it’s for this very simple reason;

YAML stands for “YAML Ain’t Markup Language”

Aaaahh, I see what they did there as well. Another recursion gag.

So why are people so freaked out about it? Well, anyone who directly or unknowingly subscribes to Knuthian programming principles believes that their code should read like a good novel. Somebody should be able to visibly see the thought processes that went into constructing any piece of code, even if they were not the author. When was the last time you read a novel that went on forever, or instructed you to go back and read a bit that you’ve already read?

In going through these examples, we’ve stumbled upon the very reason that most programmers will avoid recursion like the plague if they can: Basically because it messes with your head; The human brain can’t really comprehend the concept of infinity and it’s something that makes people go “aaaaah” in the context of a gag. Why on earth would anyone want to introduce complex and ridiculous factors such as these into their code!?

Well, the first thing to make clear is that the word recursion has a very different meaning when applied to computer science. Here, recursion is used as an adjective to describe a function. To give it a really sterile definition, a recursive function is one that “calls itself”.

Let’s just bin the concept of infinity straight away – all function calls go on a stack and a stack can overflow, ergo a recursive function needs to stop somewhere. Secondly, you shouldn’t ever just use recursion for the sake of it – there are very specific cases where it is appropriate and outside of those cases it is rightfully guilty of its own major criticism: it makes your code less readable.

In those situations where it is appropriate, however, recursive code can actually be far more readable than any for-loop powered equivalent. It is my personal belief that recursive functions are only “less readable” when they’re used in inappropriate situations – hopefully I’m about to convince you of the same thing.

How to think about recursion logically

In a nutshell, recursion can be summed up as follows;

If a problem domain is vast, but a simpler version of the same problem would be easy to solve, then it makes complete and total sense to simplify the problem before you solve it.

If the above statement can be applied to a situation, then recursion should be considered an appropriate solution. Literal examples are mainly focussed around either problem solving or search situations, such as breadth/width first search or any divide and conquer algorithm (some of which I’ll be covering in the aforementioned “follow-up articles”). If we boil my definition down into a pseudo-code then it kinda goes like this;

do I know the solution?
Yes: Yay I have the solution! (return)
No: Lets try solving a simpler version of the problem then…(repeat)

You can infer from this that you basically need to know two things when dealing with recursion;

  1. How do I know I have reached the solution?
  2. How do I simplify the problem?

Or, to put it another way…

  1. Stopping Criteria: When should I stop?
  2. Simplifying Algorithm: How do I simplify?

In terms of the Stopping Criteria, there are a number of ways that you can identify when to stop simplifying. Maybe you’ve reached your solution, or maybe it is not possible to simplify the problem any more (these two often go hand in hand). The Simplification Algorithm is very bespoke to a given situation, but once you’ve evaluated your problem domain it should be pretty easy to figure out. The following section shows how these two terms work in practice.

Some recursion examples, using the established logical approach

A popular recursion example is the “factorial” problem. Any number “factorial” is basically the number multiplied by each of its iterative successors (down to 1). For example, five factorial is just the result of the following equasion;

5 x 4 x 3 x 2 x 1

If we were avoiding recursion completely and just trying to create a function that would solve this problem using for-loops, it would go something like this;

private static int factorial(int num)
{
  int total = num;
  for(int i = num-1; i > 0; i–)
  {
    total = total * i;
  }
  return total;
}

So, what we’ve ended up with is not nice, readable code and is ridiculously non conventional. The counting expression is a decrementor and the initializer expression involves an equation. It’s perfectly valid code, but it does make your brain work more than it should to figure out what is going on. What I’m about to prove is that solving this problem recursively makes the code more readable.

So as mentioned previously, we know that we need to establish two things: The stopping criteria and the simplifying algorithm. In the case of the factorial problem, these are as follows;

  • stopping criteria: The simplest problem is 1 factorial, the answer to which is 1. Therefore, stopping criteria is when we are trying to find the result of 1 factorial.
  • Simplification algorithm: Multiply by the number one lower than what I’m currently evaluating.

Therefore, the factorial problem when implemented recursively looks like this;

private static int factorial(int num)
{
  if(num == 1)
    return num;
  else
    return num * factorial(num – 1);
}

Where the “if” part is the stopping criteria, and the “else” part is the simplification algorithm. For a start it’s shorter, but is it more readable? I’d argue that it is. I can clearly see that there are only two possible outcomes to the function: Either I’m at the solution or I’m trying to simplify it.

Okay lets do another one: Imagine you’re doing x to the power of y. So 5 to the power of 4 would be;

5 * 5 * 5 * 5

We won’t bother with the for-loop version this time, let’s just try and figure out how to do this recursively in a logical way. The only two things we need in order to implement recursion, once again, are the stopping criteria and the simplification algorithm. The “simplest solution” in this case would be any number to the power of 1, in which case the result would be the number itself. This is therefore our stopping criteria. In terms of our simplification algorithm, we need to keep multiplying the number by itself until we reach the stopping criteria described previously, so the number of times we multiply is the thing that is getting simpler. Therefore the code goes a little something like this;

private static int power(int num, int toThePowerOf)
{
  if(toThePowerOf == 1)
    return num;
  else
    return num * power(num, toThePowerOf – 1);
}

where once again the “if” part is the stopping criteria, and the “else” part is the simplification algorithm.

In reality, you wouldn’t need to write those kinds of algorithms because if you’re using a half decent framework then they’ll be there for you anyway, but the principles demonstrated here are completely sound when using recursion in practice. For example, a more appropriate use of recursion (which I’m not going to demonstrate here) would be in situations such as tree traversal. In this case, your “stopping criteria” would be when you’ve reached the node you were looking for, and your simplification algorithm would be to search any successor nodes that you haven’t already visited.

Conclusion

Hopefully this has been enough to convince you that recursion is absolutely nothing to be afraid of. It is completely possible to work through its implementation logically and still end up with code that is more readable than the alternative. You should however bear the following in mind;

  • only use recursion when it’s appropriate – it IS less readable if applied inappropriately.
  • Keep recursive functions short – if a function is getting too big it’s usually an indication that you should do a bit more abstraction first.
  • Don’t be freaked out by recursion: It’s just a technique that can be thought about logically and when deployed appropriately will create beautiful, readable code.