Tuesday, October 10, 2006

Functional Programming


Is functional programming the next big thing? A lot of the reading I've done lately would seem to suggest so, but that might just be the nature of what I've been reading, rather than a genuine shift in the IT community.

Of course, I've been hearing about functional programming for years. I've always skirted around it, since it was not taught in my electrical engineering course and I never pursued computer science academically until recently. (Maybe that's another reason I've been hearing about it more?)

My first exposure to this style of programming was when I learnt the C++ Standard Template Library (STL). Of course, it's no where near pure functional programming, but I was amazed at how elegant code could become with the STL. An HP example that I remember seeing demonstrated a simple program which read strings from stdin, sorted them, removed duplicates, and printed the results, all in 2 lines of code. However, if I wanted terse I could just code in Perl. The beauty of this code lay in its simplicity.

Over time I encountered this approach in many different forms, but it wasn't until I watched the lectures of Abelson and Sussman that I got a formal appreciation of it. Now I understand why programmers recommend learning Lisp, simply for the different way that it makes you think.

Recently I've started seeing many programmers whose blogs I follow commenting on functional programming. It has taken a while, given that the approach was first really pushed by Backus way back in 1978.

One of the big advantages of functional programming is the ability to provide a proof. There are mechanisms for proving the correctness of imperative programs, but these are largely impractical on real systems. Functional programs by contrast have the form of a mathematical expression, thereby making proofs easier to derive and verify.

I used to think of proofs as only being of interest to academics, but I've since changed my tune. Everyone in this industry is aware of how buggy software can be, and how often projects fail to meet deadlines due to errors. Unfortunately it is all too common that these problems (among other things) can lead to projects failing altogether. With this in mind, several companies have been successfully programming using tools for converting formal specifications in Z-notation into running code. The reported bug rate is significantly lower, along with extraordinarily high rates of success. I understand that many clients with critical applications (such as military and space deployments) are choosing to only accept code written in this way. It makes sense to me.

The more I learn about this, the more I appreciate Dijkstra point of view, particularly on teaching programming. And I'm not the only one lamenting his lack of influence (I apologise to those non-IEEE members who cannot read that link). I understand the point of view that he was Ivory Tower idealist, but with projects constantly failing in this industry, and our inability to find developers with a proper understanding of programming, then I've come to revise my point of view.

With this in mind, some months ago I started learning Haskell. This language was created for academic purposes, and is considered the only completely functional language. For that reason, it may sound impractical, though Quake Haskell, along with many other projects, provided me with enough encouragement that it really can be used in the real world.

I'm not very productive in Haskell yet (for instance, I can follow monads, but I don't really get them - though I'm still reading). But I've found that it has improved my understanding of certain programming approaches, and made me a much better developer in the languages I am good at.

In the process of learning Haskell, I started to learn more about another functional language called Erlang. This language was developed in the late 80's by Ericsson, partly in response to some of the things I've been talking about here. Ericsson also released a short film, if you're interested in learning more about it. Erlang has a number of similar features to Haskell, including pattern matching, which is phttp://beta.blogger.com/img/gl.link.gifrobably the single most important feature of these languages.

If they're similar, then why would I start learning Erlang when I still haven't mastered Haskell? Well, regardless of the success of Haskell in some of the above projects, there are still barriers to its practicality. The best comparison I've seen so far was by Joel Reymont, when he attempted to build a client application for a poker server. Regardless of his complaints on Haskell, he still finished by saying:
"That said, because it forever twisted my brain into a different shape and I think I’m overall a much better coder now."
This reflects my own experience so far, so I'm continuing to make my way through my Haskell books slowly. It's a shame that it has to be as slow as it is, but work, study and Mulgara leave me limited time. Maybe one day I will get competent enough at Haskell and Erlang that I can move on to OCaml.

It's amazing how all of these things interconnect. I'm also spending time on Description Logic and how to do this in RDF/OWL, so I can create a programming engine in Mulgara. While assertions are different to function calls, there is enough similarity that I wish I could do much of this work in Haskell rather than Java. At least Haskell has taught me many of the techniques I need to make this job easier, and much more likely to be correct.

12 comments:

Kurt said...
This comment has been removed by the author.
Kurt said...

You may have seen this already, but the most straightforward description of monads I've read has been this:
You could have invented monads

It really does explain them well.

jemfinch said...

Gofer, Miranda, and Clean are all completely functional programming languages. There are probably many more, as well.

Quoll said...

OK, I stand corrected. As I said, I'm relatively new to Haskell, and the claim of many that Haskell is the only completely functional seemed reasonable. This seemed even more so when I considered Erlang.

According to several sources Erlang is not completely functional, but looking at it from an outsider's viewpoint, I would not have realized that. In a similar way, Haskell's sequences don't appear very functional to me. I've therefore relied on the judgment of others to say what is "purely" functional, and what is not.

I notice that Gofer is a Haskell derivative, while Miranda is a predecessor to Haskell. So it makes sense when they say "purely functional". Only "Clean" seems to be unrelated, but again, I have to take their "purely functional" claims at face value.

Wikipedia does not have an extensive list of languages, though because it misses Gofer (which seems to be defunct) it may be missing others as well.

Christophe (vincenz) said...

I do think that once you know Haskell, O'Caml will feel like a step back, not forward. O'Caml, while quite a nice system, is basically ML with OO grafted onto it. It's type system, at least in my opinion, is less expressive, and it suffers from some small warts that finally made me leave it for Haskell. I always feared performance when I thought about Haskell, and that is what kept me so long with O'Caml, but Haskell is actually quite performant so that worry was not necessary. For the rest, I had already long admired Haskell from the O'Caml sidelines for many fancy things that the ML families miss: Type Classes, much richer type system, Monads, first class data constructors, etc...

Anonymous said...

1978 seems a bit late to me; Alonzo Church used the lambda calculus in practice in 1936, which had been previously developed. The lambda calculus is significant because the original Lisp, implemented in 1958, is a literal implementation of it.

mikkom said...

Believe me, when you are good with haskell and erlang, you don't want to lear ocaml. Speed is usually not the biggest obstacle and Ocaml syntax is quite horrible when compared the two you are learning.

Just my 2 cents (I went the other way and learned OCaml first)

mikko

Quoll said...

My original comment was "the approach was first really pushed by Backus way back in 1978". I'd like to emphasize the words really pushed.

Backus explicitly refers to Church, and as you say, Lisp was around for many years before. Even Dijkstra was starting to make a name for himself in formal correctness. I can also make a strong case that Church's lambda calculus was not being pushed back in the days before electronic computers were invented. :-)

Your have a valid point that the ideas were around for a long time before the citation I give. But I do think that these concepts really hit the mainstream with that paper from Backus. Either way, the point is still made that these notions have been around a very long time (given the way time is measured in IT) and yet serious interest seems to have only just started happening recently.

Bosky said...

hi,im a javascript hacker and this articles finally inspired me to dive into erlang

http://programming.reddit.com/goto?id=wyvf

Keep Clicking, Bhasker

rduht said...

I think wow gold and world of warcraft gold

Herbal Viagra said...

Thanks for sharing this working notes with us. I know that it will be extremely useful for us in order to improve our programming knowledge.

Custom Logo Design said...

This is really a great post very creative one.Thanks for taking time to share your valuable information here with us.