• C# Lambda Calculus and Dynamic Type Free Combinators

    by  • March 5, 2012 • .Net, Programming • 0 Comments

    Starting with version 4.0 of the language, C# introduced the concept of the dynamic type. It was designed to fix the growing problem arising from interoping with a COM API, where data boxed in an object is the norm, or values being passed to and from dynamic languages such as IronPython.

    Although the type dynamic is a static type, it bypasses some of the static type checking and most checks are done via late binding at runtime.

    Dynamic types extend the concept of the var type which was introduced in C# 3.0. var is a static type whose type is chosen at compile time. Dynamic types also extend the concept of generics, as it allows type specific operations to be done.

    Going back further C# 2.0 introduced anonymous methods, previously all delegates had to be named, from 2.o this could be done at runtime and were extended to incorporate lambda expressions in C# 3.0 where the delegate itself was done away with.

    What this means now in version 4.0 of C# and going forward to the beta of version 5.0 found in the Windows 8 Consumer Preview which includes a whole host of interesting features such as async and await, we can now perform most Lambda Calculus operations.

    Lambda Calculus was an offshoot of research into program language design and was meant to formalise mathematical computation into the notion of functions. Lambda Calculus paved the way for computability theory and its results are usually only found in the domain of functional languages such as ML or Haskell.

    One of the easiest and most interesting Lambda Calculus method is the Y Combinator. A reduction method which can help reduce certain recursive methods into a no recursive inline method call. The Y Combinator works by computing the recursive part of a method call as a “fixed point” on a non-recursive method.

    A “fixed point” is where an input of a function matches its output. For example in the following recursive equation:

    x = x^2 – 6

    The 2 “fixed point” solutions would be -2 or 3

    (-2) = (-2)^2 – 6

    (3) = (3)^2 – 6

    Therefore we could describe this as:

    x = f(x)

    The Y Combinator seeks to create a general purpose tool which can find these fixed points where the equation has the form:

    f = F(f)

    Where f is no longer a value, but a function.

    Deriving the Y Combinator

    To derive the Y combinator, start with the core property that we seek. Namely, if we give the Y combinator a functional F, then Y(F) needs to be a fixed point:

    Y(F) = F(Y(F))
    This is a bit useless at the moment as this still contains a self reference which would lead to an infinite recursion loop. Using a little λ-calculus, however, we can wrap the call to Y in a λ-term:
    Y(F) = F(λ x.(Y(F))(x))
    When we now invoke the the function Y, it immediately calls the function F, and passes it λ x.(Y(F))(x), which is equivalent to the fixed point. This technically would find the fixed point however the recursive element remains (the call to Y) thus we need to some more trickery to remove it.

    Using another construct called the U combinator, we can eliminate the recursive call inside the Y combinator, which, with a couple more transformations gets us to:

    Y = (λhF.F(λ x.((h(h))(F))(x))) (λhF.F(λ x.((h(h))(F))(x)))

    Hey presto, the right-hand-side makes no reference to Y!

    The Y Combinator in C#
    Here is what I have prepared earlier…

    Func, Func>, Func> Y = (f) =>
    {
        RecursiveFunction function = (h) =>
        {
            return (x) =>
            {
                return f(h(h))(x);
            };
        };
        return function(function);
    };
    

    This first part uses generics, if for the caller types dynamics are used, you can have a type free Y Combinator.

    To use the Y Combinator, you need to feed in the relevant code to perform the now non-recursive operation. For example, here is the code to work out factorials.

    Func factorial = Y(function=>
    {
        return x =>
        {
            return x == 0 ? 1 : x * function(x - 1);
        };
    });
    
    // For example, calculate the factorial of 5
    Console.WriteLine(factorial(5));
    

    About

    Software engineer. Tea drinker

    http://MrPfister.com

    Leave a Reply

    Your email address will not be published. Required fields are marked *