Functional programming is hot right now, and I love it. This XKCD Comic promotes its old (and not undeserved) reputation as complicated and esoteric. Lisp, the original functional language, was developed in the 1960s as perhaps the first computer language for non-gearheads. It was instead designed for mathematicians. And it does a good job of presenting things in a way that makes sense to mathematicians, hence tail recursion. (Which I’m not going to explain; suffice it to say that it is catnip to people who love proofs by induction.)
So for 40 years mathematicians (and their friends, Artificial Intelligence researchers) have been trying to explain why functional programming is the Next Big Thing because it’s so easy and makes so much sense. And people who don’t dig mathematical proofs have seen every argument for functional programming as an argument against it. That is, until Google got involved in a big way.
Functional programming is writing your programs the way you write algebra problems. Sounds scary, if you forget that elementary school kids learn algebra. The name comes from the fact that you’re working with mathematical-style functions. (These days, all programming languages support functions, but in the 1960s this was novel.) To show how this differs from other programming, consider a typical imperative (non-functional) way to build one list from another list. This should look at least somewhat familiar if you’ve ever taken a programming class in your life.
function personalizeList( yourList ) {
myList = new List();
for (index = 0; index < yourList.length; index = index+1) {
yourItem = yourList[index]
myList[index] = "My " + yourItem
}
return myList;
}
You have a variable (index) which starts at 0 and increases until yourList has been traversed. If yourList contains ["apple", "banana", "cranberry"], then at the end myList contains ["My apple", "My banana", "My cranberry"]. This all seems perfectly normal to anyone who has learned to program this way, but there's one very counterintuitive piece, especially when you come from an algebra background:
In mathematics, variables never change once they've been assigned a value.
Imagine how confusing D = Ax2 + Bxy + Cy2 would be if x and y could change within the equation. So in functional programming, you avoid changing the values of variables. This makes loops impossible, hence tail recursion. But there are other ways to avoid loops. Here's how you'd write personalizeList in a typical functional language:
function personalizeList( yourList ) {
return yourList.map( function(item) { return "My " + item } )
}
The "map" function applies a function you provide to each item in the list. Functional languages provide a bevy of functions for working with lists without having to explicitly iterate through all the elements. And they can be stacked on top of each other, like this:
yourList.without("cranberry").append("cherry").count()
This takes yourList, creates a similar list with "cranberry" removed, creates another similar list with "cherry" at the end, and then counts the number of items in the list. This follows the no-variable-modification rule: at each step, a new list is created, and each list cannot be modified. Here's an example of jQuery, a popular JavaScript library, for taking every paragraph ("p") on a web page and turning the text green, then counting the number of paragraphs:
var numberOfParagraphs = $("p").style("color", "green").length
If you pull up a JavaScript console on most web pages (at least the ones that use jQuery), this will work. A nerdy party trick. jQuery is functional because not looping lets you do lots of stuff in a single line of code, and when you're making web pages more interactive you often don't want more than a line of code.
Back to Google. Since at least the 1980s, supercomputer designers have been trying to figure out ways for to automatically convert C code that was written for single processors to work on multi-processor (and multi-core) computers. The theory was that writing explicitly parallel programs is too hard. The for-loop in the first example tells the computer to first handle the first item in the list, then the second item in the list, and so on. Meanwhile you have a variable (index) that is changing all the time. What you want on a 4-core computer is to simultaneously have each core process a quarter of the list, thus making the program up to 4 times faster. But as written, each processor would have to wait to see how the previous processor modified index.
The functional version, meanwhile, makes no guarantees about which elements in the list are processed first, and if you follow the no-variable-modification rule, you don't have to worry about coordinating variable changes between processors. Google called its programming system MapReduce. ("Map" you've seen, "reduce" is a generic term for functions like "count()" or "sum()" which reduce a list to something smaller.) The fundamental idea behind MapReduce is this: the programmer writes in terms of map and reduce instead of loops, and Google's system will figure out how to make it run. It works with anywhere from one computer to hundreds of thousands, and Google even built in redundancy so that if a computer fails during the calculation, another computer will take on the work. (When you have hundreds of thousands of computers, one of them is likely to go down at any moment.)
One of the hardest things about parallel programming is keeping data synchronized. The network is often the slowest component. The no-variable-modification rule can be inefficient on a single-processor machine, but on a computer network it speeds things up enormously.
But that's not why I prefer functional programming. For me, the no-variable-modification rule means no-tracking-down-how-that-variable-changed-in-my-buggy-code. And that saves me a ton of time.
