Monday, April 16, 2007

Zen and the Art of Functional Programming

I’m a regular at http://programming.reddit.com and just about every day there’s at least one (or two or three) posts about some functional programming language or the other. Usually it’s Haskell which is being showcased, though you’ll also find entries for Erlang and occasionally for some of the more obscure ones like O’Caml or Dylan. I finally zoned out under the constant barrage of propaganda and moaning softly (“brains! braaaaiiiiins!) zombie-shuffled over to check out what the fuss was all about.

What’s all this about Zen then?

The Zen of programming is when you internalise the correct way of solving a problem using the programming model you’re working with. You might start off programming with something like C, using it in a classic procedural fashion. When you move from Procedural Programming on to something like Object Oriented Programming (OOP) using Java or C++ etc., it’s a bit of a culture shock at first. You keep trying to program procedurally, fighting the language every step of the way. There finally comes a moment however, when all the abstract concepts behind OOP fall into place with an almost audible snap and suddenly, in a moment of epiphany, you attain OOP enlightenment.

Now I can’t say I’ve achieve that level of union with the Tao of Functional Programming, but I am starting to finally grok what the whole thing is about. However, all opinions listed below are subject to rather radical change!

What’s Functional Programming (FP)?

I’ll save me some time and copy-paste in some definitions.

Functional programming is a style of programming that emphasizes the evaluation of expressions, rather than execution of commands. The expressions in these language are formed by using functions to combine basic values. A functional language is a language that supports and encourages programming in a functional style.

-- FAQ for comp.lang.functional

Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast with the imperative programming style that emphasizes changes in state.

-- Wikipedia.

As far as I can make out so far, FP is all about decomposing the problem down to the various algorithms and data transformations involved and then cleanly enumerating them. We don’t really need to worry about the ‘objects’ involved (there aren’t any), or their relationship with one another. It’s all about dividing and conquering the problem by slicing it up into small bits and then figuring out what we need to do to each of the slices. Rather than identify objects, couple the data with behaviour and then deal with those objects, we pass both data and code around as required (and as easily), assembling and disassembling relationships as required.

Mind you, this is pretty much the SOP for most programming tasks, it’s just that FP makes it easier to work in this fashion. Besides, if you un-gag the Lispers for a moment, they will endlessly lecture you about the benefits of having small bits of code operate on large blobs of data. Rather like a shoal of Piranha reducing a buffalo. Be sure you re-gag them once you’re through or else they’ll never shut up.

Why spend time learning Functional Programming?

My primary reasons were:

  1. A New Paradigm: Learning a new programming paradigm helps to stretch your mind and makes you a better programmer overall, even if you never directly apply any of the new techniques you’ve used. Notice I’m talking about paradigms here, not languages. Learning C++ if you know Java may make you a lightly better programmer over all, but going from Procedural programming to OOP for example, can be a mind-bending experience.
  2. The Next Big Thing: The Functional programming weenies just can’t stop babbling about how they’re going to take over the world. And who knows, they just might. It takes a while for this sort of momentum to build up (look how long it took OOP to become mainstream!) but the signs abound; FP just might be the next big thing.
  3. Increased Productivity: Anecdotal evidence suggests that writing code in a functional way leads to smaller, cleaner code and fewer bugs. The logic of the algorithm is clearly detailed and many of the internal details of the operations are hidden away, leading to less clutter. I’ve often heard that FP is about describing what you want done, while Imperative Programming ends up detailing how you want it done as well.
  4. It’s Popping Up Everywhere!: FP isn’t all that obscure any more. You’ll regularly come across bits of functional code in various decidedly non FP languages. Java’s Comparator Interface is a good example of a common FP idiom, where you pass along a bit of code as a parameter as well as the data and have the code act on the data. Java 7 might have closures as well, which are already to be found in Ruby. Python has things like list comprehension, which has a distinctly FP feel and so on. I thought I might as well experience all these concepts in one integrated functional package rather than piecemeal.

FP vs OOP

Invariably when you start to talk about a new programming model, you’re met with slack jaws, blank stares and mewling cries of “But, but, but… OOP!”. Now I’m not one to deride OOP because I like the concept quite a lot. It’s a great fit for a range of applications and can really help model a lot of complex domains and interactions. However, it isn’t the end all and be all of computing that the OOP aficionados (and their groupies) make it out to be. One particular domain which seems to be a bit of a mismatch is the Web.

Most web programming involves a lot of pointless conversion from flat data to OOP and back again. Take a basic CRUD application. The user enters plain data without any OOP savvy behaviours or what have you. Just characters strung together. When he hits submit, we convert this data to fit into our OOP model and play around with it in the middle layer. We then flatten it once more and stick it in the database. We might also have some stored procedures in the database as well (usually written in a non-OOP language/manner). So the only place we’re really using OOP is in the middle layer and most of what we’re doing is simply converting data from one model to another. It’s just a huge waste of time. Embrace the fact that all we want to do is apply transformations to data and use FP (which is admirably suited to the role) to do just that.

I mean, what’s so Object Oriented about Servlets? They're actually very functional. You usually just implement one method/function which accepts user data as parameters, munges it and then forwards more data somewhere else, where we display the response.

Reuse?

As far as reuse goes, OOP hasn’t proven to be all that. Look at the Java Library. It’s just a bunch of methods. Useful one’s no doubt, but how many times have you inherited from one of it’s classes (other than Object of course! J)? You make an object which represents some data and you call methods on it. Most of the reusability is at the level of the methods. How much more useful then if we decouple the methods completely from the data, use duck typing and work on just about anything that’s passed in? Reusablity goes through the roof! Certainly, it won’t be any less than an OOP design.

Which FP Language should I go for?

“MMRRGH! (LISP!)” scream the Lispers through their gags, shouts of “Haskell!” from one corner and “Erlang!” from the other. They choice is endless. There are a whole load of functional languages out there, so which one should you pick up?

My 2p? Go for Erlang and Haskell. Both are relatively pure functional languages (unlike chimera like O’Caml, which are partly OOP and Lisp which is undifferentiated gloop and can be anything you want it to be) and fairly mainstream. Mind you, there’s nothing bad about being multi-paradigm, but when you’re learning FP, it’s best to suffer under a bit of disciple and be forced to be functional. Erlang is actually used in The Real World, though largely only in specialised hardware like network switches etc, which Haskell is under active developments and has a lot of mind-share.

I’m learning Erlang first because along with being FP, it has slightly different way of going about threading, though I hope to pick up Haskell as well (since it has another way of doing threading as well).

An Aside on Threading with Erlang and Haskell

Both Erlang and Haskell have taken a novel and (to me) refreshingly different way of going about threading. Neither concept is blindingly innovative, but it’s the first time I’ve seen it implemented as part of a language.

Threading is really coming into its own now. We’re moving into an age of massively multi-core CPUs where each core may be less powerful than the chips of today, but there’ll be so many per chip that the net speed will be tremendous. However, programs don’t multi-thread themselves. Developers have to identify concurrent paths and co-ordinate their interactions; something which can be quite difficult to code and fiendishly difficult to debug.

One advantage of FP is that functional code is inherently much easier to parallelise. Since functions don’t access or affect global state and act only on their parameters, you can infer possible parallel paths and have them run concurrently.

For e.g.

A = foo()
B = bar()

Here, the interpreter can run both foo() and bar()in parallel since they are not related and thus are guaranteed not to affect each other.

But wait, there’s more! Both Erlang and Haskell make threading even easier with innovative threading models. Rather than have process communicate through shared memory where you have to handle locking/concurrency yourself, both help make the process of writing multi-threaded code much easier.

  1. Erlang (Actor/Message Model) : It’s Unix IPC all over again! You basically have pipes which you use to communicate between processes. Messages are asynchronous and not location specific, so processes can migrate to different machines transparently. Errors are piped to related processes as well, giving you robust error handling. No shared memory and scaling it trivial. In fact, the possibility of basically almost unlimited scaling across multiple machines is what really draws me to Erlang and has me drooling like an idiot. Write your code properly and you can just keep slotting in boxes. Erlang also has the ability to update code while it’s running, which means theoretically zero downtime if you’re careful. And it’s all actually in use in the telecommunications industry, so all this is real, not vapour.
  2. Haskell (Software Transactional Memory Model) : Database transactions, but in local memory! Separate threads run within their own transactions and see a consistent view of the world. No need to explicitly lock bits of shared memory, we just let the system handle all the error prone bits and concentrate on our logic, confidently that our threads won’t be stepping on each other toes. This is a really powerful abstraction and it’s something that had me smacking my forehead, wondering why I didn’t think of it before. However, I see some fundamental problems with multi-machine scalability. This is a fairly well explored problem in the database world and I’m not sure I want my code doing two phase commits and roll-backs in a cluster. Still cool though.

Conclusions

There’s still a long way for me to go yet. I’m going to be going for a vacation in a couple of days, so there’s going to be a bit of a break in my journey of exploration. I hope to pick up the thread once more on my return and forge ahead. Let’s see why else I find worth writing about :-)

Socialize: del.icio.us | digg | Furl | reddit | Rojo | Spurl | Technorati | Yahoo My Web