The Design of Functional Programs

Article Wednesday, December 12 2018

Functional programming can provide an excellent alternative for developers looking to write bug-free, scalable code. In this episode of Software Engineering Daily, we spoke with Runar Bjarnason to learn more about functional programming and how to apply it in our own day-to-day work.

What is functional programming in the purest sense?

Functional programming refers to programming computers where functions serve as the primary mechanism for manipulating data. A function is said to be pure when it takes inputs, manipulates those inputs, and returns output, all without having to store some temporary or external state. This state is known as a side effect. An example is having to write to disk in order to store some data. Purely functional programming provides a guarantee inputs will always lead to predictable outputs.

Composition and modularity in functional programming

Composition is the concept that you can construct a program by layering functions. In other words, your program represents, at a high level, a single expression that can be broken down, or composed, into a series of sub-expressions via functions.

Modularity refers to the idea that you can take a program apart into modules. Those modules can be reassembled and rearranged to modify or augment your program. Since all functions in functional programming provide contracts about the inputs provided and the outputs offered, you never worry about an incomplete “circuit” in your composed expression.

Think of modularity like a puzzle, where functions are the puzzle pieces on the table. Your bottom-left corner piece may connect with 3 different pieces to the right of it but only one will make sense in the context of the whole puzzle you’re trying to build. A different piece will lead to building a different puzzle when the rest of the puzzle pieces are chained together to form a complete picture.

Referential transparency: expressions and no side effects

Referential transparency is when an expression doesn’t have any side effects. An example is as simple as 1+1. The expression always evaluates to 2 regardless of when you call it, where you call it from, or how you call it. In fact, one way to test for referential transparency is to swap your function call with the expression inside of that function and it should still work.

No side effects sounds great but how can this possibly work in a computer when everything boils down to inputs and outputs? How do you handle I/O operations?

Handling I/O in functional programming

Contrary to what you might think, functional programming perfectly complements the way a computer handles I/O; a computer normally offers an I/O system that expects to be called back. In a language like Haskell, for example, the main function that starts a program provides an I/O module as one of the argument inputs. Think of a program using functional programming as a black box for I/O: Send the I/O runtime to the program, manipulate some data inside of the program, and send that data to the runtime environment where the I/O system can write to disk.

Immutable I/O

Since I/O happens outside of our program and we are trying to minimize side effects, it helps to use data structures that are immutable. Immutability refers to data structures that cannot be changed. In functional programming, we don’t change objects in our functions, we pass them into other functions to be manipulated. Immutability is important because it helps preserve the ability to compose things.

The most basic data structure we work with in functional programming is the linked list. Linked lists are superior to arrays since they’re sequential and recursive. For performance reasons, some higher-level data structures may be composed of immutable arrays under the hood and implement functions to make them referentially transparent. One example would be Scala’s Vector structure, an immutable data structure by design but under the hood is just blocks of memory as represented as arrays.

One example of operating on immutable data structures is iterating over a list. In object-oriented programming we would use a for loop. A for loop doesn’t work in purely functional programming because we need to provide a mutable counter to increment against the index of where we are in the list as we traverse it.

Instead, functional programming offers an alternative function: fold. Fold, also known as reduce, inject, or accumulate, takes in an initial condition for a list and uses recursion to traverse the list.

Recursion is a concept in programming referring to the ability for a function to call itself. Recursion allows us to apply iteration over and over again by using the rest of the list as the input back into the function we are using to iterate over our list. These kinds of functions that accept functions as arguments are also known as higher-order functions. When the inputs do not specify a type, and instead offer the freedom to work against any type, they are called polymorphic functions. Fold is an example of a polymorphic, higher-order function. Other examples include map and filter (you can read more about them here).

Performance implications of recursion

Lots of functions equal lots of garbage to be collected on the stack. And lots of functions growing on the stack without bound lead to stack overflow. One common example of this would be asking for the Fibonacci sequence of a large number like 100. With so much recursion required in that function, you can quickly eat up the stack with all of those recursive calls and trigger a stack overflow exception.

Luckily, we can mitigate these problems by optimizing recursion with iteration. Scala, for example, knows how to convert recursive calls into iterative calls with while loops. If you’ve ever been asked to implement a depth-first search, you might have been asked to implement both the recursive and iterative versions of that algorithm. This exercise illustrates exactly what the Scala optimizer does in that all recursive expressions can be rewritten as iterative expressions as well.

Exceptions and the option pattern

Another common paradigm in object-oriented programming that doesn’t quite work in functional programming involves working with exceptions. Throwing exceptions in a function breaks functional programming because throwing an error isn’t the same as returning a value.

Instead, you should return a different value like Option (also known as Maybe) to provide an alternative return type (like Nothing or None), which is essentially like a blank version of the type you are working with. If you’re interested in learning more about this pattern in-depth, check out this article for more information.

Why would I want to use this over something like null which my language already has?

Null is like a universal keyword for “no element” across all types. The Option pattern, by contrast, is like creating an instance of a class and explicitly filling out everything with all empty values. You can then stack this with another pattern called Either for error handling so you can return either something of the type you want (which can be an Option in the event it returns an empty value) or something else like an error class.

Restriction = expression

With all of these rules and constraints imposed on functional programming, you might be wondering how such restriction can possibly allow for interesting and useful programs. Bjarnason states many times that “doing less means you can reason more about what functions will do.” In other words, limitations lead to more understandable code especially as your code grows. When you have over thousands of lines of code, it’s so much easier to understand the whole system with fewer, stricter rules.

When you have side effects, you don’t really know what the code is going to do without reading the entire source code to reason about how the state could possibly evolve in all scenarios. Instead, with pure functional programming, the scope of what you have to learn in any given moment revolves solely around the function you are looking at. This vastly simplifies the effort required to understand what you need to know in any given moment.

This simplicity also leads to higher levels of abstraction. Abstraction is about going to a higher semantic level of understanding while also being more precise about what you are defining. An example of abstraction would be the identity function. The identity function is just a mathematical function whose input is the output. This may seem like a trivial, even silly, function, but it serves to illustrate an important set of qualities.

The identity function is not constrained, which is to say that it doesn’t restrict the types of inputs, which makes it polymorphic. Because it works for all types of data, it is the kind of function that only needs to be implemented once. The identity function is a precise specification of returning the input argument as a value. This means that the realm of implementations shrinks down to one, but applications of the function grow to all types. This is what we mean when we speak of how functional programming leads to higher levels of abstraction.

Practicing functional programming & closing thoughts

Bjarnason has written a book called Functional Programming in Scala. All of the concepts we discussed today are covered in the book, plus many more. One of the great features of this book is how interactive it is. Trying to learn functional programming can be tough, but it becomes much easier when you can instantly apply the concepts you learn. Bjarnason designed the book to be interactive with lots of practice problems to solidify your learning.

Functional programming is not better or worse than object-oriented programming, but it does offer some strengths that should not be ignored. A world with more functional programs is a world with more composable software that isn’t coupled with the other parts. Composable, modular software can be mixed and matched to create infinite customization and scalability to a user’s exact needs. Functional software is software without side effects, and software without side effects affords fewer bugs to creep in. If you haven’t given functional programming an honest effort, pick up Bjarnason’s book and try something new!

In addition check out our episodes on functional programming and their languages