/ Coding

Functional Programming Mind Map

I want to share a mind map I built for teaching functional programming concepts in an introductory Scala course. Far to be complete, it is enough to show that functional programming is not only a matter of how to write map and reduce!

A few months ago I had to prepare an introductory course on Scala. I wanted to keep the things very practical but I could not get rid of a general introduction to functional programming. Thus, I came out with this mind map. The aim was to show, or at least mention, the most valuable design tools functional programming offers to a developer.

Although it does not add anything more in term of possibilities, functional style often speeds up development time by removing the burden and the clutter that can be found in some imperative languages. This is done by a well-defined set of features that recurs in every modern language. Often such features can be implemented in older languages via design patterns. But sometimes design patterns can be also a signal of an inadequacy in a language. Low ceremony and intuitive syntax help to replace these patterns and to get a cleaner code.

In my opinion, understanding functional programming features help in writing better code in any language:

  • high-order functions helps to not reinvent the wheel every time.
  • immutability an no side-effects make code easier to test and reuse.
  • declarative style increases readability and conciseness.
  • focus on typing forces to reason about your code and prevents trivial bugs.

In this post, I'll try to discuss such features.

Functional Programming Mind Map

1. First class functions

Functional programming has first-class functions. That means that functions are like standard language objects that can be assigned to variables, passed around and created dynamically. Although a simple concept, it opens up a ton of new solutions in terms of abstraction capabilities.

The same behavior can be achieved in standard Object Oriented Programming. Such a pattern is common and called Functional Interface, that is a solution to represent a function as an object which implements an interface with a single method to be invoked. The following dumb piece of code shows how functions can be considered objects and then how the code can be simplified with a little help from the language.

import java.util.function.Consumer;

public class Main {

    public static void main(String[] args) {
        //1 Passing an object function
        OOPFunction invocation = new OOPFunction();
        executor(invocation);
        //2 Method reference
        executor(ReferencedMethodClass::consumeInteger);
        //3 Lambda function created dynamically
        executor((i)->System.out.println(i));
        //4 Direct method reference
        executor(System.out::println);
    }

    private static  void executor(Consumer<Integer> firstClassFunction){
        firstClassFunction.accept(42);
    }

    static class OOPFunction implements Consumer<Integer> {
        @Override
        public void accept(Integer integer) {
            System.out.println(integer);
        }
    }

    static class ReferencedMethodClass {
        static void consumeInteger(Integer i){
            System.out.println(i);
        }
    }
}

The objective is to pass a function to an executor method:

  1. In the first case, the invocation leverages on the use of the Consumer interface, implemented by the OOPFunction class and understood by the executor method.
  2. The second invocation uses method reference and typed function that simplifies the code by removing the need for the interface implementation.
  3. The third one removes the need for an entire class and creates the function dynamically.
  4. The last statement completely removes the need for additional code by referencing the target method directly.

Thus, the "first-class function" thing is a matter of easing the design of abstractions by reducing the amount of boilerplate code. This is done with some syntactic tricks that are common in almost all the modern languages. Knowing these tools is the first brick to lay if we desire to be confident with functional programming.

1.1 Lambdas and method reference

As Wikipedia says:

An anonymous function (function literal, lambda abstraction, or lambda expression) is a function definition that is not bound to an identifier.

Practically speaking, a lambda is the easiest tool to create functions dynamically without the need for boilerplate code. It is the first choice when we need to pass around a piece of code to be executed by something else.

When we have a function that is related to an object, we talk about method reference. The main difference between lambdas is how the how the context is bound. In method reference, the function is created at object instantiation and it is bound to the object's self/this implicit parameter. In lambdas, the context is captured at execution time with a programming abstraction called closure.

1.2 Closures

A closure is a programming abstraction that is able to capture all the free variables defined in its context. This means that in a lambda we can use variables that are neither its function parameters nor local variables.
Let's see an example in Scala:

object ClosureExample {
    var variableToCapture = 3
    val lambda = (i:Int) => i + variableToCapture
    def main(args: Array[String]) {
      println( lambda(1) )      //prints 4
      variableToCapture = 1
      println( lambda(2) )      // prints ? ..3!
   }
}

The demo show how the variable variableToCapture is actually captured when the lambda is created. Subsequent re-assignment should be generally avoided. In this case Scala (2.12) creates a reference to the closured variable and thus the result is three instead of an expected five.

As usual, variables in a closure can be captured by value or by reference. This behavior typically changes a lot between programming languages; Java, for example, enforces the free variable to be final or effectively final. Scala has somehow a more elegant approach, but it's a design choice I consider particularly error-prone and difficult to read. Mutable objects complicate the thing: even if we are in a copy by value environment, one can emulate a copy by reference by using a reference to the object that is actually passed by value 😱. This is a common problem in parameter passing that gets even worse if we also take into account multi-threading. Better to stick with immutability and not reassignable variables.

1.3 Partially applied functions

A partial application consists in calling a function with fewer parameters than the ones declared in its signature. The return value is simply a function that takes as input the remaining parameters.
This is a simple example in Scala:

// function with type: (String, String, String) => String
val stringsComposer = (a:String, b:String, c:String) => s"$a$b$c"
//function with type (String, String) => String
val whiteSpaceJoiner = stringsComposer(_:String, " ", _:String)
// function with type (String) => (String)
val sayHello = whiteSpaceJoiner("Hello", _:String)
// print "Hello Jacopo"
print(sayHello("Jacopo"))

1.4 Currying

Currying is a mathematical technique that consists in splitting a function in a chain of single argument functions until other parameters are needed. Roughly speaking is very similar to the partial application.
Here an example similar to the one of the previous paragraph implemented with curried functions:

// method with type: (a: Int)(b: Int)(c: Int)Int
def addThreeNumbers(a:Int)(b:Int)(c:Int) = a + b + c
// function with type (Int => (Int => Int))
val addTwoNumbers = addThreeNumbers(0) _
// function with type (Int) => (Int)
val identity = addTwoNumbers(0)
// print 1
print(identity(1))

1.5 Behavioral parameterization

In my opinion, behavioral parameterization is the key point of functional programming. It means that we can generalize the "template" of a given algorithm and pass the actual behavior as an argument. This leads to a more modular and reusable code. Such kind of abstraction can be used at different levels whether we are implementing the behavior of a large component or defining a little control abstraction. Mathematically, this capability comes from the definition of high-order function, i.e. functions that takes as argument other functions.

As always, behavioral parameterization can be achieved also with non-functional object-oriented programming by using design patterns. Some of my favorites in this field are the Template and Strategy patterns. The Template one helps in abstracting out the outline of an algorithm, with the objective of letting clients plug in some parts of it. On the other hand, the Strategy pattern aims at standardizing an algorithm in abstract terms, so that it can be used by different clients regardless the actual implementation. The ability to define high-order functions allows us to easily replace these patterns.

2. Transform, not mutate

Mathematical functions do not have to deal with any kind of state. They take some arguments as input, elaborates them through expressions and returns values as output. The same appears in pure functional programming where functions transform immutable data structures and new ones come out. This is the opposite approach of object-oriented approach where objects represent a piece of state along with its business logic.

When we deal with immutable data structure we can't modify it piece by piece. We are obliged to throw away procedural style and write in more declarative manner.
Declarative style makes our code more readable and concise.

This is how we can count and rank words from Dante's Inferno:

//load Inferno lines from file and convert to list
val lines = scala.io.Source.fromFile("Inferno.txt").getLines().toList;
//clean lines from punctuation
val cleanedLines = lines.map(l => l.replaceAll("['?!,:;.-<>]"," ").toLowerCase);
//create a list of words
val words = cleanedLines.flatMap(_.split(" ")).filter(w => !w.isEmpty);
//create a map of words with counter as value (word -> counter)
val wordsCounter = words.groupBy(identity).mapValues(_.length);
//convert the map to a list of tuples and order desc by counter
val result = wordsCounter.toList.sortWith(_._2 > _._2).take(20);

2.1 Rich collection API

With the ability to define high-order functions, a lot of control abstractions can be defined to manipulate data. Usually, such powerful tools are given for free by the language libraries. Knowing them is fundamental to write concise code and avoid to reinvent the wheel every time.

Functional programming collections API are numerous and complex at the beginning. Fortunately, once learned, they can be recurrently found in every modern languages and library. In my experience, it is worth to dive a little deeper than usual in the documentation, since it drastically increases both the fun and the amount of code we do not have to write.

2.2 Use immutability

As discussed before, immutability helps in writing code that is concise and without side-effects. But why immutability is so important?

  • Predictability: code with no side-effects is more predictable. It can be reused more safely because we can't misunderstand or forget about a particular side effect we or our colleagues implemented a week or a month ago.
  • Removes race conditions: that is the need of synchronization between one or more threads when they need to access or modify a shared area of memory. Immutable classes are potentially easier to implement.
  • Performance: even if premature optimization is the root of all evil, it makes sense to understand what happens under the hood. Usually, immutable data structures use structural sharing to reduce the impact on memory usage. Adding an element to an immutable list doesn't mean to duplicate it entirely.

2.3 Friendly multi-threading

Parallel processing of data is often handled transparently. This reduces the burden of struggling with locking resources as well as threads management. The following examples show how transformations on collections can be parallelized with no effort.

With Java 8 Streams:

List<Integer> listOfNumbers = Lists.newArrayList(1,2,3,4);
List<Integer> seqResults = listOfNumbers.stream()
                                        .map(n->n*2)
                                        .collect(Collectors.toList());
List<Integer> parResults = listOfNumbers.parallelStream()
                                        .map(n->n*2)
                                        .collect(Collectors.toList());

With Scala:

val listOfNumbers = List(1,2,3,4)
val seqResults = listOfNumbers.map(_ * 2)
val parResults = listOfNumbers.par.map(_ * 2)

3. Favor pure functions

At the end, it's all a matter of style. Writing pure functions means that we focus on functions that take immutable data and produce new immutable data as output. In a pure function given the application of the same inputs always returns the same results, so they become easier to test and to reuse.

It's obvious that sooner or later we need to handle some sort of state whether it is an application state, a database or a file. It is useful to distinguish between pure code and the parts of our software that access the external world. This makes easier to test, organize and think about our software.

3.1 Expressions over statements

Functional writing favors expression over statements. While statements represent actions to be executed sequentially, expressions define computations.
The immediate advantage of using expressions is improved readability and testability of our code. But there's more than that.

Expressions can be defined by the following points:

  • Idempotency
  • No side-effect
  • Can be replaced at compile time with its corresponding value without changing the program's behavior (referential transparency)
  • Computation order does not matter, as long as operators precedence is preserved
  • Results can be easily cached thanks to idempotency

3.2 Declarative, not imperative

All the tools already discussed, lead us to write in a declarative style. Declarative programming means that we focus on the result we are concerned with and not on the way that allows us to obtain the answer.

Although it can increase readability and reducing errors, it has some potential drawbacks. In fact, using control abstraction can reduce the amount of code we write but on the other hand, can bring us out of control. This result in code easy to read but difficult to debug and sometimes inefficient since we do not know what happens under the hood.

3.3 Conciseness

Conciseness is important but it is not a sufficient condition for readability. Functional control abstraction let us make a lot of things in few lines of code. It's up to you to decide when to stop chaining functions and let the reader take a breath.

3.4 Tail recursion optimization

Shifting from a procedural to a functional style can be difficult. In a pure functional language, you have to resign and forget about for and while loop. Sometimes recursion is a great tool to write concise code. But not all recursions are good. This has to deal we call stack of our functions.

Tail recursion is a particular kind of recursion that can reuse the same stack frame for all the recursive function calls. This is possible only when the recursive call is the last action of the function, so there is no need to preserve the frame to keep track the execution of the next steps of the caller.

This is a classic example of tail recursion in Scala that returns the greatest common divisor using Euclid's algorithm:

def gcdProcedural(var a: Int, var b: Int): Int = {
    var nexta = a
    var nextb = b
    var tmp = b
    while(nextb != 0){
       tmp = nextb; 
       nextb = nexta % nextb; 
       nexta = tmp; 
    }
    return nexta;
}

@tailrec
def gcd(a: Int, b: Int): Int =
  if (b == 0) a else gcd(b, a % b)

4. Statically typed

A common trend in recent languages is to focus on typing. A statically typed language requires that types must be known at compile time. It is said to be strongly typed when typing rules are evaluated strictly and it is more common to get compiler errors.

One of the advantages of static type-checking is that some trivial bugs can be caught by the compiler at an early stage of development. Nevertheless, the definition of every single type can be boring and cluttering. Here type inference comes to help.

Not all type systems are the same, some are powerful than others. Understanding the inner working of types can be helpful to design better code, increasing its chances to be reused. Moreover, it is necessary to dive in the documentation of the language libraries, which often can become very complex.

4.1 Type inference

Type inference means that we have the option to decide whether to specify a type or not. I the types are not declared, the compiler will infer them, based on the type of literals constants, the explicitly declared type of objects, the functions used in the expression, and the syntactic structure of the program.

4.2 Pattern matching

Pattern matching is a powerful facility that allows to construct and deconstruct data types to control execution flows.
In its basic usage, it is a way to replace a standard switch statement.

def show(x: Option[String]) = x match {
    case Some(s) => s
    case None => "?"
}

In other languages it can be used also to define functions.
This is a recursive implementation of a map function in Haskell:

map :: (a -> b) -> [a] -> [b]  
map _ [] = []  
map f (x:xs) = f x : map f xs  
  • the first line defines the type of the function map as a function that takes a function of type (a -> b) and a list of elements of type a, as result returns a list of elements of type b.
  • the second line tells that the application of map over an empty list is always an empty list regardless of the function given as the first argument. This is the base case of the recursion.
  • the third line deconstructs the array in its head and tail, then defines a recursive rule that applies a given function to the first element of the list and calls map recursively on the tail.

4.3 Pure object orientation and null pointers

In a pure object-oriented language, there is no primitive type, everything is an object. This means that even arithmetic operations on integers are considered methods of objects whose class is Integer. Thus, arithmetic operations can be passed-around like first order functions. Although not strictly related to functional programming this is an elegant solution to mix things up.

Another important element is the attempt to remove NullPointerException bugs by mean of option type or maybe type. Scala Option, Java 8 Optional and Haskell Maybe are examples of such attempt. Roughly speaking they are containers of a given type that can hold one or zero elements. From a client perspective, one can either transform data directly into the container without explicitly handling null checks, or decide to extract the wrapped value handling the object explicitly.
The following is an example in Scala taken from the Option documentation:

val name: Option[String] = request getParameter "name"
val upper = name map { _.trim } filter { _.length != 0 } map { _.toUpperCase }
println(upper getOrElse "")

Here the request parameter "name" is an optional variable. Null checks are are implicitly handled and deferred until the actual value is really needed. If the variable "name" is None since the beginning, then the following transformations results in a chain of invocations on the None value which in turn returns nothing but another None value.

Conclusions

Thanks for reading!