Curry for Dummies

Introduction

Functional programming concepts aren’t that hard but sometimes a little abstract. In this post I’ll try to demystify the concept of currying, or - in simple words – partial function application. If you wonder where the name “curry” comes from, it’s named after Haskell Curry, one of the creative minds behind functional programming, and indeed as the name implies it adds quite some spicy taste to functional programming. To be completely honest, currying wasn’t originally invented by Haskell Curry; Haskell himself attributed the technique to Schönfinkel although another mathematician Frege was using it also at that time (in the pre-internet era, it wasn’t so uncommon for different people to have the same idea independently from each other without knowing each other’s work in real-time).

Talking beta

So, what’s it all about? In the lambda calculus, one of the basic rules to deal with functions is the so-called beta-conversion. It’s nothing more but a fancy name for function application. Assume you have a function called “add”, looking like:

λ a b . a + b

Every symbol between the λ symbol and the . acts as a parameter to the function while the function’s body is specified to the right of the .. In C# 3.0 syntax this would look like (ignoring the fact the expression above is untyped and assuming int for both parameters):

(int a, int b) => a + b

Beta-conversion allows us to apply the function, like this:

(λ a b . a + b) 1 2

which is left-associative:

(((λ a b . a + b) 1) 2)

and carried out by formal substitution. Evaluating the inner portion first looks like (the parameter “binding” is underlined):

(((λ a b . a + b) 1) 2)

This means we can substitute a for 1 in the body of the function, like this:

((λ b . 1 + b) 2)

What’s left in the inner parentheses now is a new function that takes one remaining argument:

λ b . 1 + b

This is the basic idea behind currying. Going back to C# 3.0 this would mean we’d be able to write something like:

Func<int, int, int> add = (int a, int b) => a + b;
Func<int, int> addOne = add(1);

But we can’t. The compiler would complain about the second line, telling us that the delegate doesn’t take one argument. In other words, the language (as opposed to for example F#) doesn’t support currying. However, I still want to show you how such a feature would work conceptually by lifting our lambda expressions out of the language and switching to expression trees.

A simple approach

So how can we achieve building a currying sample in C# 3.0? There are different approaches really. One way to do it would be to take the original lambda function and “invoke” it with the supplied parameters, keeping the remaining parameters in place. In other words, we’re eating certain parameters at the head and leaving the remaining tail parameters there. Let’s assume we’re given a LambdaExpression instance with whatever body you can dream of. To make it concrete, consider this lambda expression:

(int a, int b) => Add(a, b)

Here’s the corresponding code the compiler would generate if you assign the expression above to an Expression<Func<int,int,int>> typed variable (the Expression<T> part here is of enormous importance and tells the compiler to generate an expression tree as opposed to an anonymous method):

ParameterExpression a = Expression.Parameter(typeof(int), “a”);
ParameterExpression b = Expression.Parameter(typeof(int), “b”);
Expression<Func<int, int, int>> e = Expression.Lambda<Func<int, int, int>>(
Expression.Call(null, typeof(Operators).GetMethod(“Add”), a, b),
a, b
);

Given this expression object and a set of to-be-applied parameter values, we want to create a new lambda expression with less (i.e. the remaining) parameters. Let’s step back a while and come up with a generalized signature for currying:

LambdaExpression Curry(LambdaExpression func, params Expression[] parameters);

What we could do now, rather naively, is taking the original lambda expression and wrap it in an InvocationExpression, passing in the supplied parameters (getting rid of the “eaten” lambda parameters) and the remaining lambda parameters and make that the body to a new lambda expression that still has the remaining lambda parameters. More words than lines of code, so here’s how this would look like, using some LINQ to Objects operators:

LambdaExpression Curry(LambdaExpression func, params Expression[] parameters)
{
    ParameterExpression[] lambdaParams = func.Parameters.Skip(parameters.Count).ToArray();
    return Expression.Lambda(Expression.Invoke(func, parameters.Concat(lambdaParams)), lambdaParams);
}

In a “ToString” format the original lambda would look like:

(a, b) => Add(a, b)

and when applying currying like this:

LambdaExpression add1 = Curry((int a, int b) => Add(a, b), Expression.Constant(1));

the result looks like:

b => Invoke((a, b) => Add(a, b), 1, b)

The signature is definitely right, yielding a function with only one remaining argument, but the body looks like hell (imagine what it would look like if you’re currying 1 argument at a time for a 10-argument function). In addition, the parameter “b” is a little special (left to the reader to think about a bit more). Instead we’d like to see a simpler form that really illustrates formal substitution, yielding this:

b => Add(1, b)

Formal substitution

Time to switch gears and move from the quick-and-dirty solution above to a better solution that carries out real substitution. How can we achieve this? The first thing we need to know about is the fact that expression trees are immutable. There’s no way to change them, we can only create new ones. That’s exactly what we need to do here: given an expression tree for a lambda expression, take its body and clone it but while doing so, replace a set of given parameters (which will be instances of ParameterExpression) with their corresponding substitution values. Now we need to know how to clone an expression tree while rewriting certain portions on the way. The answer to this need is an expression tree visitor, and yes we have one on MSDN at http://msdn.microsoft.com/en-us/library/bb882521.aspx. What this piece of code does is simply recursively walking the expression tree and for each node it calls out to a virtual method (that we therefore can override) that has the behavior of new’ing up a new instance of an expression having the same values. Actually, ParameterExpressions are a funny exception to this rule since they act as reference placeholders for parameters and their equality is essential for this referencing to work (so, you’ll find simply “return p” in VisitParameter). Anyway, in order to use the visitor, we need to inherit from it and supply our desired behavior:

class CurryVisitor : ExpressionVisitor
{
    private Dictionary<ParameterExpression, Expression> _parameters;

    public CurryVisitor(Dictionary<ParameterExpression, Expression> parameters)
    {
        _parameters = parameters;
    }

    protected override Expression VisitParameter(ParameterExpression p)
    {
        if (_parameters.ContainsKey(p))
            return _parameters[p];

        return base.VisitParameter(p);
    }

    public Expression Clone(Expression exp)
    {
        return base.Visit(exp);
    }
}

So essentially we just have one constructor taking in mappings from parameters to their to-be-substituted-with values and one method to do the actual cloning. The only thing we override is VisitParameter to see whether the parameter being processed occurs in the dictionary of substitutions and if so, we copy in the substitution-valued expression. That’s it. Only remaining thing to look at is the Curry method:

LambdaExpression Curry(LambdaExpression ex, params Expression[] parameters)
{
    if (parameters.Length > ex.Parameters.Count)
        throw new InvalidOperationException("Too many parameters specified.");

    var assignments = new Dictionary<ParameterExpression, Expression>();

    for (int i = 0; i < parameters.Length; i++)
    {
        ParameterExpression parameter = ex.Parameters[i];
        Expression value = parameters[i];

        if (!parameter.Type.IsAssignableFrom(value.Type))
            throw new InvalidOperationException("Incompatible parameter value type for parameter " + parameter.Name);

        assignments[parameter] = value;
    }

    var visitor = new CurryVisitor(assignments);
    return Expression.Lambda(visitor.Clone(ex.Body), ex.Parameters.Skip(parameters.Length).ToArray());
}

This code is fairly straightforward. First, we make sure that the number of arguments we’re about to substitute doesn’t exceed the number of parameters we have available. Next, we cycle through the supplied parameter values, make sure their static types are compatible with the corresponding parameters’ static types, and build up the substitution dictionary. Finally, we create the visitor object, clone the lambda body, therefore eating the parameters starting from the head, and wrap the new body in a new lambda expression with the remaining parameters.

Here are a couple of examples:

    Expression<Func<int, int, int, int>> add = (a, b, c) => a + b + c;
    Console.WriteLine(add);
    Console.WriteLine(Curry(add, Expression.Constant(1)));

    Expression<Func<Func<int, int, int>, int, int, int>> binOp = (f, a, b) => f(a,b);
    Expression<Func<int, int, int>> binAdd = (int a, int b) => a + b;
    Console.WriteLine(binOp);
    Console.WriteLine(Curry(binOp, binAdd));

    Expression<Func<int, int>> d = a => a + a;
    Console.WriteLine(d);
    Console.WriteLine(Curry(d, Expression.Constant(1)));

and here’s the corresponding output:

The second sample is an interesting one to think about scoping and “name clashes” (or to get in the zen of alpha conversion). Obviously you can use the Compile method on all of the produced LambdaExpression objects above, giving you the delegate result of currying which you can invoke using DynamicInvoke:

Curry(binOp, binAdd).Compile().DynamicInvoke(1, 2); // produces 3

Enjoy your lambda with curry meal!