What is functional programming?

It has long seemed to me that functional programming is, essentially, programming viewed as mathematics. Many ideas in functional programming came from Alonzo Church’s Lambda Calculus, which significantly predates anything that looks remotely like a modern computer. Though the actual history of computing runs differently: in the early days of computing, Von Neumann’s ideas were more important than Church’s, and had a tremendous influence on the design of early computers—an influence that continues to the present. Von Neumann’s thinking was essentially imperative: a program is a list of commands that run on a machine designed to execute those commands. 

So, what does it mean to say that functional programming is programming “viewed as mathematics”? Von Neumann was a “mathematician,” and programming of all kinds found its first home in Mathematics departments. So, if functional programming is mathematical, what does that mean? What kind of math?

I’m not thinking of any specific branch of mathematics. Yes, the Lambda Calculus has significant ties to set theory, logic, category theory, and many other branches of mathematics. But let’s start with grade school mathematics and assignment statements; they’re basic to any programming language. We’re all familiar with code like this:

  i = i+1 # or, more simply
  i += 1  # or, even more simply
  i++     # C, Java, but not Python or Ruby

Mathematically, this is nonsense. An equation is a statement about a relationship that holds true. i can equal i; it can’t equal i+1. And while i++ and i+=1 no longer look like equations, they are equally nonsensical; once you’ve said that i equals something, you can’t say it equals something else. “Variables” don’t change values; they’re immutable.

Immutability is one of the most important principles of functional programming. Once you’ve defined a variable, you can’t change it. (You can create a new one in a different function scope, but that’s a different matter.) Variables, in functional programming, are invariant; and that’s important. You may be wondering “what about loops? How can I write a for loop?” Not only do you have to do without index variables, you can’t modify any of the variables in the loop body. 

Setting aside the (solvable) problem of iteration, there’s no reason you can’t write code in (almost) any non-functional language that has this same effect. Just declare all your variables final or const. In the long run, functional programming is more about a specific kind of discipline than about language features. Programming languages can enforce certain rules, but in just about any modern language it’s possible to follow those rules without language support.

Another important principle of functional programming is that functions are “first class entities.” That is, there are minimal restrictions about where you can use a function. You can also have functions without names, often called “lambdas” (which refers directly to the Lambda Calculus, in which functions were unnamed).  In Python, you can write code like this:

  data.sort(key=lambda r: r[COLUMN])

The “key” is an anonymous function that returns a specific column of an array; that function is then used for sorting. Personally, I’m not overly fond of “anonymous functions”; it’s often clearer to write the anonymous function as a regular, named function. So I might write this:

  def sortbycolumn(r): return r[COLUMN]
  data.sort(k=sortbycolumn)

The ability to use functions as arguments to functions gives you a very nice way to implement the “strategy pattern”:

  def squareit(x):   return x*x
  def cubeit(x):     return x*x*x
  def rootit(x):     import math; return math.sqrt(x)
  def do_something(strategy, x) ...

  do_something(cubeit, 42)
  weird = lambda x : cubeit(rootit(x))
  do_something(weird, 42)

I often get the sense that all programmers really want from functional programming is first-class functions and lambdas. Lambdas were added to Python very early on (1.0) but didn’t reach Java until Java 8. 

Another consequence of thinking mathematically (and possibly a more important one) is that functions can’t have side-effects and, given the same arguments, will always return the same value. If a mathematician (or a high school trig student) writes

  y = sin(x)

they don’t have to deal with the possibility that sin(x) sets some global variable to 42, or will return a different value every time it’s called. That just can’t happen; in math, the idea of a “side-effect” is meaningless. All the information that sin(x) provides is encapsulated in the return value. In most programming languages, side-effects happen all too easily, and in some, they’re almost an obsession. Again, creating functions that have no side-effects is a matter of exercising discipline. A programming language can enforce this rule, but you can follow it whether or not your language makes you do it. We don’t have cartoon devils looking over our shoulders saying “Go ahead; make a side effect. No one will notice.”

Functional languages vary the degree to which they enforce the lack of side-effects. If you’re a purist, anything that interacts with the real world is a side-effect. Printing a document? Changing a row in a database? Displaying a value on the user’s screen? Those are all side-effects (they aren’t completely encapsulated in the value returned by the function), and they have to be “hidden” using a mechanism like monads in Haskell. And that’s the point at which many programmers get confused and throw up their hands in despair. (I’ll only point you to Real World Haskell.) In both Java and Python, lambda functions can have side-effects, which means that, strictly speaking, they aren’t really “functional.” Guido van Rossum’s discussion of the addition of Lambdas to Python is worth reading; among other things, he says “I have never considered Python to be heavily influenced by functional languages, no matter what people say or think.”

Streams are often associated with functional languages; they’re essentially long (perhaps infinite) lists that are evaluated lazily—meaning that elements of the string are only evaluated as they’re needed. Maps apply a function to every element of a list, returning a new list—and that includes streams, which (for these purposes) are specialized lists. That’s an incredibly useful feature; it’s a great way to write a loop without having to write a loop—and without even knowing how much data you have. You can also create “filters” that choose whether to pass any element of the stream to the output, and you can chain maps and filters together. If you think this sounds like a Unix pipeline, you’re right. Streams, maps, filters, and the act of chaining them together really have as much to do with the Unix shell as they do with functional languages.

Another way to avoid writing loops is to use “comprehensions,” a feature of Python. It’s easy to get very fond of list comprehensions; they’re compact, they eliminate off-by-one errors, and they’re very flexible. Although comprehensions look like a compact notation for a traditional loop, they really come from set theory—and their closest computational “relatives” are to be found in relational databases, rather than functional programming. Here’s a comprehension that applies a function to every element of a list:

  # pythonic examples.  First, list comprehension 
  newlist = [ somefunction(thing) for thing in things ] 

The most general way to avoid traditional loops is to use recursion: a function that calls itself. Here’s the recursive equivalent to the previous comprehension:

def iterate(t, l) :
    if len(t) == 0 : return l     # stop when all elements are done
    return iterate(t[1:],l + [somefunction(t[0])]) # process remainder

Recursion is a mainstay of functional languages: you don’t have indices being modified, and you’re not even modifying the resulting list (assuming that append doesn’t count as modification). 

However, recursion has its own problems. It’s hard to wrap your mind around recursion; you still need to do a lot of your own bookkeeping (in this case, passing in a vector so a result can be returned); and except in one (common) special case, called “tail recursion,” it can be a performance nightmare.

I started by saying that functional programming was programming considered as “math,” and that’s at least partially correct. But is that claim useful? There are many branches of mathematics that map onto programming concepts in different ways. Functional programming only represents one of them. If you’re a topologist, you may well like graph databases. But discussing which branch of mathematics corresponds to which programming practices isn’t really helpful. Remembering high school algebra may help when thinking about immutability, statelessness, and the absence of side-effects; but most programmers will never study the real mathematical origins of functional programing. Lambdas are great; functions as arguments in method calls is great; even recursion is (sometimes) great; but we’re fooling ourselves if we think programmers are going to start using Java as if it were Haskell. But that’s OK; for Java programmers, the value of Lambdas isn’t some mathematical notion of “functional,” but in providing a huge improvement over anonymous inner classes. The tools to be functional are there, should you choose to use them.

In college, I learned that engineering was about making tradeoffs. Since then, I’ve heard very few programmers talk about tradeoffs—but those tradeoffs are still central to good engineering. And while engineering uses a lot of mathematics, engineering isn’t mathematics, in part because mathematics doesn’t deal in tradeoffs. Using “mathematics” as a way to think about a particular style of disciplined coding maybe be useful, particularly if that discipline leads to fewer bugs. It’s also useful to use the tools of mathematics to make good tradeoffs between rigor, performance, and practicality—which may lead you in an entirely different direction. Be as functional as you need to (but no more).