## Saturday, November 24, 2012

### 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 `double`s 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` 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 `Map`s 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.