Basildon Coder

Jeff Atwood has an article up today bemoaning the fact that seemingly nobody “gives a crap about freedom zero”. Well, my initial reaction was that surely nobody could care about something with such a thoroughly ridiculous name. Freedom Zero? Really? I know this is the FSF’s first freedom, and programmers count from 0 don’tcha know, but it’s still rubbish.

But the real reason is that it simply isn’t important enough to override everything else.

Certainly, for some things you want the freedom and reliability of open source. I write my essays in OpenOffice, I use Vim as my text editor for all programming languages other than C#, and I write maths papers with LaTeX. I want my personal output to remain usable and not at the whim of some company somewhere, I agree with all that.

But do I need my MP3 player to be open? No. My videogame console? No. My phone? No. My movie editor? No (though only because I always archive the source material). The irony is that people do indeed care about freedom - the freedom to choose, and the sad fact is that there is a certain type of zealot who only espouses freedom as long as it’s their type of freedom. And that isn’t freedom at all.

Now, as it happens, Linux is my operating system of choice. I don’t own any Apple computers, though I do have a first-gen iPod Mini, which is distinctly showing its age. I use Vista for .Net development, but I don’t think anyone could reasonably call me an Apple zealot or an anti-freedom capitalist whatever.

But you won’t catch me criticising Apple for their closed platform. If it results in a decent product, I’m all for it. I used to have a G4 iBook and liked it a lot. When I’m in the market for an ultraportable later this year, I will give due consideration to the Mac Air.

A Mac is a product - calling the hardware nothing more than a dongle is a ridiculous argument. You can run Linux on Mac hardware, and OSX on non-Mac hardware (suboptimally, granted). Would you call a Ferrari Enzo a dongle because you need one in order to run the Enzo engine management software?

And it should be said that Apple isn’t quite as closed as some people suggest - I can still install Firefox, Thunderbird, and other open source tools if I want to tackle the hostile internet with a trusted armoury. And OSX comes with things like Apache and SSH installed out of the box.

So do I give a crap about freedom zero? Only in as far as it suits my needs. If a piece of closed software does a better job, and the risk of losing data forever is within my tolerances, then sure I’ll use it and I won’t let ideology get in my way.

On the flip side, I care about interoperability, and I contribute or donate to a few open source projects, and will strongly oppose anything - legal or technological - that attempts to muscle open source out of existence. An open source tool deserves the right to compete. I use Amarok not because it’s open, but because I like it more than iTunes. Conversely, I use Visual Studio not because it’s proprietary, but because I prefer it to SharpDevelop.

Use the best tool for the job.

So, as previously mentioned, we’ll start with the basics. This material is probably very familiar to most coders with even a small amount of experience, but it never hurts to refresh the fundamentals. You may even find that there’s some material that seems so obvious you don’t even actively think about it any more - which is good if it has become habit, but may be bad if you’ve grown complacent in certain areas.

The overarching theme of the first chapter is complexity. Complexity is the enemy of the software developer, and it is vital to understand this fact. If you don’t identify complexity as the enemy, you will find it harder to remain vigilant against it. 

Anyone who has worked as a developer for more than a year or two will almost certainly have exposure to the problems caused by complexity, but quite often complexity itself will not be pinpointed as the root cause. It may be a case of not seeing the wood for the trees - when trying to understand a system it’s very easy to get bogged down wondering why some particular section of code does things a certain way, and not see the problems with the big picture. Of course, since complexity obscures the big picture, this is common and self-perpetuating.

Object-oriented design, then, is a tool for managing complexity. Of course, it is many other things too, but this is one of the fundamentals. In particular, OOD is a natural way to represent hierarchies, and hierarchies are the primary tool Booch presents for making complexity manageable. A number of examples from nature are provided; for example, you can view a plant simply as a plant, or as a collection of structures (leaves, stem, roots).

Importantly, the overall hierarchical view of a plant can be broken down into many interacting sub-hierarchies, each of which may be considered in terms of its own structure and its interactions. This is an example of decomposition. If you want to study roots in detail, you can study the branch roots, the root apex, and the root cap - and break that down further if you like to consider roots as a collection of cells. To study roots in this sort of detail, however, you do not have to go to the same lengths with leaves and stems - it is enough to understand the interactions between the higher-level components.

Complexity, therefore, is more manageable if it is divided into interacting components, each of which can be further divided into interacting subcomponents. At different levels of abstraction there are clear boundaries - it shouldn’t be necessary to understand the epidermis of a leaf to examine a root, and likewise the study of a leaf should not need to consider the role of the root apex. This is known as separation of concerns, and allows you to ignore the parts of the system that you are not interested in at the time.

In software, these principles are captured by OOD. Broadly, hierarchies can be modelled with inheritance, components can be modelled with modules, intercomponent interactions can be modelled with interfaces and method calls, and intracomponent interactions can be modelled with aggregation. These interactions are key, as they form part of the ‘value’ of a system - in layman’s terms, the whole is greater than the sum of its parts.

Inheritance and aggregation are, respectively, ‘is-a’ and ‘part-of’ relationships. In both cases, these represent separate but overlapping hierarchies. Booch’s example is that of an aeroplane. An aeroplane can be thought of as an aggregation of systems - propulsion, flight control, etc. Each of those can potentially be modelled as specilaised types too - for instance a jet engine is a particular type of propulsion, and a turbofan engine is a particular type of jet engine.

In OO terms, the ‘is-a’ relationships are expressed as class structures utilising inheritance, and ‘part-of’ relationships are expressed as object structures utilising aggregation.

Relative primitives are an interesting concept, and refer as much as anything to the benefit of having a sensible and appropriate vocabulary at each level of abstraction. With plants, for instance, if you are working at the cellular level your primitives are nuclei, chloroplasts etc. If, however, you are at the top level your primitives should be leaves and stems - something is wrong if you are concerning yourself with the nucleus of a cell at this level of abstraction. Relative primitives are a natural consequence of hierarchies and decomposition, if your hierarchies are sane.

Even with all these tools for managing complexity at our disposal, it is still extraordinarily hard - if not nigh-on impossible - to construct a large complex system in one fell swoop. Booch identifies that a key characteristic of successful complex systems is that they evolve from simpler systems, whilst always being useful during that evolution - they have stable intermediate forms.

Contemporary development processes, such as agile development, explicitly recognise this with the mantra of ‘deliver early, deliver often’. The idea is that functionality should be delivered iteratively, with each iteration being functional and testable. This is in contrast to more traditional waterfall methodologies, which are notoriously associated with failed projects, often due to attempting to design a large complex system up-front and develop it all at once.

In summary, then, Booch argues that the characteristics of a manageable complex system are as follows:

• Hierarchic
• Uses relative primitives
• Has robust separation of concerns
• Has stable intermediate forms

It is important to note in passing that, since OOA&D is an unashamed champion of object-orientation as a mechanism for managing complexity, OO is by no means the only approach - functional and procedural languages have their own techniques, and in some cases may be more suitable, depending on the problem to be solved. Even so, many of these principles are common and are useful things to bear in mind when designing a system.

Next week we look at chapter 2, which covers the object model in greater detail.

Scott Hanselman continues his Weekly Source Code series with a look at algorithms for generating the Fibonacci sequence in a variety of different languages. He misses my favourite implementation, though fortunately a wise commenter has already sought to correct such an egregious error. As is so often the case, it is Haskell that provides the most elegant yet mind-bending alternative:

fibonacci n = fib!!n
    where fib = 0 : 1 : zipWith (+) fib (tail fib)

This little beauty appends a list with its own tail while it’s still being generated and lazily sums the elements. On top of that, it’s fast, since unlike most naive recursive Fibonacci generators it doesn’t waste time recalculating previous values. In fact, it runs in linear time, that is O(n), and on a fairly modest 2GHz Athlon XP will calculate the 50,000th Fibonacci number in around 600 milliseconds. By contrast, the naive recursive implementation in C# (see below, adapted and corrected from the code Scott posted) takes 28 seconds to calculate the 45th number, on a much more powerful Core Duo machine.

$ time ./Fibs.exe
1134903170
Execution time: 00:00:28.2930000      

real    0m28.382s
user    0m0.000s
sys     0m0.031s

As implemented, you can’t go much higher than this since the 47th number in the sequence (2971215073) is too big to store in a 32-bit signed int. Asking for the 50,000th number results in an immediate stack overflow, which is the runtime’s way of saying “don’t be ridiculous, mate”.

Of course, the C# version could be made many times faster and more efficient by implementing it iteratively (i.e. with a for loop), but this is less natural since the Fibonacci sequence is a recurrence relation and therefore best expressed recursively. The beauty of the Haskell version is that it combines expressiveness with performance, always a happy combination.

using System; 

namespace Fibs
{
    class Program
    {
        static void Main(string[] args)
        {
            DateTime start = DateTime.Now;
            Console.WriteLine(Fibonacci(45));
            Console.WriteLine(“Execution time: {0}”,
                DateTime.Now.Subtract(start));
        }

        static int Fibonacci(int n)
        {
            if (n == 0 || n == 1)
                return n;
            return Fibonacci(n - 1) + Fibonacci(n - 2);
        }
    }
}

The late, great Douglas Adams once felt moved to write an article about how to make a decent cup of tea. His motivation was the fact that so many of our American cousins are baffled by the British predilection with a nice hot brew; he concluded that the reason for such bafflement was the fact that “most Americans have never had a good cup of tea“, thanks largely to the habit of using hot (rather than boiling) water, and no teapot.

Now, there is a similar threat to another great British tradition. Recently, a recipe for Shepherd’s Pie hit the front page of Digg, prompting a lengthy comment thread which contained a number of remarks that British food sucks, or that Shepherd’s Pie in particular was horrible. A glance at the recipe suggests a good reason for this - diligently following it to the letter will result in a ghastly concoction almost entirely unlike a good Shepherd’s Pie. No wonder British food has such a lousy reputation abroad.

To redress the balance a little, here’s a proper Shepherd’s Pie recipe for any Americans out there wondering what the fuss is about. This is only a little more complicated than the aforementioned abomination, yet immeasurably superior.

Firstly, forget any nonsense about using beef and (horror of horrors) gravy from a jar, or indeed gravy in any form. Neither have any place in a Shepherd’s Pie. Firstly, use lamb - it’s called Shepherd’s Pie for a reason. Your average shepherd is more likely to have access to lamb than beef, yes? So what do you think they would use in cooking? I thought so. Secondly, use stock instead of gravy.

In order to keep it simple, like the original recipe (which was aimed at beginners), I’ll use convenient ingredients (dried herbs, bouillon cubes, etc) rather than fresh. Obviously the recipe is even better with all fresh ingredients and homemade stock.

You will need the following:

• 1lb ground lamb
• 1 1/2 cups lamb or chicken stock
• 2lb potatoes
• 1 onion
• 1 carrot
• Rosemary
• Worcestershire sauce

The other recipe required ground beef, canned gravy, and potatoes, so basically the difference is that we use lamb instead of beef, stock instead of gravy, add a carrot and an onion, and bring out the flavour with rosemary (essential to get the best from most lamb dishes) and Worcestershire sauce. I don’t know how easy it is to get the latter in the U.S. but it was referenced as an optional ingredient in the other recipe, so I assume it’s available.

Recipe

So, first of all brown the lamb in 1tbsp olive oil, in a large pan. Make sure to break up any lumps. Whilst it is browning (about 5 minutes or so), finely chop the onion.

When the lamb is browned, transfer it to a bowl using a slotted spoon. Do not discard the pan juices. Instead, lower the heat and add the onions, cooking until soft (about 8-10 minutes). Add a pinch of minced garlic or garlic powder if you like.

Whilst the onions are cooking, finely chop the carrot. If you are using a bouillon cube for the stock, dissolve it in boiling water now. Re-add the lamb to the pan, along with the chopped carrot, the stock, a good pinch of rosemary, and 2tbsp of Worcestershire sauce. Do not omit the last two ingredients - they are essential. I mean it.

If you want to experiment further, you can also try adding a pinch of thyme, 1/2 cup of red wine (only use 1 cup of stock if you do this), and 1tsp tomato puree - but you can get a gobsmackingly tasty result without these ingredients.

Stir well, lower the heat to a simmer, and cover. Simmer for about an hour, stirring occasionally, until the stock has reduced (don’t let it dry out and stick to the pan though). Taste it - it will be phenomenal.

From here, you can more or less follow the other recipe - add the lamb to an oven dish, top with mashed potatoes made however you like them, and sprinkle with cheese (I use grated parmesan since it crisps up nicely, but you can use whatever cheese you like). I also like to add a little paprika and black pepper at this point. Finally, sling it in a preheated oven at 400ºF or 200ºC for half an hour.

Serve with whatever vegetables you like - I tend to go for peas, but if you prefer corn, great. Tuck in and enjoy.

Hopefully, in the same way your first good cup of tea convinced you that the Brits aren’t crazy when it comes to hot beverages, your first good Shepherd’s Pie will convince you that we know a thing or two about good food as well.