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.
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.
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
Tail Call Recursion
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.