What is “Functional Programming”?

“Object-oriented programming makes code understandable by encapsulating moving parts. Functional programming makes code understandable by minimizing moving parts.”

Michael Feathers, author of
Working Effectively with Legacy Code
(via Twitter)

Defining “Functional Programming”

It’s surprisingly hard to find a consistent definition of functional programming. As just one example, some people say that functional programming (FP) is about writing pure functions — which is a good start — but then they add something else like, “The programming language must be lazy.” Really? Does a programming language really have to be lazy (non-strict) to be FP? (The correct answer is “no.”)

I share links to many definitions at the end of this lesson, but I think you can define FP with just two statements:

  1. FP is about writing software applications using only pure functions.
  2. When writing FP code you only use immutable values — val fields in Scala.

And when I say “only” in those sentences, I mean only.

You can combine those two statements into this simple definition:

Functional programming is a way of writing software applications using only pure functions and immutable values.

Of course that definition includes the term “pure functions,” which I haven’t defined yet, so let me fix that.

This post is sponsored by my new book,
Learn Functional Programming Without Fear.

A working definition of “pure function”

I provide a complete description of pure functions in the “Pure Functions” lesson, but for now, I just want to provide a simple working definition of the term.

A pure function can be defined like this:

  • The output of a pure function depends only on (a) its input parameters and (b) its internal algorithm.
    • This is unlike an OOP method, which can depend on other fields in the same class as the method.
  • A pure function has no side effects, meaning that it does not read anything from the outside world or write anything to the outside world.
    • It does not read from a file, web service, UI, or database, and does not write anything either.
  • As a result of those first two statements, if a pure function is called with an input parameter x an infinite number of times, it will always return the same result y.
    • For instance, any time a “string length” function is called with the string "Alvin", the result will always be 5.

As a few examples, Java and Scala functions like these are pure functions:

  • String uppercase and lowercase methods
  • List methods like max, min
  • Math.sin(a), Math.cos(a)

In fact, because the Java String class and Scala List class are both immutable, all of their methods act just like pure functions.

Even complex algorithms like checksums, encodings, and encryption algorithms follow these principles: given the same inputs an infinite number of times, they always return the same result.

Conversely, functions like these are not pure functions:

  • System.currentTimeMillis
  • Random class methods like next, nextInt
  • I/O methods in classes like File and HttpURLConnection that read and write data

The first two examples yield different results almost every time they are called, and I/O functions are impure because they have side effects — they communicate with the outside world to send and receive data.

Note 1: Higher-Order Functions are a great FP language feature

If you’re not familiar with the term Higher-Order Function (HOF), it basically means that (a) you can treat a function as a value (val) — just like you can treat a String as a value — and (b) you can pass that value into other functions.

In writing good FP code, you pass one function to another so often that I’m tempted to add HOFs as a requirement to my definition. But in the end, you can write FP code in languages that don’t support HOFs, including Java. Of course that will be painful and probably very verbose, but you can do it.

Therefore, I don’t include HOFs in my definition of functional programming. In the end, HOFs are a terrific FP language feature, and they make Scala a much better FP language than Java, but it’s still just a language feature, not a part of the core definition of functional programming.

Note: I provide a more complete HOF definition in the glossary at the end of this book.

Note 2: Recursion is a by-product

Sometimes you’ll see a definition of FP that states, “Recursion is a requirement of functional programming.” While it’s true that pure FP languages use recursion, the need for recursion is a by-product of my FP definition.

Once you dig into FP, you’ll see that if you only use pure functions and immutable values, the only way you can do things like “calculate the sum of a list” is by using recursion. Therefore, it’s a by-product of my definition, not a part of the definition.

(I discuss this more in the recursion lessons.)

Proof: Wikipedia’s FP definition

When you google “functional programming definition,” the first link that currently shows up is from Wikipedia, and their definition of FP backs up my statements. The first line of their definition begins like this:

“In computer science, functional programming is a programming paradigm — a style of building the structure and elements of computer programs — that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.”

So, yes, FP is made of (a) pure functions and (b) immutable data. (Their “mathematical functions” are equivalent to my pure functions.)

As proof for another assertion I made earlier, that Wikipedia page also elaborates on features that make an FP language easier to use — such as being able to treat functions as values — where they state, “Programming in a functional style can also be accomplished in languages that are not specifically designed for functional programming.” (Think Java.)

Proof: A wonderful quote from Mary Rose Cook

When I first started learning FP, I was aware that pure functions were important, but this point was really driven home when I came across an article titled A Practical Introduction to Functional Programming by Mary Rose Cook.

Ms. Cook used to work at the Recurse Center (formerly known as “Hacker School”) and now works at Makers Academy, and in her “Practical Introduction to FP” essay, she refers to using only pure functions as a Guide Rope to learning FP:

“When people talk about functional programming, they mention a dizzying number of ‘functional’ characteristics. They mention immutable data, first class functions, and tail call optimisation. These are language features that aid functional programming.”

“They mention mapping, reducing, pipelining, recursing, currying and the use of higher order functions. These are programming techniques used to write functional code.”

“They mention parallelization, lazy evaluation, and determinism. These are advantageous properties of functional programs.”

“Ignore all that. Functional code is characterised by one thing: the absence of side effects. It (a pure function) doesn’t rely on data outside the current function, and it doesn’t change data that exists outside the current function. Every other ‘functional’ thing can be derived from this property. Use it as a guide rope as you learn.”

When she writes about the “absence of side effects,” she’s referring to building applications from pure functions.

Her guide rope statement is so good, it bears repeating:

“Functional code is characterised by one thing: the absence of side effects.”

When I first read this quote, the little light bulb went on over my head and I began focusing even more on writing only pure functions.

If you think about it, this statement means exactly what I wrote at the beginning of this lesson:

Functional programming is a way of writing software applications using only pure functions and immutable values.

That’s great ... but why immutable values?

At this point you might be saying, “Okay, I buy the ‘pure functions’ portion of your definition, but what does immutable values have to do with this? Why can’t my variables be mutable, i.e., why can’t I use var?”

The best FP code is like algebra

I dig into this question in the “FP is Like Algebra” lesson, but the short answer here is this:

The best FP code is like algebra, and in algebra you never re-use variables. And not re-using variables has many benefits.

For example, in Scala/FP you write code that looks like this:

val a = f(x)
val b = g(a)
val c = h(b)

When you write simple expressions like this, both you and the compiler are free to rearrange the code. For instance, because a will always be exactly the same as f(x), you can replace a with f(x) at any point in your code.

The opposite of this is also true: a can always be replaced with f(x). Therefore, this equation:

val b = g(a)

is exactly the same as this equation:

val b = g(f(x))

Continuing along this line of thinking, because b is exactly equivalent to g(f(x)), you can also state c differently. This equation:

val c = h(b)

is exactly the same as this equation:

val c = h(g(f(x)))

From a programming perspective, knowing that you can always replace the immutable values a and b with their equivalent functions (and vice-versa) is extremely important. If a and b had been defined as var fields, I couldn’t make the substitutions that I did. That’s because with mutable variables you can’t be certain that later in your program a is still f(x), and b is still g(a). However, because the fields are immutable, you can make these algebraic substitutions.

FP code is easier to reason about

Furthermore, because a and b can never change, the code is easier to reason about.

With var fields you always have to have a background thread running in your brain, “Is a reassigned somewhere else? Keep an eye out for it.”

But with FP code you never have to think, “I wonder if a was reassigned anywhere?” That thought never comes to mind. a is the same as f(x), and that’s all there is to it, end of story. They are completely interchangeable, just like the algebra you knew in high school.

Another good reason to use immutable values

Another good reason to use only immutable values is that mutable variables (var fields) don’t work well with parallel/concurrent applications. Because concurrency is becoming more important as CPUs use more cores, I discuss this in the “Benefits of Functional Programming” and “Concurrency” lessons.

As a prelude to those lessons, in the article, The Downfall of Imperative Programming, Bartosz Milewski writes, “Did you notice that in the definition of ‘data race’ there’s always talk of mutation?”

Summary

In this lesson, I defined functional programming like this:

Functional programming is a way of writing software applications using only pure functions and immutable values.

To support that, I also defined pure function like this:

  • The output of a pure function depends only on (a) its input parameters and (b) its internal algorithm.
  • A pure function has no side effects, meaning that it does not read anything from the outside world or write anything to the outside world.
  • As a result of those first two statements, if a pure function is called with an input parameter x an infinite number of times, it will always return the same result y.

I noted that higher-order functions (HOFs) are a terrific FP language feature, and also stated that recursion is a by-product of the definition of FP.

I also briefly discussed some of the benefits of immutable values (and FP in general):

  • The best FP code is like algebra
  • Pure functions and immutable values are easier to reason about
  • Without much support (yet), I stated that immutable values make parallel/concurrent programming easier

See also

books by alvin