Previous: What's in a Closure?

Today I want to revisit our recursive Fibonacci number function from my previous article and see if there might be some ways to improve it by drawing on another functional programming technique. For reference, here's the Fibonacci function:

If you stuck with me through the article on closures, you know that a closure is created by this function because the local "results" variable is used within an anonymous method even though it is declared outside of it. So, the C# compiler will turn the "results" variable into a field on a compiler-generated helper class. What's not as obvious is that "calculator" is also a local variable declared outside of the anonymous method but used inside. If you missed it, look again. "calculator" isn't a method call. In reality, it's a variable of the FibonacciCalculator delegate type which happens to reference the method that we're calling from (and hence, resulting in recursion). This might seem like a minor detail but it's extremely important. The compiler actually generates code that looks something like this:

Looking at the compiler-generated code actually helps clarify this. If you look at "CalculatorMethod", you'll notice that it is not calling itself recursively. Instead it is calling the "calculator" delegate and the effect is that it calls itself recursively. This has importance that is actually a bit mind-bending but we'll get to that in a moment.

First, in the original article, I referred to the technique of storing the results from our function for retrieval later as caching. I used that term generally but there is a more specific term: Memoization. Now, a good object-oriented programmer would recognize that this "memoization" is an idea that should be reused. Perhaps some sort of abstract class could be created to solve this problem? The class could maintain the lookup table and handle when the function is called and when results from the lookup table are returned. That would work, right? Well, it might work but it sounds like a lot of extra effort to me and it would be awkward to reuse. In reality, there is a much more elegant (and reusable) solution to this problem. The answer is to use another closure. As usual, we'll stick with C# 2.0 for now.

Look carefully at what this method does. It takes a delegate of type "FibonacciCalculator" and returns a new delegate of the same type. The new delegate is declared as an anonymous method which uses a Dictionary to store and retrieve the results of the passed function. This new delegate is a closure because it references the local variables "results" and "function". That means that the scope of those referenced variables will be promoted and will exist outside the Memoize function (see my previous article if your need a refresher). With that in mind, here's how our Fibonacci function changes:

This is a bit mind-bending if you're seeing a technique like this for the first time so let's tear it apart a bit. For those less-familiar with functional programming, it can be easier to see when expressed in the classes that are generated by the compiler:

Again, read the code carefully to see what's actually happening. The idea is that we've created a function which wraps our Fibonacci function with the memoization feature. This works because our Fibonacci function uses a delegate ("calculator") for recursion instead of calling itself directly. The delegate gets assigned to the new "memoized" function so the Fibonacci function actually calls that instead.

If you run this code, you will find that it is almost as fast as the optimized Fibonacci function from the previous article. The only differences are:

1. A slightly longer time to get the first result because the extra closure and Dictionary have to be instantiated.
2. The added indirection and Dictionary slow the algorithm down slightly but the difference doesn't register at the millisecond level.

Regardless of these extremely minor consequences, we now have a reusable Memoize function that can be used in other situations. Err... ok, it's not that reusable yet because it is tied to our FibonacciCalculator type. I held off on using generics until now because they can look bizarre to the uninitiated but we can make this reusable by creating our own generic delegate type. Instead of FibonacciCalculator, we could use this:

(Note that several generic delegates just like will be included with the .NET Framework 3.5 and used by the C# 3.0 compiler.)

Our Memoize function can become generic itself and use the new delegate like this:

And a small change is made to our Fibonacci function:

Now we have a reusable memoization function that could be used with any function that takes one argument and returns a result. And, the solution allows us to capture the elegance of the original Fibonacci algorithm and achieve reasonable performance without the added baggage of explicitly declaring and maintaining storage.

If you are interested in other applications of this technique, Wes Dyer has some excellent blog posts on memoization here and here. Wes has some very cool ways to use this technique to implement the Singleton and Multiton design patterns.

Good luck and happy coding!

Previous: What's in a Closure?