Functional C# - Part 2

For those of you who read the first part in this series(more than I expected, thank you all!) I hope you realized the beauty in continuations and CPS in particular. While you're unlikely to use this style of programming day-to-day (kudos if you do) it is another tool in the tool belt. If you have not read my previous post about continuations in C#, I recommend doing so since this is a series and I like to see the traffic.

In this second post I am going to discuss function memoization, how to use it in C# and, more interestingly, how to use this technique on functions written in CPS. See how this all comes together now? If any of you took my CPS'ed Fibonacci function from the previous post and ran it in Visual Studio, you may have been surprised to find that it could only calculate up to about the 16th Fibonacci number. Why's that you say? Let's take another look at that function:

Action<int, Action<int>> fib = null;
fib = (n, g) =>
{
    if(n > 1)
        fib(n - 1, x => fib(n - 2, y => g(x + y));
    else
        g(n);
};

Let's take a look at a portion of the call stack when running this function when n = 16:

 

Compare that with the following illustration of how this function works (from my previous post):

 

You should be able to spot a redundancy in calculations. Notice the successive recursive calls? Notice that invocations of the continuations can be recursive calls themselves? This function performs redundant calculations for like values of n. We end up exhausting our stack space invoking this function for values of n for which the result has already been calculated. If only there was something we could do to avoid these redundant calculations...

Function Memoization

Function memoization involves "remembering" the result of a function given an input. As with other forms of caching, memoization trades space for speed. Unlike other forms of caching, memoizing a function does not necessarily require modifications to the function. An additional function (the memoize function) acts as a proxy to the function needing memoization, taking care of associating inputs with outputs. This technique is relevant to referentially transparent functions as functions with this property make the distinction between a function call and its result transparent.

Note: It may have sounded before like I was alluding to memoization being able to prevent a stack overflow. The cause of our overflow is the sheer amount of recursive calls needed to compute the nth Fibonacci number. Memoizing this function can help reduce the number of recursive calls needed to calculate the nth Fibonacci number, but certainly will not prevent you from running out of stack space for large values of n.

Take for example a function which computes the nth triangle number:

Func<int, int> triangle = null;
triangle = n =>
    {
        if (n > 1)
            return n + triangle(n - 1);
        else
            return n;
    };

Yes you mathematicians out there, I know this isn't the most efficient way to calculate the nth triangle number, but doing it this way let's me demonstrate memoization.

Say we were to execute this function 2 successive times for the values 20 and 30:

Console.WriteLine(triangle(20));
Console.WriteLine(triangle(30));

During the computation for n = 30, we end up re-calculating the 20th triangle number. While this example is not necessarily an expensive calculation, it is needless nonetheless since this value was already computed. We could employ an ad-hoc caching mechanism like such:

triangle = n =>
{
    if(TriangleCache.ContainsKey(n))
    {
        returnTriangleCache[n];
    }
    if (n > 1)
    {
        int val = n + triangle(n - 1);
        TriangleCache.Add(n, val);
        return val;
    }
    else
    {
        return n;
    }
} 

The TriangleCache object here is implemented as a dictionary. The idea is to save the results for values of n to avoid having to recalculate these values in the future. While this works, the pro-modular Angel on your shoulder probably just punched you in the ear. The calculation for determining the nth triangle number should be done independently of any caching mechanism. Good modular design allows us to program in a generic and re-usable way. In this example our caching mechanism is not generic or reusable since it is embedded in the triangle function. Say we need to modify the way this function caches values, we would need to verify that this change has not affected our algorithm for generating triangle numbers. A more modular approach would provide us with a level of granularity that separates these two very different algorithms.

Let's modularize our caching logic by placing it into its own function. After all, I am stressing a function oriented approach in this series. We could have this function take a parameter representing a key and have it return the value associated with that key. But where does our function needing memoization come into play? How do we deal with the recursive calls within our triangle function? We need to be able to memoize the result of each invocation of triangle, even the recursive ones. In order do that, we need all references to triangle to actually refer to the memoize function. I would write this memoize function, but Wes Dyer has already done so in a most elegant way:

static Func<A, R> Memoize(this Func<A, R> f)
{
    var map = new Dictionary<A, R>();
    return a =>
    {
        R value;
        if(map.TryGetValue(a, out value))
        {
            return value;
        }
        value = f(a)
        map.Add(a, value);
        return value;
    };
} 

Is that beautiful or what? If you haven't ever checked out the (defunct?) blog of Wes Dyer, you're missing out. This function (notice that it's an extension method) takes a function requiring memoization and returns a reference to a new function performing the task of associating inputs with outputs. The variable map is kept in scope with a closure, and we call this function like this:

triangle = triangle.Memoize();

From this point forward all calls to triangle actually invoke the function which Memoize returns. This function determines whether or not to invoke triangle based on the existence of a value for a given key. Pretty slick isn't it?

We're not done yet though. My goal here is to memoize a function written in CPS. This memoize function above doesn't lend itself very well to functions written in CPS since it relies of return values. Functions written in CPS, remember, do not return values. Furthermore, the "result" for CPS function is a function itself (a continuation) which itself may require a calculated parameter. To refresh our memories, here is the CPS'ed Fibonacci function we wrote last time:

Action<int, Action<int>> fib = null;
fib = (n, g) =>
{
    if(n > 1)
        fib(n - 1, x => fib(n - 2, y => g(x + y));
    else
        g(n);
};

In this example, the "result" for a value n is a continuation and a parameter to that continuation. Previously, we only needed to memoize the result of invoking a function. This time around we need to memoize not only the continuation created for values of n, but we also need to memoize the values passed to those continuations for these values of n. A dictionary can still help out here, but the values associated with the dictionary keys need to collections of continuations and continuation parameters. Let's define a class to help us with this:

class ContinuationValues<T>
{
    private List<Action> _continuations;
    private List_values;
    public List<Action<T>> Continuations
    {
        get { return_continuations; }
    }
    public List<T> Values
    {
        get { return_values; }
    }
    public ContinuationValues()
    {
        _continuations = new List<Action<T>>();
        _values = new List<T>();
    }
} 

We can use this class to create a dictionary mapping values of n with the continuations and continuation parameters resulting from fib(n):

var map = new Dictionary<T, ContinuationValues<T>>();

We also know what the signature of our memoize function is going to look like with the knowledge that it will take our CPS'ed Fibonacci function as a parameter and return a new function of the same type:

static Action<T, Action> Memoize(this Action<T, Action<T>> f)
{
    var map = new Dictionary<T, ContinuationValues<T>>();
    return (m, k) =>
    {
        // now what?
    };
} 

Now here's the tricky part. We know that Memoize needs to store results (continuations and their parameters) for functions that don't return. With that said, we can't rely on the invocation of a continuation to produce any tangible result unless we can somehow get inside the body of the continuation and record the value passed to it. We can accomplish this with a callback function. The idea is to create a function of the same type as our continuation, and pass this function instead of our continuation to our memoized function. When the memoized function thinks its invoking a continuation, our callback actually gets invoked and gives us an opportunity to examine any parameters:

static Action<T, Action> Memoize(this Action<T, Action<T>> f)
{
    var map = new Dictionary<T, ContinuationValues<T>>();
    return (m, k) =>
    {
        Action<T> h = n => //callback function
        {
            k(n); //keeps the continuation k in scope and invokes it with n
        };
        f(m, h); //invokes the memoized function with a callback
    };
} 

By creating a new function h of the same type as our continuation k, we provide ourselves with the ability to inject a callback function into the memoized function. The function h keeps the continuation k in scope through the use of a closure and we also get the value the memoized function thought it was passing to a continuation. This gives us a window of opportunity to associate values with continuations and their parameters. Which is exactly what we need to do to memoize a CPS function. Your keen eye may notice that the above function just executes the memoized function normally.

Just like the original version of Memoize, we need to check our map for the key m. If our map does not have an entry for m we need to create one. Then a callback function is needed to add the value n to our map and pass this value along to any continuation associated with this key. Then we can invoke the memoized function using this callback. If our map does contain an entry for m we can add the continuation k to our map and pass all values associated with m to this continuation. Closures make this scoping nightmare possible and are a real gem to have in C#. If you don't understand Closures, I'd take some time and read up on them.

When we put the whole thing together, this is what we end up with:

static Action<T, Action> Memoize(this Action<T, Action<T>> f)
{
    var map = new Dictionary<T, ContinuationValues<T>>();
    return (m, k) =>
    {
        ContinuationValues<T> entry;
        if(!map.TryGetValue(m, out entry))
        {
            entry = new ContinuationValues<T>();
            map.Add(m, entry);
        }
        if (entry.Continuations.Count == 0)
        {
            entry.Continuations.Add(k);
            Action<T> h = n =>
            {
                if (!entry.Values.Contains(n))
                {
                    entry.Values.Add(n);
                    for (int i = 0; i < entry.Continuations.Count; i++)
                        entry.Continuations[i](n);
                }
            };
            f(m, h);
        }
        else
        {
            entry.Continuations.Add(k);
            for (int i = 0; i < entry.Values.Count; i++)
                k(entry.Values[i]);
        }
    };
} 

There's quite a bit there to swallow but take some time and run it through your head and a debugger. Without memoization our CPS'ed Fibonacci function could only calculate (around) the 16th Fibonacci number. With memoization, the 1000th Fibonacci number can be calculated within milliseconds. This is quite an improvement! Try it out yourself:

fib = fib.Memoize();
fib(1000, x => Console.WriteLine(x));

Memoization, or the functional approach to caching, is an elegant solution to redundant and expensive calculations. It didn't require any modifications to the Fibonacci function and we ended up with a higher degree of modularity because of this. Come back soon and I'm going to show how all of this looks in a functional language.

Comments

[Raine]

Great post, thanks for sharing. I think I've seen something similar in Lua that I tried to port to C#, but this is a way better implementation.

[Tahir Hassan]

Hi Patrick,

This was a great post, but I like to note that your definition of memoizing the CPS-ed Fibonacci function could be written A LOT more concisely as below (but may be a teeny bit less efficient):

public static Action> Memoize(this Action> function)
{
var cache = new Dictionary();
return (x, f) =>
{
if (!cache.ContainsKey(x))
{
function(x, fx => cache.Add(x, fx));
}
f(cache[x]);
};
}

Regards,
Tahir

[Tahir Hassan]

Oh dear,

The code in my comment is not rendered properly but I am sure that you can understand very quickly what it is trying to do.

BTW the type signature of memoize has two type parameters because the type of the first parameter may be different from the first parameter of the continuation. For example, int.Parse, if written in CPS would be Action[string, Action[int]].

I am still not sure what your memoize function aims to do with all that code (CPS version only). Can you explain what it does please?