Functional Programming

Functional programming, or fp, is a method of composing software out of pure functions, eliminating side effects caused by shared states and mutable data. Using a declarative syntax instead of imperative and chains of pure functions instead of various functions accessing and modifying shared states. Man that’s a lot of computer science terms for one sentence, let’s see if we can translate that into something a little easier to follow. Let’s start with the one that is the umbrella over most of them…

Side Effects

A side effect is defined as any application state change that is observable outside the function other than it’s return value. What this means for the actual code is that if you pass the same data to the same function (or series of functions), you will always get the same result.

Pure Functions

A function is said to be pure if there is no chance of any side effects on it, or caused by it. Mathematical equations make excellent examples of this, we can define Add(A,B)=A+B. If we pass 2 and 3 to it, the answer will always be 5. Defining Multiply, Subtract and Divide similarly, you can chain them together to more complex operations knowing at each step that the outcomes will always be the same.  Graphing functions are a fun example:

LineSlope(Rise,Run)=Divide(Rise,Run)
LinearEquation(X, Slope, YIntercept)=Add(Multiply(Slope,X),YIntercept)

Having tested Divide, Add and Multiply, we know that LinearEquation(1, LineSlope(2,4), 5) will return 5.5 no matter how many times in a row we call it. Note too that I passed a function as an argument to LinearEquation, that’s because being pure it supports higher order functions, which simply means that anywhere we would pass data, we can pass a function that will get evaluated when it’s results are needed. We can take this to crazy depths with polynomial functions:

Poly(x,Coefficient,Power,ExtraTerm)=
  Add(Multiply(Coefficient,RaiseToPower(x,Power)),ExtraTerm)

Two degree polynomial: Y=2x²+3x-4 becomes Poly(x,2,2, Poly(x,3,1,-4). We’re but an array operation away from being able to build a variable degree polynomial function!

Shared States

One of the quickest ways to make an object impure is to define an internal state that can affect how it’s functions return values. The Random class in .Net is an excellent example of this. Calling New Random().Next over and over will return different numbers each time because at each call a hidden state gets modified slightly. Besides allowing incredibly impure functions, there’s one other concept this causes problems for…

Immutable Data

As mentioned previously, pure functions when provided with the same input always have the same output. This however isn’t just a choice while coding, this is enforced by the language. Values or parameters, once defined are immutable, or unable to be changed. This also means that anything that is passed those same parameters is assured that they won’t be modified by a previous call.

Tying it all together

Reading through all these, there’s a lot that works together, functions being passed as arguments works well because arguments can’t be changed once defined anyway. Immutable data means that even if you did set up a shared state, it is easier to work without it, and less likely to have bugs. All of these things together make writing anything but pure functions more difficult in the languages than just writing it in easy to test pure chunks of logic. So we’ve talked about functional programming and key areas it differers from more commonly used paradigms, but beyond “easier testing” we’ve yet to really plug any specific problems it has the advantage in or areas that it’s not the best way to handle things.

First let’s talk about tasks that benefit from fp. These are typically tasks that would see a performance boost from some level of multithreading or distributed computing. Problems that involve translating from one vocabulary to easier to process intermediary forms (such as parsing natural language queries or compiling code).

Next we’ve got tasks that are likely to run worse with fp, most of these revolves around tasks that will need to extract every bit of performance from the hardware or can’t easily be abstracted into smaller chunks. An operating system would not be ideal due to the additional resources and delay that an fp solution would induce. GUIs also tend to be less responsive for similar reasons.

Last we have the tasks that neither benefit, nor are harmed by a functional approach. Most tasks actually fall in this category, leaving such decisions up to policy and what the developers are most comfortable maintaining.

Example time

Now that we’ve walked through all the terms, let’s look at an example. We want to take an array of integers, multiply each by 3 and return the sum. In C# that might look like the following:

int SumTriple(int[] array) {
  var accumulator=0;
  for(var i=0; i<array.Length; i++) {
    accumulator += array[i]*3;
  }
  return accumulator;
}

That function has one actual line of work, that’s surrounded by an extra 4 lines dedicated to flow control and bookkeeping. Now let’s see one possible way to do it in F#

let triple a = a*3 
let SumTriple a =
  a |> List.map triple |> List.sum

As you can see, we let all of the loop and accumulate be handled by built in functions. It’s an odd syntax that uses |> instead of additional parentheses, in a language that uses parentheses more it could be written the following way: List.sum(List.map(a, triple)). In fact you can duplicate something similar with .NET LINQ statements, again in C# taking full advantage of LINQ:

int Triple(int a) => a*3;
int SumTriple(int[] array) =>
  array.Select(Triple).Sum();

Both LINQ Select and List.map take an array of some form and apply a function to each item, then return the result as a new array. Then List.sum and LINQ Sum reduce the arrays to a single final value which is returned.

Now let’s go back to that original definition: functional programming is a method of composing software out of pure functions, eliminating side effects caused by shared states and mutable data. Hopefully, now that we’ve made it through all the definitions and the example, that sentence feels less like Star Trek technobabble.