Currying

Lambda Expressions are a shorthand function notation. Curried Lambda Expressions are a sequence of single-variable expressions that are daisy-chained together to build the result. Remember the simple arithmetic expression for addition:

(x,y) => x + y;

If we curried this expression it could be re-written as:

x => y => x + y;

Both expressions provide the same result.

Note: Currying was invented by Moses Schönfinkel and Gottlob Frege but the nom de guerre “currying” was coined by Christopher Strachey after Haskell Curry. Schönfinkelisation is another proposed name and while I like the later, I somehow don’t think it will catch on.

If you recall your undergrad computer science classes, since the 1940s there has been a lot of interest in Alan Turing’s Turing machine, in part to solve the Entscheidungsproblem or halting problem. Currying was a way to create sort-of Turing machine from the Lambda Calculus.

The trick to currying is to daisy-chain the inputs one at a time on the left, chained together with the Lambda operator ending with the final expression using all inputs on the right.

There are articles on recursion (which look pretty complicated), but there are very few (so far) complete theories on what we would practically use currying for. Consequently, in the interim I have guessed at a few but remain entirely unconvinced that there are as yet significant mainstream applications for currying. Here are my theories thus far:

Theory 1: Currying may make it easier for code generators to produce Lambda Expressions because only one part of the expression need be emitted at a time, making it easier to write the emitters (code that writes code).

Theory 2: There are so many smart people at Microsoft competing for brain-power kudos, they couldn’t help themselves. (Sorry, I couldn’t resist a friendly jab.)

Theory 3: Currying is by accidental design as to make the implementation of Lambda Expressions as complete as possible and no one really knows what to do with them.

There is an interesting game of “partial completions” one can play with Currying. A partial completion is where one takes a Lambda Expression, provides or fixes one of the many variables, and what is returned is a new Lambda Expression instead of the result. Here is an example (Listing 2):

Listing 2: A partial completion for adder.

static void PartialCompletion()
{
  Func<int, Func<int, int>> adder = x => y => x + y;
  Func<int, int> incrementer = adder(1);
  Console.WriteLine(adder(5)(4));
  Console.WriteLine(incrementer(3));
  Console.ReadLine();
}

In the listing adder is a curried Lambda Expression that accepts one argument and returns a Lambda Expression that accepts one argument. (Refer to my article on “Programming with Generic Delegates and Lambda Expressions” for more information on the generic delegate Func.) We invoke an expression like adder as follows:

Which in the example yields 9.

By fixing the first argument x, as is done with incrementer, we get the partial completion y => 1 + y; that is, we get a new function. By examining adder and incrementer one can argue that what we have done is created a new function from an existing one. This is in fact something programmers have been doing for a very long time with regular functions.

So far there are very few great books on Lambda Expressions that aren’t math books, and the math books can be very hard to find and read. I suspect that there are some pretty good non-C# books on Lambda Expressions, but I haven’t gotten my hands on any of them yet.

For fun I have provided some sample code that will let you explore closures, currying, and partial completions with your new copy of Visual Studio 2008.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Expressions;

namespace LambdaExpressions
{
  class Program
  {
    static void Main(string[] args)
    {
      // very simple lambda
      Action<int> wait = time => System.Threading.Thread.Sleep(time);

      // simple Lambda
      Func<int, int, float> divide = (x, y) => x / y;
      Console.WriteLine(divide(5, 6));

      // multi-statement lambda
      Action<string> pause = message =>
        {
          Console.WriteLine(message);
          wait(500);
        };

      pause("test");

      // closure Lambda 
      float rate = 0.06f;
      Func<float, float> michiganTax = amount => amount * (1 + rate);
      pause(michiganTax(99.99f).ToString());

      // currying
      Func<float, Func<float, float>> add = x => y => x + y;
      pause(add(1.3f)(2.5f).ToString());

      // create a new function decrement
      Func<float, float> decrement = add(-1f);
      pause(decrement(5).ToString());


      //using System.Linq.Expressions;
      Func<float, float, float> add2 = (x, y) => x + y;

      var exp = add2.ToCurryExpression();
      pause(exp.ToString());
      Console.ReadLine();

    }
  }

  public static class ExtendsLambda
  {
    // extension method that curries
    // borrowed from Dustin Campbell's blog at
    // http://diditwith.net/2007/08/15/TheArtOfCurrying.aspx
    public static Func<T1, Func<T2, TResult>> 
      Curry<T1, T2, TResult>(this Func<T1, T2, TResult> f)
    {
      return t1 => t2 => f(t1, t2);
    }

    public static Expression<Func<T1, Func<T2, TResult>>>
      ToCurryExpression<T1, T2, TResult>(this Func<T1, T2, TResult> f)
    {
      var exp = f.Curry();
      Expression<Func<T1, Func<T2, TResult>>> result = t1 => t2 => f(t1, t2);
      return result;
    }
  }
}

Summary

Lambda Expressions and especially Currying represent a paradox. Lambda Expressions are useful for LINQ (Language Integrated Query) but Lambda Expressions break the golden rule “Thou shalt write no code that is esoteric”.

Microsoft and .NET have done a great job of thinking of use scenarios and potential problems, resulting in closures and a complete implementation that supports currying. What remains to be seen is what the user community at large does with this capability. Lambda Expressions and currying will probably remain one of the more challenging language features for most programmers for some time, but I hope this article provided some food for thought.

Biography

Paul Kimmel is the VB Today columnist for HYPERLINK "http://www.codeguru.com/" \t "new" www.codeguru.com and has written several books on object-oriented programming and .NET. Check out his upcoming book LINQ Unleashed for C# due in Spring 2008. You may contact him for technology questions at pkimmel@softconcepts.com.

If you are interested in joining or sponsoring a .NET Users Group, check out www.glugnet.org. Glugnet opened a users group branch in Flint, Michigan in August 2007. If you are interested in attending, check out the www.glugnet.org web site for updates.