Mindshift: Part 1

What's the Difference Between the Imperative and Functional Styles of Programming?

This blog is the first in a series (of unknown length) about how you need to rearrange your thought processes in order to move from the imperative style of programming to the functional style.

I must point out that I am not against the imperative programming style per se, but I strongly believe that if we are going to write software that:

  • Takes full advantage of the processing power available in the now ubiquitous multi-core CPU
  • Demonstrates true elastic scalability
  • Is highly resilient to software, hardware and communication failure

then we must learn a new way of thinking because imperative programming has demonstrated that it really does not equip us with the correct tools to tackle these new challenges.

See also my earlier blog for a fuller explanation of why this shift of thought is both necessary and challenging.

Schools of Thought in Programming

In broad terms, the world of computer programming is split into various, overlapping schools of thought. These schools of thought differ primarily on the priority they assign to different aspects of software design.

The (very incomplete) diagram below shows two of the main schools of thought in programming and some of their more widely known subdivisions.

The divisions between these categories are not hard and fast, and some languages such as ABAP and JavaScript can belong to multiple categories.

Missing the Point of Why Functional Programming is Beneficial

In his 1990 paper Why Functional Programming Matters, John Hughes lays out a clear and persuasive argument for why the functional approach to programming offers genuine benefits to any and all programmers - not simply those who specialise in the abstract and obscure theories of computation.

However, he makes the excellent point that so often the features of functional programming that are presented as advantages, are exactly the things that put people off wanting to adopt this programming paradigm!

Saying things like, functional programming:

  • Has either single-assignment variables or no variables at all
  • Uses pure functions and therefore function execution cannot create any side-effects
  • Has no flow control primitives such as if or switch or goto.

These points are all true, but holding them up as the "must have" advantages of this programming paradigm has all the marketing appeal of a medieval monk denying himself the pleasures of life in order to become virtuous. They are all negative statements that in themselves, have no direct benefit.

Pardon my bluntness, but if you base the advantages of functional programming on points such as these, then do not be surprised if people simply roll their eyes and walk away...

The above features, whilst perfectly true, do not create a yardstick by which program quality can be measured. The point that has been missed here is that functional programming requires you to structure your code in terms of modular units that can be strongly reasoned about.

This strength of reasoning then leads to a greatly increased confidence that the program you've written is actually correct.

Modular design is the key to successful programming, and building your program from modular units that can be reasoned about with confidence, leads to robust software solutions.

The only remaining question is this: "Once I've broken my problem down into these modular units, how do I glue them back together again?".

In Object Oriented programming, your modular unit is the class, and the glue is features like, inheritance, subclassing and interface implementation etc.

In Functional Programming, the modular unit is the function and the glue is two specific features known as function composition and laziness.

The Böhm-Jacopini Theorem

Irrespective of the programming language or style you might use, all instructions in all computer programs can be viewed as some combination of three basic control structures:

  • Sequence: A simple sequence of “do this, then this, followed by that…”
  • Selection: Alters the instruction flow based on the outcome of a condition
  • Iteration: Performs a task multiple times until some termination condition is reached

The major differences between the imperative and functional style of programming lie in how you arrange the statements of your program within these three control structures.

Imperative Programming

Do exactly this and do it now!

The imperative programming school of thought is by far the most widely used style of coding and is implicitly assumed to be the “normal” way to program a computer.

This style of programming arose from the computer hardware architecture defined by John von Neumann in 1945 and is best suited to situations in which a known computation must be performed on a predictable dataset.

In this style of coding, the programmer is focused primarily on:

  • Transforming the computer’s state (I.E. the data in memory) by means of a precisely defined set of instructions.
  • Making explicit use of beneficial side-effects to achieve the desired result:
    • The use of global or shared memory as the repository for the evolving state of the data
    • Preserving the data in memory in some persistent store (E.G a database)
    • Interacting with peripheral devices (printer, network, camera, accelerometer etc)

Focusing on “How” and “When”

Although imperative programming is a broad term that includes many other styles of coding (E.G. procedural, modular, object oriented etc.), the programmer’s job is essentially this:

To craft a precise sequence of instructions whose side-effects modify the computer’s state in the desired manner

Something like this:

A consequence of this style of programming is that it creates a mindset among developers in which they focus very strongly on:

  • The time-line of the instructions they're writing. This is because each instruction results in a side-effect critical for that particular stage of the processing.
  • Consequently, the mechanics of how the program should arrive at the required solution is critically dependent upon the order in which the instructions are performed.

Here, we can see that the how and the when of statement execution are two sides of the same coin and lead to the understanding that imperative programming is really side-effect oriented programming.

Böhm-Jacopini's Theorem in Imperative Programming

  • Sequence: A set of instructions whose execution order is explicitly defined
  • Selection: Implemented using statements such as if or switch or case that modify the instruction flow based on the outcome of an explicitly defined condition
  • Iteration: Implemented using constructs such as do/while or for loops

Functional Programming

Focusing on “What”

In functional programming however, there is a very different focus. As much as possible, functional programming languages emphasise what a program should accomplish and are less concerned with exactly how that objective is achieved.

Functional programming is focused on:

  • Understanding and then defining the set of functions needed to transform the input data into the output data
  • Writing functions that follow (as closely as possible) the principle of Referential Transparency. This means that each function is structured such that it:
    • Receives one or more parameters
    • Is (as much as possible) free from side-effects. I.E. the return value is derived only from the values received as parameters.
    • Always returns a result back to the calling function - where that result might well be another function. If no return value is needed, then some languages like Scala use a special return type called Unit.
    • Is (as much as possible) idempotent. That is, if the same arguments are passed to the same function multiple times, then you always get back exactly the same result.

There are certain, perfectly valid situations however in which side-effects are required (such as interacting with persistent storage, the network, or a peripheral device).  Depending on your choice of functional programming language, these situations are either handled explicitly by special language constructs, or as Monads.

Böhm-Jacopini's Theorem in Functional Programming

  • Sequence: A set of instructions whose execution order is explicitly defined. Usually, such sequences of instructions are encapsulated within a function.
  • Selection: Often implemented implicitly by the language runtime using pattern matching, rather than by the developer needing to code an explicit condition such as if or switch or case
  • Iteration: Handled implicitly by means of functions such as map, reduce and flatMap, or by recursion.

Comparing the Two Styles

Here's a little program to calculate the factorial of a number written in both the imperative and functional styles.

Imperative style

This is perfectly correct, but it contains lots of extra coding needed to manage a loop: the while construct and the management of a loop index variable called n. But this is par for the course when using the imperative style.

Functional style

I could have used JavaScript here, but JavaScript does not have any intuitive way to create an array that is pre-populated with a range of integers. The following JavaScript code achieves this result, but its pretty abstract and where N is the upper bound of the range:

Array.apply(null, {length: N}).map(Number.call, Number)  

Well, enough of that silliness, here's the same function in the Clojure REPL:

user> (defn factorial [n] (reduce * (range n 0 -1)))  
user> (factorial 5)  

Notice the following important differences:

  • The entire function definition is a single line of code where defn factorial means "define a function called factorial"
  • The function takes a single parameter [n] that is used to define the upper bound of a range starting at n and going down to 0 in steps of -1.
  • The range function creates a list of values that are then reduced using the multiply (*) function. In other words, multiply together all the numbers you find in this list.
  • Where's the loop? There isn't one - or at least it is not defined with an explicit keyword. This is simply because I don't care how the program derives the required result. I have told it what I want it to do, and I am trusting that the reduce function knows how to do what I have asked.

So without having to care about any of the mechanics of looping or index counter management, we have achieved the required result by nesting one function call within another: create a range of numbers from n down to 1, then use the reduce function to multiply all of those numbers together.

One line of code. Thank you and good night...

Not only does style of programming make the code significantly simpler, it makes it far easier to reason about the correctness of the code.

Chris W

All source code from the Mindshift blog series can be found on GitHub