Friday, May 11, 2007

The advantage of functional programming

I know there have been a lot of articles on this theme before, but I wanted a go at it anyway, even though most readers of this blog already use a functional language.

I was trying to explain the advantage of a functional programming language to a friend, but ended up being rather unpersuasive. After I was done, he said, "I think it's just easier to use whatever you've learned." But in my opinion, it's more than that. There are clear, objective advantages to using a functional programming language over a non-functional one.

"Functional" is one of those programming language words (like "object-oriented" or "typed") that is often used but poorly defined. Some people use it to refer to an application-style dataflow (as I defined last March). This definition fits most functional languages but excludes languages like Factor, which are functional but use stack-based dataflow, and possibly also haXe and Scala, both of which can comfortably be used with mutation-style dataflow. Really, the dataflow style isn't the issue. In my mind, it's all about higher-order functions and little pieces of data.

Higher order functions, despite the scary name, are relatively simple and extremely useful. It's just passing a function as an argument to a function. So to apply a single operation to each element in an array and get a new one out, you don't need to iterate through the array yourself; just use some higher order function (map) and the operation that you'll be using on each element. For a more concrete example, here's a Java method that will take an ArrayList and make a new one with 1 added to each element.

public static ArrayList addone(ArrayList list) {
ArrayList out = new ArrayList(list.size());
Iterator iter = list.iterator();
while(iter.hasNext()) {
out.add(new Integer(iter.next().intValue()+1));
}
return out;
}

Now here it is in Scheme, a functional language

(define (addone lst)
(map (lambda (i) (+ 1 i)) lst))

(In Factor, it's just : addone [ 1+ ] map ; but that's just an unfair comparison, don't you think?)

Now imagine if Java supported anonymous delegates, like C#, and it also had a good set of higher order functions (unlike C#, as far as I can tell) the code could be written something like this (using something like the syntax proposed by Neal Gafter):

public static ArrayList addone(ArrayList list) {
return list.map(Integer x) {
return new Integer(x.intValue()+1);
};
}

The inner return returns a value from the closure inside, rather than the whole method. Now there are still a few kinks to be worked out (why bother with an explicit return? And why can't you put an int in an ArrayList, instead using the awkward Integer?) but it's obviously an improvement. Map only works for some particular cases, but once a few more methods are added (such as fold, find and each) almost all array processing can be covered. Currently, in Java code, the same boilerplate iterator code is used on each thing that would be replaced by map, fold, find or each.

Some languages try to solve the problem by adding a number of specific constructs--foreach, with, using, etc. which execute a block of code in a particular context, which makes examples like these look better. But these are only partial solutions, and do not allow for extension by the programmer. There will always be needs that aren't anticipated by the language designer, and little measures like these won't fulfill them all.

To get the benefit of this, there needs to be more than just access to higher order functions. It also has to be possible to use them in everyday code beyond simple UI callbacks. The standard library should make heavy use of them where appropriate (such as in array/list processing), and languages like C# and Javascript lack this. Additionally, there needs to be a nice, convenient syntax for higher order functions that makes them look just as pretty, or almost as pretty, as builtin constructs. Java has anonymous inner classes, which can do about half of what closures do, but the syntax is so horrible that it is very rarely used for higher-order functions. If these two things don't exist, practical use of higher order functions will be limited.

The other main advantage of functional programming languages is the ability to allocate lots of relatively small data structures that don't (usually) get mutated. I know this is somewhat vague, but it is actually very important. For one thing, for this to be practical, there must be garbage collection. It would be really annoying to write and inefficient to run a program that allocates and frees many little data structures in C or C++. Because of this, the practice is generally avoided. But in a functional programming language, not only is this easy syntax-wise; it's also efficient. I'm not completely sure how to describe it in objective terms, but it's much easier to write a program when you're not as concerned about minimizing consing.

Anyway, I hope this was enlightening, but it may have been hard to follow if you, you know, didn't already know what functional programming was. So feel free to comment.

4 comments:

hiren said...

Smalltalkers enjoys Objects and Functions(Blocks) both :)

list collect:[:i | i+1]

Daniel Ehrenberg said...

Sure, that's great. So do Lispers and Factor programmers. Object orientation is orthogonal to functional programming.

Justin Chase said...

C# has a great set of higher order functions! It's called linq:

list.Select(i => i + 1)

Also you could do this with a coroutine:

IEnumerable addone(IEnumerable list) {
foreach(var i in list)
yield return i + 1;
}

vapour said...

TBH, I've been seeing so many arguments about language grammars that one starts to get the feeling the whole conversation is beside the point. It's an inert discussion because the whole matter deals with how the language grammar leads to how solutions to, usually ad hoc problems like generating Fibonacci series, are expressed using the language grammar. This isn't a particularly important question since all current language grammars have such huge problems with expressiveness it becomes like arguing about which you're better off swimming the Atlantic with, a Ford Taurus or a Fiat Panda. The only genuine question you need ask about a language is how quickly and effectively it brings productivity features to the hands of users of the software constructed in the language. We already have enough examples of languages which address the question of an elegant grammar without offering much to the question of building productivity tools at the far end of the software life cycle which end users will find powerful and expressive since it's their experience you really should be thinking of.