Monday, December 10, 2007

An unrestricted closure example

An interesting question was raised recently about whether there are realistic examples of needing to pass an unrestricted closure when not using the control invocation syntax.

Let's say you were tasked with writing a method which calculates the returns on an accumulator bet. An accumulator (also known as a Parlay in many parts of the world) is a bet where you select several teams/opponents/whatever to win their matches. Your stake (the amount of money you are betting) goes onto the first of those selections, and if your prediction was correct, the returns from that part of the bet go onto the second of the selections, and so on. If any of your selections lost, you lose your money.

As an example, I could have a £10 accumulator bet on the following teams to win in the English Premiership this weekend:

Arsenal @ 2.40
Liverpool @ 2.60
Blackburn @ 2.25
Bolton @ 4.20
Everton @ 2.70

The number after the @ represents the odds for that team to win - 2.0 would mean doubling my money. If all these teams win their matches, I get £10 * 2.4 * 2.6 * 2.25 * 4.2 * 2.7 = £1592.14 back. If any one of these teams lose, I get nothing back. If any of the matches involved do not end in a decisive win/lose result (eg. a match is cancelled), that part of the bet is 'void' - I don't lose my whole bet, but it's calculated as though the odds on that selection were 1.0 (neither profit nor loss).

How could we write this?

Imagine we have a method called reduce(), which is defined as follows:

<E, R> R reduce(Iterable<E> values, R initial, {R, E => R} reducer) {
R result = initial;
for (E element : values) {
result = reducer.invoke(result, element);
}
return result;
}

This method iterates over values, and invokes reducer passing it the result of the invocation it performed on the previous element, and the current element. In the case of the first iteration, there was no previous element, so it uses the value provided as initial. The result of the very last invocation is what's returned from reduce().

Here's a silly but easy example, before I get back to the main point:

List<String> words = Arrays.asList("Mary", "had", "a", "little", "lamb");
// sum the number of characters in the words
int totalChars = reduce(words, 0, {Integer count, String word => count + word.length()});

OK, so we can also use reduce() to help us calculate the returns on an accumulator bet:

BigDecimal calculateReturns(AccumulatorBet bet) {

List<Selection> selections = bet.getSelections();

return reduce(selections, bet.getStake(),
{BigDecimal money, Selection selection =>
Result result = loadResult(selection);
if (result.isWinner()) {
money = money.multiply(selection.getOdds());
}
else if (result.isLoser()) {
money = BigDecimal.ZERO;
}
money
});
}

If you think about it though, once you hit a loser, there's no point continuing - the returns (value held in money) are now zero, and no amount of multiplication is going to change that. You might be tempted to just change:

else if (result.isLoser()) {
money = BigDecimal.ZERO;
}

to

else if (result.isLoser()) {
return BigDecimal.ZERO;
}

which would return BigDecimal.ZERO from calculateReturns(). At the very least, it would save you from unnecessary calls to loadResult(), which could well be a costly operation.

That's only possible if we're allowed to pass an unrestricted closure / function type to reduce(), which is not a method with which we can use the control invocation syntax. The current (v0.5) specification does allow this, but there's debate over whether it's a useful feature (see the comments on that page).

Real betting systems have to settle much more complicated bets, and have to do so as quickly as possible. Shortcuts like the above are very useful for achieving that.

Sunday, December 9, 2007

Memoization revisited

In last week's thrilling episode, the world watched in horror as I attempted memoization with Java Closures, then really pushed my luck with some dodgy curry.

This week, we're going to take the memoization plotline through a whole new twisty-turny story-arc, and see what happens with multi-key memoization.

Our story shall revolve around a class Font, which for some important but unspecified reason needs to ensure that only one instance will be created for any particular combination of its name and pointSize attributes:

public class Font {

private static Map<String, Map<Double, Font>> instanceMap =
new HashMap<String, Map<Double, Font>>();

public static synchronized Font getInstance(String name, double pointSize) {
Font font = null;
Map<Double, Font>> pointSizeMap = instanceMap.get(name);
if (pointSizeMap == null) {
pointSizeMap = new HashMap<Double, Font>();
instanceMap.put(name, pointSizeMap);
}
else {
font = pointSizeMap.get(pointSize);
}
if (font == null) {
font = new Font(name, pointSize);
pointSizeMap.put(pointSize, font);
}
return font;
}

private Font(String name, double pointSize) {
// construct the Font
}
}

There are a few problems with this. Although the code is fairly simple, it's still easy to make a mistake when implementing it. Worse, if we were writing a Font class for real we'd probably want to specify more than just the name and pointSize parameters - the example above doesn't even allow the user to specify any styles such as italic, or bold. The code just gets nastier when we do so:

public class Font {

private static Map<String, Map<Double, Map<EnumSet<FontStyle>, Font>>> instanceMap =
new HashMap<String, Map<Double, Map<EnumSet<FontStyle>, Font>>>();

public static synchronized Font getInstance(String name, double pointSize, EnumSet<FontStyle> styles) {
Font font = null;
Map<EnumSet<FontStyle>, Font>> stylesMap = null;
Map<Double, Map<EnumSet<FontStyle>, Font>>> pointSizeMap = instanceMap.get(name);
if (pointSizeMap == null) {
pointSizeMap = new HashMap<Double, Font>();
instanceMap.put(name, pointSizeMap);
stylesMap = new HashMap<EnumSet<FontStyle>, Font>>();
pointSizeMap.put(pointSize, stylesMap);
}
else {
stylesMap = pointSizeMap.get(pointSize);
if (stylesMap == null) {
stylesMap = new HashMap<EnumSet<FontStyle>, Font>>();
pointSizeMap.put(pointSize, stylesMap);
}
else {
font = stylesMap.get(styles);
}
}
if (font == null) {
font = new Font(name, pointSize);
stylesMap.put(pointSize, font);
}
return font;
}

private Font(String name, double pointSize) {
// construct the Font
}
}

We could abandon the nested Maps for a single Map with some kind of compound key - perhaps a String representation of the Font's attributes:

public class Font {

private static Map<String, Font> instanceMap = new HashMap<String, Font>();

public static synchronized Font getInstance(String name, double pointSize, EnumSet<FontStyle> styles) {
String key = name + " " + pointSize + " " + styles;
Font font = instanceMap.get(key);
// ...
}

// ...
}

Unfortunately this can often result in poorly distributed hash values - the hash codes for "Courier 10.0" and "Courier 10.5" are very close, compared to those for Double.valueOf(10.0) and Double.valueOf(10.5).
Worse, it's fragile. The Windows machine next to me has two distinct fonts "Rockwell" and "Rockwell Condensed", but what if "Condensed" happens to be the name of one of my FontStyles? Which font does a key of "Rockwell Condensed 10.0" represent - is it the Rockwell font with Condensed styling, or the Rockwell Condensed font with no styling?

Alternatively, we could opt to create a dedicated FontAttributes class to use as our compound key, but this just shuffles the complexity into this new class's hashCode() and equals() methods.

Finally, the simple synchronization technique employed exhibits poor concurrency, which is fixable, but at the cost of even more complexity.

Utilizing memoization, what we'd really like would be something like this:

public class Font {

private static {String, Double => Font} memoizer =
memoize({String name, Double pointSize => new Font(name, pointSize)});

public static Font getInstance(String name, double pointSize) {
return memoizer.invoke(name, pointSize);
}

private Font(String name, double pointSize) {
// construct the Font
}
}

Here, all the complexity involved in managing the creation of Font instances (including synchronization) is dealt with by the memoize() method, and it's practically effortless to add additional parameters.

So far though, we've only seen a version of memoize() which works with one key:

static <A, R> {A => R} memoize({A => R} fn) {
Map<A, R> cache = new HashMap<A, R>();
return {A a =>
R value = null;
synchronized(cache) {
value = cache.get(a);
if (value == null) {
value = fn.invoke(a);
cache.put(a, value);
}
}
value
};
}

How can we extend this to work with two, three, or even any number of keys? Obviously we can overload it, so let's see what a version which takes two keys might look like:

static <A1, A2, R> {A1, A2 => R} memoize({A1, A2 => R} fn) {
Map<A1, Map<A2, R>> cache1 = new HashMap<A1, Map<A2, R>>();
return {A1 a1, A2 a2 =>
R value = null;
synchronized(cache1) {
Map<A2, R> cache2 = cache1.get(a1);
if (cache2 == null) {
cache2 = new HashMap<A2, R>();
cache1.put(a1, cache2);
}
else {
value = cache2.get(a2);
}
if (value == null) {
value = fn.invoke(a1, a2);
cache2.put(a2, value);
}
}
value
};
}

This works, but it suffers from the same problems as our earlier implementation of getInstance() which used nested Maps - poor concurrency and increased complexity as the number of keys increases. It is better though, because now at least these problems don't need to be replicated throughout countless getInstance() methods. I'll deal with the concurrency issue later, but let's see if we can improve the complexity situation.

A useful observation we can make is that once we've retrieved the 'inner' Map (cache2), we're back to doing single-key memoization, which is a problem we already have a solution to. Can we define our two-key version of memoize() in terms of the single-key version?

In order to call the single-key memoize({A1 => R} fn), we somehow need to turn the fn we have, which is of type {A1, A2 => R}, into something of type {A1 => R}. This is exactly what partial application can do for us here, since we have the value of the first argument in a1:

static <A1, A2, R> {A1, A2 => R} memoize({A1, A2 => R} fn) {
Map<A1, {A2 => R}> cache = new HashMap<A1, {A2 => R}>();
return {A1 a1, A2 a2 =>
{A2 => R} valueMemoizer = null;
synchronized(cache) {
valueMemoizer = cache.get(a1);
if (valueMemoizer == null) {
valueMemoizer = memoize(partial(fn, a1));
cache.put(a1, valueMemoizer);
}
}
valueMemoizer.invoke(a2)
};
}

The cache is now a simple Map of keys of type A1 to values which are single-key memoizers. This is much better, since the code no longer increases in complexity as we increase the number of keys - we can see this clearly when we define our three-key version in terms of the two-key version:

static <A1, A2, A3, R> {A1, A2, A3 => R} memoize({A1, A2, A3 => R} fn) {
Map<A1, {A2, A3 => R}> cache = new HashMap<A1, {A2, A3 => R}>();
return {A1 a1, A2 a2, A3 a3 =>
{A2, A3 => R} valueMemoizer = null;
synchronized(cache) {
valueMemoizer = cache.get(a1);
if (valueMemoizer == null) {
valueMemoizer = memoize(partial(fn, a1));
cache.put(a1, valueMemoizer);
}
}
valueMemoizer.invoke(a2, a3)
};
}

In fact, the code is almost identical.

However, it's still a shame that we need to write lots of versions of memoize() to cater for different numbers of keys. Isn't there a way to do this with just one version?

Actually, there is :) If we look carefully at what's happening in the two- and three-key versions, they are essentially 'unwrapping' fn, 'injecting' memoization at each stage (ie. on each key). This sounds a lot like currying - turning a multi-argument function into a series of single-argument functions - and funnily enough, we can throw away our two- and three-key versions and rewrite the memoizer usage in curried form, just using the single-key version of memoize():

public class Font {

private static {String => {Double => Font}} memoizer =
memoize({String name => memoize({Double pointSize => new Font(name, pointSize)})});

public static Font getInstance(String name, double pointSize) {
return memoizer.invoke(name).invoke(pointSize);
}

private Font(String name, double pointSize) {
// construct the Font
}
}

So we only needed the single-key version of memoize() after all... great!

Except... we've now increased the complexity and understanding required for anyone using memoize() - not a great move in terms of API design. Perhaps there's a compromise though - we could have a method which did all 'injection' of memoization in curried form for us:

public class Font {

private static {String, Double => Font} memoizer =
injectMemoizer({String name, Double pointSize => new Font(name, pointSize)});

public static Font getInstance(String name, double pointSize) {
return memoizer.invoke(name, pointSize);
}

private Font(String name, double pointSize) {
// construct the Font
}
}

Here's a version of injectMemoizer() which copes with this:

static <A1, A2, R> {A1, A2 => R} injectMemoizer({A1, A2 => R} fn) {
{A1 => {A2 => R}} memoizer = memoize({A1 a1=> memoize({A2 a2 => fn.invoke(a1, a2)})});
return uncurry(memoizer);
}

OK, API usage is back to being relatively 'simple' again, but now we need a version of injectMemoizer() for 2 keys, 3 keys, etc etc... haven't we gone back a step? Well, yes and no. One more change and we can abstract out the call to memoize(), leaving us with a general purpose 'inject' method which we can use for other things. Perhaps we want to inject something that logs the values of the arguments, or substitutes their values for other values if some condition is met. We'll still need any number of versions of 'inject', but now it'll be in the same league as curry, uncurry and partial: one of a handful of building block methods with which this problem is more acceptable.

To do all this we need to find a way to tell inject() what it is that we want it to use (in our case, memoize()). So an additional parameter is required, but what is its type? Looking at the above example we can see that it is something which takes a function type with one argument and a return value, and returns an object of the same function type. These types aren't fixed though: in the first call to memoize() the function type is {A1 => {A2 => R}}, and in the second it is {A2 => R}.

Furthermore, we need to pass in an object, but currently we have a method. Putting all these requirements together suggests that we rewrite memoize() in terms of a type (so that we can have an object of that type), and since this is Java, that type should be an interface, which I'll call Bob because I have no idea what it should be called (same applies to inject for that matter), and the name Bob reminds me of an amusing episode of Blackadder.

public interface Bob {
<A, R> {A => R} invoke({A => R} fn);
}

public class Memoizer implements Bob {
public <A, R> {A => R} invoke({A => R} fn) {
Map<A, R> cache = new HashMap<A, R>();
return {A a =>
R value = null;
synchronized(cache) {
value = cache.get(a);
if (value == null) {
value = fn.invoke(a);
cache.put(a, value);
}
}
value
};
}
}

static <A1, A2, R> {A1, A2 => R} inject({A1, A2 => R} fn, Bob bob) {

{A1 => {A2 => R}} injected = bob.invoke({A1 a1 => bob.invoke({A2 a2 => fn.invoke(a1,a2)})});
return uncurry(injected);
}

Here's how we use it:

public class Font {

private static {String, Double => Font} memoizer =
inject({String name, Double pointSize => new Font(name, pointSize)}, new Memoizer());

public static Font getInstance(String name, double pointSize) {
return memoizer.invoke(name, pointSize);
}

private Font(String name, double pointSize) {
// construct the Font
}
}

And we're done... well, other than writing alternative versions of inject() for different versions of arguments, adding exception transparency, sorting out the poor concurrency in Memoizer.invoke(), and working out what Bob and inject() should really be called ;)

The key point is that we've now seen examples of currying, uncurrying and partial application being used as building blocks to support the creation and/or usage of a more obviously useful API.

Wednesday, December 5, 2007

Restricted syntax fun

WARNING: This entry's content relies on Javascript so you'll need to read it in a browser window.

Neal Gafter has blogged about some possible alternatives to the RestrictedFunction approach used by the current Closures spec, and I think it may be useful to get more of a glimpse at how a couple of these suggestions look in terms of code.

If you've just opened this page you should see some code below which illustrates the use of one of Neal's suggestions - allowing function types to be declared in such a way that we can additionally specify certain marker interfaces (such as RestrictedFunction) as part of a function type's type declaration.

Neal also mentions another option, which uses a slightly different syntax for unrestricted and restricted closures (and function types). The two input fields below allow you to vary the tokens used - click the 'Show me' link after changing them to see the effect. When the tokens are the same, '&RestrictedFunction' will be present in the type declarations, when they are different it will not.

Don't take the code examples too seriously!

Normal token: Restricted token: Show me

interface Foo {

void execute(Runnable r);

// invokes fn synchronously
void loop(int count, {=> void} fn);

// stores command in an instance variable for later invocation
void setCommand({=> void}&RestrictedFunction command);

// invokes reducer in the same thread
<T> T reduce(List<T> list, {T,T => T} reducer);

// invokes each evaluator concurrently, returning the evaluator with the highest
// result for the specified value
{int => int}&RestrictedFunction max(Collection<{int => int}&RestrictedFunction> evaluators, int value);

// invokes combiner in multiple threads
<T,U,V> ParallelArray<V> combine(ParallelArray<T> array1, ParallelArray<U> array2,
{T,U => V}&RestrictedFunction combiner);

// curries a 3-argument unrestricted function
<A1,A2,A3,R> {A1 => {A2 => {A3 => R}}&RestrictedFunction}&RestrictedFunction
        
curry({A1,A2,A3 => R} fn);

// curries a 3-argument restricted function
<A1,A2,A3,R> {A1 => {A2 => {A3 => R}&RestrictedFunction}&RestrictedFunction}&RestrictedFunction
        
curry({A1,A2,A3 => R}&RestrictedFunction fn);
}


silliness:
for (int i = 0; i < 10; i++) {

Foo foo = makeMeAFoo();

int count = 0;

foo.execute({=> if (++count == i) break silliness;});
foo.execute({=> System.out.println("executed!");});

foo.loop(5, {=> if (++count == i) break silliness;});
foo.loop(5, {=> System.out.println("executed!");});
foo.loop(5) {
if (++count == i) break silliness;
}

foo.setCommand({=> System.out.println("executed!");});

{String, String => String}&RestrictedFunction reducer = {String s1, String s2 => s1 + " " + s2};
String result1 = foo.reduce(myListOfStrings, reducer);
String result2 = foo.reduce(myListOfStrings,
{String s1, String s2 =>
if (++count == i) {
break silliness;
}
s1 + " " + s2
});

List<{int => int}&RestrictedFunction> evaluators = new ArrayList<{int => int}&RestrictedFunction>();
evaluators.add({int i => i + 1});
evaluators.add({int i => i * 2});
evaluators.add({int i => i * i});
{int => int}&RestrictedFunction maxEvaluator = foo.max(evaluators);

{String => {String => {String => String}}&RestrictedFunction}&RestrictedFunction
curried1 = curry({String s1, String s2, String s3 => s1 + s2 + s3});

{String => {String => {String => String}&RestrictedFunction}&RestrictedFunction}&RestrictedFunction
curried2 = curry({String s1, String s2, String s3 => s1 + s2 + s3});
}

Saturday, December 1, 2007

Currying and Partial Application with Java Closures

I had intended to dive straight in and continue with the earlier memoization example, extending it to work with cases where we have an arbitrary number of keys, but in writing that up I realised that I was making use of a couple of concepts which deserved a bit of explanation in their own right: currying and partial application.

There's a lot of confusion about these two, and the terms are often used interchangeably (although they are different!), partly because they naturally vary in their implementation depending on the underlying language. This blog entry is an attempt to informally describe the two concepts in a way that makes sense for Java with Closures, so that I can refer to them in later posts.

OK, first up then we have:

Currying (and uncurrying)

Say we have a function accepting 3 arguments of types A1, A2 and A3 and returning a value of type R. Its type would be:

{A1, A2, A3 => R}

This function's type in curried form would be:

{A1 => {A2 => {A3 => R}}}

Currying transforms a function which takes multiple arguments into an equivalent single-argument function which takes the first argument of the original function and returns another single-argument function, which in turn takes the second argument of the original function and returns yet another single-argument function... etc. The last single-argument function in the chain, which takes the last argument of the original function, will invoke the original function, passing all the arguments in one go, and returning its result.

If this is as clear as mud, a more concrete example may help. Imagine we have a simple 2-argument function which takes a String key and a Locale, and uses those to find a translation of some user-interface text by calling a method with the signature String lookup(String key, Locale locale) :

{String, Locale => String} translator =
{String key, Locale locale => lookup("somePrefix." + key, locale)};

we can use our translator function like this:

String translatedText = translator.invoke("name", customer.getLocale());

Now let's say we have a method called curry which takes any 2-argument function and returns the curried form of that function. Its signature might be:

<A1, A2, R> {A1 => {A2 => R}} curry({A1, A2 => R} fn)

This allows us to curry our translator function, and provide the arguments one at a time, rather than all in one go:

{String => {Locale => String}} curriedTranslator = curry(translator);
{Locale => String} nameTranslator = curriedTranslator.invoke("name");
String translatedText = nameTranslator.invoke(customer.getLocale());

This might not look much use at first glance, but it means that we can pass curriedTranslator to another method which knows how to provide the key but not the Locale, or that we can store nameTranslator away somewhere and use it at a later point, without having to know the key.

An implementation of the curry() method above might be:

static <A1, A2, R> {A1 => {A2 => R}} curry({A1, A2 => R} fn) {
return {A1 a1 => {A2 a2 => fn.invoke(a1, a2)}};
}

Notice that it uses closures to capture references to the original function fn and the first argument a1 so that they are available when the final function is invoked with the value a2.

This is a slightly simplistic version of curry() - in practice we might want to pass it a function which throws one or more checked exceptions; the closures proposal has provisions for implementing this in a very nice way, and I'll cover that at a later point. More importantly, this method only curries 2-argument functions so if we want to curry a function with more arguments we'll need to write a corresponding version of the curry() method; it isn't difficult to overload curry() to cope with n arguments, but how many overloaded versions should we provide by default? Solving this particular problem for all possible values of n would probably require additional support from the language however.

In any case, the key thing to remember about currying is that it takes a multi-argument function and transforms it into an equivalent single-argument function, and this can be a very important building block for more obviously useful concepts.

It's useful to note that some functions are naturally curried - these are functions originally defined in curried form and which may actually make use of arguments before the remaining arguments have been provided. I'll provide an example of this when we get to Partial Application.


While we're at it, uncurrying is the inverse of currying - it transforms a function in curried form into one which accepts all the arguments in one go. For example, uncurrying a function whose type is of the form:

{A1 => {A2 => {A3 => R}}}

results in a function with the type:

{A1, A2, A3 => R}

A simplistic uncurry() method for 2-argument functions can be implemented as follows:

<A1, A2, R> {A1, A2 => R} uncurry({A1 => {A2 => R}} fn) {
return {A1 a1, A2 a2 => fn.invoke(a1).invoke(a2)};
}



Partial Application

Closely related to currying is partial application. In practice, there are a number of subtly different interpretations of the term 'partial application', but let's start by informally defining it as the process of transforming a multiple-argument function into another function accepting fewer arguments, by providing some of the arguments.

For example, partially applying a function of type {A1, A2, A3 => R} to a value of type A1 results in a function of type {A2, A3 => R}. Partially applying it to two values of type A1 and A2 results in a function of type {A3 => R}.

To see this in practice, let's change the original translator example to allow different sets of translations depending on some Product:

{Product, String, Locale => String} translator =
{Product product, String key, Locale locale =>
lookup(product.getName() + '.' + key, locale)};

Now let's define a method called partial, which partially applies a 3-argument function to the value of its first argument:

<A1, A2, A3, R> {A2, A3 => R} partial({A1, A2, A3 => R} fn, A1 a1);

We can use this as follows:

{String, Locale => String} notepadTranslator =
partial(translator, Product.NOTEPAD);

An implementation of this version of partial() might be:

static <A1, A2, A3, R> {A2, A3 => R} partial({A1, A2, A3 => R} fn, A1 a1) {
return {A2 a2, A3 a3 => fn.invoke(a1, a2, a3)};
}

Notice again the use of a closure to capture the meaning of fn and a1 so that they are available when a2 and a3 are finally supplied.

Interpretations in other languages often define partial application in terms of functions in curried form, which we can also do:

Partially applying a function of type {A1 => {A2 => {A3 => R}}} to a value of type A1 results in a function of type {A2 => {A3 => R}}. Partially applying it to two values of type A1 and A2 results in a function of type {A3 -> R}.

The signature for an overloaded version of partial() which works with curried functions could be:

<A1, A2, A3, R> {A2 => {A3 => R}} partial({A1 => {A2 => {A3 => R}}} fn, A1 a1);

Implementing it leads us to an interesting choice, though. We could simply define it as:

static <A1, A2, A3, R> {A2 => {A3 => R}} partial({A1 => {A2 => {A3 => R}}} fn, A1 a1) {
return fn.invoke(a1);
}

which doesn't give us much compared to just calling fn.invoke() ourselves. Alternatively we could choose:

static <A1, A2, A3, R> {A2 => {A3 => R}} partial({A1 => {A2 => {A3 => R}}} fn, A1 a1) {
return {A2 a2 => {A3 a3 => fn.invoke(a1).invoke(a2).invoke(a3)}};
}

with the key difference being that the second version defers any invocation until all the arguments' values have been supplied - this may sound like a subtle distinction, but if fn is a naturally curried function, there may be an observable difference. Consider the following (somewhat contrived) example which uses a fictional database connection type DBConnection to execute some SQL:

{DBConnection => {String => boolean}} dbUpdater =
{DBConnection conn =>
conn.startTransaction();
{String sql =>
boolean success = false;
try {
executeUpdate(conn, sql};
conn.commit();
success = true;
}
finally {
conn.endTransaction();
}
success
}
};

Partially applying dbUpdater with a DBConnection results in very different behaviour depending on which implementation of partial() we opt for. Using the first version, a database transaction is started immediately, but using the second this doesn't happen until the SQL is supplied, which may be at a much later point in time.

This example may not be particularly realistic, but it should illustrate the difference in behaviour between the two implementations of partial() for curried functions.

The deferring version strikes me being as the more useful of the two, as its semantics are distinct from simply invoking a curried function with each argument in turn (which is all the first version does), but I'm not certain whether this choice could prove confusing in the long run if the distinction is not fully understood.



Bear in mind that there are other interpretations of currying and partial application which will disagree with mine on various points, or extend these definitions with other variations. Hopefully the underlying ideas will be reasonably clear, although the trivial examples above will probably seem less than convincing right now - the memoization follow-up will make better use of them.

I also have a rapidly growing set of implementations of curry, uncurry, partial and other useful methods which I'll try to include.

Memoization with Java Closures

I've been doing some catch-up reading recently, and one idea I've read about on some C# blogs is that we can borrow something from the functional programming world called 'memoization' and implement it neatly using closures to provide an alternative mechanism for some common coding problems.

Basically, memoization allows us to store a result of some kind against the input parameters from which the result was derived, and to retrieve that result again given the same parameters without having to calculate it again from scratch, which may be costly or contrary to the fundamental design. This should sound pretty familiar - if we're thinking about performance we might use an approach like this and call it a cache, and it can also be used as a way to implement the Singleton or 'Multiton' patterns for controlling object creation.

Using the BGGA Closures for Java prototype, we can implement a very simple memoize method like this:

public class Memoization {
static <A, R> {=> R} memoize({=> R} fn) {
boolean cached = false;
R cachedValue = null;
return {=>
synchronized(fn) {
if (!cached) {
cachedValue = fn.invoke();
cached = true;
}
}
cachedValue
};
}
}


This is an extremely basic form - it's only applicable when there are no parameters used to calculate the result - but we can use it to implement a singleton class Foo:

import static Memoization.*;
...
public class Foo {

private static {=> Foo} fooMemoizer =
memoize({=> new Foo()});

public static Foo getInstance() {
return fooMemoizer.invoke();
}
...
}

This works because the call to memoize() creates two local variables, cached and cachedValue, and returns a closure literal which has access to those variables and the fn parameter which knows how to get the value we're after. When we invoke() singletonMemoizer for the first time, cached is false, so fn is invoked, its result is stored in cachedValue, and cached is set to true. When we invoke singletonMemoizer again, cached is now true so we just return cachedValue.

There are neater ways to implement the singleton pattern in Java, but what if we return a value based on some key, where providing the same key multiple times should result in same value being returned each time? In Java 6 we might write:

public class Foo {

private static Map<Key, Foo> instanceMap =
new HashMap<Key, Foo>();

public static Foo getInstance(Key key) {
Foo foo = null;
synchronized(instanceMap) {
foo = instanceMap.get(key);
if (foo == null) {
foo = createFoo(key);
instanceMap.put(key, foo);
}
}
return foo;
}
...
}
This is also very common, and sometimes seen as an example of the 'multiton' pattern. Now let's overload memoize() to cope with this:

static <A, R> {A => R} memoize({A => R} fn) {
Map<A, R> cache = new HashMap<A, R>();
return {A a =>
R value = null;
synchronized(cache) {
value = cache.get(a);
if (value == null) {
value = fn.invoke(a);
cache.put(a, value);
}
}
value
};
}

There's a real advantage to using the memoize() approach here - we've abstracted the caching and thread synchronization logic into a general purpose method, and all we have to provide each time we use it is a simple closure literal which knows how to create a Foo given a particular Key:

import static Memoization.*;
...
public class Foo {

private static {Key => Foo} fooMemoizer =
memoize({Key key => createFoo(key)});

public static Foo getInstance(Key key) {
return fooMemoizer.invoke(key);
}
...
}

This advantage shouldn't be underestimated - when we re-code the same logic over and over, variations inevitably turn up in the form of bugs, which is especially nasty when we're dealing with thread-safety concerns (and you don't need to be explicitly using Threads or java.util.concurrent for thread-safety to be relevant!).

The next steps are to look at how we might write a version of memoize() which will work with multiple keys, but I'll save that for the next post.


UPDATE: Neal Gafter kindly pointed out a school-boy error in the synchronization I used in the first version of memoize() - I've updated the method accordingly. This just emphasises the point though: finding and fixing the bug in one place is far easier and better than finding and fixing all variations across multiple implementations of the same logic.