We're approaching one of those paradigm shifts again. Knowledge of functional programming (FP) is on the verge of becoming a must-have skill. Now, we're not talking about a shift on the scale of the tectonic movement that object-oriented programming brought on. Functional programming has been around since the creation of LISP in 1958 and hasn't taken over application development, nor is it about to. FP won't make your word processing program faster or better. But there are domains where it is highly useful, and in particular FP looks like the paradigm of choice for unlocking the power of multicore processors. Functional programming languages are ideally suited to, as one developer succinctly puts it, "solving the multicore problem."
Which is a big deal, because the chipmakers have essentially said that the job of enforcing Moore's Law is now a software problem. They will concentrate on putting more and more cores on a die, and it's up to you to recraft your software to take advantage of the parallel-processing capabilities of their chips.
And that means that there are real benefits in becoming proficient in parallel functional programming, and, as will be argued momentarily, that means functional programming. The bad news? Getting good at functional programming is hard, harder than moving from iterative Pascal or Basic or C coding to object-oriented development. It's an exaggeration but a useful one: When you move to FP, all your algorithms break.
FP: What It Is
Most modern programming languages, including object-oriented languages, are imperative: A program is essentially a list of instructions intended to be executed in order. Functional programming languages derive from the declarative style branch of the language tree, where there need be no explicit flow of control. This branch bifurcates further, with one branch leading to the logic-flavored languages, primarily Prolog, and one branch leading to the functional languages, the prime historical example being Lisp. Lisp and many other FP languages are based on, and are essentially implementations of, Alonzo Church's lambda calculus, a formal model for computation.
Two defining features of functional languages are that all computations are treated as the evaluation of a function and that functional language programs avoid state and mutable data. Every variable is really a constant. You can't change the state of anything, and no function can have side effects, which is the reason why FP is ideal for distributing algorithms over multiple cores. You never have to worry about some other thread modifying a memory location where you've stored some value. You don't have to bother with locks and deadlocks and race conditions and all that mess. Some companies, Ericsson, for example, are making good money exploiting this virtue of functional programming.
This is too good to be true, of course. No side effects means no I/O, for example. You can't really do anything if you can't modify any values or change state. Yet it can be shown that the lambda calculus is equivalent to a Turing machine, so you must be able to perform calculations using FP. How?
The answer is that FP languages store state in function parameters—that is, on the stack. They also cheat when it's practical to do so, breaking the pure FP paradigm in carefully controlled ways. Monads are one such trick: Impure functions that have side effects and that can call pure FP functions but can't be called by them.
That other defining feature? Everything is a function. When I learned Lisp, my professor taught that no program should be longer than three lines, four in a pinch. The idea is that the entire program is one function, and that this function simply calls two or three other functions that, if they existed, would do the job. Then you write those functions, and the functions they require, until eventually you are writing exclusively in primitive functions, at which point you're done.
In any functional programming language, you are likely to encounter these features:
- First-class functions, or higher-order functions: Functions can serve as arguments and results of functions.
- Recursion as the primary tool for iteration.
- Heavy use of pattern matching, although technically it is not a defining feature of FP.
- Lazy evaluation, which makes possible the creation of infinite sequences and other data structures.
Here's the canonical example of a functional program, the factorial function, in Haskell:
factorial n = if n > 0 then n * factorial (n-1) else 1
