Functional programming is a model of computation that avoids
making repeated changes to objects, and computes outputs from inputs in a
stateless way. The implications are far-reaching: functional programs are more
concise, easier to understand and debug, and can be executed more efficiently
on modern computer hardware. Although functional programming has been around
for a long time there has been a recent resurgence in interest with the advent
of languages like Scala, which support functional programming and can be
executed in a standard JVM. But even if you’re writing code in Java, you can
use functional programming patterns and achieve many of the benefits.
In this article we explain the basic principles of functional programming, and show some functional patterns that you can start using in your Java programs immediately.
The Problem
Object-oriented programming is about being able to define
packages of state, together with operations on that state. Typical
object-oriented languages support encapsulation, i.e., the notion that the
state can only be accessed via the defined operations, and polymorphism, i.e.,
the notion that objects of different types can be treated uniformly. Here is an
example that shows these concepts. The Reader interface defines an operation
for retrieving information one String at a time. The ArrayReader class
implements this interface, starting from an array of Strings and returning them
one at a time. The CharReader class also implements the same interface,
starting from any type of Reader and returning its output one character at a
time (see Listing 1).
Notice that both ArrayReader and CharReader have private, internal state. It’s part of the benefit of object-oriented programming that these implementations could be changed without affecting any other code as long as the public interfaces are preserved.
But in real-life object-oriented programming, subtle problems begin to emerge due to the too frequent use of mutable (i.e., changeable) state. Even this simple Reader example can be hard to understand if readers are shared or accessed concurrently from multiple threads. For example, what does the following code example do?
public static void main(String[] args) {
Reader arrayReader =
new ArrayReader (new String[] { “Foo”, “Bar”, “Baz” });
Reader charReader = new CharReader (arrayReader);
String s = arrayReader.read();
while (s != null) {
System.out.println
(s);
System.out.println
(charReader.read()); // uh oh
s =
arrayReader.read();
}
}
As it turns out, the result is:
Foo
B
Baz
a
The B and the a on the second and fourth line of the output come from the word “Bar.” It’s confusing because the loop alternates each call to arrayReader.read() that pops a word from the ArrayReader, with a call to charReader.read() that pops a word from the same ArrayReader every time it runs out of characters. The spirit of these classes was to call either the ArrayReader or the CharReader in a loop, but not to make calls to the same ArrayReader both directly and indirectly via the CharReader class. But nothing in the object-oriented paradigm (or any paradigm) stops people from violating unwritten rules. As a result, you have to understand exactly how the ArrayReader and CharReader objects interact to predict what will happen. The problem is magnified if your program is multithreaded.
The fundamental problem is that each object behaves differently depending on its current state. (Obviously the second time you call read() on an ArrayReader you get a different result from the first time you call it.) That means that in general, if you want to understand what any particular operation is doing to an object, you have to know exactly what state the object was in before you invoked the operation. But to know that you have to know at what point the object was created, and the exact sequence of subsequent operations that might have changed the object’s internal state. That’s easy if the object reference is assigned to only a local variable and never shared, but if the object reference can be obtained from anywhere in your application via reflection or a directory service, then all bets are off.
Adding Fuel to the Fire by Abstracting Away Object Creation
Design patterns that abstract away the process of object
creation bring a huge amount of benefit in terms of software configuration
management and testability. Such design patterns have become enormously popular
in recent years, but they are problematic when combined with the use of mutable
state. A programmer cannot determine which classes a particular code sequence
will instantiate just by looking at the code, and therefore cannot reason about
the code until the runtime behavior of the object factory is fully understood.
For example, let’s say we decide to rewrite our example based on Spring
retaining the exact same behavior as before:
public static void main(String[] args) {
BeanFactory factory = new XmlBeanFactory(new FileSystemResource(“applicationContext.xml”));
Reader arrayReader =
(Reader) factory.getBean (“arrayReader”);
Reader charReader = (Reader) factory.getBean (“charReader”);
String s = arrayReader.read();
while (s != null) {
System.out.println (s);
System.out.println (charReader.read());
s = arrayReader.read();
}
}
The underlying classes have not been changed at all, nor has the main logic, but we have left the instantiation of the classes to the Spring framework. Would you be able to understand the code sequence above if you hadn’t read the introduction to this article? For completeness, here is the applicationContext.xml file:
<beans>
<bean id=”arrayReader” class=”ArrayReader”>
<constructor-arg>
<list>
<value>Foo</value>
<value>Bar</value>
<value>Baz</value>
</list>
</constructor-arg>
</bean>
<bean
id=”charReader” class=”CharReader”>
<constructor-arg
ref=”arrayReader” />
</bean>
</beans>
Note that we used constructor-based dependency injection, but it’s common to use setter-based injection in which case we would have added setters to each class for the String array and Reader dependencies, thus creating even more mutable state. By changing this XML file we can cause our program to behave completely differently. Here is a version, for example, that provides the CharReader object with its own private ArrayReader and eliminates the confusing sharing of the mutable state:
<beans>
<bean
id=”arrayReader” class=”ArrayReader”>
<constructor-arg>
<list>
<value>Foo</value>
<value>Bar</value>
<value>Baz</value>
</list>
</constructor-arg>
</bean>
<bean
id=”charReader” class=”CharReader”>
<constructor-arg>
<bean
class=”ArrayReader”>
<constructor-arg>
<list>
<value>Hello</value>
</list>
</constructor-arg>
</bean>
</constructor-arg>
</bean>
</beans>
This version produces the output:
Foo
H
Bar
e
Baz
l
With this change to the configuration file, the main loop prints Foo, Bar, and Baz as expected, and the CharReader prints out individual characters from the word Hello. They no longer interfere with each other. The question of whether or not the main ArrayReader’s state is shared (creating the undesired interaction between the classes) depends on the application configuration file, which illustrates why the configuration file must be read and understood to predict the behavior of the actual program. When we are talking about configuration files running to hundreds and thousands of lines of XML, this can be daunting.
This is not a straw man argument. Code like this is getting written and deployed every day in mission-critical enterprise applications. We’ve had to debug some of it. We are not saying that object-oriented programming is bad, or that it’s wrong to abstract away the process of object creation. On the contrary, our point is that mutable state makes programs hard to understand, and modern programming practices magnify the problem. Complexity in software is inescapable, but unnecessary complexity is, well, unnecessary. By attacking the problem at its root (mutable state), we hope to have our cake and eat it too.
Functional Programming: An Alternative Approach
To understand better how functional programming can simplify
this problem, we’ll first look at an even simpler problem in Haskell (one of
the most mature modern functional programming languages).
If you only remember one thing about functional programming, it should be this central idea: that it should be possible to substitute a function call with its result, without changing the meaning of a program. This simple principle (generally referred to as referential transparency) has radical implications. At its best, this idea strengthens the intuition we’ve developed from high school algebra that, difficult as a problem may be, we can write it out in its entirety and solve it by progressively simplifying it.
Rather than taking on the full-grown horror of a decades-old legacy system, let’s consider a very simple functional program and analyze it in ways representative of real-life concerns.
sum [] = 0
sum x:xs = x + sum xs
This definition is intended to describe a function, “sum,” that adds up all of the numbers in a list. If the input list is empty (denoted by empty square brackets) the sum is 0. Otherwise we can break the list into its head (“x”) and its tail (“xs” – read as the plural of “x”), in which case the sum is just the head plus the sum of the tail. It might help clarify this to read the function out loud in English:
“The sum of an empty list is zero. Otherwise, the list has an initial value x followed by the remaining values xs, and the sum is x plus the sum of the xs.”
This is a recursive definition, and although it may at first glance seem like an endless loop, the sum will always decrease the length of the input list by one until the simplest case (the empty list) is reached. Let’s try it out on an example:
sum [1, 2, 3, 4, 5]
Using the principle of referential transparency, and substituting the appropriate body of the “sum” function at each step, we can proceed to rewrite this as follows:
sum 1:[2, 3, 4, 5]
1 + sum [2, 3, 4, 5]
1 + sum 2:[3, 4, 5]
1 + 2 + sum [3, 4, 5]
1 + 2 + sum 3:[4, 5]
1 + 2 + 3 + sum [4, 5]
1 + 2 + 3 + sum 4:[5]
1 + 2 + 3 + 4 + sum [5]
1 + 2 + 3 + 4 + sum 5:[]
1 + 2 + 3 + 4 + 5 + sum []
1 + 2 + 3 + 4 + 5 + 0
Having made each step of the computation explicit, the derivation of the final result is clear. What’s more, we can be certain that each step in the above derivation completely describes the computation, as we’ve given up the possibility of implicit “side effects” happening between steps. You can imagine that if the “sum” function had a side-effect (like updating the input list) this simple two-line example would become much more difficult to understand.
Because a functional program implies that you can always substitute a function call with its result, there are two very important things that our compiler can do to help us without any effort on our part. The first is that, according to the principle of referential transparency, the compiler can substitute the final result for the call to “sum” at compile-time, without changing the behavior of the program. This has the effect, in our example, of doing no runtime computation at all!
In more realistic cases, the compiler may not be able to compute the entire function ahead of time, but with this principle as a guide it can still simplify the inevitable runtime computation by partially evaluating as much of it as possible at compile-time. The second thing the compiler can do is to perform the final computation in parallel where possible. Given some simple properties of the functions involved (in this case, the fact that a + b + c = a + (b + c) = (a + b) + c), the compiler could easily generate code to compute the final sum as (with concurrent evaluation denoted by parentheses):
1 + 2 + 3 + 4 + 5 + 0
(1 + 2) + (3 + 4) + (5 + 0)
3 + 7 + 5
(3 + 7) + (5)
10 + 5
(10 + 5)
15
Remarkably, the compiler can (given just these few reasonable assumptions) produce a very specialized, efficient executable from our compact functional program. The key to passing all of this complexity off to the compiler is that we go out of our way to leave the compiler as many implementation options as possible. To summarize this viewpoint: functional programs describe what is to be computed, allowing functional compilers to decide how to compute it. Unnecessary complexity creeps into software projects where these problems of what and how are intermixed.
Introduction to Scala
A good way for Java programmers to experiment with
functional programming concepts is to give Scala a try. Scala is an interesting
programming language first released in 2003 by Martin Odersky, a computer science
professor at the Swiss Federal Institute of Technology, and one of the
designers of Java generics. Scala is a multi-paradigm language, smoothly
integrating features of both object-oriented and functional languages. Most
importantly it is fully interoperable with Java. It compiles to JVM bytecodes
(i.e., standard .class files), Java libraries can be used freely in Scala
programs, and it is possible to inherit from Java classes and implement Java
interfaces directly in Scala. An Eclipse plug-in is even available.
Installation Instructions via the Eclipse Plug-in
If you’re an Eclipse user, it’s easy to get started with
Scala by installing the Scala Eclipse Plug-in. You don’t even have to install
Scala first. Just select:
Help -> Software Updates -> Find and Install -> Search for new features to install
and create a new remote site called “Scala Plugin Update Site” with this URL:
http://scala-lang.org/downloads/scala-plugin
Install the feature Scala Plugin UpdateSite. If you get an error that package org.eclipse.pde.runtime is missing, then go back to:
Help -> Software Updates -> Find and Install -> Search for new features to install
and select The Eclipse Project Updates, expand the category corresponding to your version of Eclipse, and select the Eclipse Plugin Development Environment. Install it and restart Eclipse. That plug-in includes the required org.eclipse.pde.runtime package, so once it’s installed you should be able to install the Scala plug-in.
If you are not an Eclipse user, you can install Scala the traditional way, starting from this URL:
http://www.scala-lang.org/downloads/index.html
Once you’ve installed Scala, create a new Scala Project.
Create a package called com.lab49.example and within it create a Scala Object
called
package com.lab49.example;
object Main {
def main(args: Array[String]) {
println(“Hello, world!”)
}
}
Select Run as Scala Application. If it displays Hello, world then congratulations! You have just written your first Scala application.
Now let’s try rewriting the sum function in Scala:
package com.lab49.example;
object Main {
def sum (l: List[Int]): Int = {
l match {
case Nil => 0
case ::(x,xs)
=> x + sum(xs)
}
}
def main(args:
Array[String]) {
println
(sum(List(1, 2, 3, 4, 5)));
}
}
This is slightly more verbose, but similar in spirit to the two-line Haskell example we started with. The Haskell version didn’t declare a package, enclosing class, or Main function, so a fair comparison is to look at only the sum function that is six lines long in Scala and includes type declarations. Note the pattern-matching syntax, for example, the use of :: to match a list and split the head node from the remaining nodes. This is an example of a nice Scala feature called case classes that lets you write pattern-matching case statements for your own classes as well as built-in ones.
Note that it’s not the objective of this paper to be a Scala tutorial. There are already many of those on the Web. But we want to introduce Scala because it provides excellent support for functional programming, fits well with the Java technology stack, and is gaining momentum in the Java community.
This sum example we started with may be simple, but it already illustrates how functional programming is different. The obvious way to code this in Java would have been to initialize a counter to zero, iterate through the list, and keep modifying the counter by adding the next value. If you’ve been writing Java code for a long time, you may not realize how deeply ingrained it is for us to solve problems by constantly modifying variables, calling methods that modify objects, and so on. But in functional programming, your first instinct should be to think of every problem in terms of computing an output directly from an input, breaking it into smaller problems that you solve recursively if necessary.Let’s come back to our original problem now and try to apply these concepts.
Rewriting Our Original Example
First let’s consider the Reader interface we started with:
public interface Reader {
String read();
}
The idea of this interface is to provide access to a list of strings one at a time, presumably so we can do something to those strings. But the fundamental idea of this interface is not in keeping with functional programming, since every time you call read you change the state of the object. Can we come up with a more functional way of doing the same thing? Indeed we can, by changing the responsibilities slightly. Instead of feeding strings to a consumer one at a time, we will instead ask the consumer to tell us what work they want done on each string (using a callback) then we will do it to all of the strings. In Scala the equivalent to a Java interface is a trait, so our revised example will look like this:
trait Reader {
def repeatForEach (f: String => Unit) = ()
}
We are replacing the read method with one called repeatForEach, which takes a callback as an argument. The callback must take a string as input and return nothing as output (that’s what the Unit type means in Scala), the idea being that repeatForEach will invoke the callback for each individual string. We say = () to declare that by default, this method does nothing. Now we need an equivalent to the ArrayReader that takes a list of strings at construction time, and can be used later to provide one-at-a-time access to those strings. In Scala you don’t implement an interface, you extend a trait. Furthermore, although Scala supports an Array type, we want to use the List type, which is immutable and emphasizes our functional style. So we end up with this:
class ArrayReader (strings : List[String]) extends Reader {
override def repeatForEach (f: String => Unit) = {
strings.foreach (f);
}
}
This defines a class ArrayReader that extends the Reader trait and that requires a list of Strings upon construction. Note that in Scala you can specify arguments in a class definition (almost like a function definition). This means that the arguments must be provided in every use of the constructor and they automatically become available as immutable class members. Thus the following code in Scala:
class ArrayReader (strings : List[String]) {
}
is analogous to the following Java code:
public class ArrayReader {
private final List<String> strings;
public ArrayReader (List<String> strings) {
this.strings = strings;
}
}
Once you have an instance of the Scala ArrayReader class, at any point in the future you can call repeatForEach and pass it a callback, and it will perform the callback on each of the strings in the original list, in sequence. This is equivalent in usefulness to our original ArrayReader class. For example, here is how you would print out all of the strings:
object Main {
def main(args: Array[String]) {
val arrayReader: Reader = new ArrayReader(List(“Foo”, “Bar”, “Baz”));
arrayReader.repeatForEach (println);
}
}
Now let’s write the CharReader class. It requires a Reader upon construction, and provides character-by-character access to all of the items in that reader:
class CharReader (r: Reader) extends Reader {
override def repeatForEach (f: String => Unit) = {
r.repeatForEach ((s: String) =>
s.toList.foreach ((c: Char) =>
f
(c.toString)));
}
}
This is more difficult to understand, so let’s work through it step-by-step. The CharReader takes any kind of Reader as an argument upon construction, and is also a Reader itself – just like in our original example. Like the ArrayReader it provides a repeatForEach method that takes a callback argument. Whenever this method is called with a callback argument f, the CharReader calls repeatForEach on its underlying reader, providing its own callback, which calls toList.foreach on each String, allowing each character to be processed individually. The callback f is invoked on each character after converting it to a one-character string.
Scala supports type inference, meaning that you can omit many of the type declarations without sacrificing any type safety at all. Thus you can write this more compactly this way:
class CharReader (r: Reader) extends Reader {
override def repeatForEach (f: String => Unit) = {
r.repeatForEach (s => s.toList.foreach (c => f (c.toString)));
}
}
Now let’s try using our new classes:
object Main {
def main(args: Array[String]) {
val arrayReader: Reader = new
ArrayReader(List(“Foo”, “Bar”, “Baz”));
val
charReader: Reader = new CharReader (arrayReader);
arrayReader.repeatForEach (println);
charReader.repeatForEach (println);
}
}
Here’s the output:
Foo
Bar
Baz
F
o
o
B
a
r
B
a
z
This looks surprisingly like our original example, doesn’t it? We have a Reader interface with ArrayReader and CharReader implementations with roughly the same meanings as in the corresponding Java versions. The only difference is that this example has no mutable state whatsoever. There is no point at which any variable is modified from an old value to a new value. Although state is still shared between the arrayReader and charReader objects (the charReader contains a reference to the arrayReader), it’s simply not possible for them to interact inappropriately. Whenever you call:
arrayReader.repeatForEach (...)
a given input of ... will always produce exactly the same result. There isn’t any method for resetting the iterator either, because there’s no such concept in this design. You can call arrayReader.repeatForEach as many times as you like, and each time it will iterate through the entire list with no possibility of problems occurring. It can be used in a multithreaded environment and race conditions won’t even be possible. Race conditions can only occur when you have mutable state.
It may seem like cheating to convert the program to a functional one by changing the design to use callbacks, but we argue that it’s fair game. Functional programming is all about programming without side effects (i.e., mutating state), and that means coming up with new idioms for solving familiar problems. In this case, the original iterator-based solution was very typical Java code. To achieve the same thing without side effects we had to pass callbacks around (also known as closures, function objects, or anonymous functions) but this is very typical in functional languages, which typically provide a clean, elegant syntax to support that style of programming.
Functional Programming in Java
Let’s explore how we can introduce functional programming
concepts into our Java code, in case our managers are not yet ready to allow the
use of Scala for commercial software development. Unfortunately Java lacks many
advanced functional programming features and its syntax is not ideal for this.
Higher order functions (i.e., functions that operate on other functions) are
almost impossible to express, especially if you want to make them strongly
typed. (Defining strongly typed higher order functions requires the use of
generics and Java’s “type erasure” implementation of generics throws away a significant amount of type information at runtime in the interest of
efficiency. Martin Odersky giveth and Martin Odersky taketh away.)
That being said, the recent support in Java for anonymous classes still allows us to represent our Scala Reader example reasonably faithfully in Java.
The reader example is revisited on Listing 2.
This Java solution is written in a functional style, although it may look awkward to most Java programmers. We had to introduce a StringCallback interface to represent the callback, and used the new anonymous class capability in several places. However this solution has all the virtues of the Scala solution. It is immune to the problems associated with shared mutable state, and can be used safely in a multithreaded environment without any need for locking or any risk of race conditions.
Not all functional programming idioms can be translated into Java, but some of the simpler ones can, and although they may seem unnatural at first, they do bring benefits. It’s always worth asking the question: Can I solve this problem without the use of mutable state?
A Reconciliation Example
Say you have two lists of information that have to be
reconciled. You want to know which items are in one list and not in the other,
and vice versa. This kind of problem sometimes crops up in financial applications,
and is often solved by traversing both lists and building a data structure to
store the differences (e.g., a hash table). A more functional solution to the
problem is to write code that can subtract the contents of one list from
another as shown in Listing 3.
This example shows a functional approach to reconciling lists of information, but also shows the kind of compromise that has to be made when doing this style of programming in Java. Unfortunately the built-in Java Collection classes do not efficiently support immutable lists, so there is no way in the diff function to build up the result without either using mutation or creating our own immutable collection classes. We chose a practical approach: Create a fresh LinkedList object when the recursion bottoms out then mutate it repeatedly by calling addFirst to build up the result. Although this is not functional, we are doing it in only one place, and we are changing an object that was created within the diff method, is never shared, and has no permanent state after the initial call returns. So the implementation of diff is “mostly functional,” and the rest of the example is completely functional. This solution has most of the virtues of functional programming in terms of avoiding the problems of shared mutable state, and doesn’t destroy its input lists the way the removeAll method would (as defined in the Java Collection classes).
A Tree Aggregation Example
Say you have a tree of any type of object. Let’s keep it
simple and represent the tree as an array of Java objects, each element of
which could be a leaf node or another array. You might want to calculate a
value based on all elements of the tree. A functional approach to this problem is to define a TreeWalker that can traverse any tree and accept a user-provided aggregation function (see Listing 4).
Once again we rely on Java’s new anonymous class capability, but we avoid the use of generics because Java’s “type erasure” implementation of generics would not allow us to use instanceof.
In this example we created a tree of numbers called myTree with eight nodes. Then we used the TreeWalker twice, each time passing it a different aggregation rule; one that knows how to aggregate a tree by adding, and another that knows how to aggregate a tree by multiplying.
The point is that tree traversal and aggregation have been factored into a general-purpose capability, and complex operations can be performed on the tree without any need for mutable state. As in the previous example, there is brief use of mutable state in the implementation of the aggregate function, but it’s on a locally created unshared object, so it’s acceptable. Programming languages like Scala that are designed for functional programming would not even require that, since they support immutable collections.
Summary
The use of mutable state makes programs hard to understand,
especially in conjunction with currently popular programming practices in which
objects are created indirectly and state sharing is not obvious from reading
the code. Furthermore in multithreaded environments, programs relying on
mutable state are prone to race conditions, requiring the use of locking that
can impact performance and make programs even harder to understand and debug.
Functional programming offers an alternative approach to solving computing problems based on transforming inputs into outputs in a stateless way. Functional programs are referentially transparent, meaning function calls can always be substituted with their results without changing the meaning of the program. The loss of expressive power from having to avoid the use of mutable state is compensated for by providing better support for manipulating function objects and combining them in useful ways.
You can start using rudimentary functional programming techniques in Java immediately, but advanced techniques require better programming language support than Java offers. Scala is a useful language for Java programmers to explore, as it provides excellent support for functional programming while fitting smoothly into the Java developer’s world.
Additional Reading
- Wikipedia.
- Can Your Programming Language Do This?
-
Bill Venners,Martin Odersky, and Lex Spoon. First Steps to Scala. May 9, 2007.