Functional Programming - the True Silver Bullet.
Many programming paradigms have come and gone. Is Functional Programming here to stay? Or is it just another fad?
Most things in the world of programming are simply tools. Programming languages are tools. Frameworks and libraries are tools. Even programming paradigms like Object Oriented Programming are also tools.
Functional Programming has been becoming more and more popular in the recent years. Where does it fit in the picture? Is it simply another tool, or something much bigger? Perhaps even a silver bullet that will solve all of our problems?
Let’s find out!
What is a silver bullet?
What is the definition of a silver bullet? It is something that can be used to solve all of our problems. Is mathematics a silver bullet? If anything, it comes very close to being a silver bullet.
We owe it to the thousands of extremely intelligent men and women who worked hard for millennia to give us mathematics. Euclid, Pythagoras, Archimedes, Isaac Newton, Leonhard Euler, Alonzo Church, and many many others.
It is extremely fortunate that mathematics is extremely predictable. 2 + 2 will always be equal to 4, no matter what.
Our world wouldn’t go very far if something unpredictable was used as the backbone of science. What if 2 + 2 would mostly result in 4, but also sometimes would result in 3, other times in 1000? What would happen if 2 + 2 would blow up (i. e. cause an exception), once in a while?
We’d probably still stay in the middle ages. Something similar has actually happened in the world of medicine — in the past there were no rigorous trials to confirm the efficacy of a particular treatment or medication. People relied on the opinion of doctors to treat their health problems (which unfortunately still happens in countries like Russia). In the past, ineffective techniques like bloodletting have been popular. Something as unsafe as arsenic was widely used.
Would it be useful for software to be predictable? Most certainly!
Yet unfortunately, the software industry of today is way too similar to the medicine of the past. As unfortunate as it sounds, simple things like calling a function to add 2 + 2, might once in a while give a wrong result, or crash the program entirely.
What makes software this bad? Why can’t it be more reliable?
In order for software to be reliable, it has to be predictable. Just like the addition function 2 + 2 in mathematics. And how do we create software that is predictable?
We should avoid nondeterminism.
— Wikipedia article on Nondeterministic Algorithms
Let’s take a look at a code sample that simply calls a function:
We don’t know what the function does, but it seems that the function always returns the same output, given the same input. Now let’s take a look at another example that calls another function,
This time, the function has returned different values for the same input. What is the difference between the two? The former function always produces the same output, given the same input, just like functions in mathematics. In other words, the function is deterministic. The latter function may produce the expected value, but this is not guaranteed. Or in other words, the function is nondeterministic.
What makes a function deterministic or nondeterministic?
- A function that does not depend on external state is 100% deterministic.
- A function that only calls other deterministic functions is deterministic.
In the above example,
computea is deterministic, and will always give the same output, given the same input. Because its output depends only on its argument
On the other hand,
computeb is nondeterministic because it calls another nondeterministic function
Math.random(). How do we know that
Math.random() is nondeterministic? Internally, it depends on system time (external state) to calculate the random value. It also takes no arguments — a dead giveaway of a function that depends on external state.
What does determinism have to do with predictability?
Deterministic code is predictable code. Nondeterministic code is unpredictable code.
Determinism vs Nondeterminism
(Or Predictability vs Unpredictability)
Let’s take a look at an addition function:
We can always be sure, that given the input of
(2, 2) , the result will always be equal to
4 . How can we be so sure? In most programming languages, the
addition operation is implemented on the hardware, in other words, the CPU is responsible for the result of the computation to always remain the same. Unless we’re dealing with the comparison of floating-point numbers, (but that is a different story, unrelated to the problem of nondeterminism). For now, let’s focus on integers. The hardware is extremely reliable, and it is safe to assume that the result of addition on the hardware will always be correct.
Now, let’s box the value of
So far so good, the function is deterministic!
Let’s now make a small change to the body of the function:
What happened? Suddenly the result of the function is no longer predictable! It worked fine the first time, but on every subsequent run, its result started getting more and more unpredictable. In other words, the function is no longer deterministic.
Why did it suddenly become non-deterministic? The function has caused a side effect by modifying a value outside of its scope. The function has modified its argument
A deterministic program guarantees that
2+2==4 . In other words, given an input of
(2, 2) , the function
add , should always result in the output of
4 . No matter how many times you call the function, no matter whether or not you call the function in parallel, and no matter what the world outside of the function looks like.
Nondeterministic programs are the exact opposite. In most of the cases, the call to
add(2, 2) will return
4 . But once in a while, the function might return 3, 5, or even 1004. Nondeterminism is highly undesirable in programs, I hope you can now understand why.
What are the consequences of nondeterministic code? Software defects, or as they are more commonly referred to as “bugs”. Bugs make the developers waste precious time debugging, and significantly degrade the customer experience if they made their way into production.
To make our programs more reliable, we should first and foremost address the issues of nondeterminism.
Is functional programming deterministic?
Functional programming encourages the use of pure functions, which are 100% deterministic.
Other programming paradigms have no such focus on function purity, which means that there can be no guarantees about the code being deterministic (and predictable).
In other words, pure Functional Programming is probably the only programming paradigm that is 100% predictable.
Avoid mutable state
How do we make our code deterministic? By avoiding mutable state.
Mutable state is something that you probably are using unknowingly day to day.
Let’s take a quick detour, and talk about the early days of computer science.
In the past, the
goto statement was widely used in programming languages, before the advent of procedures/functions. The
goto statement simply allowed the program to jump to any part of the code during execution. This made it really hard for developers to answer the question “how did I get to this point of execution?”. And yes, this has caused a large number of bugs.
A very similar problem is happening nowadays. Only this time the difficult question is “how did I get to this state” instead of “how did I get to this point of execution”.
Let’s take a look at another example:
Line 11 prints:
Before: [3, 5, 4, 1, 2, 9].
Line 15 prints:
After: . With no numbers in sight.
Surprised? This is mutable state in action.
Here’s the implementation of
joinNumbers used above.
numbers.shift method on line 4 has actually mutated the
numbers array that was passed in. The
numbers.shift method returns the first element in the array and actually removes the value from the original array, leaving the array empty at the end.
Such a bug might not be that hard to catch in a simple program. However, as programs grow bigger, as their state gets more complex, debugging becomes much more complicated.
The need for discipline
Mutable state can rightfully be called an “undisciplined approach to state management.”
This is one of the reasons for the growing popularity of state-management libraries, like Redux. However, one has to be skilled and disciplined to properly use such tools. I’ve seen cases where Redux has been used improperly, effectively rendering the tool useless.
Embrace immutable state
To drive the point home, mutable state is an undisciplined approach to state management. Yes, mutable state, indeed, is the
goto of state. Just like
goto, it’s an undisciplined approach to managing program flow. Mutable state is the same problem that plagued our programs decades ago — only this time we’re dealing with state instead of code.
Most of us are trying hard to answer the complex question of “how did I get to this state” instead of the same older question “how did I get to this point of execution”.
We really should be spending our time solving real problems and delivering value instead of trying to answer the unnecessary questions.
Immutable state is a very simple idea. Functions can only return new values and can never change the values that were passed in.
Programming with immutable values nowadays is becoming more and more popular. Even modern UI libraries like
React are intended to be used with immutable values. Languages with first-class support for immutable data values will be ranked higher simply because immutability eliminates a whole category of bugs from our code.
OK, but what’s immutable state exactly? Simply put, it’s data that doesn’t change — just like strings in most programming languages. For example, capitalizing a string will never change the original string. A new string will always be returned instead.
Nothing changed, nothing shared. Ever.
Immutability takes this idea further and makes sure that nothing is ever changed. A new array will always be returned instead of changing the original one. Updating the user’s name? A new user object will be returned with its name updated, leaving the original one intact.
With immutable state, nothing is shared; therefore, we no longer have to worry about the complexity of thread safety. Immutability makes our code easy to parallelize.
Functions that don’t mutate (change) any state are called pure and are significantly easier to test and reason about. When working with pure functions, we never have to worry about anything outside of the function. Just focus on this one function you’re working with, and forget about everything else. You can probably imagine how much easier development becomes.
I’ll cover pure functions in more depth later in this article.
Example with immutable state
Let’s rewrite the example from the previous section using immutable state.
array.sort should return a new array, instead of sorting the original array in place. Same goes for the
joinNumbers function, which should make a copy of the original array, before making any changes:
And, indeed, this approach produces the expected result:
Before: [3, 5, 4, 1, 2, 9]
After: [1, 2, 3, 4, 5, 9]
In fact, you’ve already encountered the idea of immutable state in other languages. Strings are immutable in most programming languages.
string.toUpperCase() won’t change the original string — it’ll always return a new string. Working with strings would’ve been terrible had they defaulted to mutating the string in place.
Working with numbers is also immutable. The addition function, as in
2+2, can be thought of as
add(a, b). It doesn’t mutate the original numbers — it simply returns a new number that’s the sum of the values that were passed in.
Advantages of immutable state
Immutable state has numerous advantages over mutable state:
- Programs become easier to reason about (there’s no need to worry about the objects changing over time)
- Concurrency: Immutable data is great for sharing information between multiple threads. Concurrent software and immutable state is a match made in heaven.
- Chaining: Operations on immutable data are easy to chain — e.g.,
"a" + "b" + "c"can be thought of as (
"a" + "b") + "c" == "ab" + "c". This is only possible because the
+operator is immutable and is guaranteed to always return a new string without having any side effects — and without changing the original string.
- Predictable: Immutable data can’t be modified, which means that its state is very predictable — always the same
- Comparison: Instead of performing an expensive deep-equality comparison of two data structures, we can simply compare their hashes, which is nearly instantaneous
- Testing: Functions using immutable data structures are extremely easy to test since they typically have no side effects
Disadvantages of immutable state
You may have noticed that with immutable state, we create a brand new copy of some data structure on every single change. Imagine copying over an array of over 100,000 items over and over again — that must be slow, right? Isn’t this wasteful?
Yes, it is.
That’s why functional programming languages make use of a concept called persistent data structures. This simply means that whenever a change is being made, we don’t have to create a deep copy of the entire data structure.
Instead of creating a copy, persistent data structures simply reuse a reference to the older data structure, while adding in the desired changes.
Persistent data structures
Here’s how a persistent binary tree might be implemented:
Whenever making changes to the
xs tree, the original tree is never modified. Instead, a new tree
ys is created. This tree has its own modified root node
d', which links to the
b node of the original
xs tree. The
e nodes are different in the new
ys tree — however, it still reuses the
h node from the original
Unfortunately, mainstream programming languages typically don’t have built-in support for proper persistent data structures. While solutions using libraries like Redux and Immutable.js are acceptable, it’s preferable to have proper state-management features (e.g., immutable data structures) built into the language. For a list of great (and not-so-great) programming languages, read “These Modern Programming Languages Will Make You Suffer.”
No discussion of Functional Programming is complete without mentioning concurrency.
We’ve reached the end of Moore’s law: Processors aren’t getting any faster. We live in the era of multi-core CPUs. Any modern application has to take advantage of multiple cores.
Unfortunately, most of the programming languages in use today were created in the era of single-core computing and simply don’t have the features to effectively run on multiple cores.
Libraries that help with concurrency are an afterthought — they simply add Band-Aids to languages that weren’t initially designed for concurrency. This doesn’t really count as good developer experience.
What do we need to help writing concurrent applications, while avoiding race conditions? Immutable state!
And thankfully, Functional Programming is fully built upon immutable state, which makes it a great fit for building concurrent programs.
Avoiding nulls — the billion dollar mistake
Having discussed mutable vs immutable state, let’s talk about nulls, the “billion dollar mistake”.
“I call it my billion-dollar mistake. It was the invention of the null reference in 1965. At that time, I was designing the first comprehensive type system for references in an object oriented language. My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I couldn’t resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years.”
— Tony Hoare, the inventor of null references
Simply put, nulls are a terrible way to handle missing values. Null references have been called a “billion-dollar mistake” by Tony Hoare, the person who has invented them.
Why are null references bad? Null references break type systems. When null is the default value, we can no longer rely on the compiler to check the validity of the code. Any nullable value is a bomb waiting to explode. What if we attempt to use the value that we didn’t think might be null but is, in fact, null? We get a runtime exception.
We have to rely on manual runtime checks to make sure the value we’re dealing with isn’t null. Even in a statically typed language, null references take away many benefits of a type system.
Such runtime checks (sometimes called null guards) in reality are workarounds for bad language design. They litter our code with boilerplate. And worst of all, there are no guarantees we won’t forget to check for null.
Functional programming provides a solid alternative to nulls. It encourages the use of an
Option pattern, which forces the developer to explicitly check for a value that may not be present. Even better, functional programming languages type-check the lack or presence of a value at compile time. Typically, the
Option pattern is used:
Catching exceptions isn’t a good way to handle errors. Throwing exceptions is fine — but only in exceptional circumstances, like when the program has no way to recover and has to crash. Just like nulls, exceptions break the type system.
When exceptions are used as a primary way of error handling, it’s impossible to know whether a function will return an expected value or blow up. Functions throwing exceptions are also impossible to compose.
Obviously, it’s not OK for an entire application to crash simply because we couldn’t fetch some data. Yet, more often than we’d like to admit, this is what happens.
One option is to manually check for raised exceptions, but this approach is fragile (we may forget to check for an exception) and adds a lot of noise:
Functional programming generally discourages the use of exceptions. Instead, the
Result pattern is used (which allows for possible errors to be type-checked at compile time):
Programming with pure functions
No discussion of Functional Programming is ever complete without talking about pure functions.
What’s a pure function? The idea is very simple — a pure function will always return the same output, given the same input. For example,
2 + 2 will always return
4, which means that the addition operator,
+, is a pure function.
Pure functions aren’t allowed to interact with the outside world (through making API calls or even writing to the console). They’re not even allowed to change state.
One can easily tell pure functions from impure functions — does the function take no arguments or return no value? Then it’s an impure function.
Here’s an example of a few impure functions:
And a couple of pure functions:
Such an approach may seem to be very limiting and can take some time getting used to. It certainly was confusing for me at first!
What are the benefits of pure functions? They’re very easy to test (no need for mocks and stubs). Reasoning about pure functions is easy — there’s no need to keep in mind the entire application state. You only need to worry about the current function you’re working with.
Pure functions can be composed easily. Pure functions are great for concurrency since no state is shared between functions. Refactoring pure functions is pure joy (pun intended) — just copy and paste, no need for complex IDE tooling.
Functional programming encourages the use of pure functions — it’s good when more than 90% of the code base consists of pure functions. Some languages take this to an extreme and disallow nonpure functions altogether (not always a great idea).
Algebraic data types
What are Algebraic Data Types? They’re a Functional Programming feature and are a powerful way of modeling application state. One can think of them as Enums on steroids. We specify the possible “subtypes” that our type can be composed of, along with its constructor parameters:
shape above can be either a
Rectangle, or a
Square constructor takes a single
int parameter (width),
Rectangle takes two
intparameters (width and height), and
Circle takes a single
int parameter (its radius).
Functional Programming has another great feature, called pattern matching. In general, pattern matching allows one to write very expressive code.
Here’s an example of pattern matching on an
Here’s the same code, without pattern matching:
No doubt, the pattern matching version is much more expressive and clean.
Pattern matching also provides compile-time exhaustiveness guarantees, meaning that we won’t forget to check for a possible case. No such guarantees are given in non-functional languages.
Is Functional Programming a silver bullet?
This brings us to the main question of this article. Is Functional Programming a silver bullet?
Once again, what is the definition of a silver bullet? Something that can be used to solve all of our problems. Is mathematics a silver bullet? If anything, it comes very close to being a silver bullet. Mathematics is beyond being predictable, mathematics is the very definition of predictability.
Many mathematical concepts translate directly to programming, and lay the foundation of Functional Programming.
This makes Functional Programming the mathematics of programming — an extremely solid and robust foundation, that can be used to build solid and robust programs. What makes it so robust? It is based upon mathematics, Lambda Calculus in particular.
Its core building block is a function, in most cases a pure function. Pure functions are deterministic, which makes them predictable. This means that programs composed of pure functions will be predictable. Will they always be bug-free? No, but if there’s a bug in the program, it will be deterministic as well — the same bug will always occur for the same inputs, which makes it easier to fix.
Apart from being predictable, Functional Programming is great for writing concurrent software. It offers solid alternatives to null references, and great ways to handle errors. On top of that, it offers cool features like pattern matching that makes our lives much easier.
In short, Functional programming combines the best ideas from computer science to make developers more productive, while enabling us to write robust and scalable software.
Is Functional Programming a silver bullet? Yes, it comes very very close to being one.
For a fun comparison of Functional Programming with Object Oriented Programming, make sure to read Functional Programming? Don’t Even Bother, It’s a Silly Toy (a satire).
For an ultimate rating of modern (functional and non-functional) programming languages make sure to read These Modern Programming Languages Will Make You Suffer.