Functional Programming in Mainstream Languages, Part 3: Higher-Order Functions in Java 7 and 8

(Jump to Table of Contents)

Having seen (in the part 2 of this series) the basic syntax for expressing functions in Java 8, we will now explore some functional-programming techniques and compare how they are expressed in Scheme, Java 7, and Java 8.  The examples are adapted from the book Structure and Interpretation of Computer Programs (2nd Edition) by Abelson and Sussman.

The following function attempts to compute an approximation to a fixed point of a given function f; that is, a value x such that x = f(x).  The computation starts from an initial guess c, and repeatedly applies the function f to it, to get the series f(c), f(f(c)), f(f(f(c))), ....  If this process converges, the result is close to a fixed point, since convergence means that applying f one more time returns (almost) the same value.  However, the process may not converge at all, either because f has no fixed points at all, or because the process oscillates without finding a fixed point.

Here are the implementations of this function in the three languages:

Scheme

(define (fixed-point f first-guess)   (define (try guess) (let ((next (f guess))) (if (< (abs (- guess next)) epsilon) next (try next)))) (try first-guess))

Java 7

public double fixedpoint(UFunc<Double, Double> f, double v) { double next = f.apply(v); if (Math.abs(next - v) < epsilon) return next; else return fixedpoint1(f, next); }

Java 8

public double fixedpoint(DoubleUnaryOperator f, double v) { double next = f.applyAsDouble(v); if (Math.abs(next - v) < epsilon)         return next; else         return fixedpoint1(f, next); }

Functional implementations usually use recursion instead of loops; the Scheme implementation defines an internal recursive function try, which computes the next value in the series and checks whether it is already close enough to the previous one to consider the series to have converged.  If so, it returns the last value in the series; if not, it continues recursively to try the next value.

The two Java implementations are quite similar, except for the types.  For the Java 7 implementation, I created the following interface to represent unary functions from a domain D to a range R:

Java 7

public interface UFunc<D, R> { R apply(D arg1); }

As I explained in the previous post, Java 8 supplies a large set of interfaces to describe functions; DoubleUnaryOperator is the type of functions that take a double and return a double.

There is a fundmemtal difference between functional languages (including Scheme) and most other languages, including Java.  In the former, tail-recursive calls are converted by the compiler into jumps that don't add a frame to the execution stack.  This means that such calls behave like loops in terms of their memory consumption.  (For more details see Abelson and Sussman.)  However, the latter languages don't guarantee this property.  As a result, the Java implementations above may use stack space proportional to the number of applications of the function required for convergence.

A more natural style for implementing these methods in Java is imperative rather than functional:

Java 7

public double fixedpoint(UFunc<Double, Double> f, double v) { double prev = v; double next = v; do {         prev = next;         next = f.apply(next); } while (Math.abs(next - prev) >= epsilon); return next; }

Java 8

public double fixedpoint(DoubleUnaryOperator f, double v) { double prev = v; double next = v; do {         prev = next;         next = f.applyAsDouble(next); } while (Math.abs(next - prev) >= epsilon); return next; }

While functional-programming purists frown at this style, which modifies the values of the variables prev and next, this style is more natural for Java, and uses constant space on the stack.  For those reasons, I find it acceptable when using functional techniques in Java, provided that the changes are confined to local variables (rather than fields), and, in particular, locals that aren't referenced in any other method (such as those in inner classes) or function.

We can now try to use the fixedpoint function to compute square roots, using the fact that y is a square root of x if y = x/y; in other words, if y is a fixed point of the function λy.x/y:

Scheme

(define (sqrt x) (fixed-point (lambda (y) (/ x y)) 1.0))

Java 7

public double sqrt(final double x) { return fixedpoint(new UFunc<Double, Double>() {         @Override         public Double apply(Double y) {             return x / y;         } }, 1.0); }

Java 8

public double sqrt(double x) { return fixedpoint(y -> x / y, 1.0); }

Here we need to create an anonymous function ("lambda"), and here the difference between Java 7 and Java 8 becomes very clear.  In Java 7 we need to create the function as an anonymous inner class, with all the necessary boilerplate code, which obscures the essentials of what we are trying to do.  (For example, it is quite difficult to figure out that 1.0 is the second parameter to the fixedpoint method.)  In contrast, in Java 8 we can just use the new lambda notation, and the meaning is immediately clear.

In both versions of Java, it is only possible to refer in inner methods to variables defined in enclosing constants if these variables are final; that is, if they can't be modified.  In Java 8 the variables doesn't need to be declared final, but it needs to be "effectively final," which means that it is never changed.  (It is as though the compiler added the final modifier itself; this is similar to the type inference done by the Java 8 compiler.)

The reason for this restriction is that local variables have a lifetime (sometimes called "extent") that coincides with the lifetime of the method in which they are defined.  In other words, when the method returns, these variables are no longer accessible.  This is done so that the variables can be allocated on the stack rather than on the heap, avoiding the need for garbage-collecting them.  However, an object containing an inner method that refers to these variables may be used after the method that generated the object has already returned.  If (and only if) the variables are final is it possible to copy their values to the new object so that references to their values are still valid.  This is a poor-man's version of a closure, which is an object containing a function pointer together with all accessible variables in outer scopes.  As we will see in a later post, Scheme (like other dialects of Lisp) supports full closures, which also allow changing bound variables.

Unfortunately, the method above doesn't work in any language.  The problem is that the computational process oscillates between two values and doesn't converge (try it for x=2).  One value is too high, and the other is too low.  However, if we take their average, the process converges; the following implementations all compute the square root:

Scheme

(define (sqrt x) (fixed-point (lambda (y) (/ (+ y (/ x y)) 2.0) 1.0))

Java 7

public double sqrt(final double x) { return fixedpoint(new UFunc<Double, Double>() { @Override public Double apply(Double y) { return (y + x / y) / 2.0; } }, 1.0); }

Java 8

public double sqrt(double x) { return fixedpoint(y -> (y + x / y) / 2.0, 1.0); }

It turns out that this is a general technique, called average damping.  It takes any function f and returns the function λx.(x+f(x))/2; this function has exactly the same fixed points as f.  In certain cases, however, the computational process of the fixed-point function converges with the new function when it diverges on the original function.  This technique is easily specified as a program:

Scheme

(define (sqrt x)(define (average-damp f) (lambda (x) (average x (f x))))

Java 7

public UFunc<Double, Double> averageDamp(final UFunc<Double, Double> f) { return new UFunc<Double, Double>() { @Override public Double apply(Double x) { return (x + f.apply(x)) / 2.0; } }; }

Java 8

public DoubleUnaryOperator averageDamp(DoubleUnaryOperator f) { return x -> (x + f.applyAsDouble(x)) / 2.0; }

Again, the Java 7 version is obscured by the boilerplate code (not to mention the annoying repetitions of the template type).  Here is the definition of sqrt that uses average damping (this time I will spare you the agony of the Java 7 version):

Scheme

(define (sqrt x) (fixed-point (average-damp (lambda (y) (/ x y))) 1.0))

Java 8

public double sqrt(double x) { return fixedpoint(averageDamp(y -> x / y), 1.0); }

Computationally, this is exactly the same as the previous version, except that we use the original function  λy.x/y after applying the average damp operator to it.

In summary, it is possible to use functional abstraction in Java 7, but it is very painful.  The one case where it is widely used (although not usually thought of as such) is the case of callback functions, which are encapsulated as methods in one-method classes.  Java 8 makes higher-order functions much easier to use, even though the cumbersome type system is still annoying and gets in the way.

In subsequent posts we will see how to express the same ideas in other languages.

#functionalprogramming #java