It's hard not to notice how much more attention functional programming is getting amongst the .Net community. Look at the last release of C#, most of the new features from that release borrow from the functional programming playbook. It's great to see that the attention being given to this style of programming isn't solely from the academic community anymore, developers from all sorts of different backgrounds are embracing it. Along with this new-found attention, a whole new vocabulary with words like lambda, monad and immutable gets everyone excited to advance in the evolutionary chain of Geek. I'd like to think that developers new to functional programming are excited about it not because of the cool words, but because of the relevance and the excitement of learning something new.
With that said, I would like to devote time to exploring some practices found mostly in functional programming and introduce them in C#. The first part of the series is going to focus on presenting continuations. Later, I'll cover memoization and eventually take what we've learned and apply in a function language. If you're familiar with continuations and memoization then you're probably wondering why I'm presenting these two topics together. This is not because they're closely related practices, but rather because combining the two in practice is challenging and fun.
So get excited to learn something new. And if this isn't new, hopefully you still find it somewhat stimulating. Let's start with continuations.
A continuation represents the remainder of a computation at a given point in the computation. In short, a continuation describes what to do next. Continuations are represented as functions and are used to control program flow in a style known as Continuation Passing Style, or CPS. As the name describes, CPS practices using continuations as a means of controlling the flow of a program. An interesting side affect of this style of programming is that you can eliminate return statements in functions because, well, there isn't anything to return to!
Let's define a simple program that adds two numbers together:
Boring, I know. Let's get to the fun part then. You'll see above that I've annotated the AddTest function with a comment denoting a point P in our program. The remainder of our program after our call to Adder is to print the result out to the console. If we were to represent this as a function, it might look something like the following:
Here I've defined a void returning function which accepts a parameter of type int. This function g (our continuation) simply prints the parameter z out to the console. Our original program above does the same thing; once it receives the return value from Adder, its prints that value out to the console. This is the first step in transforming a program into CPS; identify a point in a computation and encapsulate the remainder of the computation into a continuation. Once we have created our continuation, we need to plumb it into our program. Since CPS involves encapsulating and passing "what to do next", we have to determine where to pass our continuation. Since we've created a continuation representing our program after the call to Adder, our poor Adder function now has nothing to return to. So let's give it our continuation!
We can shorten this up a bit by passing the body our lambda directly to Adder:
So far we've identified a point in our program, created a continuation representing the remainder of the program after that point. Then we passed our continuation along to our Adder function. We're going to have to modify the Adder function to accept our continuation. Since the remainder of our program has been encapsulated into a function, Adder now has no reason to return to AddTest. This is a very powerful concept; CPS lets you explicitly control program flow in a such a way that a call stack is no longer needed.
Lets think about how Adder has to change to accommodate a continuation. We know it needs to accept another parameter of type Action<int> (our continuation). That's easy enough, but what should Adder do with our continuation? Before this function just added together two numbers and returned that value. Now, Adder has no reason to return any value since it was passed the remainder of the program as a function. Shouldn't Adder perform its addition and then just invoke the remainder of the program?
Adder still fulfills its responsibilities of adding two numbers, but instead of returning this value (notice the return type has changed) it invokes our continuation with this value. The semantics of our program has not changed, but we've sort of turned our program inside-out. The same scoping rules apply between our two adding programs, but the CPS version needs to leverage a closure in order to keep things scoped in the intended manner. For example:
When K invokes its continuation, 1 is printed to the console because our continuation (a delegate) uses lexical scoping rules. All bets would be off had our closure used dynamic scope. It's this same principal which helps us justify that we haven't changed the semantics of our adding program when we converted it to CPS.
Now that we've seen how to convert a simple program into CPS, let's tackle something a bit more difficult. I'm going to apologize up front for using the Fibonacci numbers in the next example. Even though their use in programming examples has been abused for quite some time, I'm hoping you haven't seen the Fibonacci numbers like this. Here is a function which calculates the nth Fibonacci number:
For those of you familiar with this algorithm you also now know why I'm presenting continuations with memoization. For those of you not familiar with this algorithm, here is an illustration of how this works:
The above illustration shows the series of recursive calls needed to compute fib(4) where x and y hold the results of each recursive call in the above function and each successive line is a recursive call. As you can see this function love it some stack space, so don't get crazy and try to compute the 100th Fibonacci number with this implementation. In a future post, we'll see how to compute the 1000th Fibonacci number in record time using memoization. But I digress...
Given what we know about continuations, let's try and create a CPS version of our Fibonacci function above. First, we know that our function takes a parameter of type int and returns an int. With that knowledge, we can shape our continuation parameter and alter the definition of our function accordingly. Remember that the return type of our original version of this function dictates the signature of our continuation, and so our continuation should accept 1 parameter of type int:
The first change we made was to alter our function signature from an int to a void returning function. Programs written in CPS do not return values and so our function will behave the same way. The second change we made was to accept an additional parameter of type Action<int>, our continuation. We don't know what this continuations looks like yet, but we do know that each recursive call needs to pass a continuation:
Our function now takes a continuation as a parameter, g, and instead of returning values we need to pass a continuation in our first recursive call. What's the remainder of the computation after our first recursive call? Well, it's a second recursive call:
Notice how the continuation takes a parameter x. The continuation is going to need to know the value of fib(n - 1) so that it can add that value to the value of fib(n - 2). The parameter x is the same value as x in figure a. What's the remainder of the computation after our second recursive call? This is where we add the values of fib(n - 1) and fib(n - 2):
Looks good right? Not quite. Our function is void returning, so we can't return the value x + y. Furthermore, we're completely ignoring our continuation. And from what we learned before, we replace all return statements with invocations of a continuation:
We can call this function by passing in a continuation with what we want to do with the nth Fibonacci number:
And you thought the non-CPS version of this function used a lot of stack space? Well, we just took stack abuse to a whole new level. Again, I have to digress and save that for a future post. While this particular example is not the most practical use of continuations, I feel it does a tremendous job of demonstrating the inside-out nature of CPS.
In my next post I am going to explore memoization and what we can do to our CPS'ed Fibonacci function to make it more efficient.