Wednesday, August 15, 2007

Oh! How I love that spicy Indian food!

Currying is a topic that I have wanted to cover in my C# 2.0 functional programming series for quite awhile. In fact, it is one of the reasons I decided to restrict this series to C# 2.0 in the first place. While curried lambda expressions in C# 3.0 are extremely compact, they are difficult to understand if you've never encountered them before. In contrast, C# 2.0's verbosity actually helps to clarify the concept.

Since Visual Studio 2008 Beta 2 has been released and many people are becoming more comfortable with it, you might see a little C# 3.0 slip in now and then. However, this article will continue to use C# 2.0 as its main dialect.

Let's get started.

What, Exactly, Is This "Currying" Thing?

First of all, currying has nothing to do with Indian or Thai food. It is named after the logician Haskell Curry (for whom the fabulous functional programming language, Haskell, also is named). The term refers to a special technique found in both mathematical logic and computer science.

The HaskellWiki defines currying as "the process of transforming a function that takes multiple arguments into a function that takes just a single argument and returns another function if any arguments are still needed." Errr... come again?

OK. Suppose that we have a simple function that takes two arguments and returns a value.

class Program
{
  delegate int Operation(int x, int y);

  static
 void Main()
  {
    Operation add = delegate(int x, int y)
    {
      return x + y;
    };

    Console
.WriteLine(add(13, 29));
 
}
}

Here we use an anonymous delegate to create a function that performs simple addition. This function takes two arguments, x and y, and returns a value, their sum.

To curry, we will transform our two-argument function into a single-argument function using a pair of anonymous delegates. The first delegate takes x and returns a second delegate which takes y. The second delegate actually contains the meat of the function and performs the addition of x and y.

class Program
{
  delegate CurriedOperation2 CurriedOperation(int x);
  delegate
 int CurriedOperation2(int y);

  static
 void Main()
  {
    CurriedOperation add = delegate(int x)
    {
      return delegate(int y)
      {
        return x + y;
      };
    };

    Console
.WriteLine(add(13)(29));
  }
}

Notice that the inner delegate can reference the argument x from the outer delegate through the principle of closure. This point will become very important a bit later. In addition, we have to change the way in which we call the add function. Extra parentheses must be used because we are now calling two functions instead of one.

The process of currying a function is not particularly difficult, but it requires a bit of thought. It would be useful to create some sort of general-purpose "Curry" function. This would be a higher-order function that takes an Operation delegate and returns a CurriedOperation delegate, performing the curry process for us.

class Program
{
  delegate int Operation(int x, int y);
  delegate CurriedOperation2 CurriedOperation(int x);
  delegate int CurriedOperation2(int y);

  static
 CurriedOperation Curry(Operation op)
  {
    return delegate(int x)
    {
      return delegate(int y)
      {
        return op(x, y);
      };
    };
  }

  static
 void Main()
  {
    Operation add = delegate(int x, int y)
    {
      return x + y;
    };

    CurriedOperation curriedAdd = Curry(add);

    Console
.WriteLine(curriedAdd(13)(29));
  }
}

This successfully makes the currying process more general purpose, but it is still tightly coupled to the types on which the delegates operate. To correct this, we should use C# 2.0 generics to parameterize by type. Introducing generics can be complicated, so let's start with our first example of the currying process.

class Program
{
  delegate TResult Func<TArg, TResult>(TArg a);

  static
 void Main()
  {
    Func<int, Func<int, int>> add = delegate(int x)
    {
      return delegate(int y)
      {
        return x + y;
      };
    };

    Console
.WriteLine(add(13)(29));
  }
}

The Func<int, Func<int, int>> syntax might look a little daunting at first, but using generics recursively only requires one delegate type instead of two. Essentially, we're defining a delegate that takes an int and returns a delegate that takes an int and returns an int. Got it? Other than that, the code is essentially the same.

Moving on to the more general-purpose solution...

class Program
{
  delegate TResult Func<TArg1, TArg2, TResult>(TArg1 a1, TArg2 a2);
  delegate TResult Func<TArg, TResult>(TArg a);

  static
 Func<TArg1, Func<TArg2, TResult>> Curry<TArg1, TArg2, TResult>(Func<TArg1, TArg2, TResult> f)
  {
    return delegate(TArg1 a1)
    {
      return delegate(TArg2 a2)
      {
        return f(a1, a2);
      };
    };
  }

  static
 void Main()
  {
    Func<int, int, int> add = delegate(int x, int y)
    {
      return x + y;
    };

    Func
<int, Func<int, int>> curriedAdd = Curry(add);

    Console
.WriteLine(curriedAdd(13)(29));
  }
}

Look carefully at this code. Sometimes it can be challenging to see the "forest for the angle brackets." However, the introduction of generics provides us with a function that can be used to curry two-argument functions of any type. Besides, most of the generic code can be shuffled off to a library, leaving the client code relatively simple.

Earlier, I mentioned that currying is much more concise in C# 3.0. Here's a translation of the last code sample to prove my claim.

static class Program
{
  static Func<TArg1, Func<TArg2, TResult>> Curry<TArg1, TArg2, TResult>(this Func<TArg1, TArg2, TResult> f)
  {
    return a1 => a2 => f(a1, a2);
  }

  static
 void Main()
  {
    Func<int, int, int> add = (x, y) => x + y;

    var
curriedAdd = add.Curry();

    Console
.WriteLine(curriedAdd(13)(29));
  }
}

First of all, we can remove the declarations of the Func<...> delegate types because they already exist in the C# 3.0 libraries. In addition, the conciseness of lambda expressions makes our anonymous delegates look like big, ugly brutes by comparison. Finally, C# 3.0 type inference takes care of the hideous Func<int, Func<int, int>> type through use of the "var" keyword. As icing on the cake, the Curry function can be turned into an extension method and called as if it were a member of "add."

The double-arrow-lambda-expression-thingy might look foreign until you realize that it actually represents two functions. So, the conciseness of C# 3.0 comes at the small price of a little familiarity.

What's the Point of All This?

The value of currying a function lies in what you intend to do with it afterward. Used wisely, curried functions can be building blocks in the creation of other functions. Consider the following code:

static void Main()
{
  Func<int, int, int> add = delegate(int x, int y)
  {
    return x + y;
  };

  Func
<int, Func<int, int>> curriedAdd = Curry(add);

  Func
<int, int> increment = curriedAdd(1);

  Console
.WriteLine(increment(41));
}

Here, we pass 1 to our curried "add" function and create a new function, "increment." The "increment" function is really just a reference to the inner delegate of the curried "add" function with x bound to the value of 1 through closure. This technique is known as partial application and is extremely powerful. (At the time of this writing, the Wikipedia article on currying doesn't distinguish between currying and partial application, but they are clearly different activities.)

Next time, we'll look deeper into partial application. The example in this article is simple but contrived, and it doesn't delve deeply enough into the possibilities. In the next article, we'll look at some truly useful examples of currying combined with partial application.

posted on Wednesday, August 15, 2007 11:35:46 AM (Pacific Standard Time, UTC-08:00)  #    Comments [7]

kick it on DotNetKicks.com