Functional programming in Java: Architectural patterns

[Yago Segura]

This question is for Pierre-Yves Saumont and his book ' Functional Programming in Java: How functional techniques improve your Java programs. '

The book looks great . Functional programming is a topic I can't wait to read about . My question is ...

How deep the book exposes architectural topics ? How deep it talks about the functional point of view ?  

I mean , I think functional programming it's not only a matter of coding . You have to change your mind about lot of elements . There are lot of resources where you can find how to use a lambda or lazyness , but it's difficult to find places that talk about this change of point of view . Does the book shows elements of this aspect ?

Thanks in advance .

[Pierre-Yves Saumont]

Hi Yago,

Functional programming is not a bunch of coding techniques that can be applied to write better programs. Although it can be used this way, it is not functional programming. Most of the techniques described in the book could be (and some are) used to improve imperative programs.

But the book is not about learning such techniques as laziness, lambdas, recursion, corecursion, referential transparency, immutability, persistence, and the like. Of course, by reading the book you will learn how to use them. But these could apply to imperative programming as well. The most important part of the book is not about using these techniques, but about learning how to avoid using other techniques that are not compatible with functional programming. This means for example programming without using control structures. No loops, no branching, no try..catch, and so on. This implies thinking in a completely different way. This is what the book is about.

[Yago Segura]

wow ... nice . I've been playing with scala and his functional approach for some time . Indeed , I want to read the red book . As you are telling to me , I think your book is the one I'm looking for jeje . I  can't wait to start reading your book .

[Campbell Ritchie]

Have linked to this discussion here.

[Kent Bull]

Pierre-Yves Saumont wrote:

Functional programming is ...
The most important part of the book is not about using these techniques, but about learning how to avoid using other techniques that are not compatible with functional programming.
This means for example programming without using control structures. No loops, no branching, no try..catch, and so on. This implies thinking in a completely different way. This is what the book is about.

This seems very interesting to me. How could you program without control structures? Would a function abstract away the control structure? It seems like elimination of try..catch would end up being how a compiler does an AST transformation from try/catch to a continuation passing style.

[Pierre-Yves Saumont]

Programming without control structures is possible through implementing the same abstractions into functions. A good way to learn about functional programming is to try refactoring and imperative program in order not to use any control structures. Try with a simple loop. For example, try producing a list of integers from 0 to 10 while not using any loop. Try to do this in Java without using any of the following:

- loops

- if..then

- switch...case

- try..catch

- any member of the Stream package

- ternary operator (a.k.a Elvis, or ?:)

Ones you have done this, try to write a version capable of doing the same for integers from 0 to 1_000_000. (The fact that this is a somewhat different problem is an indication of how you can solve these problems.)

Tell me if you want more hints (or even the solution).

[Kent Bull]

I will try this and report back here.

[Kent Bull]

So I tried this and need more hints. I don't want the solution yet. The two solutions I came up with use loops and if conditions, things you said not to use.

Solution 1: First thing that came to mind:

        private static List<Integer> buildListLoop(Integer end) {
        int a = 0;
        List<Integer> resultingList = new ArrayList<>();
        while(a <= end) {
            resultingList.add(a);
            a++;
        }
        return resultingList;
    }

Problem: has a while loop


Solution 2: recursive solution

        private static List<Integer> buildListRecursive(List<Integer> lastList, Integer currentValue, Integer end) {

        if (currentValue.compareTo(end) > 0) {
            return lastList;
        }
        List<Integer> list = new ArrayList<Integer>();
        list.addAll(lastList);
        list.add(currentValue);
        return buildListRecursive(list, currentValue + 1, end);
    }

Problem: Has an if statement


Question: Does the final solution include recursion of some sort?

[Paul Clapham]

Here's a way of producing a list of integers from 0 to 10 without a loop or if-then:

public List<Integer> makeList() {
  private List<Integer> list = new ArrayList<>();
  list.add(0);
  list.add(1);
  list.add(2);
  list.add(3);
  list.add(4);
  list.add(5);
  list.add(6);
  list.add(7);
  list.add(8);
  list.add(9);
  list.add(10);
  return list;
}

Clearly as Pierre-Yves says, producing a list of integers from 0 to 1,000,000 is a different problem and my code can't be adapted to do that.

[Pierre-Yves Saumont]

@Paul

You're right, and I did not choose 1_000_000 at random. Using a sequence of add instructions is not only difficult for building a list of 1_000_000 elements. It would not be reusable. Would you need to build the list for any value between 0 and 1_000_000, you would have to write 1_000_000 different programs.

A possible solution would be producing a list of 1_000_000 elements instead of a list of n elements, and then using n as the index to the end of the list. But still, writing a program of one million lines is not possible. Or is it?

In fact, it is very easy. Simply use a program to write your program. After all, when using an editor to write code, you are using a program to write a program. This editor often has the capacity to generate code for you.

If your editor has not the capacity to generate this million of "add" instructions, why not writing your own program that will write this million of instructions. Once you have written this program (which is not the solution to the problem, so you can write it with whatever control structure you want), just write an interpreter to execute it and you're done:

    public static void main(String... args) {
        Runnable listProgram = generateListProgram(1_000_000);
        listProgram.run();
    }

    private static Runnable generateListProgram(int n) {
        Runnable r = () -> {};
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int x = i; // A trick to avoid closing over a mutable reference
            r = compose(r, () -> list.add(x));
        }
        return r;
    }

    private static Runnable compose(Runnable r1, Runnable r2) {
        return () -> {
            r1.run();
            r2.run();
        };
    }

The first line of the main method does not generate a list. It generates a program that generates a list. The generated program does not use any loop nor any conditional statement.

The second line of the main method runs this program. And it fails with a StackOverflowException although there is no recursive call. Would it work (we would need to configure the stack size much higher than the default value for this), it would not produce any usefull result. If you try the program for a list of 1_000 elements, it works fine, building the list. But you don't have any mean to use it. This can be solved by using Callable instead of Runnable:

    public static void main(String... args) throws Exception {
        Callable<List<Integer>> listProgram = generateListProgram(1000);
        System.out.println(listProgram.call());
    }

    private static Callable<List<Integer>> generateListProgram(int n) {
        List<Integer> list = new ArrayList<>();
        Callable<List<Integer>> c = () -> list;
        for (int i = 0; i < n; i++) {
            c = add(c, i);
        }
        return c;
    }

    private static Callable<List<Integer>> add(Callable<List<Integer>> c, int i) {
        return () -> {
            List<Integer> list = c.call();
            list.add(i);
            return list;
        };
    }

This now works for n = 1_000, but still not for n = 1_000_000.

Although it might seem nonsense to some, this is actually how functional handling of effects, I/O and state mutation may be handled in functional programming. This example is not the solution to the original problem, but it shows something very important: There is no way to really avoid control structures. All we can do is hide control structures by taking them out of our programs and putting them somewhere else. Here, it is in the program generating the program (and still it is not enough). But it could be in the compiler. Unfortunately, the Java compiler is not able to do it autimatically for us. There is however a mean to push the limit so that it would be possible to generate a list of 1_000_000. But it would not work for 1_000_000_000. Or it could work, with addtional complexity, but it would not work for very large numbers.  But it could be make to work with 2_147_483_647, which is the maximum int value in Java.

[Pierre-Yves Saumont]

@Kent

You got the most important part of the solution, although it's not recursion, but corecursion. Here is an example showing the difference:

    public static void main(String... args) {
        System.out.println(buildListRecursive(new ArrayList<>(), 10, 0));
        System.out.println(buildListCorecursive(new ArrayList<>(), 0, 10));
    }

    private static List<Integer> buildListRecursive(List<Integer> lastList, int currentValue, int end) {
        if (currentValue < end) {
            return lastList;
        } else {
            List<Integer> list = buildListRecursive(lastList, currentValue - 1, end);
            list.add(currentValue);
            return list;
        }
    }

    private static List<Integer> buildListCorecursive(List<Integer> lastList, int currentValue, int end) {

        if (currentValue > end) {
            return lastList;
        } else {
            List<Integer> list = new ArrayList<>();
            list.addAll(lastList);
            list.add(currentValue);
            return buildListCorecursive(list, currentValue + 1, end);
        }
    }

Both solutions use a "recursive" call, meaning a method calling itself, but not both represent a recursive process. A recursive process is a process calling itself as part of a computation. This is obviously the case with the buildListRecursive method. On contrary, it's not the case with the buildListCorecursive method since when the "recursive" call is done, the computation (inside the method) is finished. This is what is called "tail recursion", although it is actually corecursion. The "recursive call is what is called a "tail call".

Modern compilers (I am using the term "modern" as a euphemism.) do "Tail Call Elimination" (TCE) consisting in replacing the tail call with a loop. With such a compiler, your solution would work. Unfortunately, it does not work in Java. As I said in my answer to Paul, hiding the loop somewhere else (in the compiler when using TCE) is a solution. Another would be using the solution I describe in my book (chapter 4, available as a free download on Manning site). This solution allows implementing TCE on the heap instead of on the stack. It is, however, a trick in the sense that it uses a loop inside. So, it is pushing the loop out of view, in a library.

But there is another solution for solving the stack overflow problem that would result both from the recursive and corecursive solutions, you have to find a trick that will limit the number of recursive steps to an acceptable value (let's say around 3_000 in Java, but YMMV). Beware that it is not a solution that would be helpful in any production code. In real life, you would either use a language with TCE, of the library solution described in my book or do the TCE by hand, which means be using a loop. But as a puzzle, I think it's interesting to search for the solution.

Regarding the use of if..else, it is a totally different trick, just for added fun. Also not something you could use in a real solution to this problem. However, it's also fun to search for it. Think about laziness, and especially operator laziness.