Chapter 1. An Introduction to Functional Programming

To better understand how to incorporate a more functional programming style in Java, we first need to make ourselves knowledgeable about functional programming’s origin and foundational concepts. This chapter will explore the roots of functional programming and what concepts contribute to making an approach to programming more functional.

The Origin of Functional Programming

The functional programming paradigm evolved from Lambda Calculus, invented by the logician Alonzo Church in the 1930s.1 Lambda calculus is a formal mathematical system to express computations with abstract functions and apply variables to them. The name “lambda calculus” came from the Greek letter chosen for its symbol: λ

Don’t worry! I promise I won’t torture you with more complex math than needed.

There are three pillars to support the general concept of lambda calculus:

  • Abstraction

  • Application

  • Reduction

Lambda Abstractions

What you as a developer refer to as a “function call” is, mathematically speaking, the application of lambda abstraction to a value. It can be declared as a function like this: f=λx.E

A function declaration consists of multiple parts:

x

A variable, the argument representing a value.

E

An expression, or term, containing the logic.

λx.E

The abstraction, an anonymous function accepting a single input x.

f

The resulting function that can apply an argument to its abstraction.

Let’s imagine a Java function for calculation a quadratic value, as seen in Example 1-1.

Example 1-1. Quadratic function (Java)
// As "classical" method

Integer f(Integer value) {
  return value * value;
}

// As lambda expression

Function<Integer, Integer> f = x -> x * x; 1
1

A functiona accepting a single Integer, and returning an Integer.

Note

Example 1-1 uses Integer instead of int due to generic nature of Java’s functional types. The use of value types in generics is part of the upcoming Project Valhalla.

The Java lambda expression quite resembles its lambda calculus counterpart in Equation 1-1.

Equation 1-1. Quadratic function (lambda calculus)
f=λx.x*x

Application

The application of an abstraction in Equation 1-2 looks like a method call that you’re quite used to in Java.

Equation 1-2. Application of f to argument 5 (lambda calculus)
f5

The Java equivalent in Example 1-2 is a little bit more verbose because it uses the “normal” method calling syntax that requires a name, but you can’t deny the similarity.

Example 1-2. Application of f to argument 5 (lambda calculus)
// As applied lambda expression

f.apply(5);


// As method call

f(5);

Reduction

If you apply a lambda abstraction to an argument, the variable in the expression gets substituted by the argument. This form of substitution is called β-reduction, as seen in Equation 1-3.

Equation 1-3. ß-reduction
f55*525f(f3)f(3*3)f99*981

The equivalency between a function application and the result itself allows simplifying more complex constructs. Complex calculations will be more approachable and less intimidating after reducing them to a more simple form.

Of course, there are way more details to it2, but that’s all you will need to understand the origin of functional programming.

What is Functional Programming?

Like most paradigms, functional programming doesn’t have a single agreed-upon definition, and many turf wars are fought about what defines a language as really functional. Instead of giving my own definition, I will show you different aspects of what makes a language functional.

As an object-oriented developer, you are used to imperative programming: by defining a series of statements, you are telling the computer what to do to accomplish a particular task.

Functional programming uses a declarative style to express the logic of computations without describing their control flow. It is a description of how a program should work, not what it should do. Your code is bound in a sequence of functions, representing evaluable expressions instead of statements.

The primary distinction between expressions and statements is that the latter has possible side-effects to program state, and the former is supposed to be self-contained with immutable state. These properties aren’t absolute or mutually exclusive. Especially in a general-purpose, multi-paradigm language like Java, the lines between them can quickly blur.

Expressions

An expression is a sequence of operators and operands that define a computation, like in Example 1-3. An expression can return some form of a result but doesn’t have to. They are analogous to the concept shown in “Lambda Abstractions”. Side-effects are discouraged but aren’t forbidden either.

Example 1-3. Simple Java Expressions
x * x 1

2 * Math.PI * radius 2
1

The quadratic expression used in Example 1-1.

2

An expression to calculate the circumference of a circle.

Statements

In Java, you’re used to statements. Assigning or changing the value of a variable, calling methods, or control-flow like if/else; all of these are statements. They are actions taken by your code, as in Example 1-4.

Example 1-4. Java Statements
int treasureCounter = 0; 1

treasureCounter += findTreasure(6); 2

if (treasureCounter > 10) { 3
  System.out.println("You have a lot of treasure!");
}
else {
  System.out.println("You should look for more treasure!");
}
1

Assigns an initial value to a variable, introducing state into the program.

2

The function call findTreasure(6) might be a pure functional expression, but the reassignment of treasureCounter is state-change and therefore a statement.

3

The control-flow statement if/else expresses what action should be taken based on the result of the expression (treasureCounter > 10).

Functional Programming Concepts

Functional programming is a conglomerate of different concepts, forming a paradigm in which everything is bound together with pure mathematical functions. Its primary focus is on “what to solve” in a declarative style, in contrast to the imperative “how to solve” approach.

We will go through the most common and significant aspects functional programming builds upon. But remember, these aren’t exclusive to a particular paradigm. Many of the ideas behind them apply to other programming paradigms as well.

Pure Functions

Functional programming categorizes functions into two categories: pure and impure.

Pure functions have two elemental guarantees:

  • The same input will always create the same output.

  • They are self-contained without any kind of side-effect, e.g., affecting the global state or changing argument values, or using I/O, like in Figure 1-1.

Separation of a Pure Function from Program State
Figure 1-1. Pure Functions are separated from Program State

These two guarantees allow pure functions to be safe to use in any environment, even in a parallel fashion.

Functions violating any of these guarantees are considered impure. That is a rather unfortunate name because of the connotation it might invoke. Impure functions aren’t second-class to pure functions. They are just used in different ways.

Referential Transparency

Due to the predictable result of side-effect-free expressions and pure functions based on their input, their respective return values can replace them for any further invocations once evaluated, without changing the result of the program. These kinds of functions and expressions are referentially transparent. You have seen this kind of substitution in Equation 1-3.

Optimization techniques, like memoization, can use this concept to cache function calls to prevent unnecessary reevaluation of expressions.

Immutability

Object-oriented code, like in Java, is often based around a mutual state. Objects can usually be changed after their creation, using setters. But mutating data structures can create unexpected side effects.

With immutability, data structures can no longer change after their initialization. By never changing, they are always consistent, and therefore predictable, side-effect-free, and easier to reason with. Like pure functions, their usage is safe in concurrent and parallel environments without the usual issues of unsynchronized access or out-of-scope state changes.

If data structures never change at all, a program would not be very useful. Instead of mutating existing data, you have to create a new data structure containing the changed data. At first, this might sound like a chore, and actually, it can be. But in general, the advantages of having side-effect-free data structures outweigh the extra work that might be necessary.

Recursion

Recursion is an approach for problems that can be partially solved, with a remaining problem in the same form. In layman’s terms, recursive functions call themselves, but with a slight change in their input arguments until they reach an end condition and return an actual value. The later chapter “Mathematical Explanation” will go into the more finer details of recursion.

A simple example is calculating a factorial, the product of all positive integers less than or equal to the input parameter. Instead of calculating the value with an intermediate state, the function calls itself with a decremented input variable, like in Figure 1-2.

Separation of a Pure Function from Program State
Figure 1-2. Calculating a factorial with recursion

Pure functional programming prefers using recursion instead of loops. Some languages, like Haskell, don’t even provide the traditional for or while-loops.

As with most of the other concepts, recursion is also not exclusive to functional programming.

First-Class and Higher-Order

Many of the previous concepts don’t have to be (fully) available to support a more functional programming style in a language. But this one is an absolute must-have.

Functions are supposed to be a “first-class citizen”, giving them all the properties inherent to other entities of the language. They need to be assignable to variables and be used as arguments and return values in other functions and expressions, like in Example 1-5.

Example 1-5. First-Class Functions
Function<Integer, Integer> quadraticFn = x -> x * x; 1

var result = quadraticFn.apply(5); 2
1

Expressions are based on so-called functional interfaces, and can be assigned to variables like any other value.

2

It can be used like any other “normal” Java variable, calling the apply method of its interface.

Higher-order functions use their first-class citizenship to accept functions as arguments or to return a function as their result, or both. That is essential for the next concept, functional composition.

Functional Composition

Pure functions can be combined to create more complex expressions. In mathematical terms, this means that the two functions f(x) and g(x) can be combined to a function h(x)=g(f(x)), as seen in Figure 1-3.

Composing function f and g to a new function h
Figure 1-3. Composing functions

This way, the initial functions can be small and reusable, and the resulting composed function will perform a more complex and complete task. Let’s combine the previous quadratic function with other functions in Example 1-6.

Example 1-6. Functional Composition in Java
Function<Integer, Integer> quadratic = x -> x * x; 1

Function<Integer, Integer> triple = x -> 3 * x; 2

var quadraticThenTriple = quadratic.andThen(triple); 3

var tripleThenQuadratic = quadratic.compose(triple); 4

var result1 = quadraticThenTriple.apply(3); // => 27

var result2 = tripleThenQuadratic.apply(3); // => 81
1

The simple quadratic function from previous examples.

2

Another pure function, tripling the applied value.

3

Composing a function, calling triple with the result of quadratic.

4

Composing a function the other way around, tripling first.

If you look at the source code of andThen and compose, you can clearly see the concept of first-class and higher-order functions in action. Example 1-7 is a simplified version of what’s actually happening.

Example 1-7. Source code of andThen and compose.
Function<Integer> andThen(Function<Integer, Integer> after) { 1
  return value -> after.apply(apply(value)); 2
}

Function<Integer, Integer> compose(Function<Integer, Integer> before) { 3
  return value -> apply(before.apply(value)); 4
}
1

andThen is a higher-order function, accepting a function as its argument, and returning a combined function.

2

The returned function accepts a value and applies the current function to it first, and the result is then applied to after.

3

As with andThen, a function is accepted as an argument and returns a new function.

4

This time, before is applied to the value first, and the original function is applied to the result.

Laziness

Lazy evaluation is a common technique to decouple the evaluation of an expression until its result is actually needed. Expressions evaluate just-in-time. It is another concept that is not rooted in functional programming itself but provides a foundation for many related concepts.

Some form of laziness is already available in Java: logical short-circuit operators, as seen in Example 1-8.

Example 1-8. Logical Short-Circuit Operators
var result1 = simple() && complex();

var result2 = simple() || complex();

The number of evaluated expressions depends on the results of simple(), as seen in Table 1-1.

Table 1-1. Evaluation of Logical Operators

Operator

Result of simple()

Is complex() evaluated?

&&

true

yes

&&

false

no

||

true

no

||

false

yes

The JVM can discard expressions not related to the final result. This behavior even allows infinite data structures to exist, as you will learn about in [Link to Come].

Laziness works well with referential transparency. If there is no difference between an expression and its result, it doesn’t matter when you will execute it. Delayed evaluation might still impact the program performance because you might not know the precise time of evaluation.

Advantages of Functional Programming

Now that you have learned about the different concepts functional programming relies on, what advantages does it provide to you and your code?

Simplicity

Without state and side-effects, your functions tend to be smaller, doing “just what they are supposed to do”.

Consistency

Immutable data structures are reliable and consistent. No more worries about changed state without you knowing.

(Mathematical) Correctness

Simpler code with consistent data structures will automatically lead to “more correct” code with fewer bugs. The “purer” your code, the easier it will be to reason with, leading to easier debugging and testing.

Concurrency

Concurrency is one of the most challenging tasks to do right in “classical” Java. Functional concepts allow you to eliminate many headaches and gain safer parallel-processing (almost) for free.

Modularity

Small, independent, and reusable functions allow a new form of modularity and reusability, like functional composition.

Academia Versus “The Real World”

The foundation of functional concepts consists of strictly mathematical principles due to their roots in academia. That provides us with a straightforward, easy to reason with, and safe paradigm.

But all of us know that not everything obeys the rules, especially in real-world projects. That’s why many functional programming languages deviate from the purest interpretation of the fundamental concepts for various reasons, most likely to provide a broader range of use. And even then, how much of the remaining strictness you want to introduce into your code relies mostly on you and your requirements.

Language design is always a balancing act between being safe and being convenient. For example, Haskell, a purely functional programming language, has the slogan “avoid success at all costs”. “Success” in this case means broad popularity and widespread use, and “costs” being concessions made to further such “success”. They won’t “make things easier” for beginners or add any changes that might impact the core values of Haskell. That can make a language “useless” but “safe”. Simon Peyton Jones, lead developer of the Glasgow Haskell Compiler and major contributor to Haskell, describes the relationship between the two properties in an informal Youtube video.

With Haskell arguably being an academia language with only niche-adaption, it can afford to stand up for its convictions. Java does it, too, but has other priorities. Every new Java version provides you with safer and more useful tools.

The goal you should strive for in your own code shouldn’t be relying on one extreme position or another. Instead, it should be the amalgamation of the best of both worlds.

Takeaways

  • The mathematical principle of lambda calculus and abstractions builds the foundation for FP.

  • FP emphasizes expressions, while imperative programming emphasizes statements.

  • There are many inherently functional concepts, but they are not an absolute requirement to make code “functional”.

  • Trade-offs are often necessary between “pureness” of functional concepts and their real-world application.

1 Church, Alonzo. 1936. “An unsolvable problem of elementary number theory”. American journal of mathematics, Vol. 58, 345–363.

2 The Wikipedia entry on lambda calculus provides more information.

3 Turing, A.M. 1937. “On Computable Numbers, with an Application to the Entscheidungsproblem.” Proceedings of the London Mathematical Society, Vol. s2-42 Issue 1, 230-265.

4 There are certain restrictions on lambda calculus to be turing complete. See the Wikipedia entry on Turing completeness for more information.

5 Copeland, Jack and Oron Shagrir. 2019. “The Church-Turing Thesis: Logical Limit or Breachable Barrier?” Communications of the ACM, January 2019, Vol. 62 No. 1, Pages 66-74.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
35.175.246.88