---

July 2011

Volume 26 Number 07

The Working Programmer - Multiparadigmatic .NET, Part 9: Functional Programming

By Ted Neward | July 2011

Any time an article series gets close to double digits, one of two things is happening: either the author is pretentious enough to think that his readers are actually interested in that subject that many times in a row, or he is just too boneheaded to think to come up with a new topic. Or, I suppose, sometimes the subject just merits that much coverage. No matter which is the case here, rest assured we’re in the home stretch now.

In the previous piece in the June issue (msdn.microsoft.com/magazine/hh205754), the idea of providing variability along a name-based axis came under the microscope, using naming conventions and dynamic programming—that is, binding by name, which in .NET typically means reflection at some level—to solve some interesting design problems. Most .NET developers, I imagine, expect that most of the dynamic programming they encounter will be through the “dynamic” keyword that C# 4 provides. As old-hand Visual Basic developers know, however, C# only came by its dynamism recently, whereas Visual Basic programmers have known it—and used it, in many cases quite successfully—for decades.

But that’s not the last of the paradigms—one more remains to be explored, and, again, it’s one that’s been hiding in plain sight for a few years now. And while it’s certainly easy (if a tad cheeky) to describe functional design as design along the algorithmic axis of commonality-variability, this simultaneously oversimplifies and obscures its capabilities.

In a single sentence, functional programming is about treating functions as values, just like any other data value type, meaning we can pass functions around just as we can data values, as well as derive new values out of those values. Or, put more accurately, functions should be treated as first-class citizens within the language: they can be created, passed to methods and returned from methods just as other values are. But that explanation, again, doesn’t precisely enlighten, so let’s begin with a simple case study.

Imagine the design exercise is to create a small command-line calculator: a user types (or pipes) a mathematical expression in, and the calculator parses it and prints the result. Designing this is pretty straightforward, as shown in Figure 1.

Figure 1 A Simple Calculator

class Program
{
  static void Main(string[] args)
  {
    if (args.Length < 3)
        throw new Exception("Must have at least three command-line arguments");
    int lhs = Int32.Parse(args[0]);
    string op = args[1];
    int rhs = Int32.Parse(args[2]);
    switch (op)
    {
      case "+": Console.WriteLine("{0}", lhs + rhs); break;
      case "-": Console.WriteLine("{0}", lhs - rhs); break;
      case "*": Console.WriteLine("{0}", lhs * rhs); break;
      case "/": Console.WriteLine("{0}", lhs / rhs); break;
      default:
        throw new Exception(String.Format("Unrecognized operator: {0}", op));
    }
  }
}

As written, it works—until the calculator receives something other than the cardinal four operators. What’s worse, though, is that a significant amount of code (compared to the overall size of the program) is duplicate code, and will continue to be duplicate code as we add new mathematical operations to the system (such as the modulo operator, %, or the exponent operator, ^).

Stepping back for a moment, it’s clear that the actual operation—what’s being done to the two numbers—is what varies here, and it would be nice to be able to rewrite this in a more generic format, as shown in Figure 2.

Figure 2 A More Generic Calculator

class Program
  {
    static void Main(string[] args)
    {
      if (args.Length < 3)
          throw new Exception("Must have at least three command-line arguments");
      int lhs = Int32.Parse(args[0]);
      string op = args[1];
      int rhs = Int32.Parse(args[2]);
      Console.WriteLine("{0}", Operate(lhs, op, rhs));
    }
    static int Operate(int lhs, string op, int rhs)
    {
      // ...
    }
  }

Obviously, we could simply recreate the switch/case block in Operate, but that doesn’t really gain much. Ideally, we’d like some kind of string-to-operation lookup (which, on the surface, is a form of dynamic programming again, binding the name “+” to an additive operation, for example).

Within the design patterns world, this would be a case for the Strategy pattern, where concrete subclasses implement a base class or interface, providing the necessary signature and compile-time typechecking for safety, something along the lines of:

interface ICalcOp
{
  int Execute(int lhs, int rhs);
}
class AddOp : ICalcOp { int Execute(int lhs, int rhs) { return lhs + rhs; } }

Which works … sort of. It’s pretty verbose, requiring a new class to be created for each operation we want. It’s also not very object-oriented, because we really only need one instance of it, ever, hosted inside of a lookup table for matching and execution:

private static Dictionary<string, ICalcOp> Operations;
static int Operate(int lhs, string op, int rhs)
{
  ICalcOp oper = Operations[op];
  return oper.Execute(lhs, rhs);
}

It somehow feels like this could be simplified; and, as some readers have probably already realized, this is a problem that has already been solved once before, except in the context of event-handler callbacks. This is exactly what the delegate construct was created for in C#:

delegate int CalcOp(int lhs, int rhs);
static Dictionary<string, CalcOp> Operations = 
  new Dictionary<string, CalcOp>();
static int Operate(int lhs, string op, int rhs)
{
  CalcOp oper = Operations[op];
  return oper(lhs, rhs);
}

And, of course, Operations has to be initialized properly with the operations that the calculator recognizes, but adding new ones becomes a bit easier:

static Program()
{
  Operations["+"] = delegate(int lhs, int rhs) { return lhs + rhs; }
}

Savvy C# 3 programmers will immediately recognize that this can be shortened even further, using lambda expressions, which were introduced in that version of the language. Visual Basic can, in Visual Studio 2010, do something similar:

static Program()
{
  Operations["+"] = (int lhs, int rhs) => lhs + rhs;
}

This is where most C# and Visual Basic developers’ ideas about delegates and lambdas stop. But lambdas and delegates are far more interesting, particularly when we start extending the idea even further. And this idea, of passing functions around and using them in various ways, goes deeper.

Reduces, Maps and Folds—Oh My!

Passing functions around is not something we’re used to in mainstream .NET development, so a more concrete example of how this can benefit design is necessary.

Assume for a moment that we have a collection of Person objects, as shown in Figure 3.

Figure 3 A Collection of Person Objects

class Person
{
  public string FirstName { get; set; }
  public string LastName { get; set; }
  public int Age { get; set; }
}
class Program
{
  static void Main(string[] args)
  {
    List<Person> people = new List<Person>()
    {
      new Person() { FirstName = "Ted", LastName = "Neward", Age = 40 },
      new Person() { FirstName = "Charlotte", LastName = "Neward", Age = 39 },
      new Person() { FirstName = "Michael", LastName = "Neward", Age = 17 },
      new Person() { FirstName = "Matthew", LastName = "Neward", Age = 11 },
      new Person() { FirstName = "Neal", LastName = "Ford", Age = 43 },
      new Person() { FirstName = "Candy", LastName = "Ford", Age = 39 }
    };
  }
}

Now, it so happens that Management wants to celebrate something (perhaps they all made quota). What they want to do is give each of these people a beer, which is pretty easily accomplished using the traditional foreach loop, as shown in Figure 4.

Figure 4 The Traditional foreach Loop

static void Main(string[] args)
{
  List<Person> people = new List<Person>()
  {
    new Person() { FirstName = "Ted", LastName = "Neward", Age = 40 },
    new Person() { FirstName = "Charlotte", LastName = "Neward", Age = 39 },
    new Person() { FirstName = "Michael", LastName = "Neward", Age = 17 },
    new Person() { FirstName = "Matthew", LastName = "Neward", Age = 11 },
    new Person() { FirstName = "Neal", LastName = "Ford", Age = 43 },
    new Person() { FirstName = "Candy", LastName = "Ford", Age = 39 }
  };
  foreach (var p in people)
    Console.WriteLine("Have a beer, {0}!", p.FirstName);
}

There are some minor bugs here (mostly in that your code is handing a beer to my 11-year-old son), but the biggest problem with this code? It’s intrinsically un-reusable. Attempts to later give everybody another beer require another foreach loop, which violates the Don’t Repeat Yourself (DRY) principle. We could, of course, gather the beer-issuing code into a method (classic procedural commonality response), like so:

static void GiveBeer(List<Person> people)
{
  foreach (var p in people)
    if (p.Age >= 21)
        Console.WriteLine("Have a beer, {0}!", p.FirstName);
}

(Notice that I added the over-21 age check; my wife, Charlotte, insisted I include it before this article could go to publication.) But what if the desire is to find everybody who is over the age of 16 and give them a free R-rated movie ticket, instead? Or to find everybody who is over the age of 39 and give them a “Holy Cow You’re Old!” balloon? Or find everybody over the age of 65 and give each of them a small notebook to write things down that they’re likely to forget (like their name, age, address …)? Or find everybody with the last name other than “Ford” and invite them to a Halloween party?

The more of these examples we toss off, the more it becomes clear that each of these cases presents two elements of variability: filtering the Person objects, and the action to take with each of those Person objects. Given the power of delegates (and the Action<T> and Predicate<T> types introduced in .NET 2.0), we can create commonality while still exposing the necessary variability, as shown in Figure 5.

Figure 5 Filtering Person Objects

static List<T> Filter<T>(List<T> src, Predicate<T> criteria)
{
  List<T> results = new List<T>();
  foreach (var it in src)
    if (criteria(it))
      results.Add(it);
  return results;
}
static void Execute<T>(List<T> src, Action<T> action)
{
  foreach (var it in src)
    action(it);
}
static void GiveBeer(List<Person> people)
{
  var drinkers = Filter(people, (Person p) => p.Age >= 21);
  Execute(drinkers, 
      (Person p) => Console.WriteLine("Have a beer, {0}!", p.FirstName));
}

One more common operation is to “transform” (or, to be more accurate about it, “project”) an object into another type, such as when we want to extract the last names from the list of Person objects into a list of strings (see Figure 6).

Figure 6 Converting from a List of Objects to a List of Strings

public delegate T2 TransformProc<T1,T2>(T1 obj);
static List<T2> Transform<T1, T2>(List<T1> src, 
  TransformProc<T1, T2> transformer)
{
  List<T2> results = new List<T2>();
  foreach (var it in src)
    results.Add(transformer(it));
  return results;
}
static void Main(string[] args)
{
  List<Person> people = // ...
  List<string> lastnames = Transform(people, (Person p) => p.LastName);
  Execute(lastnames, (s) => Console.WriteLine("Hey, we found a {0}!", s);
}

Notice that, thanks to the generics use in the declarations of Filter, Execute and Transform (more commonality/variability!), we can reuse Execute to display each of the found last names. Notice, too, how the use of the lambda expressions make an interesting implication begin to come clear—one that becomes even more obvious when we write yet another common functional operation, reduce, which “collapses” a collection down into a single value by combining all values together in a specified way. For example, we could add up everybody’s age to retrieve a sum-of-all-ages value using a foreach loop, like so:

int seed = 0;
foreach (var p in people)
  seed = seed + p.Age;
Console.WriteLine("Total sum of everybody's ages is {0}", seed);

Or we can write it using a generic reduce, as shown in Figure 7.

Figure 7 Using a Generic Reduce

public delegate T2 Reducer<T1,T2>(T2 accumulator, T1 obj);
static T2 Reduce<T1,T2>(T2 seed, List<T1> src, Reducer<T1,T2> reducer)
{
  foreach (var it in src)
    seed = reducer(seed, it);
  return seed;
}
static void Main(string[] args)
{
  List<Person> people = // ...
  Console.WriteLine("Total sum of everybody's ages is {0}", 
    Reduce(0, people, (int current, Person p) => current + p.Age));
}

This reduction operation is often referred to as a “fold,” by the way. (To the discerning functional programmer, the two terms are slightly different, but the difference isn’t critical to the main discussion.) And, yes, if you’d begun to suspect that these operations were really nothing more than what LINQ provides for objects (the LINQ-to-Objects feature that got so little love when it was originally released), you’d be spot-on (see Figure 8).

Figure 8 Fold Operations

static void Main(string[] args)
{
  List<Person> people = new List<Person>()
  {
    new Person() { FirstName = "Ted", LastName = "Neward", Age = 40 },
    new Person() { FirstName = "Charlotte", LastName = "Neward", Age = 39 },
    new Person() { FirstName = "Michael", LastName = "Neward", Age = 17 },
    new Person() { FirstName = "Matthew", LastName = "Neward", Age = 11 },
    new Person() { FirstName = "Neal", LastName = "Ford", Age = 43 },
    new Person() { FirstName = "Candy", LastName = "Ford", Age = 39 }
  };
  // Filter and hand out beer:
  foreach (var p in people.Where((Person p) => p.Age >= 21))
    Console.WriteLine("Have a beer, {0}!", p.FirstName);
  // Print out each last name:
  foreach (var s in people.Select((Person p) => p.LastName))
    Console.WriteLine("Hey, we found a {0}!", s);
  // Get the sum of ages:
  Console.WriteLine("Total sum of everybody's ages is {0}", 
    people.Aggregate(0, (int current, Person p) => current + p.Age));
}

To the working enterprise .NET developer, this seems silly. It’s not like real programmers spend time looking for ways to reuse age-summation code. Real programmers write code that iterates over a collection of objects, concatenating each one’s first name into an XML representation inside of a string, suitable for use in an OData request or something:

Console.WriteLine("XML: {0}", people.Aggregate("<people>", 
  (string current, Person p) => 
    current + "<person>" + p.FirstName + "</person>") 
  + "</people>");

Whoops. Guess that LINQ-to-Object stuff might be useful after all.

More Functional?

If you’re a classically trained object-oriented developer, this seems ridiculous yet elegant at the same time. It can be a mind-blowing moment, because this approach quite literally comes at software design in a nearly diametrically opposite way from objects: rather than focusing on the “things” in the system, and making behavior something that is attached to each of those things, functional programming looks to identify the “verbs” in the system and see how they can operate on different types of data. Neither approach is more right than the other—each captures commonality and offers variability along very different axes, and as might be imagined, there are places where each is elegant and simple, and where each can be ugly and clumsy.

Remember, in classic object orientation, variability comes at a structural level, offering the ability to create positive variability by adding fields and methods or replacing existing methods (via override), but nothing about capturing ad hoc algorithmic behavior. In fact, it wasn’t until .NET got anonymous methods that this axis of commonality/variability became feasible. It was possible to do something like this in C# 1.0, but each lambda had to be a named method declared somewhere, and each method had to be typed in System.Object terms (which meant downcasting inside those methods), because C# 1.0 didn’t have parameterized types.

Longtime practitioners of functional languages will cringe at the fact that I end the article here, because there are numerous other things a functional language can do besides just pass functions around as values—partial application of functions are a huge concept that make much of functional programming incredibly tight and elegant, in languages that support it directly—but editorial needs must be satisfied, and I’m pushing my length limitations as it is. Even so, seeing just this much of the functional approach (and armed with the functional capabilities already present in LINQ) can offer some powerful new design insight.

More importantly, developers interested in seeing more of this should take a long, hard look at F#, which, of all the .NET languages, is the only one that captures these functional concepts (partial application and currying) as first-class citizens within the language. C# and Visual Basic developers can do similar things, but require some library assistance (new types and methods to do what F# does naturally). Fortunately, several such efforts are underway, including the “Functional C#” library, available on CodePlex (functionalcsharp.codeplex.com).

Various Paradigms

Like it or not, multiparadigm languages are in common use, and they look like they’re here to stay. The Visual Studio 2010 languages each exhibit some degree of each of the various paradigms; C++, for example, has some parametric metaprogramming facilities that aren’t possible in managed code, owing to the way that the C++ compiler operates, and just recently (in the latest C++0x standard) gained lambda expressions. Even the much-maligned ECMAScript/JavaScript/JScript language can do objects, procedures, metaprogramming, dynamic and functional paradigms; in fact, much of JQuery is built on these ideas.

Happy coding!

---

Ted Neward is a principal with Neward & Associates, an independent firm specializing in enterprise .NET Framework and Java platform systems. He has written more than 100 articles, is a C# MVP and INETA speaker, and has authored or coauthored a dozen books, including “Professional F# 2.0” (Wrox, 2010). He consults and mentors regularly—reach him at ted@tedneward.com if you’re interested in having him come work with your team, or read his blog at blogs.tedneward.com.

Thanks to the following technical expert for reviewing this article: Matthew Podwysocki