A Bite of Functional Programming

Functional programming is a programming paradigm — a style or a way of thinking when writing software programs. There are many programming paradigms available, some of which are presented in the following diagram.

The imperative programming paradigm is the oldest, and still the most popular, paradigm used today. As the term “imperative” indicates, this paradigm models a program as a sequence of commands that change a program’s state—“first do this, then do that.” Even if we follow the object-oriented programming paradigm by encapsulating logic into classes, we’ll likely implement the class methods in the imperative style.

Why has imperative programming dominated the programming world? In his Turing Award lecture titled “Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs,” the computer scientist John Backus gives an insightful answer. According to his observation, the reason can be traced back to the Von Neumann architecture. Named after the mathematician John Von Neumann, who took inspiration from the Turing machine, it is a computer architecture used by most computers produced today.

In the following, we’ll review the Von Neumann architecture and discuss several problems of the imperative programming paradigm due to its tight pairing with this architecture. Then we’ll see how the functional programming paradigm can elegantly overcome those problems.

Von Neumann architecture

In its simplest form, a Von Neumann computer consists of a Central Processing Unit (CPU), a memory, and a bus that connects them. The CPU acts as the brain of the computer with the ability to execute a predefined set of machine code instructions. These instructions are in binary form, consisting of 0s and 1s, and do a very primitive thing, such as adding two numbers or testing whether a number equals zero or not. The CPU has a handful of registers to store data needed when executing an instruction.

The memory is the place where a program and its data are stored. A program is a sequence of machine code instructions. The CPU and the memory are connected via a bus. Due to this, a subset of machine code instructions is dedicated to loading data from memory onto the registers or storing the data from the register onto the memory.

The following diagram illustrates the Von Neumann architecture.

So, how does a program run? It’s quite simple. The CPU runs the program following a mechanical fetch-execute cycle. First, it fetches the first instruction in the program and executes it. Then it fetches the next instruction and executes it, and this cycle continues on. Some instructions affect the order of execution. For instance, a jump instruction directs the CPU to jump back to a previous point of the instruction sequence. A branch instruction tells the CPU to branch to a particular instruction if some condition is true, for example, if two registers have the same values. These instructions are typically combined to implement loops and if-statements.

Low-level nature of imperative programming

Let’s stop for a moment and reflect on the thought process when programming for the Von Neumann computer. A program is constructed as a sequence of instructions whose main task is to move data back and forth between the CPU and memory. These instructions also perform arithmetic and logical operations. The primary concern is how to update the memory cells in a stepwise manner. This model of programming for the Von Neumann architecture is the essence of what imperative programming is about.

Consider, for instance, an example of calculating the sum of squares of the first n numbers in the imperative style.

int sum = 0; i = 0;
while (i < n) {
   i = i + 1;
   sum = sum + i * i;
}

This program might be written with a high-level language, such as C, Java, or Python. Yet, the code is nothing more than a sequence of statements telling the physical computer how to update the memory. In particular, the variables sum and i correspond to the memory cells. An assignment statement, such as i = i + 1, equals moving the data from the memory to the CPU’s registers, asking the CPU to perform the addition, and moving the data from the registers to the memory to update the memory cell occupied by i. The while loop corresponds to how a physical computer uses branch and jump instructions to execute instructions repeatedly so long as the condition is still valid.

Its pairing with the Von Neumann architecture makes the imperative programming paradigm quite limited when it comes to forming abstractions and compositions when constructing programs.

Functional programming can do better

Let’s use the functional programming paradigm to calculate the sum of squares of the first n numbers and compare the functional version with the imperative one.

The imperative program (left column) is just a sequence of low-level statements for updating variables rather than constructed from simpler parts. The loop is a single unit and cannot be broken into smaller components. In contrast, the functional program (right column) is built from reusable parts. Only the functions — square, addition (+), and the initial value 0 — are specific to this program. The rest is assembled from general-purpose components, such as map, fold, and function composition. In particular, map applies a given function to all list elements, whereas fold combines elements in a list using a function, starting from an initial value. The function composition operator, ., allows us to turn the output of one function into the input of another one.

In fact, we can view the functional program above as a dataflow program that emphasizes the composability of this solution.

Another critical difference is that the program on the left column is imperative, while the right one is descriptive. More specifically, the imperative program contains a sequence of commands stating how to initialize variables and update them in each step. The downside is we must mentally execute it to understand what it does, which requires a higher cognitive load. The functional program is declarative because it describes what the program does rather than how each step is computed. We can grasp the program based on its structure in one fell swoop without mentally executing it.

Now assume we would like to write another program that computes the sum of squares of only prime numbers between 1 and n. Using the imperative style, we can copy the code of the old program and add an if statement.

int sum = 0; i = 0;
while (i <= n) {
   i = i + 1;
   if (isPrime(i)) {
      sum = sum + i * i;
   }
}

Here, we assume isPrime is a method that returns true if the argument is a prime and returns false otherwise.

However, in the functional programming paradigm, the solution is much more elegant.

(fold (+) 0 . map square . filter isPrime) [1..n];;

Compared to the imperative version, this program has a higher degree of composability, with functions readily combined into more powerful constructs. Here, we plug in another general-purpose function called filter to choose prime numbers from the list before passing them to map and then fold.

Let’s look at the data flow diagram below:

It is important to emphasize that it’s by no means the purpose of this comparison to show that functional programming is better than imperative programming. As with any tool, way of thinking, or method of solving problems, each programming paradigm is more suitable for particular situations and less for others. Developing an intuition to decide when to use what tool and method is part of becoming an expert in any field, including programming. This course aims to help us develop this intuition so that we’ll know when to utilize the power of functional programming and when not to.