Refactoring Towards the Y Combinator: Part 6

This is a multi-part series. Part 1. Part 2. Part 3. Part 4. Part 5. Part 6.

This is the final part of my series on the Y combinator. By the end of part 5, the bulk of the work was done. All I have to do today is generalize it, clean it up and make it look pretty. Here is the code from part 5:

public class Solution09 : ISolution
    {
        public Factorial MakeFactorialFunction()
        {
            HigherOrderFunction<Factorial> algorithm = (Factorial f) =>
            {
                return (int x) =>
                {
                    return x < 2 ? 1 : x * f(x - 1);
                };
            };

            SelfApplicable<HigherOrderEvaluator<Factorial>> factorial = (SelfApplicable<HigherOrderEvaluator<Factorial>> self) =>
            {
                return (HigherOrderFunction<Factorial> alg) =>
                {
                    return (int x) =>
                    {
                        return alg(self(self)(alg))(x);
                    };
                };
            };
            return factorial(factorial)(algorithm);
        }
    }

I claimed that the factorial function, as it is defined here, is a version of the Y combinator. Indeed if you take a look at it, you will see that it really doesn’t have anything to do with calculating factorials anymore – that code has long since been moved into the “algorithm” function. But the signature of the function still mentions factorials, specifically the Factorial delegate. To get my definition for the Y combinator into a more usable state, I can replace usages of the Factorial delegate with Func<int,int>. Later on, I’ll be able to define a generic version so it can even be used for functions that take and compute a double, or string, or whatever. However when I make this change, I still need to return a Factorial (because my test harness requires the MakeFactorialFunction method to return a Factorial delegate). To get around this I will use an earlier trick of returning a lambda that can be cast as a Factorial delegate:

/// <summary>    
/// Its possible to make a generic version of the Y combinator for application to functions that take 1 argument and return a value of the same type.
/// Unfortunately we cannot continue to use the Factorial delegate if we want to make this generic version.
/// We rename the functions to better represent their purpose (factorial becomes Y, algorithm becomes factorial).
/// We can't just return Y(Y)(factorial)(x) because that will return a Func<int,int> but this method is supposed to return a Factorial. Although
/// they are basically the same thing, a conversion cannot be made. Therefore I have to return a lambda that calls Y(Y)(factorial)(x).
/// </summary>
public class Solution10 : ISolution
{
    public Factorial MakeFactorialFunction()
    {
        HigherOrderFunction<Func<int, int>> factorial = (Func<int, int> f) =>
        {
            return (int x) =>
            {
                return x < 2 ? 1 : x*f(x - 1);
            };
        };
        
        SelfApplicable<HigherOrderEvaluator<Func<int, int>>> Y =
            (SelfApplicable<HigherOrderEvaluator<Func<int, int>>> self) =>
            {
                return (HigherOrderFunction<Func<int, int>> alg) =>
                {
                    return (int x) =>
                    {
                        return alg(self(self)(alg))(x);
                    };
                };
            };
        
        return x =>
        {
            return Y(Y)(factorial)(x);
        };
    }
}

I can now make Y generic by moving it into its own generic class:

/// <summary>
/// Move Y into its own class.
/// </summary>
public class Solution11 : ISolution
{
    public Factorial MakeFactorialFunction()
    {
        HigherOrderFunction<Func<int, int>> factorial = (Func<int, int> f) =>
        {
            return (int x) =>
            {
                return x < 2 ? 1 : x * f(x - 1);
            };
        };

        return x =>
        {                
            return YCombinator<int>.Y(YCombinator<int>.Y)(factorial)(x);
        };
    }

    private static class YCombinator<T>
    {
        public static SelfApplicable<HigherOrderEvaluator<Func<T, T>>> Y =
            (SelfApplicable<HigherOrderEvaluator<Func<T, T>>> self) =>
            {
                return (HigherOrderFunction<Func<T, T>> alg) =>
                {
                    return (T x) =>
                    {
                        return alg(self(self)(alg))(x);
                    };
                };
            };
    }
}

There is some ugliness with calling Y on itself now, so I add a “ApplyY” helper to the YCombinator class to make this part easier. I let Resharper help me use a more terse syntax for the lambdas, and this is the result:

public class YCombinator<T>
{
    private static readonly SelfApplicable<HigherOrderEvaluator<Func<T, T>>> Y =
        self => algorithm => t => algorithm(self(self)(algorithm))(t);

    public static readonly HigherOrderEvaluator<Func<T, T>> ApplyY = Y(Y);

}

I’ve avoided using the terse lambda syntax up until now because I think it would have made comprehending the individual steps more difficult. I can use ApplyY like this:

return YCombinator<int>.ApplyY(factorial)(10);

Here is my final implementation for this entire exercise, utilizing the above class:

/// <summary>
/// This is the final implementation.
/// The Y combinator has been moved to a separate file. 
/// The factorial algorithm has been pushed to a static member and condensed.
/// </summary>
public class Solution12 : ISolution
{
    private static readonly HigherOrderFunction<Func<int, int>> factorial =
                    f => x => x < 2 ? 1 : x * f(x - 1);

    public Factorial MakeFactorialFunction()
    {
        return x => YCombinator<int>.ApplyY(factorial)(x);
    }

    // Example of using Y without any need for the Factorial delegate:
    public int CalculateFactorialOf10()
    {
        return YCombinator<int>.ApplyY(factorial)(10);            
    }

}

Now lets test my implementation of the Y combinator by using it to calculate Fibonacci numbers:

public static class Fibonacci
{
    private static readonly HigherOrderFunction<Func<int, int>> fibonacci =
        f => x => x < 3 ? 1 : f(x - 1) + f(x - 2);

    public static int Calculate(int nthNumber)
    {
        return YCombinator<int>.ApplyY(fibonacci)(nthNumber);
    }
}

Its horribly inefficient, but it works:

Console.WriteLine(Fibonacci.Calculate(10));

>> 55

So there you have it: the Y combinator implemented in C#, derived via many gradual refactorings. This implementation still has some limitations. For example, it won’t support a recursive algorithm that takes two arguments. You could of course modify the Y combinator class to support this, but because of the strongly typed nature of C#, it seems very difficult to make a definition of Y that could be applied to an algorithm with ANY signature. If you are interested in exploring the code that I provided in this series, you can download it here.

I really enjoyed this exercise and I would definitely encourage other programmers that are weak at functional programming to have a go at it. If you really know this stuff and my clumsy explanations made you cringe, please leave a comment! If you were following along with the series and got lost or stuck at some point, again, please comment! Practice makes perfect, but some constructive criticism can really help too. Thanks!

Refactoring Towards the Y Combinator: Part 5

This is a multi-part series. Part 1. Part 2. Part 3. Part 4. Part 5. Part 6.

Here is the state of affairs at the end of part 4:

public delegate Factorial HigherOrderFactorial(Factorial factorial);

public class Solution07 : ISolution
{        
    public Factorial MakeFactorialFunction()
    {
        HigherOrderFactorial algorithm = (Factorial f) =>
        {
            return (int x) =>
                {
                    return x < 2 ? 1 : x * f(x - 1);
                };
        };

        SelfApplicable<Factorial> factorial = (SelfApplicable<Factorial> self) =>
        {
            return (int x) =>
            {
                return algorithm(self(self))(x);
            };
        };

        return factorial(factorial);
    }
}

As I mentioned at the end of part 4, the problem with this implementation is that the factorial function creates a closure, capturing the algorithm variable. I fixed a similar problem in step 2 – in this case its fixed by having the factorial function accept ‘algorithm’ as an argument. Unfortunately my first attempt at this will not compile:

SelfApplicable<Factorial> factorial = (HigherOrderFactorial alg, SelfApplicable<Factorial> self) =>
{
    return (int x) =>
    {
        return alg(alg, self(self))(x);
    };
};

return factorial(algorithm, factorial);

Its not that simple, because it breaks the signature of the SelfApplicable delegate. So I will have to define a new delegate. To figure out what to call it, lets take a look at its signature:

public delegate Factorial SomeDelegate(SomeDelegate self, HigherOrderFactorial algorithm);

So it takes itself, and a HigherOrderFactorial, and its returns a Factorial. Well in that case isn’t it fair to say that it is a “higher order evaluator”? Its also self applying, so lets call it SelfApplyingHigherOrderFactorialEvaluator:

public delegate Factorial SelfApplyingHigherOrderFactorialEvaluator(SelfApplyingHigherOrderFactorialEvaluator self, HigherOrderFactorial algorithm);

/// <summary>
/// We can make the algorithm an argument to the factorial function. Unfortunately its not a particularly simple refactoring, because of the
/// self calling nature of the factorial function. We are forced to define a new self applying delegate that accepts the higher order function.
/// </summary>
public class Solution08 : ISolution
{        
    public Factorial MakeFactorialFunction()
    {
        HigherOrderFactorial algorithm = (Factorial f) =>
        {
            return (int x) =>
            {
                return x < 2 ? 1 : x * f(x - 1);
            };
        };

        SelfApplyingHigherOrderFactorialEvaluator factorial =
            (SelfApplyingHigherOrderFactorialEvaluator self, HigherOrderFactorial alg) =>
        {
            return (int x) =>
            {                            
                return alg(self(self, alg))(x);
            };
        };

        return factorial(factorial, algorithm);
    }
}

Phew! I was excited when this one worked – I could smell blood in the air. The body of that factorial function is starting to look pretty close to the Y combinator. Now I don’t know about you, but that factorial function is looking kind of hungry, so lets give it some curry! By currying it, I will have the opportunity to go back to using the SelfApplicable delegate. This is a tricky step, and I’m not quite sure how to break it down. I can start off by looking at the existing signature:

public delegate Factorial SelfApplyingHigherOrderFactorialEvaluator(SelfApplyingHigherOrderFactorialEvaluator self, HigherOrderFactorial algorithm);

I called this thing an evaluator, because it takes a HigherOrderFactorial, and it returns a Factorial. Essentially, it evaluates the higher order function which results in a normal order one. I could create a generic delegate to represent an evaluation operation, but to do so I would need to first create a generic delegate for representing a higher order function. Well that should be pretty straightforward:

public delegate T HigherOrderFunction<T>(T function);

The HigherOrderFunction delegate could be used instead of the HigherOrderFactorial delegate. Here is ‘algorithm’ modified to use the HigherOrderFunction delegate:

HigherOrderFunction<Factorial> algorithm = (Factorial f) =>
{
    return (int x) =>
    {
        return x < 2 ? 1 : x * f(x - 1);
    };
};

Now that I have a generic delegate for higher order functions, I can also create a generic delegate for their evaluation:

public delegate T HigherOrderEvaluator<T>(HigherOrderFunction<T> higherFunction);

Lets try to get comfortable with this before we move on. Lets say I used it like so:

HigherOrderEvaluator<Factorial> evaluator;

Then this is the same as (formatted for clarity):

Func<
    HigherOrderFunction<Factorial>, 
    Factorial
    > evaluator;

Which is the same as:

Func<
    Func<Factorial, Factorial>, 
    Factorial
    > evaluator;

I could expand out those Factorial delegates, but I do not think that is necessary. It would just cause an <int> explosion. Now that the HigherOrderEvaluator is defined and explained, I have the necessary tools to discuss how the SelfApplicableHigherOrderFactorialEvaluator is going to be replaced. Again, to make it easier to eyeball the changes, here it is:

public delegate Factorial SelfApplyingHigherOrderFactorialEvaluator(SelfApplyingHigherOrderFactorialEvaluator self, HigherOrderFactorial algorithm);

This delegate can be retired, because I can use this instead:

SelfApplicable<HigherOrderEvaluator<Factorial>>

BUT! I can only make that replacement if I curry the factorial method, as was discussed before. SelfApplicable only takes one argument, while you can see that the SelfApplyingHigherOrderFactorialEvaluator above takes two. Currying will allow me to reduce it to one argument, so I get to use SelfApplicable. Here is what it looks like:

public delegate T HigherOrderFunction<T>(T function);
public delegate T HigherOrderEvaluator<T>(HigherOrderFunction<T> higherFunction);

/// <summary>
/// Once again, we curry. This time its the factorial function again.
/// Believe it or not, the second function defined here is the Y combinator. Unfortunately, in this form it is specific to the factorial method..
/// </summary>
public class Solution09 : ISolution
{
    public Factorial MakeFactorialFunction()
    {
        HigherOrderFunction<Factorial> algorithm = (Factorial f) =>
        {
            return (int x) =>
            {
                return x < 2 ? 1 : x * f(x - 1);
            };
        };


        SelfApplicable<HigherOrderEvaluator<Factorial>> factorial = (SelfApplicable<HigherOrderEvaluator<Factorial>> self) =>
        {
            return (HigherOrderFunction<Factorial> alg) =>
            {
                return (int x) =>
                {
                    return alg(self(self)(alg))(x);
                };
            };
        };
        return factorial(factorial)(algorithm);
    }
}

I jumped out of my chair when this worked. I did a lap of my apartment, punching at the air. Yes, I am really that lame. ANYWAY…

The function that is still called ‘factorial’ is actually a version of the Y combinator specifically typed for being applied to factorials. In the final post for this series I will make it more general, clean it up, demonstrate it being used for Fibonacci and post the full source code.

Refactoring Towards the Y Combinator: Part 4

This is a multi-part series. Part 1. Part 2. Part 3. Part 4. Part 5. Part 6.

I finished the previous post with the following code:

public delegate T SelfApplicable<T>(SelfApplicable<T> self);

public class Solution05 : ISolution
{
    public Factorial MakeFactorialFunction()
    {
        SelfApplicable<Factorial> factorial = (SelfApplicable<Factorial> self) => 
        {
            return (int x) =>
            {
                return x < 2 ? 1 : x * self(self)(x - 1);
            };
        };
        
        return factorial(factorial);
    }
}

The next step, as I mentioned previously, is to attempt to remove the self(self) business from the factorial algorithm. The self calling aspect is really a technical concern, while the algorithm is more like business logic – it makes sense to want to separate the two. To do this, I’m going to apply a variation on the Extract Method refactoring. I’ll define the factorial algorithm using a new RecursiveFactorial delegate, and let the existing factorial function call it:

public delegate int RecursiveFactorial(int x, Factorial f);

/// <summary>
/// Lets try to seperate the algorithm definition for factorial from the infrastructure that is applying the recursion.
/// I extract the bit that calculates the factorial as a seperate function, and call it "algorithm". The existing factorial function now calls
/// the algorithm, applying itself to itself as it does.
/// </summary>
public class Solution06 : ISolution
{        
    public Factorial MakeFactorialFunction()
    {
        RecursiveFactorial algorithm = (int x, Factorial f) =>
        {
            return x < 2 ? 1 : x * f(x - 1);
        };

        SelfApplicable<Factorial> factorial = (SelfApplicable<Factorial> self) =>
        {
            return (int x) =>
            {
                return algorithm(x, self(self));
            };
        };

        return factorial(factorial);
    }
}

If you compare the two versions, you should be able to see that I have replaced the “return x < 2…” line of code with a call to “algorithm”, but I left the self(self) part where it was. The two concerns are seperated. But the RecursiveFactorial delegate should look familiar to you. Its sort of like my old friend, the SelfCallingFactorial, except it doesn’t seem to call itself, it just calls the factorial function you pass it. The funny thing is that it IS calling itself. Suprised? Perhaps I can help..

At the last line of the function, I return the result of evaluating the factorial function, passing in itself as an argument. I will try to expand this out by performing substitutions:

           
            // Redefine factorial to use more compact syntax.
            factorial = self => x => algorithm(self(self))(x);

            // This is the line of code to expand.
            return factorial(factorial);

            // Substitute the body of factorial in, replacing the self parameter with factorial
            return x => algorithm(factorial(factorial))(x);            

            // If you look inside, you can see that the line we just substituted has another factorial(factorial). Lets substitute that one too.
            // I will have to rename the integer parameter when I do so, to avoid a clash. I'll call it x1.
            return x => algorithm(x1 => algorithm(factorial(factorial))(x1))(x);

            // Whoops! That pesky factorial(factorial) has appeared again! Substitute, substitute!
            return x => algorithm(x1 => algorithm(x2 => algorithm(factorial(factorial))(x2))(x1))(x);

            // Is there no end in sight?

No, there is not. Doing it this way, it looks like I am stuck in some sort of infinite loop, but this is because I’ve expanded the code incorrectly. The first few substitutions are fine – its when I attempted to expand this line that I made a mistake:

return x => algorithm(x1 => algorithm(factorial(factorial))(x1))(x);

The point to notice about this line is that the factorial(factorial) is inside the body of a lambda, being passed as an argument. It will only be evaluated if x is >= 2. If I called the function this line returns with the argument of 1, then that factorial(factorial) part will never be called. I would like to show you the correct expansion of this line but I struggled to get an expansion that compiled properly. Perhaps it would suffice to say that the next step would be to expand the algorithm call, rather than the factorial call.  Hopefully this expansion discussion has illuminated the self calling nature of the solution, but also explained how an infinite loop is avoided.

Getting back on track, the reason why I pointed out that RecursiveFactorial bares some resemblance to SelfCallingFactorial is because I intend to repeat an operation I performed in part 3; I want to apply the currying technique to ‘algorithm’. I will define yet another delegate to represent the curried version of algorithm and call it HigherOrderFactorial. Why “higher order”? Because the curried version accepts a Factorial function and returns a Factorial function –  it operates on functions rather than operating on integers:

public delegate Factorial HigherOrderFactorial(Factorial factorial);

/// <summary>
/// Apply the currying techinque again, this time to algorithm, we arrive at a higher order function. 
/// Now algorithm takes a factorial function, and returns a factorial function.
/// </summary>
public class Solution07 : ISolution
{        
    public Factorial MakeFactorialFunction()
    {
        HigherOrderFactorial algorithm = (Factorial f) =>
        {
            return (int x) =>
                {
                    return x < 2 ? 1 : x * f(x - 1);
                };
        };

        SelfApplicable<Factorial> factorial = (SelfApplicable<Factorial> self) =>
        {
            return (int x) =>
            {
                return algorithm(self(self))(x);
            };
        };

        return factorial(factorial);
    }
}

If you take a look at the changes made to ‘algorithm’ in this step, you will see that they are really quite similar to the changes made in Part 3, where the factorial function was curried. Of course, when I modified the signature of ‘algorithm’, I also had to modify the call to it:

This should be really familiar. Go back and reread part 3 if you are not comfortable with this transformation.

The next step is to address the fact that ‘algorithm’ is a captured variable inside the factorial closure. It would be better to pass in the algorithm as an argument to the factorial function. I will tackle this in the next post.

Refactoring Towards the Y Combinator: Part 3

This is a multi-part series. Part 1. Part 2. Part 3. Part 4. Part 5. Part 6.

I would like to begin this post with an explanation of a technique called currying. Currying is a mechanism that allows a function that takes multiple arguments to be converted to a function that takes only a single argument. I will be using it today, but it would probably be best to look at currying in a simpler context before it is applied to the factorial scenario. I’ve constructed a simple example of currying based on adding two numbers. The inline comments should explain what is going on. Brief disclaimer: currying is another one of those theoretical computer sciency concepts that I’ve understood just enough to get by. If my explanation sucks, please leave a comment so I can fix it.

// The addition function takes two integers, and returns the result of adding them together.
Func<int, int, int> add = (x, y) => x + y;
int five = add(2, 3);

// If you often needed to add two to something, you could explicitly define a function that does so.
// It would only need to take one argument.
Func<int, int> addTwo = x => add(x, 2);
five = addTwo(3);

// Perhaps you also need to add four often. Again, you could make a function for it, and it would only take one argument.
Func<int, int> addFour = x => add(x, 4);
five = addFour(1);

// Now there is some duplication between addTwo and addFour. What if we could make a function, that makes adders?
Func<int, Func<int, int>> makeAdder = (int valueToAdd) =>
{
   return x => add(x, valueToAdd);
};

// Excellent, now we can reconstruct addTwo and addFour using makeAdder
addTwo = makeAdder(2);
addFour = makeAdder(4);

// And use them like before
five = addTwo(3);
five = addFour(1);
          
// Lets compute 6 + 4, by making an adder that adds 6 to numbers, an then passing 4 to it.
int ten = makeAdder(6)(4);

// Well it appears we can now add any two numbers together by using makeAdder. But makeAdder only takes one argument, not two.
// makeAdder is the result of applying currying to the add method.

Here is another way of stating it: if you have a function that takes arguments A and B and returns C, you can create a function that takes argument A, and returns a function that takes argument B and returns C. By calling this function with A, you then call the resulting function with B, and you get C. That is currying. Lets get back to factorials – here is the code the last post finished up with:

public delegate int SelfCallingFactorial(int x, SelfCallingFactorial self);

/// <summary>
/// Creating the factorial method inside the returned lambda resolves the garbage collection problem.
/// This solution does not involve a closure, so its pretty good. But...
/// </summary>
public class Solution03 : ISolution
{
   public Factorial MakeFactorialFunction()
   {
       return (int x1) =>
       {
           SelfCallingFactorial factorial = (int x, SelfCallingFactorial self) =>
           {
               return x < 2 ? 1 : x * self(x - 1, self);
           };

           return factorial(x1, factorial);
       };
   }
}

Its sort of annoying how I have to do all my work inside a lambda. I’ve had to do this for the last few solutions, ever since I introduced the idea of using self calling function. It would be great if the SelfCallingFactorial could return a Factorial (the delegate). That way I could just return the result directly, and I wouldn’t have to deal with the fact that I have two integer parameters running about (x and x1). This change can be achieved by using currying. Its somewhat tricky so I will do it in two steps. The first step is to perform the currying operation, making as few changes as possible, the second step will clean up, simplify and generalize. Here is the first part:

public delegate Factorial SelfCallingFactorial2(SelfCallingFactorial2 self);

/// <summary>
/// Apply a technique called currying. Now the self calling factorial function returns a factorial delegate.
/// </summary>
public class Solution04 : ISolution
{
   public Factorial MakeFactorialFunction()
   {
       return (int x1) =>
       {
           SelfCallingFactorial2 factorial = (SelfCallingFactorial2 self) =>
           {
               return (int x) =>
               {
                   return x < 2 ? 1 : x*self(self)(x-1);
               };
           };

           return factorial(factorial)(x1);
       };
   }
}

I had to modify the SelfCallingFactorial delegate. It no longer accepts an integer, instead it returns a Func<int,int> which I replaced with the Factorial delegate. You will notice I stuck a 2 on the end of the name, this is just to avoid clashes with previous delegate. This will get cleaned up in a second. Once the delegate was modified, I had to change the factorial function, and then its invocation. A side-by-side comparison might help:

Do you see how the sections in the boxes follow the same pattern, where instead of there being two arguments, there is just one argument, and then the result is invoked with the second argument?

Step two of this change is to take advantage of what I gained in step one. Now that the self calling factorial function returns a Factorial delegate, I don’t need to wrap the entire thing in a lambda – I can just return the result directly. I can also change the SelfCallingFactorial2 delegate to be generic. Ideally I could use it for other recursive algorithms such as Fibonacci. While I’m in cleanup mode, I want to rename the delegate to “SelfApplicable”. By doing this, I’ve changed the terminology somewhat – I’m using “applicable” instead of “calling”. I’ve done this because the delegate doesn’t actually “know” what the function is doing with the self argument. Its probably calling it, but perhaps its just inspecting its members? What the delegate can say is that the function is definitely applying itself to itself, because it takes itself as an argument, after all. This change also gets me closer to the code I’m aiming for in Mads’ post. So here is the result of applying these changes:

public delegate T SelfApplicable<T>(SelfApplicable<T> self);

/// <summary>
/// We can generalize the previous delegate to work with any function, and create SelfApplicable<T>.
/// I wish I could constrain T to be a delegate type but unfortunately it is not supported.
///
/// Because we removed the integer argument from the function, we no longer have to nest the entire body in
/// a lambda as we did in the previous step.
/// </summary>
public class Solution05 : ISolution
{
   public Factorial MakeFactorialFunction()
   {
       SelfApplicable<Factorial> factorial = (SelfApplicable<Factorial> self) =>
       {
           return (int x) =>
           {
               return x < 2 ? 1 : x * self(self)(x - 1);
           };
       };
      
       return factorial(factorial);
   }
}

Pretty neat huh! My only complaint with this code is that my factorial algorithm has this yucky self(self) business. Ideally I could refactor this out, so that the factorial algorithm is as readable as possible, and the tricky self calling nonsense is somewhere else. I shall pursue this in the next post.

Refactoring Towards the Y Combinator: Part 2

This is a multi-part series. Part 1. Part 2. Part 3. Part 4. Part 5. Part 6.

Lets get started with discovering the Y combinator. To start off, I came up with the most straightforward recursive implementation of the factorial function I could think of, restricting myself to anonymous methods (or more specifically, lambdas):

public delegate int Factorial(int x);

/// <summary>
/// This is the cheating way. Define a variable and use a closure on that variable.
/// Its cheating because it only works in an impure language.
/// </summary>
public class Solution01 : ISolution
{
    public Factorial MakeFactorialFunction()
    {            
        Factorial factorial = null;
        factorial = (int x) =>
        {
            return x < 2 ? 1 : x * factorial(x - 1);
        };
        
        return factorial;
    }
}

I define a delegate for the Factorial function – it takes an int, returns an int. I could have used Func<int,int> but believe me, as this gets more complicated, you’ll be glad I introduced the delegate. I also define a MakeFactorialFunction() method, which is intended to be used as so:

var s1 = new Solution01();
Factorial f = s1.MakeFactorialFunction();
int factorialOf10 = f(10);

You can mostly ignore the Solution01 and ISolution stuff, they are just artefacts from the testing harness I set up. Lets focus on the code that matters:

Factorial factorial = null;
factorial = (int x) =>
{
    return x < 2 ? 1 : x * factorial(x - 1);
};

return factorial;

In this code, I call factorial recursively by utilizing a closure. The body of the lambda expression refers to a variable that lies outside the scope of the lambda; that variable is ‘factorial’. You might have noticed, my code comment above states that I consider this implementation to be “cheating”. This is because I reassign the value of factorial. First it is null, then it is a lambda expression. Perhaps you are wondering why I bother reassign it? Why not just do it like this:

Factorial factorial = (int x) =>
{
    return x < 2 ? 1 : x * factorial(x - 1);
};

I am afraid this won’t work, the compiler identifies this as an error, “use of unassigned local variable ‘factorial’”. This is why I use the extra step of declaring factorial to be null. Now I said before that reassigning the factorial variable is cheating. Why? The Y combinator is much more relevant to the functional programming paradigm than it is to the imperative paradigm – functional programming has a concept called “purity”, which means no side effects, and no variables (no variables with varying values, that is) . For the purposes of this exercise, it will be helpful to limit myself to pure operations. The reassignment of the factorial variable is a impure operation. So how to get rid of it?

My next attempt:

public delegate int SelfCallingFactorial(int x, SelfCallingFactorial self);

/// <summary>
/// We can remove the impurity by having the factorial function accept a reference to itself, so it can call itself.
/// We can't just return this implementation because it doesn't match the Factorial signature, so we have to return
/// a lambda that calls it. Unfortunately, doing so will create a closure and as a result, as long as a reference
/// to the result of MakeFactorialFunction method is held, the Solution2 instance will not be garbage collected.
/// </summary>
public class Solution02 : ISolution
{
    public Factorial MakeFactorialFunction()
    {
        SelfCallingFactorial factorial = (int x, SelfCallingFactorial self) =>
        {
            return x < 2 ? 1 : x * self(x - 1, self);
        };

        return x =>
        {
            return factorial(x, factorial);
        };
    }
}

Okay, so what has happened? Rather than having the factorial function call itself by utilizing the variable, we could pass a reference to the factorial function as an argument to itself. I modify the Factorial delegate to accept an instance of itself, and call it a SelfCallingFactorial instead. You can see that delegate definition at the top. I then define ‘factorial’ similarly as before, but this time I have a ‘self’ parameter which I can invoke as the recursive step. When it is invoked, I have to pass two arguments: the value I want to calculate the factorial of, and another self reference. Try to think of the ‘self’ parameter as a manually implemented equivalent of the ‘this’ keyword in normal C#, but for functions. The ‘this’ keyword allows code inside an object to obtain a reference to that object, similarly, my ‘self’ parameter allows code inside a function to call that function!

The result of this trick is that I have successfully removed the impurity - there is no reassignment in this solution. However we are not finished yet: unfortunately, I cannot simply return ‘factorial’ after it has been defined, because it is a SelfCallingFactorial, and the MakeFactorialFunction method is supposed to return a Factorial. Instead I have to return a lambda that will execute my SelfCallingFactorial. This creates another closure, again, on the ‘factorial’ variable. As mentioned in the code comment, the instance of Solution02 used to create the factorial function will stay in scope as long as the factorial function stays in scope, because the returned factorial function holds a reference to the ‘factorial’ local variable defined in the MakeFactorialFunction() method. Fortunately, this is easy to fix:

/// <summary>
/// Creating the factorial method inside the returned lambda resolves the garbage collection problem. 
/// This solution does not involve a closure, so its pretty good. But...
/// </summary>
public class Solution03 : ISolution
{
    public Factorial MakeFactorialFunction()
    {
        return (int x1) =>
        {
            SelfCallingFactorial factorial = (int x, SelfCallingFactorial self) =>
            {
                return x < 2 ? 1 : x * self(x - 1, self);
            };

            return factorial(x1, factorial);
        };
    }
}

Solution03 is just a very minor revision on Solution02. All I had to do was move the code that defines the SelfCallingFactorial inside the returned lambda expression (if you look at the code above, you will see that it was previously outside). Now when a Solution03 instance is used to construct a FactorialFunction, that instance will be free to be garbage collected while the result, the factorial function, can continued to be used. Now please don’t get me wrong, I know that this garbage collection ‘issue’ is quite irrelevant – I am actually just using it as an excuse to get the code closer to my satisfaction. I am not exactly sure why I want it this way – it just seems neater.

So, where to go from Solution03? It seems pretty good, and we are still nowhere near the Y combinator. In the next instalment, I will start making the code a little more general, with the eventual goal that the same technique might be applied to other recursive algorithms (such as Fibonacci).

Refactoring Towards the Y Combinator: Part 1

This is a multi-part series. Part 1. Part 2. Part 3. Part 4. Part 5. Part 6.

Sometimes I wish that I had studied computer science rather than software engineering at university. The software engineering degree was much more practical, and as a result there is a bunch of interesting computer science theory out there that I am yet to be exposed to. In an effort to make some tiny progress on this front, this Christmas break I decided to spend a few days exposing myself to a lovely little thing called the Y combinator.

What is the Y combinator exactly? Basically, its a mechanism that can be used to call functions recursively, even if your programming language does not support recursion, as long as it does have support for first class functions (e.g. you can pass one function to another as an argument). It is extremely unlikely that you will find a use for it in your day to day work as a programmer, but I found learning about the Y combinator to be a worthwhile exercise nonetheless simply because it made my head hurt in a good way.

I found three particularly useful resources for learning about the Y combinator. These were:

• Recursive Lambda Expressions by Mads Torgersen
• The Y Combinator by Mike Vanier
• The Why of Y [PDF] by Richard Gabriel

Just reading through them, they all managed to lose me at some point. The Y combinator is really a functional programming concept, so programmers such as myself that were crippled at a young age by being first exposed to an imperative language like Basic will really struggle with it. It was clear that the only way I was really going to understand it was roll up my sleeves and write some code.

Mads’ post uses C#, and it had enough code to give me a clear goal. I would start with the most basic implementation of a recursive method I could, and try to slowly refactor it towards the final Mads code. This turned out to work very well, but I probably would not have succeeded without the help of the other resources, especially The Why of Y. Both Mike and Richard use Scheme (a dialect of Lisp), but fortunately I have watched enough SICP lectures to be able to follow it at a basic level. In the Why of Y, Richard provides an example derivation of Y, and I was able to successfully translate each of his steps to the appropriate C#. I promise you, there will be no Lisp code in any of the posts in this series.

So what does the Y combinator look like? Well here is the definition I ended up with:

SelfApplicable<HigherOrderEvaluator<Func<T, T>>> Y =
   self => algorithm => t => algorithm(self(self)(algorithm))(t);

HigherOrderEvaluator<Func<T, T>> ApplyY = Y(Y);

Here is my definition for the factorial function:

HigherOrderFunction<Func<int, int>> factorial =
               f => x => x < 2 ? 1 : x * f(x - 1);

And here is the usage:

public int CalculateFactorialOf10()
{
   return YCombinator<int>.ApplyY(factorial)(10);
}

What’s the phrase you’re looking for? How about: “My eyes! The goggles do nothing!”

Even now when I look at it, I struggle to make sense of it. This is the compressed version, but in my opinion even a far more verbose version is still difficult to comprehend. I understand this code by understanding the steps I followed to arrive at it, and hopefully by the end of this series of posts, so will you.

One Year

Its been one year since I started this blog, so I figured a reflective post might be appropriate.

What went right in 2008:

• I made a dramatic change to my free time habits. I did significantly more reading and programming, and spent much less time playing videogames.
• I read a bunch of software related books cover-to-cover. Probably more than in all previous years combined.
• I involved myself in an open source project.

What went wrong:

• I started many things, finished few. I played with lots of stuff but didn’t deliver a whole lot.
• I didn’t learn javascript or ruby. At least, not to the point where I can write idiomatic code in either language.
• I failed to deliver a worthwhile MVC based web application.
• I made very little progress in the area of algorithms and data structures.

Rereading my posts from a year ago, it is quite evident that my year did not proceed quite as I intended. However, I am not disappointed - I learned quite a bit about my own capabilities and study habits. My career goal changed – while Google is very alluring, I recognise that Microsoft would probably be an awesome place for me to work and a better fit. I have concluded that my focus on the Microsoft stack is not a bad thing. From my perspective, there are lots of exciting things in the works for the Microsoft stack:

• Microsoft will be, for the first time ever, providing and fully supporting a proper functional programming language: F#.
• The introduction of the DLR promises to foster a healthy ecosystem of dynamic programming languages, with IronPython and IronRuby at the forefront.
• Spec# has been transformed into a code contract library with compiler support and will be part of the .NET 4.0 release.
• Windows Azure, Microsoft’s cloud computing platform, could make a significant impact on the .NET development ecosystem over the next few years.
• Oslo, simply because it could help push domain specific languages into the mainstream. I am sceptical about much of what Oslo promises, but I think better tooling and raising awareness of what DSLs can offer is a good thing.

In the next few years I will be able to explore functional languages, dynamically typed languages, code contracts, cloud computing and domain specific languages all within the .NET platform. There is an immense amount for me to learn (this list, obviously, is nowhere near enumerating all of it), so why not go with the path of least resistance and learn what I can within the MS stack?

I hope to do a better job this year of actually finishing things. My study habits are still a long way off being optimal.