patrick dewane gathers wool

Threading the Needle – Coroutines and Continuations

If you haven't already noticed, my blogs trends mostly towards the obscure for no reason other than I find it fun and interesting. Well, let's keep trending in that direction then.

A few weeks back while iterating over some set of data (a generic list if I recall), I paused for a moment and re-realized the enumerator I was using was a form of coroutine. If you're not familiar with the term, a coroutine is generalized subroutine that supports multiple entry points and can pause and resume execution at pre-determined points in its definition. Take for example:

foreach (var y in SuccessiveSubtract(10, 1))
{
    Console.Write("{0} ", y);
}

Where SuccessiveSubtract is defined as:

static IEnumerable<int> SuccessiveSubtract(int x, int y)
{
    int z = x - y;
    while (z >= 0)
    {
        yield return z;
        z -= y;
    }
}

You can immediately appreciate the convenience of a coroutine. The signature of SuccessiveSubtract fools us into thinking of it as a run of the mill subroutine with one entry and one exit point. However, its body reveals its true intentions; to return integer data in an on demand fashion. What we don't see is the actual run-time implementation of the coroutine in the above example. The yield statement acts as a sugar for the actual guts of the coroutine which is implemented in the spirit of a finite state machine. Anyhow, a quick glance at the above code shows how the foreach construct works in tandem with the yield statement to call SuccessiveSubtract multiple times all while the coroutine maintains its state across yields. Nifty.

What I do not necessarily care to talk about at this time is how to implement the enumerator design pattern and I'm also not concerned with finite state machines. But it would be fun to talk about state machines at some time in the future, so let's add that item to the to-do list. What I do care to talk about at this time is how to implement SuccessiveSubtract as a coroutine without using the foreach/yield combo. Furthermore, I plan on using continuations as a means to define control flow in and out of the coroutine.

The first step in this process is to rewrite the SuccessiveSubtract function in continuation passing style. From an earlier blog post of mine, we know the steps to follow in order to convert a function into one written in CPS:

1. Change the return type, T, to void.
2. Add an additional parameter C; a void returning function which takes a single argument of type T. This is our continuation.
3. Replace all return statements with invocations of C.

Applying those steps to the SuccessiveSubtract function, yields its CPS'd cousin:

static void SuccessiveSubtract(int x, int y, Action<int> next)
{
    int z = x - y;
    while (z >= 0)
    {
        next(z); 
        // there isn't anything explicitly getting us back
        // here other than when the continuation returns
        z -= y;
    }
}

Easy enough. So what do we have to do to the call site to accommodate the new signature of this function? What you're about to see will validate the distaste I expressed in the comment above.

// this works, but to call the coroutine again, you have to return from the continuation. is that lame?
Action<int> print = y =>
    {
        Console.Write("{0} ", y);
        return;
    };
SuccessiveSubtract(10, 1, print);

By eliminating the foreach statement we've sacrificed explicit enumeration of our sequence. Imperatively, I feel this is a sacrifice, but a functional perspective makes me think I'm on the right track and that I can do a better job of explicitly defining control flow.

In order to explicitly define control flow out of this function, I'll need it to accept a continuation N for it to invoke. To define control flow back into this function I'll pass a continuation to N to act as a hook back into the coroutine. Also, I'll want some type of mechanism to alert any call site that the sequence is out of values. Here's how that looks:

static void SuccessiveSubtract(int x, int y, Action<int> onValue, Action<Action> onNext, Action onDone)
{
    int z = x - y;
    if (z >= 0)
    {
        onValue(z);
        onNext(() => SSC3(z, y, onValue, onNext, onDone));
    }
    else
    {
        onDone();
    }
}

When enumerating a sequence in C# using the foreach construct, there are three things it is aware of:

1. When a value is present.
2. When another value exists.
3. When no other values exists.

You can see how I've taken those ideas and made each into its own continuation above. This way, we're explicitly defining control flow when a value is present, when another value exists, and when our sequence is out of values. Here is how we can call this function:

Action onDone = () => Console.WriteLine("I'm done");
Action<Action> onNext = a => a();
SuccessiveSubtract(10, 1, print, onNext, onDone);

What's interesting about this is how a void returning function is able to generate a sequence of values in the spirit of a C# enumerator. If this seems like voodoo, I would recommend running this through a debugger to appreciate how I've defined control flow.

Before you get pedantic, I am aware that because of my use of recursion above I can't really call this a coroutine since the internal state of the routine is actually being maintained with closures and recursive calls. With that said, this approach was better in my eyes than the alternative use of goto statements. Which would require me to piss off Dijkstra and would also require a discussion on finite state machines.

With all that said, I think feel this was a fun and interesting exercise. I've used continuations to define control flow in and out of our coroutine, and even leveraged them in a such a way where we can iterate over a sequence of values without using an iterative structure. Well, I think that's fun and interesting at least. We also managed to use recursion and closures along the way.

It looks this this post aligned itself nicely with the spirit of this blog; obscure, fun and interesting. Stop back soon since last time I promised a post on streams, and I promise to post it shortly.

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.