Have you ever had this frustrating experience? You need to drive somewhere that you’ve not been before, so you look that place up on the web. You find its site, and start looking through the pages for the address and postcode. Instead, you find this kind of thing:
To get to us from the south/east (for example, if driving from London), the easiest way is to get onto the A4136 heading southwest, then turn right onto Morse Road which takes you straight to Ruardean. Our house is on the right as you approach from this direction, almost immediately after the 30-mile-per-hour speed-limit sign that marks the boundary of the village.
You didn’t want instructions on how to find the place. You just wanted to know what the address is: you know how to reach a place with a known address, because you have Google Maps and a satellite navigation system and a helpful wife who will shout “Left! Left! No, LEFT! Why didn’t you turn LEFT?” when required.
The postcode GL17 9XF tells you what the destination is; the series of instructions on the unhelpful web-site tell you how to reach the destination.
And this seems to be the core of the difference between imperative programming (which is what most of us do most of the time) and functional programming (which is what exotic academic types like to do in their ivory towers, never actually getting anything done but writing a lot of papers).
Except, wait, didn’t we just agree that functional addresses are better than imperative ones? They give you more freedom in figuring out how to implement them, and they are not sensitive to global state such as whether you happen to be coming from London in the first place. What if you’re coming from Cardiff? If you follow the imperative address (and you are of a literal turn of mind) you’ll drive to London, then follow the directions quoted above(*), which is hardly optimal.
So could it be that functional programming is better than imperative programming after all?
What does a functional program look like? At the risk of perpetuating a cliché, consider the toy problem of factorials. (I nearly said “the problem of calculating factorials, but even saying it that way presupposes an imperative approach to solving the problem.) A factorial is the product of a specified integer and all smaller positive integers, so that factorial(5) is 1x2x3x4x5 = 120. And the obvious way to write a function for that is of course:
This is nice, simple code, and hard to get wrong. (Although as a matter of full disclosure, I guess I should admit that I did get it wrong when I typed it in just now for this article: I forgot the x = x – 1 and got into an infinite loop. Oops.)
That’s an imperative program, which tells you how to calculate a factorial. But a functional program just says what a factorial is — the number you first thought of times the factorial of the number one less than that. (I’m using Ruby as a sort of executable pseudocode for both versions of the factorial function so that language-wars don’t obscure the conceptual point.)
And this version also works just fine. Of course I cheated a bit, by not saying up front how this version avoids getting into an infinite loop of its own. The answer is that the factorial of 1 is just 1 — there’s no need to go figure out the factorial of one-less-than-one.
Which version is better? That’s a matter of judgement and, yes, opinion. Leaving aside all performance considerations (which we probably don’t understand as well as we think we do anyway), and thinking only about comprehensibility, which is clearest? I really couldn’t say.
But of course this function is so short and simple anyway that both versions are bound to be easy to read and understand. The real question is: which approach scales better to realistic-sized problems? And the answer to that seems to depend as much on the temperament of the individual as it does on the intrinsic merits of one approach of the other.
Like a lot of programmers, I was raised imperative but have been repeatedly drawn to functional — often seeing the appeal, but never yet able to make the leap into actually doing anything in a functional style beyond artificial exercises. It’s time that changed: I am going to make a serious attempt at Lisp, the canonical functional language, and I’m going to blog it as I go.
Let me be clear: I am not setting myself up to teach anyone anything about this subject, since I know close to nothing about it myself. I’m just hoping my notes might be useful to fellow travellers, if only so that they can avoid making the same dumb mistakes as I do. And those of you who are further along the road than I am, please do shout when I wander off the path!
We start next week!
(*) A favourite joke of mine (not original to me, but I don’t remember where it’s from). The university’s Health and Safety officer is checking that the faculty know what to do in the event of a fire. He asks an engineer, “What would you do if you were locked in the laboratory and a fire broke out?” The engineer thinks for a moment and says “The centrifuge in the lab is pretty heavy: I’d use that to smash the door down and make my escape”. “Very good”, says the H&S guy, and turns to a mathematician. “And what would you do”, he asks, “if you were up on the roof when a fire broke out?” Quick as a flash, she replies “I’d lock myself in the engineering lab, thus reducing the problem to one that has already been solved.”
Thank you, thank you, I’m here all week. Don’t forget to tip your waitress.
*** Special bonus EoPS extract ***
As I’ve continued my re-reading of The Elements of Programming Style, I ran across this old favourite from page 70, which I thought you might enjoy:
“Finally, the two inner loops (on K2) are handled differently even though they perform similar functions. This tips us off that one of them is incorrect. (As a matter of fact both are, but the details are not worth pursuing.)”
This, by the way, in the section illustrating the rule “Don’t patch bad code — rewrite it.“