20 Jun 2006 wnewman   » (Master)

I have some comments on the recent http://www.defmacro.org/ramblings/fp.html article on functional programming, and I decided I might as well post them here and send the author a pointer rather than just putting them in an email.

(You are approaching a skirmish in the language wars! Hit *BACK* now!)

I like functional programming, and I liked the http://www.defmacro.org/ramblings/fp.html article, but I think he probably should present more disadvantages up front.

One of the reasons that I prefer Common Lisp to Haskell (and why others prefer ML variants to Haskell) is that there are things which are clumsy or slow to express in purely functional form. Okasaki's _Purely Functional Data Structures_ is a marvellous book well worth reading for other good reasons, but one smaller benefit of reading it is that some such things come through there.

One annoying performance issue for me is hash tables; in an imperative language, it's straightforward to use the idiom of hash index into a modifiable collection to get O(1) lookup. Good luck doing this in FP! And, if you tell people that they should rewrite their BDD packages for reliability and clarity and shareability in Haskell instead of C++, and tolerate the extra O(log2 1E7) performance hit of doing all their cache lookups in nice purely functional search trees instead of ugly imperative hash tables, you will encounter some sales resistance --- though perhaps not as much, in the eventual runout, as if you conceal this performance issue from them and let them discover it for themselves.:-|

The issue of making small incremental modifications to large indexed or cross-linked data structures isn't just an algorithms performance issue, it can also make programs difficult to read and think about. I have done a lot of work on programs to play the game of Go, where on each move a player places a stone on one of the 361 points on a board. At various times I have written complete programs in C++, CL, and Haskell. In the imperative languages there is some programming hassle involved in making the changes undoable (so that you can try a variation, then backtrack to the starting point to try another), whereas you get undoability for free in Haskell; but in Haskell I found considerably more hassle in trying to express the small changes without doing a deep copy of potentially very large cross-linked data structures. It seems to me that this is a fundamental issue, not just a symptom of my naivete about functional programming. It might not be a big issue for an Erlang telephone switch, because I expect most of the state in such a switch is tied to an individual call, interacts weakly if at all with the state of other calls, and goes *poof* when the call ends. But if you tried to write, say, a MMORPG server in a purely functional language, I would expect that the ongoing small modifications to the complicated shared global state of the world would be a source of programming pain.

Also, purely functional languages seem to be unusable without laziness (to create cycles) and the purely functional languages people have not convinced me, as a casual user, that their handling of laziness is completely ready for prime time in large hairy systems. The difficulty of debugging lazy code is a minor issue; the difficulty of bounding the performance (especially heap usage) of complicated lazy code is worrisome, a potential showstopper. I would be very nervous about planning to develop a large Haskell system for something complicated and not similar to existing FP software (perhaps the MMORPG server example) without doing some serious investigation into that. I think it might be easy to end up with a server which failed from heap exhaustion when lazy-variable placeholders held pointers into futures which "common sense" shows could never happen, but which aren't manifestly unreachable and so therefore aren't garbage collected. Both my intuition and my superficial reading of the mailing lists suggests that such bugs are not hard to create, and can be hard to test for and hard to debug. The existence of various large FP systems successfully "used in anger" is reassuring, but only incompletely so: it's not hard for me to come up with a story why from the ability of version control systems and telephone switches and compilers to manage this problem it does not follow that it's manageable for all systems.

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!