Christopher Bennage is an the dev lead on the patterns & practices team at Microsoft. Christopher began programming on his Texas Instrument in elementary school, but fell in love with computers with the advent of the Commodore Amiga. More recently he's been attracted to client technologies like XAML, HTML5, and JavaScript. In his free time, Christopher is usually very distracted by a dozen different, competing creative ideas. He lives in Kirkland, WA with his wife, Sandra, and their three children. Christopher is a DZone MVB and is not an employee of DZone and has posted 40 posts at DZone. You can read more from them at their website. View Full User Profile

What is Functional Programming?

09.07.2010
| 2191 views |
  • submit to reddit

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.9t2 + 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 two 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;  
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;
}
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);
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);  
var sum = add(3,4);

can be replaced with

var sum = 7;  
var sum = 7;

and there will be no change in meaning.

More to come…

References
Published at DZone with permission of Christopher Bennage, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)