Java 8 in Action: Lambdas, streams, and functional-style programming (2015)
Part 4. Beyond Java 8
In the final part of this book, we draw back a little with a tutorial introduction to writing effective functional-style programs in Java, along with a comparison of Java 8 features with those of Scala.
Chapter 13 gives a full tutorial on functional programming, introduces some of its terminology, and explains how to write functional-style programs in Java 8.
Chapter 14 covers more advanced functional programming techniques including higher-order functions, currying, persistent data structures, lazy lists, and pattern matching. You can view this chapter as a mix of practical techniques to apply in your codebase as well as academic information that will make you a more knowledgeable programmer.
Chapter 15 follows by discussing how Java 8 features compare to features in the Scala language—a language that, like Java, is implemented on top of the JVM and that has evolved quickly to threaten some aspects of Java’s niche in the programming language ecosystem.
Finally, chapter 16 reviews the journey of learning about Java 8 and the gentle push toward functional-style programming. In addition, we speculate on what future enhancements and great new features may be in Java’s pipeline beyond Java 8.
Chapter 13. Thinking functionally
This chapter covers
· Why functional programming?
· What defines functional programming?
· Declarative programming and referential transparency
· Guidelines for writing functional-style Java
· Iteration vs. recursion
You’ve seen the term functional quite frequently throughout this book. By now, you may have some ideas of what being functional entails. Is it about lambdas and first-class functions? Or is it about restricting your right to mutate objects? In which case, what do you achieve from adopting a functional style? In this chapter, we shed light on these questions. We explain what functional programming is and introduce some of its terminology. We first examine the concepts behind functional programming such as side effects, immutability, declarative programming, and referential transparency and relate these to Java 8. In the next chapter, we look more closely at functional programming techniques such as higher-order functions, currying, persistent data structures, lazy lists, pattern matching, and combinators.
13.1. Implementing and maintaining systems
Let’s start by imagining you’ve been asked to manage an upgrade to a large preexisting software system, which you haven’t yet seen. Should you accept this job maintaining such a software system? A seasoned Java contractor’s only slightly tongue-in-cheek maxim for deciding is “Start by searching for the keyword synchronized; if you find it, then just say no (reflecting the difficulty of fixing concurrency bugs); otherwise consider the structure of the system in more detail.” We provide more detail in the next paragraphs, but first observe that, as you’ve seen in previous chapters, Java 8’s addition of streams allows you to exploit parallelism without worrying about locking, provided you embrace stateless behaviors (that is, functions in your stream-processing pipeline don’t interact by one reading from or writing to a variable that’s written by another).
What else might you wish the program to look like so it’s easy to work with? You’d want it to be well structured, with an understandable class hierarchy reflecting the structure of the system; there are even ways to estimate such structure by using software engineering metrics of coupling (how interdependent parts of the system are) and cohesion (how related the various parts of the system are).
But for many programmers, the key day-to-day concern is debugging during maintenance: this code crashed because it observed some unexpected value. Why is it this way and how did it get this way? Just think of how many of your maintenance concerns fall into this category![1] It turns out that the ideas of no side effects and immutability, which functional programming promotes, can help. Let’s examine this in more detail.
1 We recommend reading Working Effectively with Legacy Code (Prentice Hall, 2004) by Michael Feathers for further discussion on this topic.
13.1.1. Shared mutable data
Ultimately, the reason for the unexpected variable value problems just discussed is that shared mutable data structures are read and updated by more than one of the methods your maintenance centers on. Suppose several classes keep a reference to a list. Who owns this list? What if one class modifies it? Do other classes expect this change? How do other classes learn of this change? Do they need to be notified of this change to satisfy all assumptions on this list, or should they make a defensive copy for themselves? In other words, shared mutable data structures make it harder to track changes in different parts of your program. Figure 13.1 illustrates this idea.
Figure 13.1. A mutable shared across multiple classes. It’s difficult to understand who the owner is.
Consider a system that doesn’t mutate any data structures. It would be a dream to maintain because you wouldn’t have any bad surprises about some object somewhere that unexpectedly modifies a data structure! A method, which modifies neither the state of its enclosing class nor the state of any other objects and returns its entire results using return, is called pure or side-effect free.
What constitutes a side effect more concretely? In a nutshell, a side effect is an action that’s not totally enclosed within the function itself. Here are some examples:
· Modifying a data structure in place, including assigning to any field, apart from initialization inside a constructor (for example, setter methods)
· Throwing an exception
· Doing I/O operations such as writing to a file
Another way to look at this idea of no side effects is to consider immutable objects. An immutable object is an object that can’t change its state after it’s instantiated so it can’t be affected by the actions of a function. This means that once immutable objects are instantiated, they can never go into an unexpected state. You can share them without having to copy them, and they’re thread-safe because they can’t be modified.
The idea of no side effects might appear as a pretty severe restriction, and you may doubt whether real systems can be built in this way. We hope to convince you of this by the end of the chapter. The good news is that components of systems that embrace this idea can use multicore parallelism without using locking, because the methods can no longer interfere with each other. In addition, this is great for immediately understanding which parts of the program are independent.
These ideas come from functional programming, which we turn to in the next section. But first, let’s explore the idea of declarative programming, upon which functional programming is based.
13.1.2. Declarative programming
There are two ways of thinking about implementing a system by writing a program. One way centers on how things are done: “first do this, then update that, then ....” For example, if you want to calculate the most expensive transaction in a list, you’ll typically execute a sequence of commands: take a transaction from the list and compare it with the provisional most expensive transaction; if it’s more expensive, then it becomes the provisional most expensive; repeat with the next transaction in the list and so on.
This “how” style of programming is an excellent match for classic object-oriented programming, sometimes called imperative programming, because it has instructions that mimic the low-level vocabulary of a computer (for example, assignment, conditional branching, and loops), as shown in this code:
Transaction mostExpensive = transactions.get(0);
if(mostExpensive == null)
throw new IllegalArgumentException("Empty list of transactions")
for(Transaction t: transactions.subList(1, transactions.size())){
if(t.getValue() > mostExpensive.getValue()){
mostExpensive = t;
}
}
The other way centers instead on what’s to be done. You saw in chapters 4 and 5 that using the Streams API you could specify this query as follows:
Optional<Transaction> mostExpensive =
transactions.stream()
.max(comparing(Transaction::getValue));
The fine detail of how this query is implemented is left to the library. We refer to this idea as internal iteration. The great advantage is that your query reads like the problem statement, and because of that it’s clear to understand immediately in comparison to trying to understand what a sequence of commands does.
This “what” style is often called declarative programming. You give rules saying what you want, and you expect the system to decide how to achieve it. It’s great because it reads closer to the problem statement.
13.1.3. Why functional programming?
Functional programming exemplifies this idea of declarative programming (“just say what you want, using expressions that don’t interact, and for which the system can choose the implementation”) and side-effect-free computation explained previously. As we discussed, these two ideas can help you implement and maintain systems more easily.
Note that certain language features such as composing operations and passing behaviors, which we presented in chapter 3 using lambda expressions, are required to help read and write code in a natural way using a declarative style. Using streams, you were able to chain several operations together to express a complicated query. These features are what characterize functional programming languages; we look at them more carefully under the guise of combinators in the next chapter, in section 14.5.
To make things tangible and connect them with the new features in Java 8, we now concretely define the idea of functional programming and its representation in Java. What we’d like to impart is that by using functional-programming style, you can write serious programs without relying on side effects.
13.2. What’s functional programming?
The oversimplistic answer to “What is functional programming?” is “programming using functions.” So what’s a function?
It’s easy to imagine a method taking an int and a double as arguments and producing a double—and also having the side effect of counting the number of times it has been called by updating a mutable variable, as illustrated in figure 13.2.
Figure 13.2. A function with side effects
But in the context of functional programming a function corresponds to a mathematical function: it takes zero or more arguments, gives one or more results, and has no side effects. You can see it as a black box, which takes some inputs and produces some outputs, as illustrated in figure 13.3.
Figure 13.3. A function with no side effects
The distinction between this sort of function and the methods you see in programming languages like Java is central. (The idea of the mathematical functions like log or sin having such side effects in unthinkable.) In particular, mathematical functions when repeatedly called with the same arguments always return the same results. This rules out methods such as Random.nextInt, and we further discuss this idea later under the concept of referential transparency.
When we say functional we mean “like mathematics—no side effects.” Now a programming subtlety appears. Do we mean that every function is built only using functions and of course mathematical ideas such as if-then-else? Or might we allow a function to do nonfunctional things internally, as long as it doesn’t expose any of these side effects to the rest of the system? In other words, if we as programmers perform a side effect that can’t be observed by callers, does that side effect actually exist? The caller doesn’t need to know or care, because it can’t affect them.
When we wish to emphasize the difference, we refer to the first as pure functional programming (we return to this later in the chapter) and the latter as functional-style programming.
13.2.1. Functional-style Java
In practice, you can’t completely program in pure functional style in Java. For example, Java’s I/O model consists of side-effecting methods (calling Scanner.nextLine has the side effect of consuming a line from a file, so calling it twice typically gives different results). Nonetheless, it’s possible to write core components of your system as if they were purely functional. In Java you’re going to write functional-style programs. First, there’s a further subtlety about no one seeing your side effects and hence the meaning of functional. Suppose a function or method has no side effects, except for it incrementing a field just after entry and decrementing it just before exit. From the point of view of a program consisting of a single thread, this method has no visible side effects and can be regarded as functional style. On the other hand, if another thread could inspect the field—or worse could call the method concurrently—it wouldn’t be functional. You could hide this issue by wrapping the body of this method with a lock, and this would again enable you to argue that the method is functional. But in doing so you would have lost the ability to execute two calls to the method in parallel using two cores on your multicore processor. Your side effect may not be visible to a program, but it’s visible to the programmer in terms of slower execution!
Our guideline is that to be regarded as functional style, a function or method can mutate only local variables. In addition, objects it references should be immutable. By this we mean all fields are final, and all fields of reference type refer transitively to other immutable objects. Later you may also permit updates to fields of objects that are freshly created in the method, and so aren’t visible from elsewhere, and that aren’t saved to affect the result of a subsequent call.
Our previous guideline is incomplete, and there’s an additional requirement on being functional, which feels less important at first. To be regarded as functional style, a function or method shouldn’t throw any exceptions. There’s a simple overlegalistic explanation: you can’t throw an exception because this means a result is being signaled other than being passed as a proper result via return as in the black-box model discussed previously. But then this seems countered by practical mathematical use: although legally a mathematical function gives exactly one result for each possible argument value, many common mathematical operations are what we should properly call partial functions. That is, for some or most input values they give exactly one result, but for other input values they’re undefined and don’t give a result at all. An example is division when the second operand is zero or sqrt when its argument is negative. It might seem natural to model these situations by throwing an exception as Java does. There’s some scope for debate here, with some authors arguing that uncaught exceptions representing fatal errors are okay, but it’s the act of catching an exception that represents nonfunctional control flow, in that it breaks the simple “pass arguments, return result” metaphor pictured in the black-box model, leading to a third arrow representing an exception, as illustrated in figure 13.4.
Figure 13.4. A function throwing an exception
So how might you express functions like division without using exceptions? The answer is to use types like Optional<T>: instead of sqrt having signature “double sqrt(double) but may raise an exception,” it would have signature "Optional<Double> sqrt(double)"—either it returns a value that represents success or it indicates in its return value that it couldn’t perform the requested operation. And yes, this does mean that the caller needs to check whether each method call may result in an empty Optional. This may sound like a huge deal, but pragmatically, given our guidance on functional-style programming versus pure functional programming, you may choose to use exceptions locally but not expose them via large-scale interfaces, thereby gaining the advantages of functional style without the risk of code bloat.
Finally, to be regarded as functional, your function or method should call only those side-effecting library functions for which you can hide their nonfunctional behavior (that is, ensuring that any mutation they make on data structures is hidden from your caller, perhaps by copying first and by catching any exceptions they might raise). In section 13.2.4, “Functional style in practice,” you’ll see an example where we hide the use of side-effecting library function List.add inside our method insertAll by copying the list.
These prescriptions can often be marked using comments or by declaring a method with a marker annotation—and match the restrictions we placed on functions we passed to parallel stream-processing operations such as Stream.map in chapters 4–7.
Finally, for pragmatic reasons, you may find it convenient for functional-style code still to be able to output debugging information to some form of log file. Yes, this means the code can’t be strictly described as functional, but in practice you retain most of the benefits of functional-style programming.
13.2.2. Referential transparency
The restrictions on “no visible side-effects” (no mutating structure visible to callers, no I/O, no exceptions) encode the concept of referential transparency. A function is referentially transparent if it always returns the same result value when called with the same argument value. The methodString.replace is referentially transparent because "raoul".replace('r', 'R') will always produce the same result (the method replace returns a new String with all lowercase 'r' replaced with uppercase 'R') rather than updating its this object so it can be considered a function.
Put another way, a function consistently produces the same result given the same input, no matter where and when it’s invoked. It also explains why we don’t regard Random.nextInt as functional. In Java using a Scanner object to get the input from a user’s keyboard violates referential transparency because calling the method nextLine may produce a different result at each call. But adding together two final int variables always produces the same result, because the content of the variables can never change.
Referential transparency is a great property for program understanding. It also encompasses a save-instead-of-recompute optimization for expensive or long-lived operations, which goes under the name memoization or caching. Although important, this is slightly at a tangent to the development here, so we defer this explanation to the next chapter, in section 14.5.
In Java there’s one slight complication about referential transparency. Suppose you make two calls to a method that returns a List. Then the two calls may return references to distinct lists in memory but containing the same elements. If these lists were to be seen as mutable object-oriented values (and hence non-identical) then the method wouldn’t be referentially transparent. If you plan to use these lists as pure (immutable) values, then it makes sense to see the values as equal and hence the function as referentially transparent. In general, in functional-style code you choose to regard such functions as referentially transparent. We discuss this issue again in the next chapter, in section 14.5. We now explore the issue of whether to mutate from a wider perspective.
13.2.3. Object-oriented vs. functional-style programming
We start by contrasting functional-style programming with (extreme) classical object-oriented programming before observing that Java 8 sees these styles as mere extremes of the object-oriented spectrum. As a Java programmer, without consciously thinking about it, you almost certainly use some aspects of functional-style programming and some aspects of what we’ll call extreme object-oriented programming. As we remarked in chapter 1, changes in both hardware (for example, multicore) and programmer expectation (for example, database-like queries to manipulate data) are pushing Java software-engineering styles somewhat more to the functional end of this spectrum, and one of the aims of this book is to help you adapt to the changing climate.
At one end of the spectrum is the extreme object-oriented view: everything is an object and programs operate by updating fields and calling methods that update their associated object. At the other end of the spectrum lies the referentially transparent functional-programming style of no (visible) mutation. In practice, Java programmers have always mixed these styles. You might traverse a data structure using an Iterator containing mutable internal state but use this to calculate, say, the sum of values in the data structure in a functional-style manner (in Java, as discussed, this can include mutating local variables). One of the aims of the next sections in this chapter and more generally in the next chapter is to discuss programming techniques and introduce features from functional programming to enable you to write programs that are more modular and more suitable for multicore processors. Think of these ideas as additional weapons in your programming armory.
13.2.4. Functional style in practice
Let’s start by solving a programming exercise given to beginning students exemplifying functional style: Given a List<Integer> value, for example, {1, 4, 9}, construct a List<List<Integer>> value whose members are all the subsets of {1, 4, 9}—in any order. The subsets of {1, 4, 9} are {1, 4 ,9}, {1, 4}, {1, 9}, {4, 9}, {1}, {4}, {9}, and {}.
There are eight subsets including the empty subset, written {}. Each subset is represented as type List<Integer>, which means the answer is of type List<List<Integer>>.
Students often have problems thinking how to start and need prompting[2] with the remark that “the subsets of {1, 4, 9} either contain 1 or do not.” The ones that don’t are simply subsets of {4, 9}, and the ones that do can be obtained by taking the subsets of {4, 9} and inserting 1 into each of them. This gives an easy, natural, top-down, functional-programming-style encoding in Java. (A common programmer error is to say that an empty list has no subsets.)
2 Troublesome (bright!) students occasionally point out a neat coding trick involving binary representation of numbers (the Java solution code corresponds to 000,001,010,011,100,101,110,111). We tell such students to calculate instead the list of all permutations of a list; for the example {1,4,9} there are six of these.
The solution program produces {{}, {9}, {4}, {4, 9}, {1}, {1, 9}, {1, 4}, {1, 4, 9}} when given {1, 4, 9} as input. Do try it when you’ve defined the two missing methods.
Let’s review what you’ve just done. You’ve assumed that the missing methods insertAll and concat are themselves functional and deduced that your function subsets is also, because no operation in it mutates any existing structure. (If you’re familiar with mathematics, then you’ll recognize this argument as being by induction.)
Now let’s look at defining insertAll. Here’s the first danger point. Suppose you defined insertAll so that it mutated its arguments, perhaps by updating all the elements of subans to contain first. Then the program would incorrectly cause subans to be modified in the same way assubans2, resulting in an answer mysteriously containing eight copies of {1,4,9}. You instead define insertAll functionally as follows:
Note that you’re creating a new List that contains all the elements of subans. You take advantage of the fact that an Integer object is immutable (otherwise you’d have to clone each element too). The focus caused by thinking of methods like insertAll as functional gives you a natural place to put all this careful copying code—inside insertAll rather in its callers.
Finally, you need to define the method concat. In this case, there’s a simple solution, which we beg you not to use (we show it only so you can compare the different styles):
static List<List<Integer>> concat(List<List<Integer>> a,
List<List<Integer>> b) {
a.addAll(b);
return a;
}
Instead, we suggest you write this:
static List<List<Integer>> concat(List<List<Integer>> a,
List<List<Integer>> b) {
List<List<Integer>> r = new ArrayList<>(a);
r.addAll(b);
return r;
}
Why? The second version of concat is a pure function. It may be using mutation (adding elements to the list r) internally, but it returns a result based on its arguments and modifies neither of them. By contrast, the first version relies on the fact that after the call concat(subans,subans2), no one refers to the value of subans ever again. It turns out that, for our definition of subsets, this is indeed the case, so surely using the cheaper version of concat is better. Well, it depends on how you value your time spent later searching for obscure bugs compared with the additional cost of making a copy.
No matter how well you comment that the impure concat is “only to be used when the first argument can be arbitrarily overwritten, and only intended to be used in the subsets method, and any change to subsets must be reviewed in the light of this comment,’’ somebody sometime will find it useful in some piece of code where it apparently seems to work, and your future nightmare debugging problem has just been born. We revisit this issue in the next chapter in section 14.2, “Persistent data structures.”
Takeaway point: thinking of programming problems in terms of function-style methods that are characterized only by their input arguments, and their output result (that is, what to do) is often more productive than thinking how to do it and what to mutate too early in the design cycle. We now turn to recursion in more detail, a technique promoted in functional programming to let you think more in terms of this what to do style.
13.3. Recursion vs. iteration
Pure functional programming languages typically don’t include iterative constructs like while and for loops. Why? Because such constructs are often a hidden invitation to use mutation. For example, the condition in a while loop needs to be updated; otherwise the loop would execute zero or an infinite number of times. But for a lot of use cases loops are perfectly fine. We’ve argued that to be functional style you’re allowed mutation if no one can see you doing it, meaning it’s acceptable to mutate local variables. Using the for-each loop in Java, for(Apple a : apples { }decodes into the Iterator shown here:
Iterator<Apple> it = apples.iterator();
while (it.hasNext()) {
Apple apple = it.next();
// ...
}
This isn’t a problem because the mutations (both changing the state of the Iterator with the method next and assigning to the variable apple inside the while body) aren’t visible to the caller of the method where the mutations happen. But using a for-each loop, such as a search algorithm, as follows is problematic because the loop body is updating a data structure that’s shared with the caller:
public void searchForGold(List<String> l, Stats stats){
for(String s: l){
if("gold".equals(s)){
stats.incrementFor("gold");
}
}
}
Indeed, the body of the loop has a side effect that can’t be dismissed as functional style: it mutates the state of the stats object, which is shared with other parts of the program.
For this reason, pure functional programming languages such as Haskell omit such side-effecting operations entirely! How then are you to write programs? The theoretical answer is that every program can be rewritten to avoid iteration by using recursion instead, which doesn’t require mutability. Using recursion lets you get rid of iteration variables that are updated step by step. A classic school problem is calculating the factorial function (for positive arguments) in an iterative way and in a recursive way (we assume the input is > 1), as shown in the following two listings.
Listing 13.1. Iterative factorial
static int factorialIterative(int n) {
int r = 1;
for (int i = 1; i <= n; i++) {
r *= i;
}
return r;
}
Listing 13.2. Recursive factorial
static long factorialRecursive(long n) {
return n == 1 ? 1 : n * factorialRecursive(n-1);
}
The first listing demonstrates a standard loop-based form: the variables r and i are updated at each iteration. The second listing shows a recursive definition (the function calls itself) in a more mathematically familiar form. In Java, recursive forms are typically less efficient, and we discuss this shortly.
But if you’ve read the earlier chapters of this book, then you know that Java 8 streams provide an even simpler declarative way of defining factorial, as the next listing shows.
Listing 13.3. Stream factorial
static long factorialStreams(long n){
return LongStream.rangeClosed(1, n)
.reduce(1, (long a, long b) -> a * b);
}
Now let’s turn to efficiency. As Java users, you should beware of functional-programming zealots who tell you that you should always use recursion instead of iteration. In general, making a recursive function call is much more expensive than the single machine-level branch instruction needed to iterate. Why? Every time the factorialRecursive function is called, a new stack frame is created on the call stack to hold the state of each function call (the multiplication it needs to do) until the recursion is done. This means your recursive definition of factorial will take memory proportional to its input. This is why if you run factorialRecursive with a large input, you’re likely to receive a StackOverflowError:
Exception in thread "main" java.lang.StackOverflowError
Does this mean recursion is useless? Of course not! Functional languages provide an answer to this problem: tail-call optimization. The basic idea is that you can write a recursive definition of factorial where the recursive call is the last thing that happens in the function (we say the call is in a tail position). This different form of recursion style can be optimized to run fast. To exemplify, here’s a tail-recursive definition of factorial
Listing 13.4. Tail-recursive factorial
static long factorialTailRecursive(long n) {
return factorialHelper(1, n);
}
static long factorialHelper(long acc, long n) {
return n == 1 ? acc : factorialHelper(acc * n, n-1);
}
The function factorialHelper is tail recursive because the recursive call is the last thing that happens in the function. By contrast in our previous definition of factorial-Recursive, the last thing was a multiplication of n and the result of a recursive call.
This form of recursion is useful because instead of storing each intermediate result of the recursion onto different stack frames, the compiler can decide to reuse a single stack frame. Indeed, in the definition of factorialHelper, the intermediate results (the partial results of the factorial) are passed directly as arguments to the function. There’s no need to keep track of the intermediate result of each recursive call on a separate stack frame—it’s accessible directly through the argument of the function.
Figures 13.5 and 13.6 illustrate the difference between the recursive and tail-recursive definitions of factorial.
Figure 13.5. Recursive definition of factorial, which requires several stack frames
Figure 13.6. Tail-recursive definition of factorial, which can reuse a single stack frame
The bad news is that Java doesn’t support this kind of optimization. But adopting tail recursion may be a better practice than classic recursion because it opens the way to eventual compiler optimization. Many modern JVM languages such as Scala and Groovy can optimize those uses of recursion, which are equivalent to iteration (they’ll execute at the same speed). This means that pure-functional adherents can have their purity cake and eat it efficiently too.
The guidance when writing Java 8 is that you can often replace iteration with streams to avoid mutation. In addition, iteration can be replaced with recursion when it lets you write an algorithm in a more concise and side-effect-free way. Indeed, recursion can make examples easier to read, write, and understand (for example, in the subsets example shown previously), and programmer efficiency is often more important than small differences in execution time.
In this section, we discussed functional-style programming but only used the idea of a method being functional—everything we said would have applied to the very first version of Java. In the next chapter we look at the amazing and powerful possibilities offered by the introduction of first-class functions in Java 8.
13.4. Summary
Following are the key concepts you should take away from this chapter:
· Reducing shared mutable data structures can help you maintain and debug your programs in the long term.
· Functional-style programming promotes side-effect-free methods and declarative programming.
· Function-style methods are characterized only by their input arguments and their output result.
· A function is referentially transparent if it always returns the same result value when called with the same argument value. Iterative constructs such as while loops can be replaced by recursion.
· Tail recursion may be a better practice than classic recursion in Java because it opens the way to eventual compiler optimization.