FROM THE ARCHIVES OF PRAGPUB MAGAZINE AUGUST 2012
Functional Thinking for the Imperative Mind: Getting Your Feet Wet
By Michael Bevilacqua-Linn
In which we dip our toe into the functional programming waters and answer the question, how does functional thinking differ from the imperative kind?
It’s difficult to pin down exactly what functional programming is.
It’s difficult because the phrase has come to imply several different, though related, things. If you talk to a Clojure hacker, you’ll probably get an earful of macros. A Haskell programmer might talk about monads, and an Erlang programmer about actors.
These are all different concepts. Macros give programmers extremely powerful metaprogramming, monads allow us to model changing state in a purely functional way, and actors provide a robust way of doing distributed and concurrent programming.
Yet all of these come from functional languages. The breadth of concepts can make it a bit difficult for someone new to figure out what it’s all about.
At its core, functional programming is about programming with pure, side-effect-free functions.
This is a pure function: f(x) = x². So is this:
public int incrementCounter(int counter) {
return counter++;
}This is not:
private int counter = 0;
public void incrementMutableCounter() {
counter++;
}The first example increments a counter by returning a new integer that’s one higher than than the passed-in integer. The second example does so by mutating a bit of state that may be shared across many pieces of a program.
A function like incrementCounter that doesn’t rely on mutating state is called a pure function. Purity has many benefits. For instance, if you’ve got a pure function that does some expensive computation, you can optimize your program by only calling the function once and caching the result, a technique known as memoization.
Pure functions also make programs easier to reason about. An object-oriented program is a graph of objects, each with its own bundle of mutable state. Modifying one object’s state can lead to another’s state being modified, possibly many nodes in the graph away. In a program with only pure functions, this sort of action at a distance is impossible.
That’s the simplistic description of functional programming. Unfortunately, strict purity and the real world don’t play well together. Pure functions can be used to model some domains well, others not so much. Compilers are pure functions. Google’s search is not.
Practical functional programming languages emphasize immutability and functional purity, though they must have some means of modeling a changing world that stops short of total functional purity. Haskell is probably the most strict. In Haskell, you can model change using monads, and otherwise maintain strict purity.
Other languages have their own techniques for minimizing and controlling state change that may not be quite as strict as Haskell’s. Clojure, for instance, uses a software transactional memory system in combination with a set of reference types and fiendishly clever immutable data structures to maintain a high degree of purity while still letting programmers deal with a changing world.
So to a first approximation, functional programming is about programming with pure functions and immutable state, while imperative programming relies heavily on mutability. Around this immutable core there is a set of language techniques and features that replace imperative techniques that rely on mutability. Looking at these will give us a deeper feeling for what it is to think and program functionally.
Let’s take a look at a simple example, filtering a list so it only contains odd numbers.
public List<Integer> filterOdds(List<Integer> list) {
List<Integer> filteredList = new ArrayList<Integer>();
for(Integer current : list) {
if(1 == current % 2) {
filteredList.add(current);
}
}
return filteredList;
}This is fine imperative code. We iterate through a list, and for each element we check to see whether it’s odd by computing its modulus. We could, perhaps, make its intent a bit clearer if we were to pull that check out into a helper function and name it.
public List<Integer> filterOdds(List<Integer> list) {
List<Integer> filteredList = new ArrayList<Integer>();
for (Integer current : list) {
if (isOdd(current)) {
filteredList.add(current);
}
}
return filteredList;
}
private boolean isOdd(Integer integer) {
return 1 == integer % 2;
}Now, what if we want to create a function that allows us to filter evens instead of odds? The only bit of code that needs to change is calling an isEven instead of isOdd.
public List<Integer> filterEvens(List<Integer> list) {
List<Integer> filteredList = new ArrayList<Integer>();
for (Integer current : list) {
if (isEven(current)) { filteredList.add(current);
}
}
return filteredList;
}
private boolean isEven(Integer integer) {
return 0 == integer % 2;
}This works, but we committed one of the cardinal coding sins. Most of filterOutEvens is cut and pasted from filterOutOdds. What we really want is a way to have a filter that can use some arbitrary bit of logic to do its filtering.
Let’s take a look at how we might accomplish this in Java. Both isOdd and isEven take a single argument and return a boolean value. Let’s define an interface that captures the essence of this computation. We’ll call it Predicate, which is a mathy name for a function that returns a boolean value.
public interface Predicate {
public boolean evaluate(Integer argument);
}Now we can rewrite filterEvens and filterOdds to be more generic.
public List<Integer> filter(List<Integer> list, Predicate predicate) {
List<Integer> filteredList = new ArrayList<Integer>();
for (Integer current : list) {
if (predicate.evaluate(current)) { filteredList.add(current);
}
}
return filteredList;
}Then we define our two predicates.
class isEven implements Predicate {
public boolean evaluate(Integer argument) {
return 0 == argument % 2;
}
}
class isOdd implements Predicate {
public boolean evaluate(Integer argument) {
return 1 == argument % 2;
}
}Now we can simply instantiate one of the predicates and pass it into the filter method. If we come up with a new way to filter our list, say we only want to keep integers that are perfect squares, we can just define a PerfectSquare predicate rather than having to cut and paste the entire filtering function.
What’s we’ve just done with the filter method and Predicate interface simulates a concept from the functional world, higher order functions. A higher order function is a function that can be passed into, or returned from, another function. Let’s take a look at how we’d do similar filtering in Clojure, a modern, functional variant of lisp.
(filter odd? [0 1 2 3])
(filter even? [0 1 2 3])That’s it! The first thing you probably noticed it that it’s much shorter than that Java version. The second is probably that the parentheses aren’t in their usual spot. Clojure, and other lisps, use prefix notation for functions calls. This means that the function that’s being called is the first thing inside the parentheses, with its arguments coming afterward.
Syntactic differences aside, notice how the Clojure version uses all built-in functions and language features? There’s no need for us to define a Predicate interface. odd? is a function that takes a number and returns true if it’s odd, while even? does the same for even numbers. We can pass those functions directly into the filter function using the power of higher order functions.
This turns our original imperative solution, in which we wrote code that was concerned with the nitty gritty details of iterating through a list, into a very declarative one. We’re working at a higher level of abstraction that often lets us describe what results we want, rather than the details of getting them.
So when people talk about functional programming, they’re generally talking about at least two separate, but very closely related things. First, they’re talking about programming with pure functions. Since this is a pipe dream for most real world problems, practical functional programming languages generally settle for making it easier to use immutability than not, and for facilities that control mutation when you absolutely need to do it.
Second, they’re talking about the style of programming that has grown up around this functional core. As we’ve seen, this style relies heavily on higher-order functions and other related techniques. These techniques often produce code that operates at a higher level of abstraction, such as using the filter function we saw above rather than explicit iteration.
These two facets of functional programming have significant benefits. The extreme emphasis on immutability makes programs easier to reason about. The behavior of a function can be understood just by reading the code in the function itself, rather than worrying about some bit of mutable state that it may rely on that’s hundreds or thousands of lines away. The use of higher-order functions often leads to declarative code, which is shorter and more direct than the imperative equivalent.
So if you think of these two things when you think of functional programming, you won’t be wrong: a preference for programming with pure functions, and a style of programming that involves higher-order functions in declarative code.
If this peek into the functional mindset has inspired you to look into functional programming in more detail, both Scala and Clojure are excellent languages for practicing programmers to learn functional techniques. They both run on the JVM and interoperate well with Java, so they’re suitable for any development task you’d care to throw at them.
Thanks for reading, and happy hacking!
About the Author
Michael Bevilacqua-Linn has been programming computers ever since he dragged an Apple IIGS that his parents got for opening a bank account into his fifth grade class to explain loops and variables to a bunch of pre-teenagers. In his spare time he likes rock climbing and good beer, though not at the same time. He blogs here.
Michael’s book with The Pragmatic Bookshelf:
