What is Functional?

It occurred to me that in all of my writing about functional programming so far, I haven't really talked about the basic idea of what a function really is, at a fundamental level, and how this informs functional programming.

What is a function?

The idea of a function really comes from mathematics. It's just been implemented (in various ways) in computer languages since then. Essentially, a function is a transformation -- given an input value drawn from some set, it produces an output in some set (which could be the same as the input set, but in many useful cases, it's not).

In math, we usually write something like "Let f be a function ℝ ⟶ ℝ, given by f(x) = x." In this case, we're declaring the domain and codomain of the function as the set of real numbers, and then defining the "implementation" of the function.

To define a similar function in C, we could write:

double f(double x) { return x; }

Of course, this isn't exactly the same as the mathematical definition, since doubles can't represent all of the real numbers, but it is usually "close enough". That said, we've declared a domain (double) and a codomain (double), and defined the means by which values are transformed. Generalizing, we can say that types effectively describe sets. (On any actual computer (without infinite memory), types describe finite sets.)

At some point, math students become comfortable with functions over multidimensional sets. For example, the function to determine the magnitude of a 2d vector over the real numbers is f:ℝ × ℝ ⟶ ℝ given by f(x,y) = sqrt(x^2 + y^2), where the domain ℝ × ℝ denotes the Cartesian product between the real numbers and themselves. (Since the magnitude function only returns non-negative values, we could declare the codomain to be ℝ+ or some such notation. Usually, we'll just leave the more general codomain, despite the fact that the function only hits a subset of it. This is the difference between the codomain and image of the function.)

Similarly, in software, we have functions of multiple parameters. That magnitude function can be (approximately) defined in C as:

double magnitude(double x, double y) { return sqrt(x*x + y*y); }

Equivalently, we can consider the function as taking a single tuple (double, double).

One area where mathematics and imperative languages have diverged is in the ease of defining Cartesian product codomains. For example, we can define a function that reflects through the line y=x, as f: ℝ × ℝ ⟶ ℝ × ℝ, where f(x,y) = (y,x). To denote the two return values, we generally need to define a new type that has two fields (with each field representing an operand of the Cartesian product). Typically, this would be a struct in C, a record in Pascal, or a class in an object-oriented language. We can make this somewhat generic by defining a set of tuple typeclasses.

Composition

In math, functions can be composed. That is, given a function f: A ⟶ B and a function g: B ⟶ C, we can produce the composed function g ◦ f : A ⟶ C. In traditional imperative programming, we tend to do the equivalent by defining a new function that invokes f then passes the result as input to g, returning the result. Functional languages or libraries often have more convenient syntax for composing functions. (While I haven't included an example in my "Functional programming with examples in Java" series, it is not hard to add a "compose" method to Function1.)

Partial functions

Many functions that we encounter in programming aren't "true" functions, but rather partial functions. That is, they don't actually produce values over the full range of possible input. Instead, they may throw an exception, crash, or otherwise reject a value that is "acceptable" given the input type.

In mathematics, we usually deal with this by restricting the input domain to valid values. For example, the function f(x) = 1/x would have domain ℝ∖{0} -- that is, the real numbers, excluding zero. Unfortunately, in a statically-typed programming language, we don't have a type that represents the non-zero real numbers (at least in any language with which I'm familiar).

Another approach you sometimes see in math is to define a function piecewise, where you define a "total" function over a domain by specifying the existing partial function over the values for which it's valid, and then "something else" for the other values. In particular, we could augment the codomain to include a special "undefined" value, which could propagate through other functions that "accept" an undefined value. So, the function above becomes f: ℝ ⟶ ℝ ∪ {undefined} where f(x) = 1/x, if x ≠ 0, and undefined otherwise. Then, any function that composes with f needs to do something with the undefined value. We can accomplish roughly the same thing in programming by returning null (for non-primitive types), but we risk losing track of it. A better alternative is to use an option typeclass, since it provides a compile-time guarantee that composed functions expect an Option.

Functions in disguise

A number of data structures can also be thought of as functions. An array int[10] is effectively a function from the natural numbers between 0 and 9 to the set of integers. (Similarly, a List<T> is a partial function from the integers to T.) A Set<T> in Java can be thought of as function T ⟶ boolean, via the contains method. A Map<K,V> is a function K ⟶ V, where Java makes it a total function by returning null for missing keys, while Scala treats Maps as functions K ⟶ Option[V].

Independent evaluation and substitution

Mathematical functions can be evaluated in any order and can substitute their results arbitrarily. That is, if we know f(x) = 5, we can write 5 anywhere that we see f(x) and vice-versa. This is because mathematical functions are defined in terms of equivalences, independent of side-effects. Evaluating a mathematical function doesn't log output to a console, update some state, or strangle a kitten.

Unfortunately, the same cannot generally be said for functions in a programming context (especially if you're using the Apache Commons Kittenstrangler library). In particular, for a program to be useful, it must perform some I/O, which is inherently a side-effect. (Even the most mathematical program eventually needs to update state -- mutating a user who doesn't know the answer into one who does.)

Fortunately, we can isolate our "impure" side-effecting code from our "pure" functional code. In fact, this is generally how programs in Haskell are structured. They are spawned within the impure IO monad, and dive into the pure functional logic, only coming back up to the impure world to interact with the user.

That said, even the IO monad has a functional feel, if you twist your mind just right. The way I think of it is that your program takes "the world" as input. Your pure functional code is mapped over the IO monad and can be used to produce a "new world" as output. Thus, a "Hello, world" program in Haskell takes as input the universe and outputs a new, slightly different universe: one where "Hello, world" is written one more time on your screen.

Generally, you want to keep the impure part as small as possible. In traditionally imperative languages, we can theoretically structure our programs in a similar way -- writing side-effect-free functions wherever possible, and keeping side-effects within a specific layer. Unfortunately, most imperative languages also have standard libraries that encourage updating of mutable state.

What do we get as programmers for following a purely functional approach? Like mathematical functions, it is safe to evaluate pure functions in an arbitrary order, or even all at once. Effectively, we can have near-arbitrary concurrency of our functional code, which is quite useful in today's multi-core world.

Obviously, even with pure functional code, we need to be careful about how/when we parallelize, since the overhead of context-switching could quickly dominate the gains obtained by parallel evaluation. That is, we as developers still need to find appropriately-sized work units. That said, pure functional code can be parallelized without worrying about locking shared state. When you have mutable state, you need to worry about finding appropriately-sized work units as well as locking shared state. Picking the wrong work units leads to degraded performance. Making mistakes with locking can lead to degraded performance, deadlocks, or race conditions. Worst of all, deadlocks and race conditions often only show up under heavy load (which tend to involve production scenarios).

Conclusions

In this post, I've tried to make a more mathematical argument in favour of functional programming. Computer science is a comparatively young field of study. Unfortunately, it's also very useful. This has resulted in a lot of unproven (and unprovable) solutions running our world. As a step toward maturity and stability, I believe we would benefit from adhering to the boring, predictable logic of mathematics where possible, isolating those pieces that cannot be represented by pure functions.

While Haskell (more-or-less) enforces this separation between pure functions and side effects, we can move toward purity in traditionally imperative languages like C/C++, Java, Pascal, Objective C, and the .NET languages. It's largely just a matter of changing your coding style a bit. If you find that you're bumping against limits of the language to write elegant pure code (as in my previous blog posts, where there's a lot of boilerplate involved with making Java act functional, and I dropped purity in a few cases -- e.g. memoization and lazy evaluation), you could also try a hybrid OO/functional language like Scala, or a functional language that still gives you easy mutability and side-effects when needed, like F# or most Lisps. Additionally, Python and Ruby have some convenient functional constructs in their standard libraries/syntax. Finally, while the language itself can be pretty ugly, remember that Javascript is basically Lisp disguised as a C-family language.