I’m two weeks shy of six months at Microsoft. When I arrived here I was immediately thrown into the fray on Project Silk. The primary developer on the project was heading into paternity leave. Fortunately, I had read JavaScript: The Good Parts on my flight out to Redmond.

I’m lazy. I remember reading somewhere that that was a desirable trait to have in a developer. I’m not sure where though, and honestly it’s just too much effort to bingle it. This laziness came to the forefront recently as I was playing with Node.

In my last post, I showed you how to spin up a quick web app using Node. As I was playing with this app, I found that I had to restart Node every time I made a change to the source. This meant I had to switch to the console, stop the process, start the process and THEN refresh my page to see the effect of my change. Too much work I say.

What is Node?

The simplest answer, albeit a simplistic answer, is that Node (or Node.js) is JavaScript on the server. Actually, it’s a more than just that, but you can read about the more in other places. This is a good enough answer for us n00bs.

Unless you’ve been living in in cave, you might have noticed that JavaScript is all the rage now. It’s the new assembly language of the Web. (It’s even for the enterprise.) With Node, you can now take that webby clienty goodness to your server applications.

Chapter XXXVI

My time with Blue Spire has officially ended. I have accepted a position with Microsoft on the Patterns & Practices team. My start date is April 18th.

Even though I’ve been professionally restless for a while, leaving Blue Spire turned out to be rather emotional for me. Untangling myself from a business I spent almost five years building up depressed me. Nevertheless, it’s done and Blue Spire lives on. Keep an eye on Rob’s blog for details about the company and his future plans.

On March 31, 1998, around 10am, my then-manager Alex and I left the office we shared together and headed over to Electronics Boutique. Alex and I were both developers working for the IT department of an up and coming software company called PC DOCS. In those days, we didn’t have a corporate firewall. My desktop was a node on the internet. In fact, I was running a web server on it. A bunch of us would stay late after work, barricaded in other peoples’ cubicles, all phones on speaker, playing WarCraft II and Quake. Those were halcyon days. I was just about to turn 23. I was just about to get married.

N.B. this is unrelated to the concept of bindings in Silverlight and WPF.

One of my aha moments in learning F# occurred while I was reading Real World Functional Programming. Specifically, it was when the meaning of the let keyword really clicked. Before I explain, here are couple of samples:

let x = 42


let multiply a b = a * b

I was predisposed to interpret let as merely declaring a variable. but you will recall from the first post that we made a distinction between working with mutable “variables” and immutable “values”. Functional languages eschew mutability.

If you look up let in the official documentation and you’ll see that it is called a binding and it is very clearly described:

A binding associates an identifier with a value or function. You use the let keyword to bind a name to a value or function.

This also aligns with the concept of referential transparency we mentioned way back in the first post.

This may seem obvious or even a subtle distinction to make, but I think it is fundamental in understanding the functional approach.

Update: This next part is not technically accurate and I do not mean to imply that it is. Rather, this is how my poetic eye has begun to see the code.

After this clicked with me, I also to think of

let x = 42

as a function with no arguments that returns a value of 42. The distinction between binding to a value and binding to a function blurs (for me). It is the Marriage of Value and Function.

Next stop, pattern matching in F#.

If you are new to this series, start here.

Before I move on to the two remaining items on my list (pattern matching and memoization), I’d like to take a brief excursion and talk about about Linq in C#. I never said it explicitly, but I have been writing this series for C# developers. I do plan to show you more F#, but while reading the aforementioned Real World Functional Programming I found it very helpful to first learn these concepts in a familiar language.

Linq is Functional

You might have heard it mentioned that Linq was born from the influence of functional languages. Let’s take a moment and connect some dots.

It the last post, I gave you a functional version of our Reduce function. However, both the imperative version and the functional version were tied to working just with integers.

Now you might have notice that these specific implementations can be abstracted into the concept of reducing a list of items of a certain type to a single item of the same time.

Starting with our imperative version, we just need to replace all of the ints with a generic type parameter:

// generic imperative version
static T Reduce<T>(Func<T, T, T> reducer, IEnumerable<T> values)
{


T accum = default(T);
foreach (var i in values)
{
    accum = reducer(accum, i);
}
return accum;


}

A generic version of the functional one is

static T ReduceF<T>(Func<T, T, T> reducer, IEnumerable<T> values, T seed)
{
    if (!values.Any()) return seed;

    var first = values.First();
    var remainder = values.Skip(1);
    var next = reducer(seed, first);

    return ReduceF(reducer, remainder, next);
}

or even better

static T ReduceF(Func<T, T, T> reducer, IEnumerable<T> values, T seed)   
{   
    return values.Any()    
        ? ReduceF(reducer, values.Skip(1), reducer(seed, values.First()))    
        : seed;   
}  

Now, in C# would could save even more typing by implementing our Reduce using Linq

static T ReduceLinq<T>(Func<T, T, T> reducer, IEnumerable<T> values)
{
    return values.Aggregate(default(T), reducer);
}

Of course, after we do, we realize that our Reduce function is the same as the Aggregate extension method that already exists in Linq!

You see, if you are using Linq then you are already utilizing functional language concepts.

N.B. The implementations of ReduceF are not something that you’d want to use in practice. Even though I followed a tail call style for the recursion, you’d still end up with a stack overflow in C#.

Removing the Extra Parameter

Of course, the functional version ReduceF still has that extra parameter that we named seed. We’d like to get rid of that.

The approach that I have frequently seen, is to wrap the recursion function in another function that provides the initial state. In other words, we’d leave ReduceF as it is (though we’d likely make it private) and then we’d add a new function that looked like this:

static T ReducePublic<T>(Func<T, T, T> reducer, IEnumerable<T> values)
{
    return ReduceF<T>(reducer, values, default(T));
}

Update: there is some good discussion about removing the extra parameter in the comments of part 3. As mentioned there, the primary reason for doing it this way is an academic desire to preserve the tail call form.

In our next post, we’ll start digging a little deeper into F#.

In the first post in this series, I provided a list of concepts that I found to be characteristic of functional languages. We’ve talked bout the first four so far.

• First Class Functions
• Higher Order Functions
• Pure Functions
• Currying or Partial Application Covered in the 2nd post.
• Recursion
• Pattern Matching
• Memoization

Updated: Thanks to Brad Wilson for recommendation to use !Any() instead of Count()==0.

Recursion

A recursive function is a function that calls itself. To quote Wikipedia,

“Recursion […] is a method of defining functions in which the function being defined is applied within its own definition”
- en.wikipedia.org/wiki/Recursion

In general, we programmers are shy about using recursion as it can easily lead to the dreaded stack overflow. However, recursion is crucial aspect of using functional languages. The problem of overflowing the stack can be avoided using something called tail recursion. But this post is not about explaining what recursion is, rather it is about explaining its role in functional languages.

Recursion is a mechanism for controlling flow. In fact, you’ll hardly ever see a loop when writing functional code; you’ll use recursion instead.

Let’s jump straight into an example. Consider our C# function Reduce from the first post:

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;  
} 

Now, we can define another function that produces the same output, but uses recursion instead of a loop:

static int ReduceF(Func<int, int, int> reducer, IEnumerable<int> values, int seed)
{
    if (!values.Any()) return seed; // #5

    var first = values.First();       // #1
    var remainder = values.Skip(1);   // #2
    var next = reducer(seed, first);  // #3

    return ReduceF(reducer, remainder, next);  //#4
}

The first thing to note is that ReduceF includes an extra parameter, seed. This new parameter plays a role analogous to the variable accum in the original Reduce. In order to have the same behavior as Reduce, we’d need to pass in an intial value of 0 for seed when calling ReduceF. Don’t get hung up on the extra parameter though. Let’s step through the logic.

1. Skipping over #5, we’ll come back to that. The first real step is to grab the first element in the list. We’ll use the extension method defined in System.Linq to do so. In functional terms, we’d refer to this as the head of the list.
2. Next we want to grab the remainder of the list. That is everything remaining after we’ve removed the head. The remainder is called the tail. Depending on the length of the list it might be any number of elements or it might be empty. Again, we’ll use a System.Linq extension method to skip over the first element and return the rest.
3. Here we apply our reducer function using the head of the list and the seed value. I named the value next because it will be the seed in our next call to ReduceF.
4. This is the recursive call. The reducer function is merely passed through. Notice though that we are passing remainder and next. Each time the function is called, the remainder has one less item. You’ll also see here how the seed parameter takes the place of our mutable accum variable from Reduce.
5. Eventually, we’ll pass in a list with no remaining items. When we detect that, we know that seed contains the final reduced value and so we return it.

If the code still doesn’t make sense, spin up a quick console application and execute this

Func<int, int, int> add = (i, j) => i + j;
var integers = new[] {1, 2, 3, 4, 5};
var sum = ReduceF(add, integers, 0);

and step through each call to ReduceF. Pay attention to the value of seed during each call as well as the count of elements in values.

Recursion Helps Us Avoid Mutable Data

We mentioned before that Reduce is a higher order function. Of course, the same is true for ReduceF. However, ReduceF is also more pure.

In our original Reduce, we maintained the state of our reduction using the variable accum. In each iteration of the loop we mutated the value of accum. At first glance, you might think that we are doing something similar in ReduceF. After all, we are defining even more variables inside of it. However, I added these superfluous variables just for readability. We can easily refactor ReduceF into

static int ReduceF(Func<int, int, int> reducer, IEnumerable<int> values, int seed)
{
    return (!values.Any()) 
        ? seed 
        : ReduceF(reducer, values.Skip(1), reducer(seed, values.First()));
}

All I did here was to replace the variables with the functions that I was using to set their values. (Well, I also threw in the glorious conditional operator too.)

Now we’ve done away with any internal state! Or, well, at least there is no mutable data. Technically we are still have a state, only it is now in the form of our seed parameter. We’ll see why this is vitally important when we begin discussing “why should we care about functional programming”.

Check out the comment from Irné Barnard under the first post to see an example of Reduce in Lisp.

Continue to Part 4.

In my last post, I provided a list of concepts that I found to be characteristic of functional languages. We’ve talked bout the first three so far.

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

Currying

Updated based on some feedback from Matthew Podwysocki.

Let’s begin with the term “partial application”. This is application in the sense of “applying a function”. Based on my reading thus far, I am inferring that the term “apply” means to resolve the result of a function with a certain set of arguments. Thus, partial application is resolving the result of a function with only a partial set of arguments. The result will be another function that requires fewer arguments that the original function.

In light of this, currying is the act of structuring a function so that it can be partially applied.

Ok, that’s a pretty naive definition. Here’s what wikipedia says:

“[Currying] is the technique of transforming a function that takes multiple arguments in such a way that it can be called as a chain of functions each with a single argument.” - en.wikipedia.org/wiki/Currying

In the book Real World Functional Programming: With Examples in F# and C# by Tomas Petricek and Jon Skeet (a book that I found immensely helpful), the authors define currying specifically as the act of converting a function with multiple arguments into a function that takes the first argument and returns a function taking the next argument (p140). This definition clarified my reading of the wikipedia definition.

Let’s consider an example based on these definitions. Recall our add function (in C#) from the last post:

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

We can convert this into:

Func<int, Func<int,int>> add_c = i => j => i + j;

That might be hard to read, so I’ll break it down a bit.

add_c is a function that takes an integer and returns another function. That means add_c is a higher order function. The returned function takes an integer and returns an integer.

If we define Tx as Func<int,int> then would could define add_c as as having the type Func<int,Tx>. Remember that the final parameter is the return type.

In regards to the nested lambda expressions that define add_c, realize that the expression j => i + j is the actual returned function.

If we were to invoke these functions to add 3 and 4, it would look like this:

var sum = add(3,4);
var sum = add_c(3)(4);

The expression, add_c(3), actually returns a function. We invoke it (or apply it) immediately providing 4 as an argument. We could partially apply it like this:

var add3 = add_c(3); // no second set of parentheses

or with the type made explicit:

Func<int,int> add3 = add_c(3);

So now, our curried function is partially applied and we can reuse this function as needed. To complete our task of adding 3 and 4 (which I guess would be fully applying the function):

var sum = add3(4);

The type signature can get ugly quickly in C#, not to mention those crazy nested lambda expressions. Also, we could not curry our original add function without rewriting it. Even though we are able to express these functional concepts in C#, they are not elegant.

Introducing A Bit of F#

F# has a cleaner syntax and functions are more, um, curriable by default. We could express our add function in F# like this:

let add (i,j) = i + j

This is very much equivalent to our original C# add function. However, a more natural way in F# would be this:

let add_c i j = i + j

This might seems like a trivial difference, but it is not. To fully understand it, we need to look at the way F# defines the signatures of these two functions.

In F#, the type for add is

int * int -> int

The –> indicate that something is returned. Specifically, something with the type designated after the –>. In this case, an integer. Now the thing to the left of the arrow is what is passed into the function. What isn’t obvious though is that int * int is a single thing. That is, it is a single value comprised of two integers. That’s what the * means. It’s a way of separating the constituents of a single value. This single thing is called a tuple. We won’t dig deep into it yet, but the important thing to understand is that add takes a single value (a tuple consisting of two integers) and returns an integer.

This signature is actually a lot like Func<int,int,int>. (Nitpickers: Yes, we could get very exact and use the new Tuple<T1,T2> in .NET 4.0. However, it doesn’t make much of a difference practically.)

Now, let’s move on to add_c. The signature for it is

int -> int -> int

Look back at the wikipedia definition for currying. In particular consider “a chain of functions each with a single argument”.

Okay, now compare this to the C# definition of add_c with the nested lambdas:

i => j => i + j

There are oddly similar, aren’t they?

Now I said to interpret the –> as meaning that whatever comes after it is returned and that whatever comes before is the input. If that is so, then we can understand

int -> int –> int

as meaning that the function takes a single integer and then returns a function with a signature of

int –> int

Are you thoroughly confused? Don’t be ashamed. It takes time to sink in.

What this means is that our F# version of add_c really does have the same type that we expressed in C#. That is Func<int, Func<int,int>>. However, it’s easier on the eyes (and fingers).

Ultimately, this means that the natural way of writing functions in F# makes them very easy to curry.

Now why is this helpful? Well, we can talk about that later.

Continue on to Recursion…

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…