An Introduction to Thinking in a Functional Way

The Porsche 911 Turbo S has a front spoiler called a pneumatically dropped front lip. It works by reclining into the front bumper when the car is moving at low speeds and automatically deploying at high speeds when more drag is required to keep the car on the ground. This is how the car achieves stability at high speeds. The benefit is that when it is out of the way, it lends itself to a clean design, by not getting in the way of the beautiful swooping lines on the front bumper. I find this brilliant from a design perspective.I appreciate declarative programming in a similar manner, in what it affords the programmer: out of my way when not required, fully operational when it is required.Mainstream programming languages have been adopting functional programming axioms faster than an associate developer can spell functional programming. Which is all well and good, but an astute software developer should pose and reflect on why this is the case. It is turtles all the way down to invoke map, reduce and filter after a cursory introduction to functional programming, however, the calculus of negligence is high if the ethos of the axioms is not fully comprehended, as to appreciate them for what they bring to the table.To understand the benefits, let’s contrast functional programming to the more commonly used Object-Oriented Programming paradigm. To grasp the differences, we have to inspect the schools of thought from which the paradigms originate. Object-oriented programming flows from the imperative school of thought, where the main method of computation is assigning values to variables and manipulating them until they achieve the desired result. Conversely, in functional programming, the main method of computation is passing values to functions.To illustrate the concept, an example suffices:Suppose we want to find the sum of numbers from 1 to 10. In the imperative school of thought, a programmer could start assigning values to variables, creating something close to this (assuming JavaScript as a language):[pastacode lang="markup" manual="let%20total%20%3D%200%3B%0Afor%20(let%20x%20%3D%200%3B%20x%20%3C%3D%2010%3B%20x%2B%2B)%20%7B%0A%20%20%20total%20%2B%3D%20x%3B%0A%7D%0Aconsole.log(total)%20%2F%2F55" message="" highlight="" provider="manual"/]Decomposed into pseudo-code, it would probably read like this:1. Create a variable total2. Assign 0 as the initial value3. Compute the number using an iteration protocol of type for4. In the for-loop, define a variable x and assign it an initial value of zero5. On every subsequent iteration, check that the value of x does not exceed the max number6. Increment the variable x on every iteration by 17. Increment the total by assigning x to the current value of total on every iterationNotice that assignment is the main method of computation here, without which, it would be very hard to achieve effective computability. Furthermore, note that we not only specify the problem we want to solve (summing numbers 1 to 10), we also specify how we want the computer to do it (using assignment and iteration). This conflation of problem and solution is the bane of software engineering because it introduces variables that can be modified while being accessed by other sects of the program. This can lead to all sorts of problems.Now imagine that we want to solve the same problem using a functional mindset:[pastacode lang="markup" manual="%5B...Array(11).keys()%5D.reduce((a%2C%20b)%20%3D%3E%20a%20%2B%20b%2C%200)" message="" highlight="" provider="manual"/]Notice how succinct that code is. More importantly, notice how declarative (how the code lends itself to problem definition and solution) it is. If we were to decompose this to pseudo-code, it would read like this:1. Given a list of items 0 to 10 (I cheated because I am lazy to create the array values manually - blame it on being declarative)2. Reduce the items by summing them3. Start with an initial value of zeroIn essence, we have composed the steps from 7 down to 3, which is a good thing since the fewer mental hoops a developer has to skip when writing code the better. And therein lies the allure of functional programming, or at least thinking about solutions in a functional way.

Benefits of Functional Programming

What then, is the craze about functional programming? Let’s examine some of the benefits that functional programming affords a programmer.

Immutability

Remember we mentioned that the road of assignment is paved with gremlins all the way to hell (ok, I didn't say that but you get the gist). The raison d'etre for functional programming is immutability. Good functional programming languages avoid mutability or at least make it very hard to reassign variables, as the primary device of computation.Immutability simply means that once a value comes into existence, it cannot be changed (modified or otherwise). This property is what functional programmers call immutability. Let’s illustrate with an example:[pastacode lang="markup" manual="const%20duplicateBook%20%3D%20(bookData%2C%20bookList)%20%3D%3E%20%7B%0A%20%20%20%20let%20bookDataCopy%20%3D%20%7B%0A%20%20%20%20%20%20%20%20fname%3A%20bookData.fname%2C%0A%20%20%20%20%20%20%20%20lname%3A%20bookData.lname%2C%0A%20%20%20%20%20%20%20%20dateCreated%3A%20Date.now()%2C%0A%20%20%20%20%20%20%20%20metaData%3A%20bookData.metaData%2C%0A%20%20%20%20%7D%0A%20%20%20%20%2F%2F%20modify%20name%0A%20%20%20%20bookDataCopy.metaData.name%20%3D%20bookData.metaData.name%20%2B%20'%20'%20%2B%20Math.floor(Math.random()%20*%20(bookList.length%20%2B%201))%3B%0A%20%20%20%20return%20bookDataCopy%3B%0A%7D%0A" message="" highlight="" provider="manual"/]I have used the above code in a recent project. To the untrained eye averse to immutability, this code is good to go. It will probably pass a PR review, especially if it is backed up with unit tests. However, this innocuous-looking code has a major gremlin in it. Line 9 in the example code above inadvertently modifies the value of the name on the original book object. Why is this so? Because metaData is open to modification. Such subtle errors abound in code bases out there (it is a dangerous world after all), and they are hard to catch during a cursory code review.This is not possible in languages that do not support mutability via reassignment. At the very least, a new copy of metaData will be returned, and the original value will remain intact, unchanged.This idea is an extension of arithmetic. When was the last time anyone fretted over adding 2 numbers? Human beings have not invented a test-driven approach to arithmetic because they are sure that the numbers do not change. When we add 2 to 3, the arithmetic values do not magically transmogrify into 5, however, a new value of 5 comes into existence. But we are fully aware that 2 and 3 are immutable values waiting to be summoned the next time you need an arithmetic fix.Some programming languages like Clojure (a LISP) avoid the concept of assignment altogether by not even providing an assignment operator, the lack of which causes untold discomfort to imperative programmers when they encounter Clojure, but immense joy to functional programmers since it helps them avoid inadvertent modifications. However, imperative programmers do not have to worry because the same results can technically be achieved by using hygienic devices like recursion or reduce.To get around the warts of mutability, programming languages that support it differentiate between primitive types and mutable types. Usually, numbers, strings, and booleans are immutable, and all the other data types are mutable. Functional programming languages (at least the good ones) treat values the same way. In that way, they conform to the rights of values, in that they are all born equal. :)To some extent, some mainstream languages try to achieve the same thing through unnatural contraptions. Python and JavaScript have a freeze function that anesthetizes a mutable type and prevents further modifications on it. However, they also provide functionality for unfreezing the frozen value (cloning etc), in case you want to modify the data and lose all the benefits of immutability.Working in an environment that does not support immutability from the get-go leads to a sequestered approach to programming (by separating state and value), forcing developers to rely on mutating state by updating values in place, sometimes globally, to design solutions for effective computability.

Pure Functions

The pièce de résistance of functional programming is the ability to define pure functions. A function is pure if it conforms to two properties:1. Referential transparency: meaning that it returns the same result given the same arguments2. Zero side effects: It does not cause observable side effects out of its current scope.These two qualities make it a lot easier to reason about programs since they provide the machinery to isolate functions and their scope and make it hard for a function to do more than is necessary to achieve the desired result. The functions are stable and non-inscrutable, which is what programmers mean when they talk about code quality.

Referential Transparency

A function is referentially transparent when it returns the same result given the same arguments. It doesn’t rely on data outside the current function, and it doesn’t change data that exists outside the current function. Functional programming provides aids to support referential transparency. By only relying on function arguments and immutable values for computation, functions operate within a scope that guarantees that no observable unintentional side effects occur.As a way of illustration, here is a function that is not referentially transparent:[pastacode lang="markup" manual="const%20multiplier%20%3D%202%3B%20%0Afunction%20multiply(x)%20%7B%0A%20%20%20return%20x%20*%20multiplier%3B%0A%7D%0A" message="" highlight="" provider="manual"/]The above function is not referentially transparent because it relies on a global variable multiplier to accomplish its work. That global variable could be changed by another function, which would technically affect the correctness of the function.Modifying global variables also hurts purity:[pastacode lang="markup" manual="const%20total%20%3D%200%3B%0Afunction%20sum(x%2C%20x)%20%7B%0A%20%20%20total%20%3D%20x%20%2B%20x%3B%0A%20%20%20return%20total%3B%0A%7D%0A" message="" highlight="" provider="manual"/]This is a contrived example, but it illustrates the point. The function is modifying a global variable (or at least a variable outside of its scope) to accomplish its computational task. This side effect is observable outside of the function scope and thus hurts purity. This kind of programming should be avoided for pure functions like this:[pastacode lang="markup" manual="function%20multiply(x%2C%20multiplier)%20%7B%0A%20%20%20return%20x%20*%20multiplier%3B%0A%7D%0A" message="" highlight="" provider="manual"/]This function only relies on its arguments, plus it is easier to test and reason about since we can always change the multiplier, or even extend it to support additional multipliers through currying (a functional programming technique):[pastacode lang="markup" manual="function%20variableMultiplier(multiplier)%20%7B%0A%20%20%20return%20function(x)%20%7B%0A%20%20%20%20%20%20%20return%20x%20*%20multiplier%0A%20%20%20%7D%0A%7D%0A%0Alet%20square%20%3D%20variableMultiplier(2)%3B%0Aconsole.log(square(2))%20%2F%2F%204%0A" message="" highlight="" provider="manual"/]Using pure functions allows the programmer to rely on small isolated and contained functions that can be composed to create elegant solutions.

How to achieve mutability

This is where I sort of shot myself in the foot, but any sufficiently complex software program has to modify some data lest it is useless. In functional programming, this is achieved through recursion. Let's look at an example:[pastacode lang="markup" manual="let%20flights%20%3D%20%5B%7B%0A%20%20%20%20%20%20%20passengers%3A%2010%2C%0A%20%20%20%20%20%20%20flight_number%3A%201%0A%20%20%20%7D%2C%20%7B%0A%20%20%20%20%20%20%20passengers%3A%20210%2C%0A%20%20%20%20%20%20%20flight_number%3A%201%0A%20%20%20%7D%2C%20%7B%0A%20%20%20%20%20%20%20passengers%3A%20323%2C%0A%20%20%20%20%20%20%20flight_number%3A%202%0A%20%20%20%7D%2C%0A%5D%3B%0A" message="" highlight="" provider="manual"/]Suppose we want to find the total number of passengers that have flown on a given flight number, the quintessential way to do it would be:[pastacode lang="markup" manual="let%20total_passengers%20%3D%200%3B%0Aconst%20LEN%20%3D%20flights.length%3B%0Afor%20(let%20x%20%3D%200%3B%20x%20%3C%3D%20LEN%3B%20x%2B%2B)%20%7B%0A%20%20%20let%20flight%20%3D%20flights%5Bx%5D%3B%0A%20%20%20total_passengers%20%2B%3D%20flight.passengers%3B%0A%7D%0Aconsole.log(total_passengers(flights))%20%2F%2F%20543%0A" message="" highlight="" provider="manual"/]This works, but we are thinking imperatively, something we should avoid if we can help it. Instead of assigning values to variables, we can use the concealed scope of a function and achieve the same result using recursion:[pastacode lang="markup" manual="const%20total_passengers%20%3D%20(flights%2C%20total%20%3D%200)%20%3D%3E%20%7B%0A%20%20%20%20if%20(flights.length%20%3D%3D%3D%200)%20%7B%0A%20%20%20%20%20%20%20%20return%20total%3B%0A%20%20%20%20%7D%0A%20%20%20%20total%20%2B%3D%20flights.shift().passengers%3B%0A%20%20%20%20return%20total_passengers(flights%2C%20total)%3B%0A%7D%0Aconsole.log(total_passengers(flights))%20%2F%2F%20543%20" message="" highlight="" provider="manual"/]Notice how recursion handles assignment, iteration and scoping of the value being incremented. It has the added benefit of being elegant. But as much as recursion is elegant, the idiomatic way of achieving this in functional programming is through folding, also called reducing in some languages. In JavaScript, the same computation can be achieved by this code:[pastacode lang="markup" manual="const%20total_passengers%20%3D%20flights.reduce((total%2C%20flight)%20%3D%3E%20%7B%0A%20%20%20return%20total%20%2B%3D%20flight.passengers%3B%0A%7D%2C%200)%0Aconsole.log(total_passengers)%20%2F%2F%20543%0A%0A" message="" highlight="" provider="manual"/]By now, you notice that you do not need to mutate state, nor have global variables to achieve effective computability. Working with recursion or reduce makes the code easier to reason about because it is a self-contained unit that is pure. I admit that it takes getting used to, but once the mindset is set in, you will be reducing and recursing instead of iterating. There is the added benefit of your PRs looking cool.

Tail Call Recursion

Some people quip that you need tail call recursion (TCO) to achieve proper recursion. However, it is important to understand that tail call recursion is an optimization technique (under Tail Call Optimization) achieved at the compiler level, not a construct that the developer needs to understand to use recursion. JavaScript, python and a slew of mainstream programming languages do not support tail recursion, but programmers can use recursion in those languages. ECMAScript 6 has a proposal to implement tail call recursion, but it has not yet been adopted by all browsersAs long as there is a terminating condition that avoids infinite recursion, the compiler is happy to recurse until it reduces the value to your heart’s desire. And that is how mutation is achieved in functional programming.

Why Functional Programming Got a Slow Start

It is usually mentioned that, if functional programming is the best thing since sliced bread (it really is), why is it not mainstream, or at least as prevalent as other software programming paradigms. Like time slippage, the answer to this question depends on your vantage point of view. There are many reasons why this is the case, and I am unashamed to add to the pile.In an attempt to answer the above question, a historical perspective is in order:Euclid (325-265 BCE), defined what a computer is (as a person who executes an algorithm) in his work on Euclid elements. But a formal mathematical definition of an algorithm did not suffice until the 20th century, when three eponymous scholars independently formulated formal definitions in three subsequent papers: Alonzo Church (An Unsolvable Problem of Elementary Number Theory, May 1935), Kurt Gödel (General Recursive Functions of Natural Numbers, July 1935) and Alan Turing (On Computable Numbers, with Application to the Entscheidungsproblem, May 1936).For an algorithm to be valid in every structure satisfying the axioms, it has to decide whether a given statement is provable from the axioms. Thus, in 1928, David Hilbert and Wilhelm Ackermann defined the Entscheidungsproblem (Decision Problem), in which they sought an algorithm which when given a statement in formal logic will determine if the statement is true or false. Hilbert based his work on the assumption that logic is complete, meaning every provable statement is true and every true statement is provable.As long as academia held that there was a solution to the Entscheidungsproblem problem (Hilbert believed that there would be no such thing as an unsolvable problem until 1930), a formal definition of algorithms was not necessary. But if the goal was to show the undecidedness of the Entscheidungsproblem, then a formal definition of an algorithm was required, since it had to filter out the algorithms that would not prove the validity of a statement from its axioms.Kurt Gödel published his Incomplete Theorems that invalidated Hilbert's premise by proving that any logic powerful enough to represent arithmetic encoded the statement: This statement is not provable. Gödel achieved this using a novel numbering scheme called Gödel numbering, which he used to encode statements and proofs as numbers. In essence, this was the world's first functional program.May 1935 to May 1936 provided the formal mathematical and philosophical research requisite for the adoption of functional programming. Alonzo Church proposed his solution to the Entscheidungsproblem, when he came up with Lambda Calculus, and showed that it can express algorithms and to an extent show that the Entscheidungsproblem is undecidable, in his work on the proof of the undecidability of a problem.Lambda Calculus provides the foundation for functional programming:[pastacode lang="markup" manual="L%2C%20M%2C%20N%20%3A%3A%3D%20x%0A%20%20%20%20%20%20%20%7C%20%20(%CE%BBx.N)%0A%20%20%20%20%20%20%20%7C%20%20(L%20M)%0A" message="" highlight="" provider="manual"/]It has three constructs, variables (L, M, N), function definition and functional application. This was defined before computers became en vogue. Notice the structural similarity to functions in mainstream programming languages (or methods, for languages like Java). To date, lambdas have been added to python, Java and pretty much every mainstream programming language.Kurt Gödel later countered that Church's definition was unsatisfactory, and devised General Recursive functions as a rejoinder to Church. In doing so, Gödel inadvertently showed that both his definition and Church's were identical. This impasse was finally resolved when Alan Turing, whose doctoral supervisor was Alonzo Church, put forth his work on Turing machines and showed that if a Turing machine was the definition of an algorithm, then the Entscheidungsproblem was undecidable.Alan Turing provided the philosophical argument for adopting Kurt Gödel's research, which had demonstrated the inherent limitations of formal axiomatic systems performing arithmetic, which had in turn provided the logical framework to reason about the research of Alonzo Church, who had discovered Lambda Calculus. In essence, Alan provided a philosophical framework (as opposed to mathematics) for reasoning about algorithms by showing that anything a computer can do (by a computer we mean a person following a sequence of instructions), could be done by a Turing machine.Notice that three independent definitions (Kurt Gödel, Alonzo Church, and Alan Turing) of computing algorithms turned out to be equivalent, although they were put forth by different people. This is powerful evidence that good ideas are not invented, they are discovered. The same applies to functional programming.It certainly took a long time from Euclid to Alan Turing, but along the way, functional programming was born. And since it took quite a while to formalize Lambda Calculus (Alonzo Church "stumbled" upon it through discovery), it is plausible to conclude that functional programming had to follow a similar trajectory given that it takes time to discover good ideas, as opposed to inventing them.

Invention versus Discovery

Is mathematics invented or discovered?Paul Graham mentioned that good ideas take a long time to adopt (he suggests 30 years). For example, John McCarthy put forth the formalisms for garbage collection in his 1959 paper titled Recursive Functions Of Symbolic Expression and their Computation by Machine, as a way to automatically manage memory in LISP. However, it was not until 1996, when Java was released that garbage collection became a mainstream phenomenon. That is 37 years later for those counting. Almost all mainstream programming languages support garbage collection because it's benefits are self-evident.James Gosling did not invent garbage collection, rather, he discovered that John McCarthy had put forward a formal definition of the GC, and if implemented properly, could afford the John Doe programmer untold joys as they write code, as opposed to phantasms of calamity when they manage their own memory. It certainly eliminates the set of bugs that arise due to poor memory management.The TL;DR version is that functional programming, like mathematics, is a discovered idea that flows from Lambda Calculus. Philip Wadler said, "Many programmers use languages that are invented ...". Consider this post as an invitation to consider using languages that are discovered.A developer could start by looking at the LISP family of languages like Scheme or Clojure, since they are not dissimilar to Alonzo’s Lambda Calculus.