One of my favorite pastimes is playing games. No not XBox 360, PS3, or Wii games nor other computer games, but board games, card games, and other such games. It’s probably because I’m from a large family – I have 8 siblings – and we would often spend time together playing games. It is a good way to accommodate a wide variety of interests, skills, and aptitudes. Some of my favorite games are Settlers of Catan, Carcassonne, Spades, Rook, Mafia, Take Two, Stratego, Ticket to Ride, and of course Axis and Allies.

For my birthday this past year, I received an interesting board game titled RoboRally. The premise of the game is there are a number of robots in a factory and they are bored, so they begin to indulge themselves by competing in races around the factory floor. Each player takes command of a robot and seeks to win these competitions by controlling the robot. The players are dealt a number of *instruction* cards whereupon each player elects five cards to load into his *program registers*. After all the players have programmed their robots, their programs are executed somewhat simultaneously. The robots can interact with each other by shooting, pushing, or otherwise hampering each other’s progress. But the real catch is that the board also interacts with the robots by way of conveyer belts, lasers, pushers, gears, pits, etc. The uncertainty caused by the sheer number of interactions coupled with the deterministic behavior of programmed robots creates pandemonium.

One day I was just itching to write some code so I thought why not implement a computer version of RoboRally. I thought that it would be particularly fun because of the number of interacting objects and the amount of state that is involved. So I began to code away on a board editor. This took a little bit of time mostly because I’m not very skilled at graphic art. *Here is a screenshot from an early version of the board editor.*

The code for the editor consists of three assemblies: the windows application, a game engine, and a functional programming library. This was one of the first non-trivial apps that I wrote using C# 3.0 and it was very fun to use the new language features. In fact, it was incredible because I found that many design patterns that I commonly used changed drastically or were no longer needed. Furthermore, I found that entirely new designs were possible. Today, I will touch on just one of these design patterns and the underlying principle used in it.

The game engine has an class called *Board* and these boards are composed of many *Tiles *which are each associated with a *Location*. Tiles can be simple or rather complex. For instance, there are blank tiles and there are move left express conveyer belt tiles. But there are also gear tiles with a normal wall on the top side and a laser wall on the left side which also have a flag on the tile. I made a design decision early on to have basic tiles and decorator tiles. So complex tiles are formed from the composition of a basic tile and any number of decorator tiles. I wrote a factory which creates either some basic tile or some decorator tile. For a first cut, I didn’t worry that I created an overabundance of blank tiles even if they are all identical. Nor did I worry about the fact that all move right conveyer tiles are the same. However, later as I was refining the design I came back to the factory and wanted to improve it by reducing the number of tiles that were created to the bare minimum. A typical solution to this problem for the blank tiles would look like this:

IBlankTile blankTile;

public IBlankTile CreateBlankTile()

{

if (blankTile == null)

blankTile = new BlankTile();

return blankTile;

}

But how do we do this for conveyer tiles?

Dictionary<Direction, IConveyerTile> conveyerTiles = new Dictionary<Direction, IConveyerTile>();

public IConveyerTile CreateConveyerTile(Direction direction)

{

IConveyerTile result;

if (!conveyerTiles.TryGetValue(direction, out result))

{

result = new ConveyerTile(direction);

conveyerTiles.Add(direction, result);

}

return result;

}

Ick! It only gets even more complicated for tiles that are parameterized on more items. Furthermore, it seems that there is a lot of repetition going on. Specifically, all of the machinery to track instance existence and creation is being duplicated for each tile type. To some extent the Singleton and Multiton patterns also suffer from the same problem. There must be a better way.

In fact, there is a better way. What we really want here is a function that returns the same value each time it is applied to the same parameter values. Functional programmers will instantly recognize this as function memoization.

Memoization can be implemented as a function which takes a function as a parameter and returns a new function which when invoked the first time on some set of parameters will compute the result and when invoked with the same values will not recompute the result but will instead return the previously computed result.

Now let’s see how our code would have looked if we had a static method called *Memoize* is a functional library called *Fun *(why not? functional programming is fun isn’t it?).

public readonly Func<IBlankTile> CreateBlankTile = Fun.Memoize(() => new BlankTile());

public readonly Func<Direction,IConveyerTile> CreateConveyerTile = Fun.Memoize(dir => new ConveyerTile(dir));

The new code is beautiful and doesn’t have all of the redundancy and complexity of the old code. This is a very practical example of the modularity of functional style code that I referred to previously.

“But wait”, you say, “how exactly does the magic happen?” Well, let’s take a look. First, let’s examine a memoize function which takes a function of no arguments and returns a memoized version of that function.

public static Func<R> Memoize<R>(this Func<R> f)

{

R value = default(R);

bool hasValue = false;

return () =>

{

if (!hasValue)

{

hasValue = true;

value = f();

}

return value;

};

}

Memoize takes a function which has no arguments and a return type of R and returns a function with the same signature. When Memoize is called it creates two local variables *value *and *hasValue*. Memoize then returns a new function that returns *value* if *hasValue *is true otherwise it computes *value* by evaluating the parameter *f*, sets *hasValue* to true, and then returns *value*. Notice that the function that is returned from Memoize accesses *hasValue, value, *and *f*. These three variables are local to Memoize. The three variables together with a reference to the function that is created by Memoize form a closure.

So what happens when we invoke the function returned from Memoize for the first time? The variable *hasValue* will be set to false, so we will set *hasValue *to true and then apply *f* saving the result to *value*. Finally, we will return the *value* which is the result of *f*. So the memoized function will return the same thing that *f* would have returned on its first invocation.

But what about on subsequent invocations? When we call memoized function again, *hasValue* will be true so we will simply return *value* without recomputing it. So the memoized function will always return the same value as it did on the first invocation without recomputing the result through *f*.

This has subtle implications such as if *f* has side effects then those side effects will only occur when we apply the memoized function the first time. So we need to be careful about using it. But consider how CreateBlankTile used Memoize. When CreateBlankTile is run the first time, it will create a blank tile and then return the result, but on subsequent invocations it will continue to return the same blank tile. This is exactly the behavior that we want.

Can we do the same thing for functions that have arguments? Absolutely, let’s take a look at how to Memoize functions of one argument.

public static Func<A, R> Memoize<A, R>(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;

};

}

This time instead of storing the computed values in a local variable directly, we store them in a dictionary and instead of marking that we have computed the value we just check for existence in the dictionary. This can be generalized to functions of n arguments by creating composite keys of n fields that are used in the dictionary.

Consider how this Memoize function works with CreateConveyerTile. When we invoke it with some direction for the first time then it will not find that direction in the dictionary and so it will create a new conveyer tile parameterized on that direction and then store it in the dictionary. Subsequent calls with the same direction will not create new tiles but instead grab out the existing one from the dictionary. Again this is the behavior that we want. Furthermore, all of the mechanics of storing and fetching tiles are located in Memoize instead of CreateBlankTile or CreateConveyerTile.

Memoize is also useful for the improving performance of recursive functions. Eric Lippert has a great post about how not to teach recursion where he specifically mentions not to use fibonacci numbers. However, I’m going to use fibonacci numbers not to teach recursion but to show how to improve the performance of recursive functions. Recall, that the definition of the nth fibonacci number where n >= 0 is:

fib(0) = 0

fib(1) = 1

fib(n) = fib(n – 1) + fib(n – 2) if n > 1

We can easily write a little function to do this:

Func<int, int> fib = null;

fib = n => n > 1 ? fib(n – 1) + fib(n – 2) : n;

The problem is this function is very inefficient. Consider calculating the 5th fibonacci number.

fib(5)

= fib(4) + fib(3)

= fib(3) + fib(2) + fib(2) + fib(1)

= fib(2) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + 1

= fib(1) + fib(0) + 1 + 1 + 0 + 1 + 0 + 1

= 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1

= 5

Notice how the computation branches out forming a tree of expansions. In fact, the number of leaves in a tree for the computation of the nth fibonacci number is fib(n + 1) where the number of ones is fib(n) and the number of zeros is fib(n – 1).

So calculating fib(5) will cause fib to evaluated twelve times (the sum of the fibonacci numbers from 0 to 5) but only six distinct calls will be made (fib(0), fib(1), …, fib(5)). The problem only gets worse because the fibonacci numbers grow very quickly. Here are the first 20 fibonacci numbers:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181

So our straightforward recursive function for computing fibonacci numbers will be exponential in n. Ouch! But wait, we can Memoize fib so that if it calls fib again with the same argument then it will not recalculate but instead use the previous result. This will move our exponential function to a linear one at the cost of linear space to store the previous results (we could possibly use a weak reference hash map instead to solve problems with space if they existed). In fact, subsequent calls to fib with previously computed values will be evaluated in constant time.

Func<int, int> fib = null;

fib = n => n > 1 ? fib(n – 1) + fib(n – 2) : n;

fib = fib.Memoize();

If you want, you can add a Console.WriteLine to show when the evaluations happen to both versions and compare. It is very enlightening.

Memoize is turning into quite the useful function. We have used it to solve parameterized identity creation problems and performance issues. Later, we will see other ways we can use Memoize to solve design problems.

Wow, someone else that has heard of Robo Rally. That is a fun game. Have fun with your project.

Theres a great article on using memoisation to speed up Conways Game Of Life here: http://www.ddj.com/dept/ai/184406478

The basic idea is to treat the change in state of the board as a function from one moment in time to the next. By recursively subdividing the board, and memoising the state transitions, a lot of computation can be re-used. The same idea is then applied in time, by memoizing entire sequences of state transitions. The result is speedups of the order of a million-fold.

Thanks for the article, Wes. I enjoyed the Channel 9 video too, very informative. Gets me excited about LINQ. ðŸ™‚

FWIW, it’s possible to do memoization today in C# 2. It’s a bit more verbose without lambdas, of course, but it’s do-able nonetheless. See this post for Sriram’s how-to:

http://blogs.msdn.com/sriram/archive/2006/01/15/lisp_is_sin.aspx

Great learning resource = Wes Dyer…

Thanks for the ongoing functional stuff …

I was wondering if you had any opinions on how best to approach ensuring such functions are thread safe?

Damien:

That is fascinating. I love the game of life and was not aware of that speed up. Thanks for the link.

Judah:

You are right. But I would add that not only is it more verbose, it is also uglier and doesn’t include type inference.

James Jones:

Good question. I’ll prep a post about that.

James:

As I was thinking about what to write concerning thread safe functions, it seemed that nothing would be particularly helpful without a little more context concerning what problems you are facing.

Could you describe the specific problems that you are having?

If you care just to learn general strategies then I could always discuss a few, but this is a topic about which we could write whole books.

Hi Wes

Thank you for the feedback .. it’s appreciated.

I’m very much an OOP minded programmer who is trying very hard to appreciate and adopt a more functional style of programming that will inherently promote thread neutral development. The idea being that my applications scale naturally on multi-processor machines into the future.

I’m currently working on a system, part of which involves delegating well known interface type instantiation to a factory class. What I’d really like is a way of promoting Singleton type usage of types that do not necessarily implement that pattern themselves. It struck me that your memorize function could be just the ticket to this … kindof a surrogate singleton.

Thank you for taking the time to respond and please keep up the excellent posts.

James

Welcome to the twentieth Community Convergence. I’m Charlie Calvert, the C# Community PM, and this is

Welcome to the twentieth Community Convergence. I’m Charlie Calvert, the C# Community PM, and this is

James:

Probably the easiest way to make Memoize thread-safe is to put a lock on map. Like so:

public static Func<A, R> Memoize<A, R>(this Func<A, R> f)

{

var map = new Dictionary<A, R>();

return a =>

{

lock (map)

{

R value;

if (map.TryGetValue(a, out value))

return value;

value = f(a);

map.Add(a, value);

return value;

}

};

}

This will ensure that the function that is being memoized will only be run once for each set of distinct arguments.

In my example of the RoboRally game, I actually used function memoization to act as "surrogate singleton". It isn’t really a singleton since there can be one instance per factory instance (unless the factory is static). But that is exactly what I wanted.

Baby Names I recently finished reading Freakonomics . It is a fascinating book about a number of strange

Great!

I finaly understood why was Lambda Calculus included in my Informatics Lectures at the university:)

Thanx for your post

Pingback from :

http://codingly.com/2008/05/02/optimisation-des-invocations-dynamiques-de-methodes-en-c/

Hi Wes,

Do you think that this is a good way to cache results from REST webservices that are safe to cache when using Silverlight or the .NET framework?

If I could do that, then caching the results in the ASP.NET cache would be a good thing to do.

Thank You,

Vish

using System;

using System.Data;

using System.Configuration;

using System.Linq;

using System.Web;

using System.Web.Security;

using System.Web.UI;

using System.Web.UI.HtmlControls;

using System.Web.UI.WebControls;

using System.Web.UI.WebControls.WebParts;

using System.Xml.Linq;

/// <summary>

/// Summary description for fibonancy

/// </summary>

public class fibonancy

{

int[] arr=new int[100];

int k;

int cal1=0;

int[] arr1 = new int[100];

public fibonancy()

{

for (int i = 0; i < 100; i++)

arr[i] = -1;

}

public int CAL1

{

get { return cal1; }

}

public int[] pr1

{

set

{

for (int i = 0; i < 100; i++)

{

arr1[i] = arr[i];

}

}

}

public int pr2

{

set { k = value; }

}

public int fib(int n)

{

//int s = getnthnumber(n);

if (n < 3)

{

arr[n] = 1;

return 1;

}

else if (getnthnumber(n) > -1)

return getnthnumber(n);

else

{

cal1++;

int nval = 0;

nval = fib(n – 1) + fib(n – 2);

setnthnumber(n, nval);

return nval;

}

}

public int getnthnumber(int n)

{

if (arr[n] != -1)

{

k = arr[n];

return k;

}

else

return -1;

}

public void setnthnumber(int n, int val)

{

arr[n] = val;

}

public int[] returnarr()

{

return arr;

}

}

using System;

using System.Data;

using System.Configuration;

using System.Linq;

using System.Web;

using System.Web.Security;

using System.Web.UI;

using System.Web.UI.HtmlControls;

using System.Web.UI.WebControls;

using System.Web.UI.WebControls.WebParts;

using System.Xml.Linq;

/// <summary>

/// Summary description for fibonancy

/// </summary>

public class fibonancy

{

int[] arr=new int[100];

int k;

int cal1=0;

int[] arr1 = new int[100];

public fibonancy()

{

for (int i = 0; i < 100; i++)

arr[i] = -1;

}

public int CAL1

{

get { return cal1; }

}

public int[] pr1

{

set

{

for (int i = 0; i < 100; i++)

{

arr1[i] = arr[i];

}

}

}

public int pr2

{

set { k = value; }

}

public int fib(int n)

{

//int s = getnthnumber(n);

if (n < 3)

{

arr[n] = 1;

return 1;

}

else if (getnthnumber(n) > -1)

return getnthnumber(n);

else

{

cal1++;

int nval = 0;

nval = fib(n – 1) + fib(n – 2);

setnthnumber(n, nval);

return nval;

}

}

public int getnthnumber(int n)

{

if (arr[n] != -1)

{

k = arr[n];

return k;

}

else

return -1;

}

public void setnthnumber(int n, int val)

{

arr[n] = val;

}

public int[] returnarr()

{

return arr;

}

}