This is the fourth and last part in a series of posts introducing functional concepts to OO/Java developers. The first three parts introduced visitors, functional data types, and increasingly sophisticated and powerful continuations. We have used a running example of expression evaluation to illustrate the concepts.

In the previous part we set up our expression language with a JIT compiler and looked at various ways to extend the language, either by adding syntactic sugar as the language implementer, or as the developer after we added named functions. At the very end, we discovered that our implementation could not handle recursion. Our language as it is now does not stand to gain anything from recursion since right now, we do not have a way to terminate the recursion.

Let’s therefore first add a way to make our language able to terminate the recursion by implementing conditional expressions. After that, we fix our implementation of functions to also accommodate recursive functions by leveraging Java fixpoints. Finally, we finish up this series by taking a look at some common functional concepts that are part of the basic functional programming vocabulary but is not really necessary for OO/Java developers.

## Conditional Expressions (and Exception Handling)

Adding conditionals is a matter of adding a new expression node, a new visitor interface, and an implementation of our IntegerAlgebra:

class ConditionalExpression<T> extends Expression<T> { Expression<T> test; Expression<T> yes; Expression<T> no; public ConditionalExpression(Expression<T> test, Expression<T> yes, Expression<T> no) { this.test = test; this.yes = yes; this.no = no; } public <V> V visit(ConditionalExpressionVisitor<T, V> visitor) { return visitor.visit(this, test.visit(visitor), yes.visit(visitor), no.visit(visitor)); } @Override public <V> V visit(SimpleExpressionVisitor<T, V> visitor) { if (visitor instanceof ConditionalExpressionVisitor<?, ?>) { return visit((ConditionalExpressionVisitor<T, V>) visitor); } throw new IllegalArgumentException(); } } interface ConditionalExpressionVisitor<T, V> extends ExpressionVisitor<T, V> { V visit(ConditionalExpression<T> conditional, V test, V yes, V no); } class ConditionalIntegerAlgebra extends FancyIntegerAlgebra implements ConditionalExpressionVisitor<Integer, Function<Function<String, Integer>, Integer>> { @Override public Function<Function<String, Integer>, Integer> visit(ConditionalExpression<Integer> conditional, Function<Function<String, Integer>, Integer> test, Function<Function<String, Integer>, Integer> yes, Function<Function<String, Integer>, Integer> no) { return env -> test.apply(env) > 0 ? yes.apply(env) : no.apply(env); } }

For simplicity, we have temporarily shed the function types and just build atop the basic expression type. A conditional expression has a test and two expressions, one to return when the test evaluates to true (the “then” part, called “yes” to avoid keywords) and one when it evaluated to false (the “else” part, called “no” to avoid keywords). As our language does not have booleans, our test expression is an integer, and we consider it “true” if it is greater than zero and false if it is zero or negative. We could also have considered it true if it was equal to zero or any other comparison with a fixed integer.

Exercise: Why can we arbitrarily just check for positivity?

We can relatively easily translate between various different notions of “true”. For example, we can check “a = 0” using “not(a > 0)” and “a+1 > 0”. The second is easy to implement using our expressions, and the first can be implemented by checking “(-1 * a) + 1 > 0”, all of which are supported by our language. We can check “e1 and e2” using that “e1 && e2 ? yes : no” is equivalent to e1 ? (e2 ? yes : no) : no. As an example, here’s an expression that returns 0 if p is zero and 1 otherwise:

Expression<Integer> equals = new ConditionalExpression<>(new Plus<>(new Variable<>("p"), new Constant<>(1)), new ConditionalExpression<>( new Plus<>(new Times<>(new Constant<>(-1), new Variable<>("p")), new Constant<>(1)), new Constant<>(0), new Constant<>(1)), new Constant<>(1)); Function<Function<String, Integer>, Integer> evaluation = equals.visit(new ConditionalIntegerAlgebra()); System.out.println(evaluation.apply(FunctionMap.put(FunctionMap.empty(), "p", -2))); System.out.println(evaluation.apply(FunctionMap.put(FunctionMap.empty(), "p", -1))); System.out.println(evaluation.apply(FunctionMap.put(FunctionMap.empty(), "p", 0))); System.out.println(evaluation.apply(FunctionMap.put(FunctionMap.empty(), "p", 1))); System.out.println(evaluation.apply(FunctionMap.put(FunctionMap.empty(), "p", 2)));

Exercise: state in your own words what the expression does.

It computes this Java function:

public static int evaluation(int p) { return p * p > 10 ? p + 3 : p * 2; }

If we switch on the logging of the JIT compilation (visit) and execution (evaluate), we see that we visit all the nodes, but we only evaluate the relevant ones. That is, we really have branching code: the rejected path is never evaluated.

Optional exercise: extend the language with a conditional that uses equality using desugaring.

Exercise: consider how to implement other comparisons like not, or, <, >=, <=.

Exercise: extend the language with exceptions.

You want to extend the language with two expressions, one for raising/throwing an exception and one for handling/catching the exception.

You can either make the raise/throw operation take no parameter or take an expression parameter. If you use no parameter, handle/catch will handle every exception, otherwise it too can take an expression and only handle expressions with a given value. The first is simpler but the latter a bit more generic.

Exceptions clearly have something in common with our conditional expressions and functions. Consider making our evaluation take two parameters: an environment and an exception handler.

## Recursive Functions

If we revisit the cliff-hanger from part 3:

FunctionDefinition<Integer> recursiveFunctionExpression = new FunctionDefinition<>("factorial", new Times<>(new Variable<>("p"), new FunctionApplication<>("factorial", new Plus<>(new Variable<>("p"), new Constant<>(-1)))), new FunctionApplication<>("factorial", new Constant<>(5))); assertThrows(IllegalArgumentException.class, () -> recursiveFunctionExpression.visit(new BetterFunctionIntegerAlgebra()).apply(FunctionMap.empty()));

it should be reasonably clear that we get an exception when trying to compile the function factorial. The exception is raised in this bit of code of the BetterfunctionIntegerAlgebra:

@Override public Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> visit( FunctionDefinition<Integer> functionDefinition, String name, Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> body, Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> next) { return fenv -> { Function<Function<String, Integer>, Integer> b = body.apply(fenv); return next.apply(FunctionMap.put(fenv, name, b)); }; } @Override public Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> visit( FunctionApplication<Integer> functionApplication, String name, Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> parameter) { return fenv -> { Function<Function<String, Integer>, Integer> f = fenv.apply(name); Function<Function<String, Integer>, Integer> p = parameter.apply(fenv); return env -> { return f.apply(FunctionMap.put(env, "p", p.apply(env))); }; }; } }

The problematic bit is the combination of lines 7 and 17; when we are compiling the factorial function (l. 17), we do so in the environment before factorial is defined (l. 6). Recursion in our expression language fails for the same reason as “int a = a + 1” fails in Java.

This is a bit more complex to resolve that we might at first think. The compilation of the factorial functions depends on the function environment and we’d like to store the compiled function in the function environment we give to the compilation of the function. It seems like a catch-22. In order to resolve this, we need to be able to compile the function without the function environment and look up the function on runtime instead.

To realize this, we can instead look at the simpler FunctionIntegerAlgebra from part 3. In this visitor, we just have a simple continuation taking a function environment and a variable environment, returning a result directly. The problem is that this visitor stores raw expressions in the function environment, where we would like to store compiled functions instead.

This leads to a bit of a puzzle: what is the type of a compiled function? The answer is that is does not have a Java type! But the good news is, this is not actually a problem. If we just assume that the type of a compiled function is F. Then our function environment is Function<String, F>. We also know that our compiled functions need to take a variable environment and a function environment and return an integer. They must therefore have the type BiFunction<Function<String, Integer>, Function<String, F>, Integer>. Thus, F is a recursive type that refers to itself, which is not possible as a definite type: it would result in an infinite nesting of Fs.

This is where Java’s fixpoint system comes into play. You are likely familiar with how a List<T> can contain any element T. You may also be familiar with the list’s addAll, which takes a Collection<? extends T>, which means any collection containing subclasses of T are allowed. If you have dug really deep into Java’s standard library, you may have noticed the rather odd definition of the base class for all enumerations:

public abstract class Enum<E extends Enum<E>> implements Comparable<E>, Serializable {

The Enum is parametrized with a type E, which must extend Enum parametrized with itself. Concrete enums can then implement this as:

public class MyEnum extends Enum<MyEnum> {

This construct makes it possible for the abstract enum class to implement compareTo in a way so that it is not allowed to do something like:

public class MyOtherEnum extends Enum<MyOtherEnum> { ... } MyEnum a = new MyEnum(); MyOtherEnum b = new MyOtherEnum() a.compareTo(b); // Type error

The type of E in enum is also a weird recursive thing: it refers to itself. We can use this to implement recursive functions like this:

class RecursiveFunctionIntegerAlgebra<F extends BiFunction<Function<String, Integer>, Function<String, F>, Integer>> implements FunctionExpressionVisitor<Integer, F>, ConditionalExpressionVisitor<Integer, F> { @SuppressWarnings("unchecked") private F cast(BiFunction<Function<String, Integer>, Function<String, F>, Integer> value) { return (F) value; } @Override public F visit(Constant<Integer> constant, Integer value) { return cast((env, fenv) -> value); } @Override public F visit(Plus<Integer> plus, F left, F right) { return cast((env, fenv) -> left.apply(env, fenv) + right.apply(env, fenv)); } @Override public F visit(Times<Integer> times, F left, F right) { return cast((env, fenv) -> left.apply(env, fenv) * right.apply(env, fenv)); } @Override public F visit(Variable<Integer> variable, String name) { return cast((env, fenv) -> env.apply(name)); } @Override public F visit(Assignment<Integer> assignment, String name, F value, F next) { return cast((env, fenv) -> next.apply(FunctionMap.put(env, name, value.apply(env, fenv)), fenv)); } @Override public F visit(FunctionDefinition<Integer> functionDefinition, String name, F body, F next) { return cast((env, fenv) -> next.apply(env, FunctionMap.put(fenv, name, body))); } @Override public F visit(FunctionApplication<Integer> functionApplication, String name, F parameter) { return cast( (env, fenv) -> fenv.apply(name).apply(FunctionMap.put(env, "p", parameter.apply(env, fenv)), fenv)); } @Override public F visit(ConditionalExpression<Integer> conditional, F test, F yes, F no) { return cast((env, fenv) -> test.apply(env, fenv) > 0 ? yes.apply(env, fenv) : no.apply(env, fenv)); } }

This new visitor is parametrized with a type F representing a compiled function. A compiled function must extend the BiFunction from before, and implement the visitor interface for both functions and conditionals. This is because the two functions are implemented independently, illustrating that we can make two independent language extensions and construct a single language supporting both features.

The cast method is there to make things simpler syntactically. The technical reason is that we can only use the anonymous function syntax for things with an @FunctionalInterface annotation, and since F is a type parameter, we cannot guarantee this. BiFunction does have this annotation, so by making an unchecked cast we are allowed to use the simpler syntax.

Most of the visitor should be second nature by now. The only intricacies are in the function handling, where we define a function by adding it to the function environment. As the passed function has type F, our compiled function type, we can just directly add it to the function environment (l. 35). This is different from the FunctionIntegerAlgebra, which instead added the uncompiled expression to the function environment (l. 55) and the BetterFunctionIntegerAlgebra, which compiled the function using the original environment (l. 67) and added the result to the function environment (l. 68). Usage of the function is also pretty simple. Now, we look up the compiled function and evaluate it using the passed function environment (l. 41).

Now, we run in to a problem when using the visitor: we need to pass it a type parameter, but there is no Java type that matches F.

Exercise: how to we properly instantiate our visitor?

Try as you might, but the diamond operator (new RecursiveFunctionIntegerAlgebra<>()) and “var” will not help you here.

The solution is to use another little-known feature of Java: methods with type parameters. Just like classes can have type parameters, so can methods. Such type parameters can also make use of fixpoints, and most important do not have to be passed as an input parameter. This allows us to use our new function expressions like this:

<F extends BiFunction<Function<String, Integer>, Function<String, F>, Integer>> void testRecursiveFunctionEvaluation() { FunctionDefinition<Integer> functionExpression = new FunctionDefinition<>("square", new Times<>(new Variable<>("p"), new Variable<>("p")), new FunctionApplication<>("square", new Constant<>(5))); F continuation = functionExpression.visit(new RecursiveFunctionIntegerAlgebra<F>()); System.out.println(continuation.apply(FunctionMap.empty(), FunctionMap.empty())); FunctionDefinition<Integer> nestedFunctionExpression = new FunctionDefinition<>("square", new Times<>(new Variable<>("p"), new Variable<>("p")), new FunctionApplication<>("square", new FunctionApplication<>("square", new Constant<>(5)))); continuation = nestedFunctionExpression.visit(new RecursiveFunctionIntegerAlgebra<F>()); System.out.println(continuation.apply(FunctionMap.empty(), FunctionMap.empty())); FunctionDefinition<Integer> recursiveFunctionExpression = new FunctionDefinition<>("factorial", new Times<>(new Variable<>("p"), new FunctionApplication<>("factorial", new Plus<>(new Variable<>("p"), new Constant<>(-1)))), new FunctionApplication<>("factorial", new Constant<>(5))); F failingContinuation = recursiveFunctionExpression.visit(new RecursiveFunctionIntegerAlgebra<F>()); assertThrows(StackOverflowError.class, () -> failingContinuation.apply(FunctionMap.empty(), FunctionMap.empty())); FunctionDefinition<Integer> fixedRecursiveFunctionExpression = new FunctionDefinition<>("factorial", new ConditionalExpression<>(new Variable<>("p"), new Times<>(new Variable<>("p"), new FunctionApplication<>("factorial", new Plus<>(new Variable<>("p"), new Constant<>(-1)))), new Constant<>(1)), new FunctionApplication<>("factorial", new Constant<>(5))); continuation = fixedRecursiveFunctionExpression.visit(new RecursiveFunctionIntegerAlgebra<F>()); System.out.println(continuation.apply(FunctionMap.empty(), FunctionMap.empty())); }

Our function defined a type parameter F with the same bounds as in the visitor. We can now instantiate our visitor using this new type. The two evaluations of square return the same as before. The evaluation of our first attempt of a factorial function still fails, but this time with a StackOverflowError instead of an IllegalArgumentException. This is because we never terminate the recursion, so at some point Java’s stack will run full and raise the error. A fixed version of the factorial function leveraging our conditional expressions return the expected result.

Exercise: our improved factorial function returns correct results for positive parameters, but fails for negative values. Try extending the function using the exceptions you implemented earlier to raise and handle an exception when called with a negative value.

Exercise: our language supports nested functions, and can even handle nesting functions with the same name inside each other. Consider whether the behavior is always as you would expect when combining these two features.

Exercise: some languages require developers to explicitly specify whether a function can make use of recursion. Consider why that might be.

Try comparing the performance of a function calling other functions (but never itself) using the two implementations BetterFunctionIntegerAlgebra and RecusiveFunctionIntegerAlgebra. You willl need a lot of function invocations, preferably many different functions as well, to really see the difference.

## Accumulators

In this series, we have dived almost directly into continuations. Typically, functional programmers are taught about accumulators first, however. Accumulators are not really needed when you have continuations, but are quite a bit simpler. I did it differently here, because accumulators have limited usefulness in Java as they really solve problems you rarely see in Java.

The first problem accumulators solve is dealing with functional datatypes. Assume we have implemented functional lists like in part 2. We can easily construct a function returning a new list with all values doubled:

public static FunctionalList<Integer> times2(FunctionalList<Integer> list) { try { Pair<FunctionalList<Integer>, Integer> parts = FunctionList.remove(list); return FunctionList.add(times2(parts.getA()), 2 * parts.getB()); } catch (IllegalArgumentException e) { return FunctionList.empty(); } } @Test void testDouble() { FunctionalList<Integer> list = FunctionList.add(FunctionList.add(FunctionList.add(FunctionList.empty(), 3), 2), 1); assertEquals(1, FunctionList.remove(list).getB()); assertEquals(2, FunctionList.remove(FunctionList.remove(list).getA()).getB()); assertEquals(3, FunctionList.remove(FunctionList.remove(FunctionList.remove(list).getA()).getA()).getB()); FunctionalList<Integer> doubled = times2(list); assertEquals(2, FunctionList.remove(doubled).getB()); assertEquals(4, FunctionList.remove(FunctionList.remove(doubled).getA()).getB()); assertEquals(6, FunctionList.remove(FunctionList.remove(FunctionList.remove(doubled).getA()).getA()).getB()); }

We simply simply up the list and return a list, calling recursively. A very reasonable thing we might wish to do is to reverse the list. This is more complicated, though, as our list only supports inserting new things at the beginning. Using an accumulator, we are in luck though:

public static <T> FunctionalList<T> reverse(FunctionalList<T> list, FunctionalList<T> accumulator) { try { Pair<FunctionalList<T>, T> parts = FunctionList.remove(list); return reverse(parts.getA(), FunctionList.add(accumulator, parts.getB())); } catch (IllegalArgumentException e) { return accumulator; } } @Test void testReverse() { FunctionalList<Integer> list = FunctionList.add(FunctionList.add(FunctionList.add(FunctionList.empty(), 3), 2), 1); assertEquals(1, FunctionList.remove(list).getB()); assertEquals(2, FunctionList.remove(FunctionList.remove(list).getA()).getB()); assertEquals(3, FunctionList.remove(FunctionList.remove(FunctionList.remove(list).getA()).getA()).getB()); FunctionalList<Integer> reversed = reverse(list, FunctionList.empty()); assertEquals(3, FunctionList.remove(reversed).getB()); assertEquals(2, FunctionList.remove(FunctionList.remove(reversed).getA()).getB()); assertEquals(1, FunctionList.remove(FunctionList.remove(FunctionList.remove(reversed).getA()).getA()).getB()); }

Here, instead building up a new result after calling recursively, we instead pass an accumulator in which we accumulate the result, and at the end we return the accumulator instead of an empty list. This way, we build up the accumulator on the way “down” the recursion instead of on the way back “up,” leading to a properly reversed list.

This is less important in Java, where we can typically insert at both ends of a list, but still have some niche uses. For example, it is much more efficient to insert at the end of an ArrayList than at the beginning, so if we wish to avoid calling Collections.reverse at the end on a list, we can use an accumulator. It can also be useful if we traverse a more complex structure, e.g., something like our Expression tree, and which to accumulate all/some nodes in a list. Some uses of visitors also resemble the use of accumulators, where we pass already visited values to the visit methods.

## Tail Recursion

The one use of accumulators is to handle some function data types more efficiently. The other use is to make functions tail recursive. Consider the below implementation of the factorial function in Java:

public static int factorial(int n) { if (n < 1) { return 1; } return n * factorial(n - 1); }

This function is perfectly workable and obviously correct. Now, consider this alternative implementation where we introduce an accumulator:

public static int factorial(int n, int a) { if (n < 1) { return a; } return factorial(n - 1, n * a); }

This function is a little less obvious, but a quick test reveals it works the same as the original function:

System.out.println(factorial(5)); System.out.println(factorial(5, 1));

Both return 120 as we would expect, so why would we even consider the two-parameter version? The two parameter version has a very nice property: it is tail recursive. This just means that the last thing we do in the function is call recursively. In the one parameter version, disregarding the conditional, we first call recursively and then multiply the result by n before returning.

When a function is tail recursive, it is very easy to translate it to a function that does not use recursion. Consider this third implementation:

public static int factorialLoop(int n, int a) { while (true) { if (n < 1) { return a; } int newN = n - 1; int newA = n * a; n = newN; a = newA; } }

Sure, this version looks even worse than the second version, and is indeed not very natural Java code, but it is easy to see how we can automatically get from the second version to this version. We put the entire function body in a while true loop. We then replace the recursive call with just updating the parameter values, introducing new temporary variables to ensure that we don’t accidentally use the wrong value for n in the computation of the new value of a.

For a function this simple, this serves little purpose, but consider the below code:

FunctionalList<Integer> list = FunctionList.empty(); for (int i = 0; i < 10000; i++) { list = FunctionList.add(list, i); } FunctionalList<Integer> l = list; assertThrows(StackOverflowError.class, () -> times2(l)); assertThrows(StackOverflowError.class, () -> reverse(l, FunctionList.empty()));

In Java, both the functions raise a stack overflow error when executed because Java does not to tail recursion optimization. Java does not do that because it is rarely needed, but in functional languages with functional data types, recursion is the only way to handle traversal of large lists, so they will typically internally convert the reverse function to something like:

public static <T> FunctionalList<T> reverseLoop(FunctionalList<T> list, FunctionalList<T> accumulator) { try { while (true) { Pair<FunctionalList<T>, T> parts = FunctionList.remove(list); FunctionalList<T> newList = parts.getA(); FunctionalList<T> newAccumulator = FunctionList.add(accumulator, parts.getB()); list = newList; accumulator = newAccumulator; } } catch (IllegalArgumentException e) { return accumulator; } }

This version works identically to the original, but can also handle large lists.

Exercise: try making a tail recursive version of times2. Make sure it works the same as the original. Then translate it to a while true loop using a construction like the one seen for reverse and factorial. Test it with a list of length 10000.

Consider building up the result backwards and then reversing the result.

Advanced exercise: try implementing tail recursion optimization in our little expression language.

## Conclusion

This brings us to the end of this little series on functional programming. We started out by introducing the visitor pattern and showing how continuations can help us implement some functions more efficiently and used that to evaluate simple expressions over integers. We then looked a functional data structures and how thinking functionally can help us write clearer code without having to worry about locking in case of concurrency. We used that to extend our expression language with variables. We then took a quick look at how (functional!) tree transformations makes it easy to add convenience to our expression language. We saw how continuations can be considered JIT compiling our expressions, allowing us to compile them once and execute them multiple times with different parameters, and then took the full step to introduce named functions. We then showed how we can have branching code paths, directly using conditionals and hinted using exceptions. We used this to finally implement recursive functions by leveraging Java’s fixpoint types. Finally, we looked at how accumulators and tail recursion can be used to optimize execution of functional code.

All the code examples along with sufficient boilerplate to make it all run can be found in this file:

The file is self-contained and only depends on JUnit Jupiter. I recommend executing each test one by one. The code is roughly in the order it has been presented throughout the series.

While the series has used expressions to illustrate the concepts, it should hopefully be clear that many data models can benefit greatly from being treated as functional. If you’re using Lombok, I recommend not using the @Data annotation, but instead using @SuperBuilder(toBuilder = true) and @Getter (without @Setter). That way, you get nice immutable classes that can be constructed using a builder and converted back to a builder for construction of new objects. If you additionally add a visitor to your hierarchy, you have a very powerful way of considering the entire data structure and make computations or transforming the data structure, whether to different versions of itself or entirely different data structures.

Both continuations and accumulators allow you to reverse the order of a traversal. When implementing a visitor, you have to pick whether you wish to visit your root nodes before children, after children, or between children, but using a continuation we can change the order we traverse things given a simple traversal where we visit the root after the children (check how all visitors in the entire series traverse children and how the evaluations are almost entirely independent of that). Accumulators allow us to do the same but in a much more restricted sense.

A lot of the concepts are also useful when dealing with streams and asynchronous programming: always create new objects and leave threading to somebody else (by using parallelStream you can execute your stream processing in parallel because streams are inherently functional). Many stream operations can be thought of as implementing visitors (e.g., map), and many famous frameworks, especially MapReduce, are literally just a repackaging of a visitor and a generalized version of the times2 function we made above to leverage functional programming to allow parallel processing of large amounts of data.

Time person of the year 2006, Nobel Peace Prize winner 2012.