While my last post addressed how to go about learning to think functionally, it did not address why a programmer should embark on the journey in the first place.  Why is learning to think functionally important, especially in a mixed environment like C#, Python, or Ruby?  Why is it not good enough to stick with the tried and true object-oriented and structured programming styles?

Learning to program functionally will lead to more modular, expression-oriented, and conceptually simple code.

Modular Code

Think about a programmer who is introduced to structured programming for the first time.  He may remark that it is all about while, if, and for statements.  A programmer who encounters object-oriented programming may opine in turn that it is all about inheritance, encapsulation, and polymorphism.  In our consideration of functional programming, let's not also make the mistake of confusing the tools we use with the goals we are working towards accomplishing.  All of these programming styles are designed to increase the beauty, maintainability, and modularity of code.

Programmers are trained to notice bad smells.  One particularly potent stench is duplicated code.  A programmer tends to notice and remove the smell when the culprit is a block of contiguous statements that is repeated throughout a codebase, but sometimes the smell is more subtle and the cure is less obvious.

Consider a function that computes the sum of the squares of a list of numbers.  A typical approach might look like this:

static int SumOfSquares(IEnumerable<int> nums)
{
  int result = 0;
  foreach (var item in nums)
    result += item * item;
  return result;
}

It seems good enough, but look closely.  How many times do programmers compute the sum of a list of numbers?  All of the time.  So let's write a function to compute the sum.

static int Sum(this IEnumerable<int> nums)
{
  int result = 0;
  foreach (var item in nums)
    result += item;
  return result;
}

Ok, now we can simplify our SumOfSquares function by reusing the code to compute the sum.

static int SumOfSquares(IEnumerable<int> nums)
{
  List<int> squares = new List<int>();
  foreach (var item in nums)
    squares.Add(item * item);
  return squares.Sum();
}

Hmm.  Not really the effect we wanted.  If anything the code only got more complicated.  Maybe we should extract out the part that takes a list of numbers and returns a list of squares.  No, that really isn't a reusable piece of code so it would only be moving the complexity around.  The problem is that the code is tightly coupled to the expression item * item.  The expression is really local to the problem that we are solving, but the act of taking a list of things and performing some operation on each element to produce a new list is a common reusable operation.  Functional programmers call this function Map.

static IEnumerable<U> Map<T, U>(this IEnumerable<T> s, Func<T, U> f)
{
  foreach (var item in s)
    yield return f(item);
}

Now we can use Map to reduce the complexity of SumOfSquares.

static int SumOfSquares(IEnumerable<int> nums)
{
  return nums.Map(x => x * x).Sum();
}

Now that is something to write home about.  It does exactly what we want without specifying state-transition by state-transition how to go about doing it.  Although this is a small example, it is very compelling.  Functional programming took a tightly coupled section of code (item * item) and removed the dependency by use of higher-order functions.

Expression-Oriented vs Statement-Oriented

As a compiler guy, I often work with parsers and abstract syntax trees.  Most people are familiar enough with parsing to know there are top-down and bottom-up approaches.  What is sometimes overlooked is that there are top-down and bottom-up ways to create parse trees as well.  If parent nodes are required to be created before child nodes then the tree is created top-down but if the child nodes must be created before the parent node then the tree is created bottom-up.  There are several reasons why a particular system may prefer one approach or the other but one reason deserves closer examination for our purposes: top-down creation of trees is statement-oriented whereas bottom-up creation is expression-oriented.  Take a look at the following code to create a parse tree for an if statement.

IfNode ifNode = CreateIfNode(parent);
ifNode.Condition = ParseCondition(ifNode);
ifNode.Consequence = ParseBlock(ifNode);
ifNode.Alternative = ParseBlock(ifNode);

Contrast this statement-oriented creation with an expression-oriented approach:

CreateIfNode(ParseCondition(), ParseBlock(), ParseBlock());

The statement-oriented approach is characterized by series of state transitions caused by assignments where some syntactic elements are L-values and others are R-values.  The expression-oriented approach is just a combination of values which is itself a value.  Expression-oriented code is more succinct and easier to grasp since it is not cluttered.  Each piece is either a primitive value or a combination of values.  In contrast, statement-oriented code is marred by lack of conceptual unity.

As the C# language has added more functional features, it has become a more expression-oriented language.  Similarly, as a programmer learns to follow a functional style, he will naturally write code that is more expression-oriented in nature.

Conceptually Simpler

Imperative programming is sometimes reminiscent of a Rube Goldberg machine.  Both require meticulous thought to ensure that a process works correctly despite a myriad of state transitions and interdependencies.  It is amazing these complicated programs work at all.

Dijkstra pointed out that too many programmers rely on executing a program in order to understand it.  The reason is imperative programs lack sufficient underlying formalisms to make guarantees about any but the most trivial of programs.  As much as I love a debugger, it is disheartening to need to use it to understand my code.

Contrast this with functional programs which have solid theoretical foundations and therefore can more easily make runtime guarantees.  In fact, many functional programming books dedicate a significant portion of their pages to showing the reader how to prove various runtime properties of programs.  While most programmers wouldn't take the time to write proofs like Euclid's about their programs, it is compelling to think about creating sections of a program which are written so well that their properties are provable and understandable.  In our own codebase, those sections of the code that approach this ideal are the most understandable and solid pieces of code that we have.

The Journey to Understanding

While reaching a point where we naturally think functionally is the goal, do not think that there are not ample rewards on the journey to understanding.  Pause to appreciate the beauty of higher-order functions.  Bask in the joy of type inferencing.  Reflect on the infinite.  Over the next couple of months, I will be writing about various functional gems that pertain to C# 3.0.  And if I haven't done a good enough job explaining why functional programming is important then here are some fantastic papers which detail the subject.

Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs - John Backus

Why Functional Programming Matters - John Hughes