C# Lambda Calculus

C# Lambda Calculus

As promised in my previous article about the dynamic keyword and functional programming, I want to give a more concrete and complex examples of lambdas.

The first will cover less theoretical aspects, as the title suggests that it's going to be a article about lambda calculus not expressions. One cool thing that can be done with the new C# 4.0 features are functional tuples, normally it could be done by just defining a generic class that holds n type arguments, but then we cannot name them, well in C# .4 we can, but still it has to be a class, and let's say we want to use a tuple more like in F# when we just define the fields, to do this we can use the dynamic keyword along with anonymous delegates.

/// <summary>
/// The tuple function, that is a expressive
/// representation of ordered set.
/// </summary>
/// <param name="arg">arg</param>
/// <returns>System Func dynamic dynamic.</returns>
public static Func<dynamic, dynamic> Tuple(dynamic arg)
{
    List<dynamic> list = new List<dynamic>();

    return delegate(dynamic argument)
    {
        list.Add(arg);
        list.Add(argument);
        return new Func<dynamic, dynamic>(TupleInternal(argument, list));
    };
}

/// <summary>
/// Internal Tuple, that stores value pairs.
/// </summary>
/// <param name="arg">arg.</param>
/// <param name="list">list.</param>
/// <returns>System Func dynamic dynamic.</returns>
private static Func<dynamic, dynamic> TupleInternal(dynamic arg, List<dynamic> list)
{
    return delegate(dynamic argument)
    {
        if (argument == null)
        {
            return list;
        }

        list.Add(argument);
        return new Func<dynamic, dynamic>(TupleInternal(argument, list));
    };
}

Note: As you can see if the argument passed is null then the function will return the result list, which is not very good actually because null is a important way of carrying information, therefore some kind of typed delegate would be better, but for demonstration reasons we will stay with null.

This example is more o less the same as with curry, now we just keep storing the data in a list, so there's nothing new about this, but this is a more expressive representation of the list.add :-).

Not let's use you tuple:

List<object> tupleResult = Program.Tuple(1)(2)(3)("abc")(null);

As you can see, now the list representation is very expressive and it's similar to F# tuple, syntacticly.

But when the new added functional aspect really shines, is the lambda calculus. Now we can implement in C# a full set of predicates, and lambda functions.

We are going to look mostly on Binary Lambdas (lambdas can be numerical also).

First we need to define a True and False function, as a base of your logic, so a TRUE and FALSE in lambda calculus is a two argument function that returns a single argument.

TRUE := λxy.x

FALSE := λxy.y

The equivalent in C# can be represented like so:

var LT = new Func<dynamic, Func<dynamic, dynamic>>(x => y => x);
var LF = new Func<dynamic, Func<dynamic, dynamic>>(x => y => y);

Now that we have our functions, we need something to evaluate them, the preferred system is true, false therms, but it could be some other thing, thus resulting in L system creation etc. But let's play nice and stick to basics.

var LEval = new Func<dynamic, dynamic>(x => x(true)(false));

the LEval function will evaluate our logic functions, when we pass them as a parameter. This still is not very interesting, so lets define some functions that do binary operations like NOT, AND and OR.

AND := λpq.p q p

OR := λpq.p p q

NOT := λpab.p b a

our equivalent of those functions will look like so:

var LNot = new Func<dynamic, dynamic>(x => x(false)(true));
var LAnd = new Func<dynamic, Func<dynamic, dynamic>>(x => y => x(y)(x));
var LOr = new Func<dynamic, Func<dynamic, dynamic>>(x => y => x(x)(y));

At first this is very hard to get into, but consider the NOT function, with LT argument. NOT evaluates the LT function with false thus the x in LT is false, and the result is another delegate that takes the y argument in LT then NOT evaluates it with true, but LT returns always x no mater the y parameter and as you remember x is false now, so the value of LT was negated, the same will happen to LF.

So our logic system works, consider the same for other functions.

So that's all for now, this was an introduction to the lambda calculus, and the most basic operations but i will expand on that. And probably in some time I will define something that we could call a pseudo DSL (domain specific language), pseudo because we will use only the lambda logic, and calculus defined on different therm base.