Questioning functional programming
We've been tracking functional programming languages like Haskell and Erlang for a while, most recently watching the release of the Prags' "Programming Erlang and the rapid progress Bryan, John, and Don are making on Real World Haskell. Leon Brocard drew my attention to The 10th ICFP Programming Contest. Others like Tim Bray have also been getting their hands dirty (Tim started quite a runtime-length war in blogs with his posts on "appalling" Erland performance analysing logfiles, with various languages and factions competing to improve the benchmark's runtime in various languages).
The final report (PDF) has been released. It's notable for two things: the fiendish complexity of the problem and the absence of functional programming languages in the final results. Top place went to a C++ program, with a Perl team right behind in second. In third place was "Team Celestial Badger" using OCaml and C++. In all there were 81 teams using C++, 67 using C, 66 using Haskell, 64 using Python, 52 using OCaml, 48 with Java, and 35 with Perl. Only 4 tried Erlang (the same number as used Delphi). Quoth the judges:
One thing that struck us during and after the contest, reading IRC channels and blog postings, was that many programmers don’t have a lot of confidence in their favourite (functional) language: when they realised that their implementation of the DNA machine was too slow, their first instinct was often to switch to a “faster” language such as C. But the problem wasn’t the language but algorithmic complexity: a straight-forward Haskell implementation using the right data structure (e.g. Data.Sequence [3]) would be fast enough and outperform by several orders of magnitude an optimised C implementation using a dumb data structure. So programmers should worry less about languages and more about good old complexity.
As far as functional programming is concerned, we must conclude that functional languages didn’t fare too well this year (although in the Top 15 there were five users of OCaml and three of Haskell). Better luck next year!
It says to me that we're still in the early days of widespread adoption of functional programming. Like Ruby, which had tiny uptake until Rails and 37 Signals boosted it into the stratosphere, functional programming languages lack a reason to use them. Even those who advocate them aren't comfortable enough with them to push on with them in the face of hard problems.
tags: thought provoking
| comments: 29
| Sphere It
submit: 
0 TrackBacks
TrackBack URL for this entry: http://blogs.oreilly.com/cgi-bin/mt/mt-t.cgi/5934
Comments: 29
I've been watching functional programming for the last 15 years, and my conclusion is that it's a triumph of tools over problems.
Functional programming is great if you have a problem that fits into the paradigm, but everything else (eg, monads) are attempts to fit further problems into the paradigm.
As there is a impedence mismatch between the way functional algorithms work, and the way that machines work (represented by C), the solution will always lose out as the problem becomes more real and less functional.
C, the language, is a straightforward mapping of CPU operations to human writable (less readable) language. That's why it keeps on keeping on, because it is a fundamental reality that just isn't going to go away.
Because the ideas of functional programming can be hard, those who are champions of languages like Haskell and Prolog often confuse their mastery of those concepts with some ideal of elite programming... which is wrong.
Unfortunately, there is no end of people who have picked up some ideas and can vaguely see how it would be possible to reprogram the world with those ideas... they'll be along in short order to claim that everyone who uses C or procedural languages are braindead.
They'll probably cite Paul Graham too, who is one of the last people you should ask when it comes to writing large maintainable systems for a corporate environment. Sure, he wrote a shopping cart in Lisp. That shopping cart was also the first thing that got rewritten when Yahoo took over.
Yes, by all means, do question functional programming. And don't be afraid to come to a less than favourable conclusion. You have the right to reach that conclusion without being disparaged by those who _think_ they know better.
They'll probably cite Paul Graham too ... Sure, he wrote a shopping cart in Lisp. That shopping cart was also the first thing that got rewritten when Yahoo took over.
They'll cite Paul because he's an advocate of higher-level languages, most-notably Lisp, and because he wrote an amazing book on the subject (On Lisp), not because he wrote a shopping cart. Why did Yahoo! rewrite the shopping cart? I'd bet it wasn't because it was written in Lisp, or poorly written code (perhaps it was poorly written, I don't know), but because it didn't fit neatly into their infrastructure (they use PHP right?).
If I recall correctly, the store builder still exists and still uses RTML, the language Robert Morris and Paul Graham wrote in Lisp to build pages. Obviously they still find that suitable, don't you think?
@Anonymous: Functional programming ignores reality. Change IS a constant.
After three years of functional programming I’m nearly out of that dark cave I’ve been living in, and back into this real world. Now this might sound heretical but it’s true.
At least for me, functional programming seems to have been an infatuation - well worth the time spent on it but ultimately not useful.
This may not be true for everyone, but it’s fair to assume that it’s quite common. Most people try functional programming at some point; comparatively few people are programming functionally.
Try not to get too caught up in different paradigms, what matters more are the lessons you learn. No one has got everything right yet.
@Anonymous: Functional programming ignores reality. Change IS a constant.
After three years of functional programming I’m nearly out of that dark cave I’ve been living in, and back into this real world. Now this might sound heretical but it’s true.
At least for me, functional programming seems to have been an infatuation - well worth the time spent on it but ultimately not useful.
This may not be true for everyone, but it’s fair to assume that it’s quite common. Most people try functional programming at some point; comparatively few people are programming functionally.
Try not to get too caught up in different paradigms, what matters more are the lessons you learn. No one has got everything right yet.
Highscalability.com has an article on Twitter which is Ruby on Rails based which echoes the quote:
"[...] The problem wasn’t the language but algorithmic complexity [...] programmers should worry less about languages and more about good old complexity."
http://www.highscalability.com/scaling-twitter-making-twitter-10000-percent-faster
As you can see from the title, they got their Ruby implementation to perform 10000% faster through data structures and algorithm redesign, vs. straight rewrite which got them 10-20% faster.
Steve's comment, that Paul Graham wrote a shopping cart in Lisp is incorrect. It's also something of a straw man, which distracts from Graham's real accomplishments with the system that became Yahoo stores.
Graham did not write a shopping cart in Lisp. He wrote the store creator/editor in Lisp. This was the tool that store owners used to design and implement their stores. He made it feel and work as much as possible like a desktop application. Their competitors had their users filling out and submitting web forms to make changes to their stores, which was less friendly, and certainly less familiar to end users back when ViaWeb was created.
Here's the relevant information from the footnotes of Graham's article "Beating the Averages":
Viaweb at first had two parts: the editor, written in Lisp, which people used to build their sites, and the ordering system, written in C, which handled orders. The first version was mostly Lisp, because the ordering system was small. Later we added two more modules, an image generator written in C, and a back-office manager written mostly in Perl.
In January 2003, Yahoo released a new version of the editor written in C++ and Perl. It's hard to say whether the program is no longer written in Lisp, though, because to translate this program into C++ they literally had to write a Lisp interpreter: the source files of all the page-generating templates are still, as far as I know, Lisp code. (See Greenspun's Tenth Rule.)
Me again: In another article, or perhaps a podcast, he explained that the shopping cart needed to be fast, and it was simple, so they wrote it in C. Note that there would be many more shoppers than store creators. A shopping cart just has a few functions: add items, remove items, report totals, etc., so C was fine for it. The store creator was complex, and had fewer users, and that's where they used Lisp.
"It's notable for two things: the fiendish complexity of the problem and the absence of functional programming languages in the final results."
This is a somewhat unfair assessment. Yes, considering it's a competition organized by the International Conference on Functional Programming, perhaps the fact that most participants are using C++ is notable. Still, at least 120 teams used a functional programming language (Haskell, OCaml or Erlang). I wouldn't call this "absence", and 8 of them being among the top 15. I haven't read any summary of previous year's competitions, but at least the winning teams have used functional programming languages on several occasions. Drawing too many conclusions from a single contest seems somewhat flawed.
Re: Steve: In what way are monads a problem?
C may be a straight forward mapping from programming language to CPU operations, but a more interesting question is how it maps human design to CPU operations.
I still see promise in functional languages, and exciting things are happening in the field.
The main point of my Paul Graham comment was that he would inevitably be used as an example in this argument, whereas we need to hear from hundreds of thousands of working programmers rather than an exception that proves the rule.
Monads are a problem because they're a hack in functional languages to introduce non-commutative ordering, even though they're neatly sequestered in Haskell IO. They are an exception to the unifying vision of the functional approach.
The idea of functional programming is that making a call with the same arguments will generate the same results every time. That means no embedded state or behaviours that could change the results. The real world is almost entirely about embedded state and behaviours, so that's quite a mismatch right there!
Yet completely normal procedural languages, yes, including C, can obtain many of the advantages of this kind of thinking simply by using non-mutable data structures - eg, NSArray, NSString, NSSet, NSDictionary in Cocoa. You need NSMutableArray, NSMutableString, NSMutableSet and NSMutableDictionary to be able to change them.
It all gets very tiring. All these silver bullets with no targets to hit. Why cite human factors for functional programming when it's clear that the ideas of functional programming give people more conniptions than procedural code does in the first place?
By the way, I would point out that LISP isn't functional as it is multi-paradigm with its ability to handle procedural, object, functional, aspect and anything else you can think of... since you can just re-write for any domain specific language you like.
So writing LISP in C++ isn't an indictment of anything, it's more of an acknowledgement that domain languages probably are the best way to solve various problems. LISP is quite nice for markup even if there's no executable component.
"Make everything as simple as possible, but not simpler." -- Albert Einstein... and functional languages are too simple. It is possible to program Vista in Brainfuck, but the code size explodes due to lack of language expressiveness.
To conclude - this is written by someone you don't know, therefore you have no reason to care what I think. Believe what you want, and I expect that after 3 years you may reach the same conclusions as Mark.
I first learned about functional programming 15 years ago back at Uni and I don't think it's time will ever come. But I don't think that matters - functional programming has had an influence on modern languages, so when you're solving a problem and the functional style is the best fit then you can do it, without resorting to Haskell or Erlang (assuming, of course, you're using Groovy, Ruby or Python).
I don't know where some posters are getting the idea that functional languages can't handle "state". They certainly can, it's just in a controlled fashion - it's uncontrolled state mutation that is not allowed. Nice by-product of this is that all state-manipulating code becomes first class, capable of being recombined and manipulated. A little more effort up front, especially for beginners, but in my experience it pays off. YMMV.
Also, I don't think monad's are a "hack". They are quite a nice abstraction and Haskell-style monads have been implemented in Ocaml and Scheme (to name just two) because at least someone in those camps found them desirable on their own merits - these languages certainly don't need them to do IO!
As someone who has written production code in functional languages (I've written Haskell for the U.S. Navy) and in other languages (Perl and Ruby for several startups), I have to say that Haskell enabled me to be way more productive than the untyped scripting languages. Ruby is fun, but Haskell lets me get the work done faster and better.
Sure, it might not sink in for everyone, but it's an awfully good lever if you've got it.
LISP can be a pain to write in, but in the end, yeah, its gotta come down to algorithm bounding for performance. Also, XSL is a (mostly) functional programming language, and its fairly widespread (I use it a lot for reporting and xml parsing).
Steve; other people will get confused about your choice of name, thinking that I'm talking to myself.
I didn't say that functional languages can't handle state. I said that the idea of functions without state is the main concept of functional programming languages. Monads are an elegant way of handling state, but they are a hack in the context of the original concept.
The next step is to consider that monads are essential to making functional languages more capable. Now it's a functional programming language with an encapsulated nod to reality. Functional as a concept by itself was not a sufficient answer.
Note that Haskell is not a pure functional language. Would Jesse Tov have been able to write production code in a pure functional language? Of course - if the problem matched the solution, he could write in the domain language and interface it in the right spot.
In my own code, I run a Javascript interpreter alongside of Objective C so that I can pipe data from one to the other. E4X on one side, distributed objects on the other. Each language to its own strengths. Including functional. And productive.
1. Haskell is a pure functional language. In the sense that it is referentially transparent. It has pure functions, which have no side effects and commands, which look like functions, but can produce side effects.
2. Haskell is also an imperative language. A program written in Haskell can have side effects and all practical programs are interactive and have a lot of side effects.
This means that Haskell is superior to all languages that don't combine these two essential properties: interactivity and referential transparency. At least in theory. In practice you need tools and libraries.
A monad is defined as a set with two operations, which obey three laws. So a list is a monad with the operations
flatMap: [a] -> (a -> [b]) -> [b]
and makeList: a -> [a]
Both operations are pure functions. How can anyone consider lists with these two pure functions a hack?
flatMap = flatten . map
It applies a function to each element of a list any then flattens the resulting nested list.
makeList creates a list from a scalar value.
You could consider monads as containers, although that won't work for all monads.
Features of functional programming are finally finding it's way into mainstream imperative languages. C# will soon have first class functions and monadic comprehensions (LINQ). Java will probably get first class functions in the next version. And Quaere is supposed to bring LINQ to Java. Ruby and Groovy already have them. Even Python has some support for them.
Erlang has been successfully used for writing huge reliable concurrent systems. It is proof that functional languages are superior in practice.
> Monads are an elegant way of handling state, but
> they are a hack in the context of the original
> concept.
I'm glad you recognize the elegance, but I don't think you have supported your "hack" assertion.
If you go back to Moggi's original papers describing monads, he was using them to model what imperative programs are really doing in a way that can be reasoned about, the way future computations depend on the products of the preceeding ones. So with IO, Haskell is just modelling as an abstract datatype a certain aspect of our world - imperative computer programs. This is no different than any other act of modeling: you recognize an abstraction, create an abstract datatype representing it and the operations (in this case just bind) for manipulating its values. In other words, it is not a "hack", but a straightforward act of modeling "actions" or "computations" in a referentially transparent way. That this modeling has worked so well is pretty amazing in my view, it makes easy a kind of meta-programming that makes the imperative code being modeled more powerful. All the pieces of the imperative program are automatically "first class".
No doubt the ideas could use improvement still, I just don't buy the "hack" argument!
Cheers
> Monads are an elegant way of handling state, but
> they are a hack in the context of the original
> concept.
I'm glad you recognize the elegance, but I don't think you have supported your "hack" assertion.
If you go back to Moggi's original papers describing monads in programming, he was using them to model what imperative programs are really doing in a way that can be reasoned about, the way future computations depend on the products of the preceeding ones. So with IO, Haskell is just modelling as an abstract datatype a certain aspect of our world - imperative computer programs. This is no different than any other act of modeling: you recognize an abstraction, create an abstract datatype representing it and the operations (in this case just bind) for manipulating its values. In other words, it is not a "hack", but a straightforward act of modeling "actions" or "computations" in a referentially transparent way. That this modeling has worked so well is pretty amazing in my view, it makes easy a kind of meta-programming that makes the imperative code being modeled more powerful. All the pieces of the imperative program are automatically "first class".
No doubt the ideas could use improvement still, I just don't buy the "hack" argument!
Cheers
@John: You can't say that this proves "functional languages are superior in practice".
I could make similar claims stating how just about all system software being written in C implies: imperative languages are superior in practice.
In this example, you ignoring the fact that message-based concurrency works just as well in non-functional languages.
"C, the language, is a straightforward mapping of CPU operations to human writable (less readable) language. That's why it keeps on keeping on, because it is a fundamental reality that just isn't going to go away."
True. C does have an inherent performance advantage in serial computation as it is virtually a 1 to 1 mapping of high level language to machine instruction. However the reality is that the CPU is changing. Multi-core, parallel-based processing is where the industry is heading. This is where I suspect functional programming will shine as features such as lack of side effects has the potential for a natural mapping between high level code and assembly. Languages that better manage concurrency will have a distinct advantage here. Safe to say, the verdict on functional programming will be decided in the near term as this new hardware paradigm plays out and when a new generation of programmers (or retrained veterans) learn to formulate certain classes of problems in those terms.
Not to say functional programming is a cureall. It is a screwdriver to imperative programming's hammer belonging in everyone's toolbox. With current industry trends, that screwdriver has the potential to be a real power drill.
First point:
I don't think anyone has ever properly constructed a compiler for a functional programming language with the level of complexity represented in Haskell, or OCaML. Instead, there are a lot of poorly implemented compilers for mature and complete languages, and a few well-implemented compilers for very incomplete languages. In contrast, C++ compilers have consumed literally billions of dollars over 30 years. The results are manifest.
Second point:
Lisp-machine class toolchains for functional languages just don't exist. There is no Smalltalk-80 system for Haskell. And Haskell needs such a thing in order to be truly useful: Much of the point of the language design is that it should be tractable to machine understanding. Thus much of the point is lost if no machine actually understands it, in a useful way. The potential for Haskell toolchains is unbounded. The market is nil.
Third point:
Languages which are difficult to parse get poor use. C++ for example is a bitch to parse, and it's use is poor, in that it is typically written in terms of bugs per line. Haskell is hard to parse -- not so much for a computer, as for a human. No one has ever approached the simplicity and usability of sexprs as a vehicle for human-machine mutual understanding in an industrial-scale pure functional programming environment.
All of these points have their rhetorical excesses and are easily refuted. I'll take your refutations very seriously if they show themselves to be accompanied by an understanding of the valid substantive points which are raised above.
It’s an increasingly common misconception that functional languages are innately better at concurrency (ala Erlang).
While Erlang is very good as what it does, this in no way implies functional programming is inherently better for distributed-concurrency. (Of course it doesn’t imply its worse either.)
Smalltalk and others were using messages to handle concurrency for years before anyone had even heard of Erlang. That its designers chose a functional core for Erlang has nothing to do with this.
Frankly I’m getting annoyed that obviously uninformed people keep repeating this rubric.
I don’t mean to offend, just getting tired of hearing and correcting it.
Mark: I don't think "anon" was necessarily referring to Erlang style message passing as the way in which functional languages may be better than imperative ones for concurrency.
Thanks to referential transparency, the compiler/runtime of functional languages can do "tricks" not readily available for their imperative counterparts (e.g. nested data parallelism).
Daniel: Hey, I wasn't referring specifically to anon, others had mentioned similar things. This [messages] IS how Erlang handles concurrency.
Why aren't these "tricks" you mention more widely spread?
There's an important difference between the words 'can' and 'do' - everything works in theory.
Referential transparency has to be one of my favorite things about functional programming languages.
Here are some examples of purely functional languages that are widely used throughout the enterprise. One of these is legacy and two are growing:
1. SQL
2. XQuery
3. XSLT
One interesting note is that all three are important standards with many different implementations and a high variety among implementations. A purely functional language is a good choice in these three cases partly because it leaves open so many choices about how to build an implementation.
It's also interesting that more and more practitioners are starting to suspect that XQuery and XSLT are all that is actually needed for enterprise software and that by limiting ourselves to these, we can solve the "impedence mismatch". That is, we don't actually need PHP or Ruby or server-side Javascript or server-side Java or any of those things. We certainly don't the mappings between the objects and types of those languages and the XML types we want on wires and in databases. Instead, we can probably "do all of that" with just XQuery alone -- this is one of the ways in which it is an improvement over SQL.
It's interesting that people are trying above to puzzle out monads. As someone else noted, I think, the addition of monads to a pure functional language gives you ... a pure functional language. But, how can people think about them intuitively? This might help:
In imperative style, programs perform output by calling "magic" functions, passing them the data to output as parameters. In monadic style, programs perform output by returning the values to be output.
Similarly, in imperative style, programs perform input by calling "magic" functions and getting back data as return values. In monadic style, programs perform input by return a function that is to be called, passing the new input as parameters.
So, that's it: imperative style uses function calls to do I/O, monadic style uses function returns to do I/O. That's the only difference.
If, in addition to monads, your language has at least closures and ideally continuations, then every *imperative style* program can be trivially translated into or interpreted as a purely functional program.
Imperative vs. monadic style would *almost* be a "which side of the egg do you crack first" question but for this: If you write in monadic style or write programs designed to be translated into monadic style, you wind up with purely functional programs. They are "purely functional" because they contain no "magic functions". All of the magic of IO is pushed out of the language and into the context of how programs are run -- IO is a matter of how the return values of programs are interpreted by the run-time system. So what? Programs with no "magic" functions are easier to reason about. You can prove things about them. Optimizers can transform them more easily. For example, in a pure language, De Morgan's law applies to all boolean expressions. In an imperative langauge, with "magic functions", neither a theorem prover or an optimizer could count on De Morgan's law always being true.
Self promotional bit:
If you would like to see how to add a monadic I/O system to XQuery and thus obtain a fully general programming language suitable for nearly all aspects of implementing web services, see XQVM.
-t
Oh, I should add:
In addition to monadic I/O, XQVM adds (a more general combination of) closures and continuations.
So, although XQVM can be implemented in but a few hundred lines of code (given an XQuery implementation), nevertheless it accomplishes in a nice way all of the (technical) aims of XQUF and XQueryp while requiring no extensions at all to XQuery 1.0.
-t
So 29% of the programmers used functional languages and 53% of the successful programmers used functional languages.
Post A Comment:
STAY CONNECTED
RECENT COMMENTS
- Jon Harrop on Questioning functional programming: So 29% of the programme...
- Thomas Lord on Questioning functional programming: Oh, I should add: In a...
- Thomas Lord on Questioning functional programming: Here are some examples ...
- Salman FF on Questioning functional programming: Nat, You might want to...
- Mark on Questioning functional programming: Daniel: Hey, I wasn't r...
- Daniel Larsson on Questioning functional programming: Mark: I don't think "an...
- Mark on Questioning functional programming: It’s an increasin...
- Aminorex on Questioning functional programming: First point: I don't t...
- anon on Questioning functional programming: "C, the language, is a ...
- Mark on Questioning functional programming: @John: You can't say th...
RADAR TOPICS
Anonymous [10.16.07 05:03 AM]
Oh you Perl troll, it's just plain bull's droppings. Functional languages are not used because programmers are not clever enough to appreciate them.
What they basically want is a C syntax language with C expressive power, it doesn't matter that it is named Java, and they are scared of anything abstract and powerful.