Archive for March, 2008

The Lightbulb Moment

Weiqi Gao has a post up today discussing the trials of grokking Scala. Scala is a language I want to take a much closer look at later this year, since I want to become current on the JVM again (having not been on talking terms with it since using J2SE 1.4 around the summer of 2003) without being particularly keen on tangling with the Java language itself.

One of the key features of Scala is the functional programming style it brings to the JVM. It’s actually quite common to use certain functional idioms in Java – e.g. passing around a function as a parameter – but the syntax is clunky and verbose (unless and until closures get confirmed in 1.7, that is, and maybe even then).

For example, take a look at this very simple idiomatic code for spinning off a thread to perform an expensive operation:

new Thread (new Runnable() {
    public void run() {
        someObj.doExpensiveOperation();
    }
}).start();

Now that’s not the most hideous code I’ve ever seen, but it’s a bit…wordy. Compare it to this equivalent implementation in Java’s closest mainstream relative, C#:

new Thread(x => someObj.DoExpensiveOperation()).Start();

I much prefer this syntax, even taking into account the throwaway lambda parameter that’s only there to satisfy the ThreadStart signature. The Scala syntax is even nicer, however:

spawn({ someObj.doSomethingExpensive })

This is the sort of thing that piques my interest about the language – expressive syntax and a very funky concurrency model will get my attention, especially when running on something as mainstream as the JVM and with full interoperability with the frankly staggeringly-vast Java library ecosystem. I like F# on the CLR for similar reasons.

But I digress; what I wanted to talk about was a point made by Weiqi, when discussing the pattern-matching capabilities of Scala:

Pattern matching in Scala is exactly the point at which I would spend time trying to understand it, trying to master it, trying to learn to use it. I understand the syntax. I understand the explanation that the speakers in presentations gave. I do get to the part where I say “This is cool.” But I never get to the point where I would see a problem and say “This problem is best solved with pattern matching, let me fire up Scala and code the solution.”

This strikes a chord for me, as I have gone through that stage once or twice myself with other features in other languages and yet can’t quite put my finger on how I get past it. I don’t think it’s something you consciously do – it’s just something you keep grafting away at until suddenly you realise that the technique, whatever it is, has become part of your armoury.

Closures are an obvious example I can think of in my own background. I was raised as a straight-down-the-middle C++ man, way back in the early/mid-90s, cutting my teeth on Borland Turbo C++ 3 on Windows 3.1. When I first started to play with functional languages it took a long time for me to ‘get it’, and even when I understood what a closure was after a couple of weekends hacking around in OCaml, I couldn’t envisage when I’d ever need one.

Soon after, whilst working on a Konfabulator widget in javascript, I noticed I was using them all the time. I suddenly had much more insight into what ruby blocks were doing. It wasn’t so much that I noticed the lights go on – they’d been on for some time and I hadn’t realised.

People commonly refer to the ‘lightbulb moment’ or ‘the lights went on’ as being the point where a flash of inspiration hits and everything suddenly makes sense. I don’t like this metaphor. If I need to go to the bathroom in the middle of the night, when the lights go on I squint in pain and stagger around just as blindly as I did before. But then I acclimatise, and all becomes clear. And so it is, I think, with learning alien concepts – you need a bit of time to adjust to the dazzling light.

  • Share/Bookmark

Project Euler Problems 1 and 2

Browsing through Nate Hoellein’s blog recently led me to Project Euler. This is a problem – I have a horrendous feeling I’m about to get addicted to it, to the cost of just about everything else that normally occupies my free time. Ack.

Still, at least it provides some blogging material. I’m going to start working my way through the list, and try to create idiomatic solutions in a number of languages. I won’t always look for the most efficient solution, since I’m also interested in expressiveness (see here and here for previous posts on the subject).

To start with, here’s some code and thoughts for problems 1 and 2.

Problem 1

Add all the natural numbers below 1000 that are multiples of 3 or 5.

This is generally regarded as the easiest Euler problem, so shouldn’t present too many problems. Mainstream software development is still dominated by imperative languages and styles, so the most recognisable solution to this would be a straightforward for-loop. Here is an imperative C# solution:

int result = 0;
for (int i = 0; i < 1000; ++i)
{
    if (i % 3 == 0 || i % 5 == 0)
        result += i;
}

Simple enough, but as with all for-loops the guts are a little too visible. I have to explicitly declare and increment an accumulator variable as well as the loop counter. A functional style (Haskell in this case) allows a more declarative solution:

sum $ filter (\n -> n `mod` 3 == 0 || n `mod` 5 == 0) $ [1..999]

Or, with list comprehensions:

sum [n | n <- [1..999], n `mod` 3 == 0 || n `mod` 5 == 0]

In both cases, the loop is replaced by a list generated from Haskell’s range operator. [1..999] creates a list containing every integer between 1 and 999 inclusive. The modulo test is basically the same, though Haskell lacks a modulo operator (% in most C-family languages) so the mod function is used instead.

Just for fun, here’s an F# solution too:

let sum = List.fold_left (+) 0
let mod35 = fun x -> x % 3 = 0 || x % 5 = 0

List.filter mod35 [1..999] |> sum

This could be compressed into a one-liner like the Haskell solutions, but it would be a bit long for my taste. Also note F# is slightly hamstrung by the lack of a built-in sum function, so I have to define my own using fold. Another F# solution is here, but I prefer mine. There’s a very nice snippet in the comments of that page, though, which I like even more:

Seq.fold1 (+) {for i in 1..999 when i % 3 * i % 5 = 0 -> i}

Interestingly, C# is gaining some fairly powerful functional techniques lately, in particular LINQ. I can use the new Enumerable class to mimic range syntax and filter functionality from other languages, and lambdas to keep the code concise.

Enumerable.Range(1, 999).Where(
        f => f % 3 == 0 || f % 5 == 0).Sum();

Note the similarity between F#/Haskell’s lambda syntax and that of C#. It’s very cool that a mainstream C-derivative language is getting this sort of syntax added to it.

Alternatively, I could use LINQ query expressions for a different approach:

var nums = from n in Enumerable.Range(1, 999)
           where n % 3 == 0 || n % 5 == 0
           select n;
nums.Sum();

Fun!

It should be noted that all the Project Euler problems I’ve seen so far have mathematical solutions, meaning if you are able to classify the problem correctly it is straightforward to work out the answer with pen and paper. In this case, the problem is based around an arithmetic progression, and there are powerful formulae for reasoning about those. If you’re interested, check out the forum for problem 1.

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Ooh, Fibonacci. I’ve been here before. Using the Haskell code from that post makes problem 2 a snip:

fib = 0 : 1 : zipWith (+) fib (tail fib)
sum $ filter even $ takeWhile (<4000000) fib

Given the lazy Fibonacci generator in the first line, this just uses standard Haskell functions from the Prelude to do all the work – reading right to left, takeWhile pulls data from the fib sequence until the test fails (i.e. we’ve reached 4,000,000), filter even does exactly what it says on the tin, and sum does the business on the result.

C# could solve problem 1 very neatly – can it keep up the pace in problem 2? Actually, yes it can, after a fashion. The lazy Fibonacci generator can be implemented using the yield statement added in C# 2.0. This is much more efficient than the naive recursive solution I looked at in my previous post about Fibonacci sequences. Once I have the generator, the LINQ statement is very concise and quite similar to the Haskell code – C# 3.0 even has TakeWhile!

IEnumerable<long> Fibs()
{
    long a = 0, b = 1;

    while (true)
    {
        yield return b;

        b = a + b;
        a = b - a;
    }
}

Fibs().TakeWhile(f => f < 4000000).Where(f => f % 2 == 0).Sum();

The more I use C# 3.0, the more I like it – there’s quite a bit of power in there.

As with problem 1, there are some fascinating mathematical tricks that can be utilised when solving problem 2, and I recommend you check out the forum. It’s particularly cool to see how the Golden Ratio can be brought into play when working with Fibonacci sequences – I had no idea these techniques existed. So much to learn!

  • Share/Bookmark

The P.G. Wodehouse Method Of Refactoring

I am much given to ruminating on refactoring at the moment, as one of my current projects is a major overhaul of a fairly large (>31,000 lines) application which has exactly the kind of dotted history any experienced developer has learned to fear – written by many different people, including short-term contractors, at a time in the company’s life when first-mover advantage was significantly more important than coding best-practice, and without any consistent steer on the subjects of structure, coding conventions, unit tests, and so on.

In other words, here be dragons.

In fairness, the application works and has been a critical part of a company that has gone from nothing to market-leading multinational in 7 years, so it has certainly pulled its weight. It is in desperate need of a spring-clean though, and my team volunteered to spend 3 months evicting the cobwebs and polishing the brasswork.

Yes, volunteered – it’s a fascinating challenge, though perhaps not something you’d want to make a career of.

Now, the first mistake to avoid here is the compulsion to throw it away and rewrite from scratch. So often when confronted with a vast seething moiling spiritless mass of code a developer throws his hands into the air and declares it a lost cause. How seductive is the thought that 31,000 lines of code could be thrown away and replaced with ~15,000 lines of clean, well-designed, beautiful code?

Sadly, that’s often a path to disaster. It’s almost a rule of the game. jwz left Netscape because he knew their decision to rewrite from scratch was doomed. Joel Spolsky wrote a rant about the same decision – in fact, the Netscape rewrite is commonly cited as a major factor in Netscape losing the first browser war.

The problem is that warty old code isn’t always just warty – it’s battle-scarred. It has years of tweaks and bug-fixes in there to deal with all sorts of edge conditions and obscure environments. Throw that out and replace it with pristine new code, and you’ll often find that a load of very old issues suddenly come back to haunt you.

So, a total rewrite is out. This means working with the old code, and finding ways to wrestle it into shape. Naturally, Working Effectively With Legacy Code now has an even more firmly established place on my ‘critical books’ bookshelf than it did before.

Inspiration came from a less well-known book, however. Buried in Chapter 10 of Code Reading is a single paragraph suggesting that it can be useful when working with unfamiliar code to paste it into a word processor and zoom out, getting a ‘bird’s eye’ view.

One other interesting way to look at a whole lot of source code quickly under Windows is to load it into Microsoft Word and then set the zoom factor to 10%. Each page of code will appear at about the size of a postage stamp, and you can get a surprising amount of information about the code’s structure from the shape of the lines.

(Spinellis, 2003)

The idea is that this lets you immediately identify potential trouble spots – if you see pages where the code is all bunched up on the right, it indicates massive nesting and over-long functions. If you see heavy congestion, it indicates dense code. It’s also easy to spot giant switch statements and other crimes against humanity.

Of course, you don’t actually need MS Word to do this – the Print Preview in Open Office is more than sufficient, and no doubt most office suites can do the same.

This 50,000ft view could be a useful tool in tracking progress. I mean sure, we can have our build system spit out cyclomatic complexity and code size metrics, but wouldn’t it be neat if we could do a weekly bird’s-eye printout of the source code and pin it up on the wall, giving a nice simple visual representation of the simplification of the code?

Except, of course, that with average page lengths of 45 lines we’d need almost 700 pages each time, and a hell of a lot of wall space.

A better solution would be to print a class per page. At the start of the project, the application had about 150 classes, and the refactoring effort is focussed on about 80 of those. Initially, gigantic classes would be an incomprehensible smudge of grey, but as the refactoring process starts tidying the code and factoring out into other classes, the weekly printout would start to literally come into focus, hopefully ending up with many pages actually containing readable code (which happens roughly when the class is small enough to fit on no more than 3 pages at normal size).

The first time we pinned up the printouts, I suddenly recalled a Douglas Adams foreword reprinted in The Salmon of Doubt. Adams was a great fan of P.G. Wodehouse, and explained Wodehouse’s interesting drafting technique:

It is the next stage of writing—the relentless revising, refining, and polishing—that turned his works into the marvels of language we know and love. When he was writing a book, he used to pin the pages in undulating waves around the wall of his workroom. Pages he felt were working well would be pinned up high, and those that still needed work would be lower down the wall. His aim was to get the entire manuscript up to the picture rail before he handed it in.

(Adams, 2002)

Hmm, isn’t redrafting a literary cousin of refactoring? In many ways, I think it is – so why not apply this technique to refactoring?

And we’ve made it so. We tied a piece of string horizontally across the wall – that’s our ‘picture rail’. Every week we reprint the classes we have been working on, and replace the old printouts. Then we move them up towards the string, in accordance with how happy we are with the view.

Obviously, this doesn’t replace all the other tools we have for evaluating code quality – e.g. the aforementioned metrics, unit tests, manual QA, and so on. It does, however, make for a brilliant way of tracking our subjective satisfaction with the class. Software quality tools can never completely replace the gut instinct of a developer – you might have massive test coverage, but that won’t help with subjective measures such as code smells. With Wodehouse-style refactoring, we can now easily keep track of which code we are happy with, and which code we remain deeply suspicious of.

As an added benefit, all those pages nicely cover up the hideous wall colour. Bonus!

  • Share/Bookmark

Arthur C. Clarke, 16/12/1917 – 18/03/2008: Indistinguishable From Magic

Sad news – the legendary Arthur C. Clarke has died. He’ll be greatly missed; Clarke novels occupy a full shelf of my floor-to-ceiling bookcase, and Rendezvous With Rama stands proud as the finest sci-fi it has ever been my pleasure to read.

Aside from his very visible mastery of sci-fi, however, there is much to remember Clarke for. He is responsible for popularising the concept of geostationary orbit, which is very important for practical global telecommunications. When you watch the Olympics on TV this summer, you can thank Clarke for the fact that you haven’t had to go to China to see it.

Perhaps best of all, though, is his now-infamous Third Law:

Any sufficiently advanced technology is indistinguishable from magic.

Clarke’s Third Law has been quoted, referenced, and paraphrased copiously since he coined it, and it is almost axiomatic for many technologists. As a software engineer, I get a wry enjoyment from Gehm’s Corollary, i.e. “any technology distinguishable from magic is insufficiently advanced” – a sobering thought when confidently hacking away on the next big thing!

If your users don’t think your software is magic, then you have room for improvement. I believe Clarke would have approved of that sentiment. R.I.P.

  • Share/Bookmark