Lessons in Abstraction: What FP Can Teach OOP

Abstraction is one of the greatest visionary tools ever invented by human beings to imagine, decipher, and depict the world. – Jerry Saltz

I wish to approach truth as closely as is possible, and therefore I abstract everything until I arrive at the fundamental quality of objects. ― Piet Mondrian

One of the most advocated “best practices” in programming is the DRY principle: Don’t Repeat Yourself. Many techniques can be used to enforce this principle: encapsulation, parameterization, inversion of control, and many more. One of these techniques is abstraction and one main difference between functional programming (FP) and object-oriented programming (OOP) is the way abstraction is applied. A common practice in OOP is to limit abstraction to the strict useful minimum for the problem at hand. In OOP, premature abstraction is often considered a fault, much as premature optimization.

In FP, on the other hand, abstraction is generally pushed as far as possible. Every problem is broken into a series of the simplest possible functions, which are then composed to build the problem solution. Identifying these abstractions is generally the most important part of problem resolution. In fact, FP programmers often spend more time trying to find what problem they should solve than solving them. And of course, it generally appears that these functions are the same from one problem to the next. Only the way they are composed is different. This is the reason why abstraction is one of the most valued techniques used by FP programmers.

In this article, we will compare how OOP and FP would handle abstraction in a specific simple problem: computing the sum of integers between 1 and an arbitrary value n. The problem is so simple to solve using imperative programming that it seems there is nothing interesting to learn from it. Here is how it could be done in imperative Java:

static int sum(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

It seems that there is no simpler and more efficient way to do it. However, for an OOP programmer as well as for an FP programmer, the interesting part of the problem is still to come. But each of these programmer will probably go a very different route. We could also notice (and demonstrate!) that the sum of the n first integers is equals to (n * (n + 1) / 2). As you will see, this would be going the other way, towards the least possible abstraction.

Abstracting the Computation in Object Oriented Programming

Both FP and OOP programmers will immediately remark one possible abstraction, which is the operation that is applied to construct the result. Here, we are adding values to construct the result. What if we were asked to return the product instead of the sum?

In OOP, there are two obvious way to abstract the computation: using the strategy pattern, or inversion of control (IoC).

Using the Strategy Pattern

The Java way to abstract a computation in a form that can be handed to a program is to create an object containing the methods performing the computation. (If you’re lucky and there is just one method, lambda expressions can make this simpler but the approach remains the same.) For this to be an abstraction, we have to make the abstract part into an interface and the concrete part into an implementation:

static int compute(int n, Computer computer) {
    int result = computer.identity();
    for (int i = 1; i <= n; i++) {
        result = computer.compute(result, i);
    }
    return result;
}

interface Computer {

    int compute(int a, int b);

    int identity();

}

static class Adder implements Computer {

    @Override
    public int compute(int a, int b) {
        return a + b;
    }

    @Override
    public int identity() {
        return 0;
    }

}

static class Multiplier implements Computer {

    @Override
    public int compute(int a, int b) {
        return a * b;
    }

    @Override
    public int identity() {
        return 1;
    }

}

public static void main(String... args) {
    System.out.println(compute(5, new Adder()));
    System.out.println(compute(5, new Multiplier()));
}

Here, we have abstracted the computation and are now able to reuse the program with a different computation strategy, such as the multiplication. Note that we put the identity element, used as the start value for the computation, into the various Computer implementations, since it will be different for different types of computations (0 for addition, 1 for multiplication).

Frankly, it does not seem like a great improvement, and many programmers would not see the interest of decoupling the computation from the iteration. Furthermore, this approach does not take into account that we have in fact two nested possible abstractions: The operation itself (addition or multiplication) and the identity concept of a specific value that is paired with an operation and does not change the value to witch it is associated through this operation. The value 0 is the identity for addition, and 1 is the identity for multiplication. Many other operations have an identity value. The empty string is the identity for string concatenation, and the empty list is the identity for list concatenation.

We could of course use the Strategy pattern again for the identity, but this would create a really messy solution, and most programmers would probably think that using an interface with two methods is enough abstraction. As you will later see, FP programmers do not think this way.

Using Inversion of Control (IoC)

Another more object oriented technique for abstracting the computation is called inversion of control. The strategy pattern solution uses composition to solve the problem whereas inversion of control is based upon inheritance.

With this technique, we construct an abstract class that performs the loop, calling an abstract method to get the start value and another one to do the computation:

static abstract class Computer {

    public final int compute(int n) {
        int result = identity();
        for (int i = 1; i <= n; i++) {
            result = doCompute(result, i);
        }
        return result;
    }

    abstract int doCompute(int a, int b);

    abstract int identity();

}

static class Adder extends Computer {

    @Override
    public int doCompute(int a, int b) {
        return a + b;
    }

    @Override
    int identity() {
        return 0;
    }
}

static class Multiplier extends Computer {

    @Override
    public int doCompute(int a, int b) {
        return a * b;
    }

    @Override
    int identity() {
        return 1;
    }
}

public static void main(String... args) {
    Computer adder = new Adder();
    System.out.println(adder.compute(5));
    Computer multiplier = new Multiplier();
    System.out.println(multiplier.compute(5));
}

This approach is probably the most object oriented one, and it might seem much cleaner than the strategy pattern because it seemingly also abstracts the iteration into the Computer class. (By the way, this specific use of IoC has been given a specific name: the template method pattern.) But in fact, we did not abstract the iteration! We just encapsulated the whole program in the computer class. Let’s now see how a functional programmer would handle the problem.

Abstracting in Functional Programming

We are now going to see how a functional programmer would handle the problem of abstraction. Abstracting the computation is no different, in principle, from what we did with the strategy pattern. Functional programming however, pushes abstraction further.

Abstracting Computation

In FP, the actual computation would be abstracted in a very similar way to what we did with the strategy pattern. Again we create a Computer interface:

@FunctionalInterface
interface Computer {

    int compute(int a, int b);

}

But this time Computer is a functional interface, which more or less means that it has only a single abstract method. That’s why it’s sometimes referred to as a SAM interface. In Java, it’s called a functional interface, because it can be used to represent a function.

Since we are using Java 8, the Computer interface is not needed because it can be replaced with an IntBinaryOperator, which also maps two ints to an int:

static int compute(int n, int identity, IntBinaryOperator computer) {
    int result = identity;
    for (int i = 1; i <= n; i++) {
        result = computer.applyAsInt(result, i);
    }
    return result;
}

If we are using a language with lambdas, as is the case of Java 8, we don’t need to create classes that implement IntBinaryOperator:

public static void main(String... args) {
    System.out.println(compute(5, 0, (a, b) -> a + b));
    System.out.println(compute(5, 1, (a, b) -> a * b));
}

Abstracting the Creation of a Collection

A functional programmer would immediately notice that we are indeed creating a collection of integers from 1 to n, and applying a computation successively to the current result and each element, starting with the seed. The creation of the collection could be abstracted into a method:

static int[] range(int n) {
    int[] result = new int[n];
    for (int i = 0; i < n; i++) {
        result[i] = i + 1;
    }
    return result;
}

Abstracting Iteration

The iteration applying the computation could also be abstracted into a method:

static int fold(int[] collection, int identity, IntBinaryOperator computer) {
    int result = identity;
    for(int i : collection) {
        result = computer.applyAsInt(result, i);
    }
    return result;
}

If we put these abstractions in a library, our program becomes as simple as:

static int compute(int n, int identity, IntBinaryOperator computer) {
    return fold(range(n), identity, computer);
}

public static void main(String... args) {
    System.out.println(compute(5, 0, (a, b) -> a + b));
    System.out.println(compute(5, 1, (a, b) -> a * b));
}

By the way, these abstractions we have put in a separate library are redundant, since Java 8 already has them, although with slight differences:

• The range method can be replaced with IntStream::range, which takes two parameters, start and end value, and produces an IntStream instead of an array.
• The fold abstraction is called reduce.

The resulting program is then as simple as:

public static void main(String... args) {
    System.out.println(IntStream.rangeClosed(1, 5).reduce(0, (a, b) -> a + b));
    System.out.println(IntStream.rangeClosed(1, 5).reduce(1, (a, b) -> a * b));
}

Don’t you think the IoC example was simpler? (Just kidding.)

Applying Abstraction to More Complex Problems

The previous example was simple, because all used abstractions were already provided by Java 8.

But be aware that we have not pushed abstraction to the limit yet! We could have abstracted the int type. After all, we might want to apply the same computation to other types, such as double, or BigDecimal, or even String, or List. We could also have used a computation producing a result of a different type than the collection elements. For example, we could have applied to a list of characters an operation consisting in adding each character to a starting String (which, incidentally, might or not be empty).

Instead of going there, let’s instead look at a more complex example. We will start with a very specific computation and will abstract things as far as we can.

The Initial Problem

The initial problem is to compute a list of the intermediate results of the previous problem. Considering the sum of the integers from 1 to n, we now want to produce a list of the intermediate results of this computation. For example, if n = 5, we want to obtain the list 1, 3, 6, 10, 15.

These numbers are called triangular numbers but for our example, all you need to know about is how to compute them: by summing all integers that are lower or equal to the considered one. The five first triangular numbers are then:

1
1 + 2 = 3
1 + 2 + 3 = 6
1 + 2 + 3 + 4 = 10
1 + 2 + 3 + 4 + 5 = 15

A trivial implementation of a program computing triangular numbers could be:

private static List<Integer> triangular(int length) {
    List<Integer> result = new ArrayList<>();
    for(int i = 1; i <= length; i++) { // <1>
        result.add(result.size() == 0
                ? i
                : result.get(result.size() - 1) + i); // <2>
    }
    return result;
}

public static void main(String... args) {
    System.out.println(triangular(5));
}

We can see that in <1>, we are creating a list of the integers between 1 and n, inclusive. In <2>, we are using result.get(result.size() - 1) to get the last element of the list. As a first abstraction, we should either move this part into a method or use a collection offering this functionality.

Abstracting Collection Handling

Let’s start by creating the last operation for List. The problem we have is that although in this specific example the list is never empty when the last element is accessed (since we check that the size is not 0), this case can occur in the abstraction. In case of an empty list, we don’t know what to do. Only the callers of the abstracted method know, so we just have to let them tell us what to do. Here, we will offer the possibility to pass a default value.

But we will push the abstraction further. There is no reason to limit ourselves to lists of integers, so we will use a generic method:

private static <T> T last(List<T> list, T defaultValue) {
    return list.size() == 0 ? defaultValue : list.get(list.size() - 1);
}

With this abstraction at hand, our program becomes:

private static List<Integer> triangular(int length) {
    List<Integer> result = new ArrayList<>();
    for(int i = 1; i <= length; i++) {
        result.add(last(result, 0) + i);
    }
    return result;
}

Next, we will abstract the creation of a list of consecutive integers. Although Java offers this (with the IntSream::range method), we will create our own:

private static List<Integer> range(int start, int end) {
    List<Integer> result = new ArrayList<>();
    for(int i = start; i <= end; i++) {
        result.add(i);
    }
    return result;
  }

We will also abstract the fold operation as we did in the previous example, but we will take care of the more general case where the return value is of a different type than the list elements. Recall that fold means iterating over each element, applying an operation to the current result and the given element, starting with some initial value. In the previous example, we called this value “identity” because it was the identity of the givent operation. However, we are not limited to the identity value. We could chose any value for starting the computation. As an additional abstraction, we will make the method work on any iterable collection, not only lists:

private static <T, U> U fold(
        Iterable<T> elements, U initial, BiFunction<U, T, U> f) {
    U result = initial;
    for (T t : elements) {
        result = f.apply(result, t);
    }
    return result;
}

Our programs now becomes:

private static List<Integer> triangular(int length) {
    return fold(range(1, length), new ArrayList<>(), (a, b) -> {
        a.add(last(a, 0) + b);
        return a;
    });
}

In this version, new ArrayList<>() is the initial value, and the computation consists of adding the current value to the last result and appending the new result to the list.

There are two additional little things about lists that we might like to abstract: producing the empty list and adding a value to a list while returning the resulting list.

private static <T> List<T> emptyList() {
    return new ArrayList<>();
}

private static <T> List<T> append(List<T> list, T t) {
    list.add(t);
    return list;
}

Here is the version of our program using these abstractions:

private static List<Integer> triangular(int length) {
    return fold(
        range(1, length),
        emptyList(),
        (a, b) -> append(a, last(a, 0) + b));
}

Abstracting the Computation

As we did in the previous example, we might want to abstract the computation in order to be able to use not only addition, but, among other options, multiplication:

private static List<Integer> scan(
        int length, Integer z, BinaryOperator<Integer> op) {
    return fold(
        range(1, length),
        emptyList(),
        (a, b) -> append(a, op.apply(last(a, z), b)));
}

private static List<Integer> triangular(int length) {
    return scan(length, 0, (a, b) -> a + b);
}

private static List<Integer> factorial(int length) {
    return scan(length, 1, (a, b) -> a * b);
}

Note that z is used by convention, meaning “zero”, which does not mean 0 but the identity or neutral element of the given operation, by analogy with 0 being the identity of the addition.

One of the problems we have to solve is how to call this method. As it happens, this is a well known abstraction in functional programming, called scan. Naming the method calling this function with multiplication instead of addition is straightforward: It is simply the factorial suite.

Abstracting the Type

Of course, our program could be used for arbitrary types, and not only for numbers, so we want to abstract the type:

private static <T> List<T> scan(
        Iterable<T> elements, T z, BinaryOperator<T> op) {
    return fold(
        elements,
        emptyList(),
        (a, b) -> append(a, op.apply(last(a, z), b)));
}

Note that because the type is generic scan can no longer create the elements itself with range, so now the callers need to do that:

private static List<Integer> triangular(int length) {
    return scan(range(1, length), 0, (a, b) -> a + b);
}

private static List<Integer> factorial(int length) {
    return scan(range(1, length), 1, (a, b) -> a * b);
}

Using a Different Type for the Return Value

Again, there is no reason why the return type should be the same as the collection element type, and we can make our function even more generic:

private static <T, U> List<U> scanLeft(
        Iterable<T> elements, U z, BiFunction<U, T, U> f) {
    return fold(
        elements,
        emptyList(),
        (a, b) -> append(a, f.apply(last(a, z), b)));
}

private static List<Integer> triangular(int length) {
    return scanLeft(range(1, length), 0, (a, b) -> a + b);
}

private static List<Integer> factorial(int length) {
    return scanLeft(range(1, length), 1, (a, b) -> a * b);
}

Here, we are scanning from left to right (meaning starting with the first element of the list) and with a BiFunction<U, T, U>. This operation is a left scan, hence the name scanLeft. (We could have started from right (not with an Iterable, though) and used a BiFunction<T, U, U>, producing a different abstraction called scanRight.)

We may now use this abstracted function for a list of characters producing a list of Strings:

private static List<String> constructString(List<Character> characters) {
    return scanLeft(characters, "", (s, c) -> s + c);
}

System.out.println(constructString(Arrays.asList(
    'H', 'e', 'l', 'l', 'o', ',', ' ', 'W', 'o', 'r', 'l', 'd', '!')));

This program displays:

[H, He, Hel, Hell, Hello, Hello,, Hello, , Hello, W, Hello, Wo, Hello, Wor, Hello, Worl, Hello, World, Hello, World!]

Of course, it would be handy if the scanLeft function was added to the Collection interface. Since it is not, we will simply add it to our functional library.

Beware of Mutable Lists

Theoretically, we could also use the scan function to produce all the possible “starting” sublist of a given list, such as:

private static <T> List<List<T>> starts(List<T> list) {
    return scanLeft(list, emptyList(), (lst, elem) -> append(lst, elem));
}

System.out.println(starts(Arrays.asList(1, 2, 3, 4, 5)));

This program should then display:

[[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5]]

But this don’t work and produces:

[[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]]

Here, we are trapped with the problem of in place mutation. It is well understood that FP favor immutable persistent objects over mutable ones (like Java’s various collection implementations). This is often presented as a great benefit for concurrent programs when mutable state is to be shared between threads, meaning that the state is accessed by different threads at the same time. Here, we are facing an even more frequent problem: The same thread is accessing mutable data at different times, but the data as been mutated although it should not have.

The problem is in the append method, which take as List and an element as its argument, and returns a List with the appended element. But the list received as an argument is mutated and returned, which means the mutation is visible outside of the method. To get the correct result, we have to rewrite the method as:

private static <T> List<T> append(List<T> list, T t) {
    List<T> result = new ArrayList<>(list);
    result.add(t);
    return result;
}

This problem is known as referential transparency, and is probably the most important difference between functional programming and the other programming paradigms. Functional programming enforces referential transparency at any cost. But this is another story.

Summary

In this article, we saw how one of the concerns of functional programming is to push abstraction to the limit. This is not only a question of reusability! Abstracting each concept allows us to understand how these concepts are related. It shows what is similar in operations that seem completely different at first sight. With this new knowledge, we understand the relation that exists between concepts that formerly seemed unrelated.

So, is premature abstraction evil like premature optimization is said to be? It is indeed interesting to remark that abstraction and optimization (for performance) are two opposite things. Optimization is often done by dealing only with the specificities of the problem at hand. Abstraction, on the other hand, consists of searching for the most general representation of the problem.

Considering the initial problem (the sum of integers up to n), using the formula (n * (n + 1) / 2) is indeed an optimization, taking into account the specific nature of the operation applied to fold the list of integers, and the specific nature of these integers. The good side is that it is the fastest way to compute the result. The bad side is that if you change the operation (for example to compute the product of integers up to n), it does not help at all, and you have to write a complete new program. Even worse, unlike the abstracted solution, this one will not work for computing the sum of any other list of integers.

With the abstracted solution, you just have to change the operation and the identity, and you can apply it to any list of integers, or even to any list of elements of any type. What you have done, in fact, is discovering a specific kind of operation that can be applied to a list of any type and a function. This operation is called scanning. Computing the sum of integers from 1 to n is scanning this list of integers with addition. Computing n! is scanning the same list with multiplication. And any list of type List<T> may be scanned with a function of type BiFunction<U, T, U> to get a result of type List<U>.

The conclusion is that it is often better, whether you are doing functional or imperative programming, to understand the very nature of the problem at hand, and this is what pushing abstraction to the limit will bring you. You may then chose another more specific and faster solution, but this should remain optimization.

One of the concepts presented in this article is the fact that some collections are “foldable”. If we had more space (maybe in a other article), it could be interesting to analyze how this concept is related to Optional.orElse in Java 8. We could then realize that these two concepts are in fact two different compositions of two simpler common concepts. Incidentally, we also discovered an important difference between functional and non functional paradigm, known as referential transparency.