Disclaimer: I’m still pretty green with functional programming. This is me working out my own understanding.

Wikipedia defines Functional Programming (FP) this way:

“functional programming is a programming paradigm that treats computations as the evaluation of mathematical functions and avoids state and mutable data.” [reference]

Let’s break this apart.

Programming Paradigm

What’s a “programming paradigm”? It’s a conceptual model for creating programs. The most popular paradigm (at least in tongue) would be Object Oriented Programming (OOP). Other common paradigms are Imperative Programming (I suspect a majority of the world’s code is here) and Declarative (which includes languages like html and xaml). Here’s a list of some other programming paradigms.

It seems to me that most popular languages allow for the use of more than one paradigm. You’ll hear people referring to a language as “multi-paradigm”, this means it has characteristics from more than one model. For example, F# is described as having both functional and object-oriented characteristics. Some paradigms reinforce others. For example, OOP tends to be Imperative and FP tends to be Declarative.

Computations

In this definition, I take the term very generically. You can interpret it to mean “stuff the program does”.

Evaluations of Mathematical Functions

This is the core concept behind functional languages. In OOP we tend to think of functions as methods that change the state of objects. We have some object, say an order, and we call some method, like submit(), and the method changes the state of our object. Now, in a mathematical function we don’t really have the notion of an object or even a state. Consider a function that calculates (naively) the height of a projectile with respect to time:

f(t) = -4.9t² + 19.6t + 3

With this function, we pass in a value for t and we get back a value representing the height. There is no “state” we are modifying in this function. There’s more to this concept, but let’s come back to it.

Avoids State and Mutable Data

This point follows naturally from the last one, however it was very confusing to my object-oriented mind. In fact, FP sounded a somewhat contrary to my understanding of how computers are working at a low level. Despite this, immutability is central to functional programming. In a functional language, such as F#, you don’t work with variables. Instead you work with values. Variables (as their name implies) can change, but values are constant.

Characteristics of Functional Languages

Even after breaking it apart, the definition is still a bit of an academic one. I found it beneficial to see how these concepts played out into actual features in a language. The following list is my compilation, and I’m certain it’s not exhaustive. These are common features or concepts found in many functional languages.

• First Class Functions
• Higher Order Functions
• Pure Functions
• Currying or Partial Application
• Recursion
• Pattern Matching
• Memoization

I’ll begin by discussing the first three items. The remaining will follow in subsequent posts.

First-Class Functions

This means that functions are basic types and can be passed around just like integers or strings. In C#, we have a couple of ways to do this. Here’s one example, we’ll create a function and name it “add”. It will accept two integers and returns an integer:

Func<int, int, int> add = (i, j) => i + j;

This example relies on the type Func<T1,T2,TResult> introduced in .NET 3.5 and we set the value using a lambda expression.

Update: after writing this I found this description of first-class functions on MSDN.

Higher Order Functions

Higher order functions are functions that either take a functions as an argument or return it as a result. Let’s say that we need to write a program that takes a list of integers and then, depending on some user choice, will either add all the numbers together or subtract them. Building on our add function from above, we could create a higher order function in C# like this:

static int Reduce(Func<int, int, int> reducer, IEnumerable<int> values)
{
    int accum = 0;
    foreach (var i in values)
    {
        accum = reducer(accum, i);
    }
    return accum;
}

I named the function “Reduce” since it reduces a list of integer down to a single integer. You can see that the first parameter matches the type of our add function from above. We can call Reduce like this:

var integers = new[] {1, 2, 3, 4, 5};
var sum = Reduce(add, integers);

Pure Functions

A function is pure when it has no side effects. This mean that the function does not alter a state or mutate any data. For example, our add function is pure. We calculate a result but we do not modify any existing data. Our other function, Reduce, is pure too… well sort of. It’s pure in the sense that – if you treat it as a black box – then no state is modified. However, internally it does maintain a state. That is, the variable accum is the internal state that we modifying for each iteration of the loop. We’ll see how to remove the state from the Reduce function in another post.

Pure functions are closely tied to the concept of Referential Transparency, which says that an expression is considered referentially transparent when it can be replace with it’s value. For example,

var sum = add(3,4);

can be replaced with

var sum = 7;

and there will be no change in meaning.

Continue on to Currying…